question2 单例模式
实现单例模式：
很多实现方法，一种线程安全懒加载的实现
package q2;
/**
* @Author Redarm
* 内部类实现单例模式，线程安全，懒加载，无锁
* @Date 2020/7/21 6:00 下午
**/
public class Singleton {
private static class SingletonHolder{
private static Singleton instance = new Singleton();
}
private Singleton(){
}
public static Singleton getInstance(){
return SingletonHolder.instance;
}
}
双重校验锁实现单例模式，线程安全。
两次锁，两次判空，第一次如果实例不为空就不进入synchronized代码块中，提高效率，第二次判空的必要性，如果没有第二次判空，可能出现一种情况，线程1再判空后进入synchronized之前线程2通过判空进入synchronized创建实例，这是当线程1分到时间片后就会进入synchronized再创建一个实例，因为线程1在上一次执行已经进行了判空，所以这次执行直接就是创建实例，那么这就创建了两个实例，不是单例模式了。
package cn.redarm;
public class Singleton {
private volatile static Singleton singleton;
private Singleton(){
}
public static Singleton getInstance(){
if (singleton == null){
synchronized (Singleton.class){
if (singleton == null){
singleton = new Singleton();
}
}
}
return singleton;
}
}
question3 数组中重复的数字
问题：给出一个数组，找出其中重复的数字。
借助hashmap，时间复杂度为O(n)，空间复杂度O(n)
package com.company;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
public class Queston3 {
public static void main(String[] args) {
int[] array = new int[10];
Random random = new Random(1);
for (int i = 0; i<array.length; i++){
array[i] = random.nextInt(10);
}
System.out.println("array: ");
Arrays.stream(array).forEach(it -> System.out.print(it));
System.out.println();
System.out.println("number: " + findNumber(array));
}
public static int findNumber(int[] array){
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < array.length; i ++){
if (map.get(array[i]) == null){
map.put(array[i], 1);
continue;
} else {
return array[i];
}
}
return -1;
}
}
question4 二维数组查找
一个二维数组，数字从左到右升序，从上到下升序，从数组中查找一个数字。
从右上角看，如果要寻找的数字比右上角的数字大，那么他可能在这一列中，如果这个数字比右上角的数字小，因为从上到下为升序，所以要寻找的数字一定不再这一列中，再去找其他列。
package com.company;
public class Queston4 {
public static void main(String[] args) {
int[][] array = {{1,2,8,9}, {2,4,9,12}, {4,7,10,13}, {6,8,11,15}};
System.out.println(findNumber(array, 1));
System.out.println(findNumber(array, 222));
}
private static boolean findNumber(int[][] array, int number){
if (array == null ){
return false;
}
for (int i= array.length-1; i >=0; i--){
if (array[i][0] == number){
return true;
} else if (number < array[i][0]){
continue;
} else if (number > array[i][0]){
for (int j = 1; j < array[0].length; j++){
if (array[i][j] == number)
return true;
}
}
}
return false;
}
}
question5 替换空格
给一个字符串，把字符串中的空格用%20替换。
String.replace()
question6 翻转链表
给一个链表，翻转后打印
利用栈的性质，先进后出
package com.company;
import java.util.*;
public class Question6 {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
Random random = new Random(1);
for (int i=0; i<50; i++){
list.add(random.nextInt(50));
}
System.out.println("list: ");
list.stream().forEach(it -> System.out.print(it + " "));
System.out.println("\n" + "new list: ");
printListReversing(list);
}
private static void printListReversing(List<Integer> list){
Stack<Integer> stack = new Stack();
list.stream().forEach(it -> stack.add(it));
for (int i=0; i<list.size(); i++){
System.out.print(stack.pop() + " ");
}
}
}
Question9 两个栈实现队列
用两个栈实现队列，实现add添加和deleteHead删除队列头两个方法
增加的时候，栈1用来调整顺序，栈2用来存储数据，如果栈2为空，加到栈2里就行，如果栈2有数据，把栈2的数据反序放到栈1中，然后把新添加的数据放到栈1中，然后把栈1的所有数据反序放到栈2中，此时栈2中的栈顶就是整个队列的头元素，删除队列的头就是栈2弹出栈顶。
package com.company;
import java.util.Stack;
public class Question9 {
public static void main(String[] args) {
MyQueue<Integer> queue = new MyQueue<>();
queue.add(1);
queue.add(2);
queue.add(3);
System.out.println(queue.toString());
queue.deleteHead();
System.out.println(queue.toString());
}
}
class MyQueue<E>{
private Stack<E> stack1;
private Stack<E> stack2;
public MyQueue(){
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void add(E e){
if (stack2.isEmpty()){
stack2.add(e);
} else {
int flag = stack2.size();
for (int i=0; i<flag; i++){
stack1.add(stack2.pop());
}
stack1.add(e);
flag = stack1.size();
for (int i=0; i<flag; i++){
stack2.add(stack1.pop());
}
}
}
public E deleteHead(){
return stack2.pop();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("elements: ");
stack2.stream().forEach(it -> sb.append(it + " "));
return sb.toString();
}
}
Question10 斐波那契数列
f(0)=0; f(1)=1; f(n)=f(n-1)+f(n-2);
给任意数字求其斐波那契数列
类似的还有比如青蛙跳台阶，一次可以跳一个或者两个，一个用n个台阶求多少种跳法。
先看第一跳，有两种选择，跳一个或者跳两个，如果跳一个，那么所有的选择就是剩下的n-1个台阶有多少种跳法，即f(n-1)，如果第一跳跳两个，那么所有的跳法就是f(n-2)，所以所有的跳法就是f(n-1)+f(n-2)。
比较好的实现方法，从前到后计算，计算结果存到数组中，如果递归倒着计算，部分计算会重复计算。
package com.company;
public class Question10 {
public static void main(String[] args) {
System.out.println(fibonacci(10));
}
public static int fibonacci(int a){
int[] array = new int[a];
array[0] = 0;
array[1] = 1;
for (int i=2; i<a; i++){
array[i] = array[i-1] + array[i-2];
}
return array[a-1];
}
}
Question11 旋转数组中的最小数字
给一个旋转了的数组，比如 （4，5，6，1，2，3）就是数组（1，2，3，4，5，6，）旋转之后的数组，求其中最小的数字。
二分查找的一种应用，每次都用数组中间的数字和左右边界的数字进行比较，如果中间的数字比左面的数字大，说明最小的数字在有半部分，如果中间的数字比右边界的数字小，说明最小的数字在左半部分。
特殊情况，如果最左面的数字比最右面的数字小，说明数组是从左到右升序排列的，最小的数字就是最左面的数字，如果中间的数字等于左右两边界的数字，只能顺序查找，比如（1，1，1，1，0，1，1）。
package com.company;
public class Question11 {
public static void main(String[] args) throws Exception {
int[] array1 = {6,7,8,9,1,2,3,4,5};
int[] array2 = {1,2,3,4,5};
int[] array3 = {1,1,1,1,0,1,1};
System.out.println(findMinNumber(array1));
}
private static int findMinNumber(int[] array) throws Exception {
if (array == null || array.length == 0){
throw new Exception("error");
}
int left = 0;
int right = array.length-1;
int mid = (left + right)/2;
if (array[left] < array[right])
return array[left];
if (array[left] == array[mid] && array[mid] == array[right]){
int result = array[left];
for (int i=left+1; i<=right; i++){
if (array[i] < result)
result = array[i];
}
return result;
}
while (left < right-1){
if (array[mid] > array[left]){
left = mid;
mid = (left + right)/2;
} else if (array[mid] < array[right]){
right = mid;
mid = (left + right)/2;
}
}
return array[right];
}
}
Question14 剪绳子
给一根绳子，可以把绳子剪成n段，使得把所有段的长度相乘得到的结果最大。
比如一个100米的绳子，先看如何剪最后一下，剪最后一下之后绳子变成两段，如果左面绳子剪完之后所有段长度的乘积再乘以右面绳子剪完后所有段数的乘积最大，那么这是结果最大。
从上到下分析，从下到上计算，一米绳子最大值是1，2米是2，3米是3，四米的时候两种剪法，一米和三米或者是两个两米，然后看哪种方法两段绳子的乘积最大，就是当前长度的最大值。
package com.company;
public class Question14 {
public static void main(String[] args) {
System.out.println(findMaxAfterCutting(8));
}
private static int findMaxAfterCutting(int length){
int[] array = new int[length+1];
if (length <= 0)
return 0;
if (length == 1)
return 1;
if (length == 2)
return 2;
if (length == 3)
return 3;
array[0] = 0;
array[1] = 1;
array[2] = 2;
array[3] = 3;
int max = 0;
for (int i = 4; i<=length; i++){
max = 0;
for (int j=1; j<=i/2; j++){
int product = array[j] * array[i-j];
if (product > max)
max = product;
}
array[i] = max;
}
return array[length];
}
}
Question 15 二进制中1的个数
给一个整数，求其二进制形式中 1 的个数
二进制形势下，一个数与自己减一相与，这个数的1的数就会减一，比如 0110， 0110 - 1 为 0101，0110&0101=0100，少了一个一，所以每次运算少一个一，直到最后为0。
package com.company;
public class Question15 {
public static void main(String[] args) {
System.out.println(findTheNumberOfOne(9));
}
public static int findTheNumberOfOne(int num){
int count = 0;
while (num != 0){
num &= num - 1;
count++;
}
return count;
}
}
Question 16 数值的整数次方
求 base 的 exponent次方， 不需要考虑大数问题。
公式：求a的n次方
1。 n为偶数 那么 $an=a{n/2}*a{n/2}$
2。n为奇数 那么 $an=a{(n-1)/2}*a{(n-1)/2}*n$
package com.company;
public class Question16 {
public static void main(String[] args) {
System.out.println(powerWithUnsignedExponent(2,10));
}
public static double powerWithUnsignedExponent(double base, int exponent){
if (exponent == 1)
return base;
if (exponent == 0)
return 1;
double result = powerWithUnsignedExponent(base, exponent >> 1);
result *= result;
if ((exponent & 0x1) == 1)
result *= base;
return result;
}
}
Question 17 打印一到最大的n位数
大数问题，可以用字符串或者数组处理，java中有BigInteger和BigDecimal表示大数。
package com.company;
import java.math.BigInteger;
public class Question17 {
public static void main(String[] args) {
printOneToMax(3);
}
private static void printOneToMax(int n){
StringBuilder sb1 = new StringBuilder(), sb2 = new StringBuilder();
for (int i=0; i<n; i++){
sb1.append("0");
sb2.append("9");
}
BigInteger bigInteger1 = new BigInteger(sb1.toString());
BigInteger bigInteger2 = new BigInteger(sb2.toString());
while (bigInteger1.compareTo(bigInteger2) <0){
System.out.println(bigInteger1.toString());
bigInteger1 = bigInteger1.add(new BigInteger("1"));
}
System.out.println(bigInteger2.toString());
}
}
Question 21 调整数组顺序使得奇数位于偶数前面
在于代码重用性，需要把条件抽出来处理，这样要是想改成把负数放前面或者能整除3的数放前面只需要改条件就行，不用修改主要代码，增加了代码重用性。
package com.company;
import java.util.Arrays;
import java.util.Random;
public class Question21 {
public static void main(String[] args) {
Random random = new Random(1);
int[] array = new int[1000];
for (int i=0; i< array.length; i++)
array[i] = random.nextInt(1000);
reOrderArray(array);
Arrays.stream(array).forEach(it -> System.out.print(it + " "));
}
private static void reOrderArray(int[] array){
if (array.length == 0 )
return;
int left = 0;
int right = array.length-1;
while (left < right){
while (!isEven(array[left]))
left++;
while (isEven(array[right]))
right--;
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
}
private static boolean isEven(int num){
return (num & 0x01) == 0;
}
}
Question 22 链表中倒数k个节点
给一个链表，输出倒数第k个节点。
两个指针开始的时候都指向头结点，第一个指针开始向后移动遍历，如果两个指针的距离大于k时，第二个指针开始启动，保持两个指针的距离为k，这样当第一个指针遍历到链表尾的时候，第二个指针指向的位置就是倒数第k个节点，这样只需要遍历一遍就能找到倒数第k个节点。
package com.company;
import java.util.ArrayList;
import java.util.List;
public class Question22 {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for (int i=0; i<10; i++)
list.add(i);
System.out.println(findKthToTail(list, 2));
}
private static int findKthToTail(List<Integer> list, int k){
if (list.isEmpty())
return -1;
if (k < 0 || k > list.size())
return -1;
int flag = 0;
int behind = 0;
while (flag < list.size()){
flag++;
if (flag > behind + k)
behind++;
}
return list.get(behind);
}
}