剑指offer

1、排序算法

0、排序算法分类

1、直接插入排序

基本思想

直接插入排序的基本思想是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的

元素小，则交换，直到全部元素都比较过为止。

算法描述

1、从第一个元素开始，该元素可以认为已经被排序

2、取出下一个元素，在已经排序的元素序列中从后向前扫描

3、如果该元素(已排序)大于新元素，将该元素移到下一位置

4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

5、将新元素插入到该位置后

6、重复步骤2~5

package com.example.number1;

import java.util.Arrays;

/**
 * @author zhangshixing
 * 直接插入排序
 */
public class InsertionSort {

    public static void insertionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (arr[j - 1] <= arr[j]) {
                    break;
                }
                //交换操作
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                System.out.println("Sorting:  " + Arrays.toString(arr));
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {98, 87, 200, 300, 150, 32, -5, -3, 4, 3, 6, -1, 99, 2};
        System.out.println("Array : " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("Array Sorting:  " + Arrays.toString(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

由于直接插入排序每次只移动一个元素的位， 并不会改变值相同的元素之间的排序， 因此它是一种稳定排序。

2、希尔排序

基本思想

将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次再将gap折半减

小，循环上述操作；当gap=1时，利用直接插入，完成排序。

算法描述

1、选择一个增量序列 t1,t2,…,tk，其中 ti>tj,tk=1(一般初次取数组半长，之后每次再减半，直到增量为1)。

2、按增量序列个数k，对序列进行k 趟排序。

3、每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排

序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

package com.example.number1;

import java.util.Arrays;

/**
 * @author zhangshixing
 * 希尔排序
 */
public class ShellSort {

    public static void shellSort(int[] arr){
        int gap = arr.length / 2;
        //不断缩小gap，直到1为止
        for (; gap > 0; gap /= 2) {
            System.out.println("Gap=" + gap);
            //使用当前gap进行组内插入排序
            for (int j = 0; (j+gap) < arr.length; j++){
                for(int k = 0; (k+gap)< arr.length; k += gap){
                    System.out.println("Compare： arr[" + (k+gap)+ "]=" + arr[k+gap] + ", arr[" + k + "]=" + arr[k]);
                    if(arr[k] > arr[k+gap]) {
                        //交换操作
                        int temp = arr[k+gap];
                        arr[k+gap] = arr[k];
                        arr[k] = temp;
                        System.out.println("    Sorting:  " + Arrays.toString(arr));
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = { 98, 87, 200, 300, 150, 32, -5, -3, 4, 3, 6, -1, 99, 2 };
        System.out.println("Array : " + Arrays.toString(arr));
        shellSort(arr);
        System.out.println("Array Sorting:  " + Arrays.toString(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

希尔排序是稳定的排序算法

3、选择排序

基本思想

选择排序的基本思想：比较 + 交换。

在未排序序列中找到最小(大)元素，存放到未排序序列的起始位置。在所有的完全依靠交换去移动元素的排序方法

中，选择排序属于非常好的一种。

算法描述

1、从待排序序列中，找到关键字最小的元素；

2、如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；

3、从余下的 N - 1 个元素中，找出关键字最小的元素，重复1、2步，直到排序结束。

package com.example.number1;

import java.util.Arrays;

/**
 * @author zhangshixing
 * 简单选择排序
 */
public class SelectionSort {

    public static void selectionSort(int[] arr){
        for(int i = 0; i < arr.length-1; i++){
            int min = i;
            //选出之后待排序中值最小的位置
            for(int j = i+1; j < arr.length; j++){
                if(arr[j] < arr[min]){
                    min = j;
                }
            }
            if(min != i){
                //交换操作
                int temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
                System.out.println("Sorting:  " + Arrays.toString(arr));
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = { 98, 87, 200, 300, 150, 32, -5, -3, 4, 3, 6, -1, 99, 2 };
        System.out.println("Array : " + Arrays.toString(arr));
        selectionSort(arr);
        System.out.println("Array Sorting:  " + Arrays.toString(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

选择排序是不稳定排序

4、堆排序

基本思想

此处以大顶堆为例，堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整

成堆，找出最大的再移走，重复直至有序。

算法描述

1、先将初始序列K[1…n]建成一个大顶堆, 那么此时第一个元素K1最大, 此堆为初始的无序区

2、再将关键字最大的记录K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换, 由此得到新的无序区

K[1…n-1]和有序区K[n], 且满足K[1…n-1].keys <= K[n].key

3、交换K1 和 Kn 后, 堆顶可能违反堆性质, 因此需将K[1…n-1]调整为堆. 然后重复步骤2, 直到无序区只有一个

元素时停止

package com.example.number1;

import java.util.Arrays;

/**
 * @author zhangshixing
 * 堆排序
 */
public class HeapSort {

    public static void heapSort(int[] arr) {
        for (int i = arr.length; i > 0; i--) {
            // 创建大订堆,将Kn置为最大元素
            max_heapify(arr, i);
            // 堆顶元素(第一个元素)与Kn交换
            int temp = arr[0];
            arr[0] = arr[i - 1];
            arr[i - 1] = temp;
        }
    }

    /**
     * arr为待排序的数组
     * limit为数组的长度
     */
    private static void max_heapify(int[] arr, int limit) {
        if (arr.length <= 0 || arr.length < limit)
        {
            return;
        }
        // 折半
        int parentIdx = limit / 2;
        for (; parentIdx >= 0; parentIdx--) {
            if (parentIdx * 2 >= limit) {
                continue;
            }
            // 左子节点位置
            int left = parentIdx * 2;
            // 右子节点位置，如果没有右节点，默认为左节点位置
            int right = (left + 1) >= limit ? left : (left + 1);
            int maxChildId = arr[left] >= arr[right] ? left : right;
            // 交换父节点与左右子节点中的最大值
            if (arr[maxChildId] > arr[parentIdx]) {
                int temp = arr[parentIdx];
                arr[parentIdx] = arr[maxChildId];
                arr[maxChildId] = temp;
            }
        }
        System.out.println("Max_Heapify: " + Arrays.toString(arr));
    }

    public static void main(String[] args) {
        int[] arr = { 98, 87, 200, 300, 150, 32, -5, -3, 4, 3, 6, -1, 99, 2 };
        System.out.println("Array : " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("Array Sorting:  " + Arrays.toString(arr));
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

堆排序是不稳定的排序算法

5、冒泡排序

基本思想

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们

的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完

成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法描述

冒泡排序算法的运作如下：

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的

数。

3、针对所有的元素重复以上的步骤，除了最后一个。

4、持续每次对越来越少的元素重复上面的步骤1~3，直到没有任何一对数字需要比较。

package com.example.number1;

import java.util.Arrays;

/**
 * @author zhangshixing
 * 冒泡排序
 */
public class BubbleSort {

    public static void bubbleSort(int[] arr) {
        //外层循环移动游标
        for (int i = arr.length - 1; i > 0; i--) {
            //内层循环遍历游标及之后(或之前)的元素
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    System.out.println("Sorting: " + Arrays.toString(arr));
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {98, 87, 200, 300, 150, 32, -5, -3, 4, 3, 6, -1, 99, 2};
        System.out.println("Array : " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("Array Sorting:  " + Arrays.toString(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

冒泡排序是稳定的排序算法

6、快速排序

基本思想

快速排序的基本思想：挖坑填数+分治法。

首先选一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字

均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述

快速排序使用分治策略来把一个序列(list)分为两个子序列(sub-lists)。步骤为：

1、从数列中挑出一个元素，称为基准(pivot)。

2、重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面(相同的数可

以到任一边)。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区(partition)操作。

3、递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代

(iteration)中，它至少会把一个元素摆到它最后的位置去。

package com.example.number1;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author zhangshixing
 * 快速排序
 */
public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (arr.length <= 0) {
            return;
        }

        if (low >= high) {
            return;
        }

        int left = low;
        int right = high;
        // 挖坑1：保存基准的值
        int temp = arr[left];
        while (left < right) {
            // 坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
            while (left < right && arr[right] >= temp) {
                right--;
            }
            arr[left] = arr[right];
            // 坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
            while (left < right && arr[left] <= temp) {
                left++;
            }
            arr[right] = arr[left];
        }
        // 基准值填补到坑3中，准备分治递归快排
        arr[left] = temp;
        System.out.println("Sorting: " + Arrays.toString(arr));
        quickSort(arr, low, left - 1);
        quickSort(arr, left + 1, high);
    }

    public static void main(String[] args) {
        int[] arr = {98, 87, 200, 300, 150, 32, -5, -3, 4, 3, 6, -1, 99, 2};
        System.out.println("Array : " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Array Sorting:  " + Arrays.toString(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

快速排序是不稳定的排序算法

7、归并排序

基本思想

归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子

序列是有序的。然后再把有序子序列合并为整体有序序列。

算法描述

递归法(假设序列共有n个元素)：

1、将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；

2、将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；

3、重复步骤2，直到所有元素排序完毕。

package com.example.number1;

import java.util.Arrays;

/**
 * @author zhangshixing
 * 归并排序
 */
public class MergingSort {

    public static int[] mergingSort(int[] arr) {
        if (arr.length <= 1) {
            return arr;
        }

        int num = arr.length >> 1;
        int[] leftArr = Arrays.copyOfRange(arr, 0, num);
        int[] rightArr = Arrays.copyOfRange(arr, num, arr.length);
        System.out.println("split two array: " + Arrays.toString(leftArr) + " And " + Arrays.toString(rightArr));
        //不断拆分为最小单元，再排序合并
        return mergeTwoArray(mergingSort(leftArr), mergingSort(rightArr));
    }

    private static int[] mergeTwoArray(int[] arr1, int[] arr2) {
        int i = 0, j = 0, k = 0;
        //申请额外的空间存储合并之后的数组
        int[] result = new int[arr1.length + arr2.length];
        //选取两个序列中的较小值放入新数组
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] <= arr2[j]) {
                result[k++] = arr1[i++];
            } else {
                result[k++] = arr2[j++];
            }
        }
        //序列1中多余的元素移入新数组
        while (i < arr1.length) {
            result[k++] = arr1[i++];
        }
        //序列2中多余的元素移入新数组
        while (j < arr2.length) {
            result[k++] = arr2[j++];
        }
        System.out.println("Merging: " + Arrays.toString(result));
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {98, 87, 200, 300, 150, 32, -5, -3, 4, 3, 6, -1, 99, 2};
        System.out.println("Array : " + Arrays.toString(arr));
        mergingSort(arr);
        System.out.println("Array Sorting:  " + Arrays.toString(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

归并排序是稳定的排序算法

8、基数排序

基本思想

它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位

开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

基数排序按照优先从高位或低位来排序有两种实现方案：

• MSD（Most significant digital） 从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相

  等, 再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组

  排序后. 再将各组连接起来, 便得到一个有序序列。MSD方式适用于位数多的序列。

• LSD （Least significant digital）从最右侧低位开始进行排序。先从kd开始排序，再对kd-1进行排序，依次

  重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。

算法描述

我们以LSD为例，从最低位开始，具体算法描述如下：

1、取得数组中的最大数，并取得位数；

2、arr为原始数组，从最低位开始取每个位组成radix数组；

3、对radix进行计数排序(利用计数排序适用于小范围数的特点)；

package com.example.number1;

import java.util.Arrays;

/**
 * @author zhangshixing
 * 基数排序
 */
public class RadixSort {

    public static void radixSort(int[] arr){
        if(arr.length <= 1) {
            return;
        }

        //取得数组中的最大数，并取得位数
        int max = 0;
        for(int i = 0; i < arr.length; i++){
            if(max < arr[i]){
                max = arr[i];
            }
        }
        int maxDigit = 1;
        while(max / 10 > 0){
            maxDigit++;
            max = max / 10;
        }
        System.out.println("maxDigit: " + maxDigit);

        //申请一个桶空间
        int[][] buckets = new int[10][arr.length];
        int base = 10;

        //从低位到高位，对每一位遍历，将所有元素分配到桶中
        for(int i = 0; i < maxDigit; i++){
            //存储各个桶中存储元素的数量
            int[] bktLen = new int[10];

            //分配：将所有元素分配到桶中
            for(int j = 0; j < arr.length; j++){
                int whichBucket = (arr[j] % base) / (base / 10);
                buckets[whichBucket][bktLen[whichBucket]] = arr[j];
                bktLen[whichBucket]++;
            }

            //收集：将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞
            int k = 0;
            for(int b = 0; b < buckets.length; b++){
                for(int p = 0; p < bktLen[b]; p++){
                    arr[k++] = buckets[b][p];
                }
            }

            System.out.println("Sorting: " + Arrays.toString(arr));
            base *= 10;
        }
    }

    public static void main(String[] args) {
        int[] arr = { 98, 87, 200, 300, 150, 32, 4, 3, 6, 99, 2 };
        System.out.println("Array : " + Arrays.toString(arr));
        radixSort(arr);
        System.out.println("Array Sorting:  " + Arrays.toString(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

其中，d 为位数，r 为基数，n 为原数组个数。

基数排序只有从最低位开始才是稳定的排序算法

9、总结

2、单例模式

总共有5种方法

（1）饿汉式(线程安全，调用效率高，但是不能延时加载)

package com.example.number2;

/**
 * @author zhangshixing
 * @date 2021年12月31日 15:19
 * Singleton模式的第一种实现方式
 * 饿汉式(线程安全，调用效率高，但是不能延时加载)
 */
public class Singleton1 {

    private static Singleton1 instance = new Singleton1();

    private Singleton1() {
    }

    public static Singleton1 getInstance() {
        return instance;
    }

    public static void main(String[] args) {
        Singleton1 a1 = Singleton1.getInstance();
        Singleton1 a2 = Singleton1.getInstance();
        // true
        System.out.println(a1 == a2);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

（2）懒汉式(线程不安全，调用效率不高，但是能延时加载)

package com.example.number2;

/**
 * @author zhangshixing
 * @date 2021年12月31日 15:21
 * Singleton模式的第二种实现方式
 * 懒汉式(线程不安全，调用效率不高，但是能延时加载)
 */
public class Singleton2 {

    private static Singleton2 instance;

    private Singleton2() {
    }

    public static synchronized Singleton2 getInstance()

    {
        if (instance == null) {
            instance = new Singleton2();
        }
        return instance;
    }

    public static void main(String[] args) {
        Singleton2 a1 = Singleton2.getInstance();
        Singleton2 a2 = Singleton2.getInstance();
        // true
        System.out.println(a1 == a2);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

（3）Double CheckLock实现单例：DCL也就是双重锁判断机制（由于JVM底层模型原因，偶尔会出问题，不建议使用）

package com.example.number2;

/**
 * @author zhangshixing
 * @date 2021年12月31日 15:28
 * Singleton模式的第三种实现方式
 * Double CheckLock实现单例：DCL也就是双重锁判断机制（由于JVM底层模型原因，偶尔会出问题，不建议使用）
 */
public class Singleton3 {

    private volatile static Singleton3 instance;

    private Singleton3() {
    }

    public static Singleton3 getInstance() {
        if (instance == null) {
            synchronized (Singleton3.class) {
                if (instance == null) {
                    instance = new Singleton3();
                }
            }
        }
        return instance;
    }

    public static void main(String[] args) {
        Singleton3 a1 = Singleton3.getInstance();
        Singleton3 a2 = Singleton3.getInstance();
        // true
        System.out.println(a1 == a2);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

(4)静态内部类实现模式（线程安全，调用效率高，可以延时加载）

package com.example.number2;

/**
 * @author zhangshixing
 * @date 2021年12月31日 15:31
 * Singleton模式的第四种实现方式
 * 静态内部类实现模式（线程安全，调用效率高，可以延时加载）
 */
public class Singleton4 {

    private static class SingletonClassInstance {
        private static final Singleton4 instance = new Singleton4();
    }

    private Singleton4() {
    }

    public static Singleton4 getInstance() {
        return SingletonClassInstance.instance;
    }

    public static void main(String[] args) {
        Singleton4 a1 = Singleton4.getInstance();
        Singleton4 a2 = Singleton4.getInstance();
        // true
        System.out.println(a1 == a2);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

(5)枚举类（线程安全，调用效率高，不能延时加载，可以天然的防止反射和反序列化调用）

package com.example.number2;

/**
 * @author zhangshixing
 * @date 2021年12月31日 15:32
 * Singleton模式的第五种实现方式
 * 枚举类（线程安全，调用效率高，不能延时加载，可以天然的防止反射和反序列化调用）
 */
public enum Singleton5 {

    //枚举元素本身就是单例
    INSTANCE;

    // 添加自己需要的操作
    public void singletonOperation() {
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

package com.example.number2;

/**
 * @author zhangshixing
 * @date 2021年12月31日 15:38
 */
public class Test {

    public static void main(String[] args) {
        Singleton5 singletona = Singleton5.INSTANCE;
        Singleton5 singletonb = Singleton5.INSTANCE;
        // true
        System.out.println(singletona == singletonb);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3、找出数组中重复的数字

题目一：找出数组中重复的数字

在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复

了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组

{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。

解法: 因为列表总共有n个元素，所有元素可能取到的元素有0~n-1，共n种。如果不存在重复的数字，那么排序后

数字i将会出现在下标为i的位置。现在让我们重新扫描数组，当扫描到下标为i的数字时，首先比较这个数字(记为

m)与i是否相等： 如果是，继续扫描下一个元素，如果不是，则再拿它与第m个数字比较： 如果它和第m个数字相

同，就找到了一个重复的元素；如果不同，就将第m与第i个数字互换。接下来继续重头开始，重复换这个比较。

package com.example.number3;

/**
 * @author zhangshixing
 * 题目一：找出数组中重复的数字
 */
public class Test1 {

    public void getDuplicate1(int[] num) {

        int NumChange;
        for (int index = 0; index < num.length; index++) {
            while (num[index] != index) {
                if (num[index] == num[num[index]]) {
                    System.out.print("重复元素是:" + num[index]);
                    break;
                } else {
                    NumChange = num[num[index]];
                    num[num[index]] = num[index];
                    num[index] = NumChange;
                }
            }
        }
    }

    public void getDuplicate(int[] arr) {
        int i = 0;
        while (i < arr.length && arr != null) {
            int m = arr[i];
            if (m == i) {
                i += 1;
            } else {
                if (m == arr[m]) {
                    System.out.println("重复元素是:" + m);
                    break;
                } else {
                    int temp = arr[i];
                    arr[i] = arr[m];
                    arr[m] = temp;
                    i = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        int arr[] = {4, 3, 1, 0, 2, 5, 3};
        new Test1().getDuplicate1(arr);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

题目二：不修改数组找出重复的数字

在一个长度为n+1的数组里的所有数字都在1~n范围内，所以数字中至少有一个数字是重复的。请找出数组中任意

一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重

复的数字2或者3。

避免使用O(n)的辅助空间。我们把取值空间[1,n]从中间的数字m分为两部分，前面一部分为1~m，后面一部分为

m+1~n。如果数组中元素落在前面一部分的元素个数多于m个，那么数组中重复的元素一定落在前半区间；否

则，数组中重复的元素一定落在后半区间。然后，我们可以继续将包含重复元素的区间一分为二，直到找到一个重

复的元素。

package com.example.number3;

/**
 * @author zhangshixing
 * 题目二：不修改数组找出重复的数字
 */
public class Test2 {

    public int findDuplicates(int arr[]) {

        int low = 1;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            int count_low = 0;
            for (int a : arr) {
                if (low <= a && a <= mid) {
                    count_low += 1;
                }
            }
            if (high == low) {
                if (count_low > 1) {
                    return low;
                } else {
                    break;
                }
            }
            if (count_low > (mid - low + 1)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return 0;
    }

    public static void main(String[] args) {

        int arr[] = {2, 3, 5, 4, 3, 2, 6, 7};
        int reu = new Test2().findDuplicates(arr);
        System.out.println(reu);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

4、二维数组中的查找

题目:在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完

成一个函数，输入这样一个二维数组和一个整数，判断数组中是否含有该整数。

解法：从右上开始查找：如果数组中的数比这个整数大，向左移动一位，如果数组中的数比这个数小，向下移动一

位。

package com.example.number4;

/**
 * @author zhangshixing
 * 二维数组中的查找
 */
public class Test {

    public boolean search(int[][] arr, int value) {
        int a = arr[0].length;
        int b = arr.length;
        int i = 0;
        int j = a - 1;
        while (i <= b - 1 && j >= 0) {
            if (arr[i][j] == value) {
                return true;
            }
            if (arr[i][j] > value) {
                j--;
            } else {
                i++;
            }
        }
        return false;
    }

    public static void main(String[] args) {

        int[][] arr = {{1, 2, 8, 9},
                {2, 4, 9, 12},
                {4, 7, 10, 13},
                {6, 8, 11, 15}};
        System.out.println(new Test().search(arr, 7));
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

5、替换空格

题目:请实现一个函数，把字符串中的每个空格替换成“%20”。例如，输入"We Are Happy."，则经过替换之后的

字符串为"We%20Are%20Happy." 先计算最终需要给出的长度，然后建立两个指针p1,p2，p1指向原始字符串的

末尾，p2指向替换后的字符串的末尾。同时移动p1,p2, 将p1指的内容逐个复制到p2, 当p1遇到空格时，在p2处插

入 %20， p1向前移动一个位置，p2向前移动3个位置，当p1和p2位置重合时，全部替换完成。

package com.example.number5;

/**
 * @author zhangshixing
 * 替换空格
 */
public class Test {

    public String change(char[] charArray) {
        int n = charArray.length;
        int count = 0;
        for (int i = 0; i < charArray.length; i++) {
            if (charArray[i] == ' ') {
                count++;
            }
        }
        if (count == 0) {
            return null;
        }
        char[] temp = new char[n + 2 * count];
        int j = n + 2 * count - 1;
        int i = n - 1;
        while (i >= 0) {
            if (charArray[i] == ' ') {
                temp[j] = '0';
                temp[j - 1] = '2';
                temp[j - 2] = '%';
                j = j - 3;
            } else {
                temp[j] = charArray[i];
                j--;
            }
            i--;
        }
        return new String(temp);
    }

    public static void main(String[] args) {
        String str = "We are happy";
        char[] charArray = str.toCharArray();
        System.out.println(new Test().change(charArray));

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

6、从尾到头打印链表

题目:输入一个链表的头结点，从尾到头反过来打印每个节点的值。

从头到尾遍历链表，并用一个栈存储每个节点的值，之后出栈输出。

package com.example.commnon;

/**
 * @author zhangshixing
 * 链表结点
 */

public class Node {

    public String data;
    public Node next;

    public Node(String data) {
        super();
        this.data = data;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

package com.example.number6;

import com.example.commnon.Node;

import java.util.Stack;

/**
 * @author zhangshixing
 * 从尾到头打印链表
 */
public class Test {
    
    public Node reverse1(Node head) {
        Node pre = head;
        Node cur = head.next;
        Node temp;
        while (cur != null) {
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        head.next = null;
        return pre;
    }

    /**
     * 采用栈
     *
     * @param node
     */
    public void reverse2(Node node) {
        Stack<Node> stack = new Stack<Node>();
        while (node != null) {
            stack.push(node);
            node = node.next;
        }
        while (!stack.empty()) {
            System.out.println(stack.pop().data);
        }
    }

    /**
     * 采用递归
     *
     * @param node
     */
    public void reverse3(Node node) {
        if (node != null) {
            reverse3(node.next);
            System.out.println(node.data);
        } else {
            return;
        }
    }

    public static void main(String[] args) {

        Node node1 = new Node("A");
        Node node2 = new Node("B");
        Node node3 = new Node("C");
        Node node4 = new Node("D");
        Node node5 = new Node("E");
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        Node newNode = new Test().reverse1(node1);
        while (newNode != null) {
            System.out.print(newNode.data + " ");
            newNode = newNode.next;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

7、重建二叉树

题目:输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中

都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返

回。

利用二叉树前序遍历和中序遍历的特点，前序遍历的第一个值一定为根节点，对应于中序遍历中间的一个点，在中

序遍历中，该点左侧的值为根节点的左子树，右侧的值为根节点的右子树。这时可以利用递归，取前序遍历的

[1:i+1]和中序遍历的[:i]作为对应的左子树继续上一个过程，取前序遍历的[i+1:]和中序遍历的[i+1:]对应与右子树继

续上一个过程，重建二叉树。

package com.example.commnon;

/**
 * @author zhangshixing
 * 二叉树
 */

public class BinaryTreeNode {

    public int data;
    public BinaryTreeNode LchildNode;
    public BinaryTreeNode RchildNode;

    public BinaryTreeNode(int data) {
        super();
        this.data = data;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

package com.example.number7;

import com.example.commnon.BinaryTreeNode;

/**
 * @author zhangshixing
 * 重建二叉树
 */
public class Test {

    public BinaryTreeNode findBinaryTree(int[] pre, int preStart,
                                         int preEnd, int[] in, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd)
            return null;
        BinaryTreeNode root = new BinaryTreeNode(pre[preStart]);

        for (int i = inStart; i <= inEnd; i++) {
            if (in[i] == pre[preStart]) {
                root.LchildNode = findBinaryTree(pre, preStart + 1, i - inStart + preStart,
                        in, inStart, i - 1);
                root.RchildNode = findBinaryTree(pre, i - inStart + preStart + 1, preEnd,
                        in, i + 1, inEnd);
            }
        }
        return root;
    }

    public static void main(String[] args) {
        int preOrder[] = {1,2,4,7,3,5,6,8};
        int midOrder[] = {4,7,2,1,5,3,8,6};
        BinaryTreeNode root = new Test().findBinaryTree(preOrder, 0, preOrder.length - 1,
                midOrder, 0, midOrder.length - 1);
        System.out.println(root.data);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

8、二叉树的下一个结点

题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包

含左右子结点，同时包含指向父结点的指针。

• 分析二叉树的下一个节点，一共有以下情况：

• 1.二叉树为空，则返回空；

• 2.节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即

  为下一个节点；

• 3.节点右孩子不存在，节点是根节点，返回null。节点不是根节点，如果该节点是其父节点的左孩子，则返回

  父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。

package com.example.commnon;

/**
 * @author zhangshixing
 * TreeLinkNode
 */
public class TreeLinkNode {

    public int val;
    public TreeLinkNode left = null;
    public TreeLinkNode right = null;
    public TreeLinkNode next = null;

    public TreeLinkNode(int val) {
        this.val = val;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

package com.example.number8;

import com.example.commnon.TreeLinkNode;

/**
 * @author zhangshixing
 * 二叉树的下一个结点
 */
public class Test {

    public TreeLinkNode getNext(TreeLinkNode pNode) {
        if (pNode == null) {
            return null;
        }
        if (pNode.right != null) {
            pNode = pNode.right;
            while (pNode.left != null) {
                pNode = pNode.left;
            }
            return pNode;
        }
        while (pNode.next != null) {
            if (pNode.next.left == pNode) {
                return pNode.next;
            }
            pNode = pNode.next;
        }
        return null;
    }

    public static void main(String[] args) {

        TreeLinkNode pNode1 = new TreeLinkNode(8);
        TreeLinkNode pNode2 = new TreeLinkNode(6);
        TreeLinkNode pNode3 = new TreeLinkNode(10);
        TreeLinkNode pNode4 = new TreeLinkNode(5);
        TreeLinkNode pNode5 = new TreeLinkNode(7);
        TreeLinkNode pNode6 = new TreeLinkNode(9);
        TreeLinkNode pNode7 = new TreeLinkNode(11);
        pNode1.left = pNode2;
        pNode1.right = pNode3;
        pNode2.left = pNode4;
        pNode2.right = pNode5;
        pNode3.left = pNode6;
        pNode3.right = pNode7;

        System.out.println(new Test().getNext(pNode2).val);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

9、用两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

插入删除的过程：插入肯定是往一个栈stack1中一直插入；删除时，直接出栈无法实现队列的先进先出规则，这时

需要将元素从stack1出栈，压到另一个栈stack2中，然后再从stack2中出栈就OK了。需要稍微注意的是：当

stack2中还有元素，stack1中的元素不能压进来；当stack2中没元素时，stack1中的所有元素都必须压入stack2

中。否则顺序就会被打乱。

package com.example.number9;

import java.util.Stack;

/**
 * @author zhangshixing
 * 用两个栈实现队列
 */
public class Test {

    private Stack s1 = new Stack();
    private Stack s2 = new Stack();

    public void offer(Object x) {
        s1.push(x);
    }

    public void poll() {
        if (s1.size() == 0 && s2.size() == 0) {
            try {
                throw new Exception("empty queue");
            } catch (Exception e) {
                e.printStackTrace();
            }
        } else {
            if (s2.size() != 0) {
                System.out.println(s2.peek().toString());
                s2.pop();
            } else {
                while (s1.size() > 0) {
                    s2.push(s1.pop());
                }
                System.out.println(s2.peek().toString());
                s2.pop();
            }
        }
    }

    public static void main(String[] args) {

        Test queue = new Test();
        queue.offer("a");
        queue.offer("b");
        queue.offer("c");
        queue.poll();
      =  queue.poll();
        queue.poll();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

10、斐波那契数列

题目一：求斐波那契数列的第n项

package com.example.number10;

/**
 * @author zhangshixing
 * 题目一：求斐波那契数列的第n项
 */
public class Test1 {

    public static void main(String[] args) {
        System.out.println(new Test1().fibonacci(10));
    }

    public int fibonacci(int n) {
        int tempArray[] = {0, 1};
        if (n >= 2) {
            for (int i = 2; i < n + 1; i++) {
                tempArray[i % 2] = tempArray[0] + tempArray[1];
            }
        }
        return tempArray[n % 2];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

题目二：青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法？

package com.example.number10;

/**
 * @author zhangshixing
 * 题目二：青蛙跳台阶问题
 */
public class Test2 {

    public static void main(String[] args) {
        System.out.println(new Test2().jumpFloor(10));
    }

    public int jumpFloor(int n) {
        int tempArray[] = {1, 2};
        if (n >= 3) {
            for (int i = 3; i < n + 1; i++) {
                tempArray[(i + 1) % 2] = tempArray[0] + tempArray[1];
            }
        }
        return tempArray[(n + 1) % 2];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

11、旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个

旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

package com.example.number11;

/**
 * @author zhangshixing
 * 旋转数组的最小数字
 */
public class Test {

    public int findMin(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        if (arr[right] > arr[left]) {
            try {
                throw new Exception("非旋转数组");
            } catch (Exception e) {
                e.printStackTrace();
                return -1;
            }
        }
        while (left < right) {
            int mid = (left + right) / 2;
            // 对于{1,0,1,1,1}之类的特殊处理
            if (arr[mid] == arr[left] && arr[left] == arr[right]) {
                return seachMin(arr, left, right);
            }
            if (right - left == 1) {
                break;
            }
            if (arr[mid] >= arr[left]) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return arr[right];
    }

    private int seachMin(int[] arr, int left, int right) {
        int result = arr[left];
        for (int i = left + 1; i <= right; ++i) {
            if (arr[i] < result){
                result = arr[i];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {3, 4, 5, 1, 2};
        System.out.println(new Test().findMin(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

12、矩阵中的路径

题目:请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的

任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某

一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串

”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子

之后，路径不能再次进入该格子。

首先对整个矩阵遍历，找到第一个字符，然后向上下左右查找下一个字符，由于每个字符都是相同的判断方法(先

判断当前字符是否相等，再向四周查找)，因此采用递归函数。由于字符查找过后不能重复进入，所以还要定义一

个与字符矩阵大小相同的布尔值矩阵，进入过的格子标记为true。如果不满足的情况下，需要进行回溯，此时，要

将当前位置的布尔值标记回false。(所谓的回溯无非就是对使用过的字符进行标记和处理后的去标记)。

package com.example.number12;

/**
 * @author zhangshixing
 * 矩阵中的路径
 */
public class Test {

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        if (matrix == null || rows < 1 || cols < 1 || str == null) {
            return false;
        }
        boolean[] isVisited = new boolean[rows * cols];
        for (@SuppressWarnings("unused") boolean v : isVisited) {
            v = false;
        }
        int pathLength = 0;
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (hasPathCore(matrix, rows, cols, row, col, str, pathLength, isVisited))
                {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean hasPathCore(char[] matrix, int rows, int cols, int row, int col, char[] str, int pathLength,
                                boolean[] isVisited) {
        if (row < 0 || col < 0 || row >= rows || col >= cols || isVisited[row * cols + col] == true
                || str[pathLength] != matrix[row * cols + col]) {
            return false;
        }
        if (pathLength == str.length - 1) {
            return true;
        }
        boolean hasPath = false;
        isVisited[row * cols + col] = true;
        hasPath = hasPathCore(matrix, rows, cols, row - 1, col, str, pathLength + 1, isVisited)
                || hasPathCore(matrix, rows, cols, row + 1, col, str, pathLength + 1, isVisited)
                || hasPathCore(matrix, rows, cols, row, col - 1, str, pathLength + 1, isVisited)
                || hasPathCore(matrix, rows, cols, row, col + 1, str, pathLength + 1, isVisited);

        if (!hasPath) {
            isVisited[row * cols + col] = false;
        }
        return hasPath;
    }

    public static void main(String[] args) {
        String matrix = "abtgcfcsjdeh";
        String path = "bfce";
        System.out.println(new Test().hasPath(matrix.toCharArray(), 3, 4, path.toCharArray()));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

13、机器人的运动范围

题目:地上有一个m行和n列的方格。一个机器人从坐标(0,0)的格子开始移动，每一次只能向左，右，上，下四个方

向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格

（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到

多少个格子？

也采用回溯法，先判断机器人能否进入(i,j)，再判断周围4个格子。

package com.example.number13;

/**
 * @author zhangshixing
 * 机器人的运动范围
 */
public class Test {

    public int movingCount(int threshold, int rows, int cols) {
        if (rows <= 0 || cols <= 0 || threshold < 0)
        {
            return 0;
        }
        boolean[] isVisited = new boolean[rows * cols];
        int count = movingCountCore(threshold, rows, cols, 0, 0, isVisited);
        return count;
    }

    private int movingCountCore(int threshold, int rows, int cols, int row, int col, boolean[] isVisited) {
        if (row < 0 || col < 0 || row >= rows || col >= cols || isVisited[row * cols + col]
                || cal(row) + cal(col) > threshold)
        {
            return 0;
        }
        isVisited[row * cols + col] = true;
        return 1 + movingCountCore(threshold, rows, cols, row - 1, col, isVisited)
                + movingCountCore(threshold, rows, cols, row + 1, col, isVisited)
                + movingCountCore(threshold, rows, cols, row, col - 1, isVisited)
                + movingCountCore(threshold, rows, cols, row, col + 1, isVisited);
    }

    private int cal(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(new Test().movingCount(7,4,5));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

14、剪绳子

题目:给你一根长度为n的绳子，请把绳子剪成m段 (m和n都是整数，n>1并且m>1)每段绳子的长度记为k[0],k[1],

…,k[m].请问k[0]k[1]…*k[m]可能的最大乘积是多少？例如，当绳子的长度为8时，我们把它剪成长度分别为2,3,3

的三段，此时得到的最大乘积是18。

本题采用动态规划或者贪婪算法可以实现。一开始没有思路时，可以从简单的情况开始想，试着算以下比较短的

绳子是如何剪的。

当n=1时，最大乘积只能为0；

当n=2时，最大乘积只能为1；

当n=3时，最大乘积只能为2；

当n=4时，可以分为如下几种情况:1111，121，13，22，最大乘积为4；

往下推时，发现n≥4时，可以把问题变成几个小问题，即：如果把长度n绳子的最大乘积记为f(n)，则有：

f(n)=max(f(i)*f(n-1))，0

问题通过寻找小问题的最优组合得到。

其实这就是动态规划法，以下是动态规划法的几个特点

1.求一个问题的最优解

2.整体问题的最优解依赖各子问题的最优解

3.小问题之间还有相互重叠的更小的子问题

4.为了避免小问题的重复求解，采用从上往下分析和从下往上求解的方法求解问题

贪婪算法依赖于数学证明，当绳子大于5时，尽量多地剪出长度为3的绳子是最优解。

package com.example.number14;

/**
 * @author zhangshixing
 * 剪绳子
 */
public class Test {

    // ======动态规划======
    public static int maxProductAfterCutting_solution1(int length) {
        if (length <= 1)
            return 0;
        if (length == 2)
            return 1;
        if (length == 3)
            return 2;
        // 用于存放最大乘积值
        int[] product = new int[length + 1];
        // 下面几个不是乘积，因为其本身长度比乘积大
        product[0] = 0;
        product[1] = 1;
        product[2] = 2;
        product[3] = 3;
        // 开始从下到上计算长度为i绳子的最大乘积值product[i]
        for (int i = 4; i <= length; i++) {
            int max = 0;
            // 算不同子长度的乘积，找出最大的乘积
            for (int j = 1; j <= i / 2; j++) {
                if (max < product[j] * product[i - j])
                    max = product[j] * product[i - j];
            }
            product[i] = max;
        }
        return product[length];
    }

    // =======贪婪算法========
    public static int maxProductAfterCutting_solution2(int length) {
        if (length <= 1)
            return 0;
        if (length == 2)
            return 1;
        if (length == 3)
            return 2;
        int timesOf3 = length / 3;
        int timesOf2 = 0;
        if (length - timesOf3 * 3 == 1) {
            timesOf3--;
            // timesOf2=2;  //错误！
        }
        timesOf2 = (length - timesOf3 * 3) / 2;
        return (int) (Math.pow(3, timesOf3) * Math.pow(2, timesOf2));
    }

    public static void main(String[] args) {
        System.out.println(maxProductAfterCutting_solution2(8));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

package com.example.number15;

/**
 * @author zhangshixing
 * 二进制中1的个数
 */
public class Test {

    public static int NumberOf1_Solution1(int n) {
        int count = 0;
        int flag = 1;
        while (flag != 0) {
            if ((flag & n) != 0)
            {
                count++;
            }
            flag = flag << 1;
        }
        return count;
    }

    public static int NumberOf1_Solution2(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n = (n - 1) & n;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(NumberOf1_Solution2(7));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

package com.example.number16;

/**
 * @author zhangshixing
 * 数值的整数次方
 */
public class Test {

    boolean IsInvalid = false;

    public double power(double base, int exponent) {
        IsInvalid = false;
        double result;
        if (exponent > 0) {
            result = powerCore(base, exponent);
        } else if (exponent < 0) {
            if (base == 0) {
                IsInvalid = true;
                return 0;
            }
            result = 1 / powerCore(base, -exponent);
        } else {
            return 1;
        }
        return result;
    }

    private double powerCore(double base, int exponent) {
        if (exponent == 1) {
            return base;
        }
        if (exponent == 0) {
            return 1;
        }
        double result = powerCore(base, exponent >> 1);
        result *= result;
        if ((exponent & 0x1) == 1) {
            result *= base;
        }
        return result;
    }

    public static void main(String[] args) {
        Test demo = new Test();
        System.out.println(demo.power(2, 10));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

package com.example.number17;

/**
 * @author zhangshixing
 * 打印1到最大的n位数
 */
public class Test {
    public static void print1ToMaxOfNDights1s(int n) {
        if (n <= 0) {
            return;
        }
        char[] digit = new char[n];
        for (int i = 0; i < n; i++) {
            digit[i] = '0';
        }
        for (int i = n - 1; i >= 0; i--) {
            while (digit[i] != '9') {
                int m = 0;
                digit[m]++;
                while (m < n - 1 && digit[m] > '9') {
                    digit[m] = '0';
                    digit[m + 1]++;
                    m++;
                }
                printdigits(digit);
            }
        }
    }

    private static void printdigits(char[] digit) {
        int m = digit.length - 1;
        while (digit[m] == '0') {
            m--;
        }
        for (int i = m; i >= 0; i--) {
            System.out.print(digit[i]);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        print1ToMaxOfNDights1s(3);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

package com.example.commnon;

/**
 * @author zhangshixing
 * 列表结点
 */
public class ListNode {

	public int data;
	public ListNode next;
	
	public ListNode(int data) {
		super();
		this.data = data;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

package com.example.number18;

import com.example.commnon.ListNode;

/**
 * @author zhangshixing
 * 题目一：在O(1)时间内删除链表结点
 */
public class Test1 {

    public static void deleteNode(ListNode head, ListNode deletedNode) {

        if (head == null || deletedNode == null)
        {
            return;
        }
        // 要删除的节点不是尾节点
        if (deletedNode.next != null) {
            deletedNode.data = deletedNode.next.data;
            deletedNode.next = deletedNode.next.next;
        }
        // 链表只有一个节点，删除头结点
        else if (head == deletedNode) {
            head = null;
        }
        // 链表有多个节点，删除尾节点(需要从头到尾遍历找到要删除节点的前一个节点)
        else {
            ListNode temp = head;
            while (temp.next != deletedNode) {
                temp = temp.next;
            }
            temp.next = null;
            deletedNode = null;
        }
    }

    public static void main(String[] args) {
        ListNode node1= new ListNode(1);
        ListNode node2= new ListNode(2);
        ListNode node3= new ListNode(3);
        ListNode node4= new ListNode(4);
        ListNode node5= new ListNode(5);
        ListNode node6= new ListNode(6);
        ListNode node7= new ListNode(7);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;
        node6.next=node7;
        deleteNode(node1,node3);
        while(node1!=null) {
            System.out.println(node1.data);
            node1=node1.next;
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58