（最新版2022版）剑指offer之搜索算法题解

---

1、《剑指offer》JZ4二维数组中的查找

题目描述：

解题思路：

思路：
观察矩阵右上角的数组，该数字是当前所在列的最小值，是当前所在行的最小值，即该数在从行到列数字中的中间值，所以可以用二分查找的思想。

• 从右上角开始，首先选中右上角的数字，如果该数字等于要查找的数字，则查找过程结束。
• 如果当前数字大于target，剔除该数字所在的列，则target只会出现在行上，因为这一列上的数字都会大于target。
• 如果当前数字小于target，则剔除该数字所在的行，去列上找，因为这一行中的数字都会小于target。

编程实现（Java）：

public class Solution {
    public boolean Find(int target, int [][] array) {

        int rows = array.length;
        int cols = array[0].length;
        int row = rows - 1;
        int col = 0;
        while (col < cols && row >= 0) {
            if (target > array[row][col]) {
                col++;
            } else if (target < array[row][col]) {
                row--;
            } else {
                return true;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2、《剑指offer》JZ11旋转数组的最小数字

题目描述：

解题思路：
array表示递增排序旋转数组，使用left和right指针分别代表数组的左边界和右边界，数组中间元素的下标mid = (left+right)/2。

一个标准的递增排序旋转数组，总是有array[left] >= array[right]，当array[left] < array[mid]时，说明最小元素在mid右侧，使left = mid；array[left] > array[mid]时，最小元素在mid左侧，使right = mid。直到left和right相邻时，array[right]即是最小元素。。但有以下两种特殊情况：

第一种，即数组旋转后跟没有旋转一样，即array[left] < array[right]，此时array[left]为最小元素。

第二种，array[left] == array[right] == array[mid]，此时最小元素可能在mid左侧，也可能在右侧。因此，此时只能遍历left和right之间的数据找出最小元素。

编程实现：

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int l = 0;
        int r = array.length - 1;
        //退出条件：l=r,这时候数组里只剩下一个元素
        while (l < r) {
            //如果此时数组是严格递增的，直接返回最左边元素
            if (array[l] < array[r]) {
                return array[l];
            }

            int mid = (l + r) / 2;
            //array[mid] > array[l]，说明mid在左边，更新l
            if (array[mid] > array[l]) {
                l = mid + 1;
                //array[mid] < array[l]，说明mid在右边，更新r
            } else if (array[mid] < array[l]) {
                r = mid;
                //mid=l，说明左边有连续多个相同的值，l后移一位
            } else {
                l++;
            }
        }
        return array[l];
    }
}
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

3、《剑指offer》JZ38字符串的排列

题目描述：

编程实现（Java）：

import java.util.*;
public class Solution {
    ArrayList<String> res = new ArrayList<>();
    ArrayList<Character> list = new ArrayList<>();
    boolean[] visited;
    public ArrayList<String> Permutation(String str) {
        if (str.length() == 0) {
            res.add("");
            return res;
        }
        
        visited = new boolean[str.length()];
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        dfs(chars, 0);

        return res;
    }

    void dfs(char[] arr, int k){
        //搜索到底，把一条路径加入到res集合中
        if(arr.length == k){
            res.add(charToString(list));
            return;
        }

        //剪枝。
        for(int i = 0; i < arr.length; i++){
            //从第二个字符开始，如果连续两个字符一样并且上一个没被访问过，说明arr[i]和arr[i - 1]在同一层，剪枝
            if(i > 0 && arr[i] == arr[i - 1] && visited[i - 1] == false){
                continue;
            }

            if(visited[i] == false){
                visited[i] = true;
                list.add(arr[i]);
                dfs(arr, k + 1);
                //回溯
                list.remove(list.size() - 1);
                visited[i] = false;
            }
        }
    }

    //把字符型集合转化为字符串
    String charToString(ArrayList<Character> list){
        StringBuilder str = new StringBuilder();
        for(int i = 0; i < list.size(); i++){
            str.append(list.get(i));
        }
        return str.toString();
    }
}
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

4、《剑指offer》JZ44数字序列中某一位的数字

题目描述：

解题思路：
举例分析，比如找第1001位数字，
1）1位数的数值有10个：0~9，数字为10×1=10个，显然1001>10，跳过这10个数值，在后面找第991（1001-10）位数字。
2）2位数的数值有90个：10~99，数字为90×2=180个，且991>180，继续在后面找第811（991-180）位数字。
3）3位数的数值有900个：100~999，数字为900×3=2700个，且811<2700，说明第811位数字在位数为3的数值中。由于811=270×3+1，所以第811位是从100开始的第270个数值即370的第二个数字，就是7。
按此规律，可求出其他数字。
编程实现（Java)：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int findNthDigit (int n) {
        // write code here
        //bit记录某个数字是多少位的：123是3位，12是2位
        int bit = 1;
        //初始值：1~9为1,10~99为10,100~999为100
        long start = 1;
        //某个范围有多少个数字，1~9有9个,10~99有90个,100~999有900个
        long count = 9;
        if (n == 0) {
            return 0;
        }

        //找出是多少位的（范围）
        while (n > count) {
            n -= count;
            bit++;
            start *= 10;
            count = bit * start * 9;
        }

        //找出具体是那个数字
        String num = (start + (n - 1) / bit) + "";
        //获取那个数字的下标
        int index = (n - 1) % bit;
        return Integer.parseInt(num.charAt(index) + "");
    }
}
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