回溯与搜索-剑指offer

字数统计: 6.7k字   |   阅读时长: 31分

搜索算法

二分查找模板

当二分查找right取size的时候，偶数时middile是比一半多一个元素，奇数时middle是中间元素

当right取size-1的时候，偶数时middle是一半元素，奇数时middle是中间元素

闭区间查找形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int left = 0;
int right = size-1;
while (left <= right) {
  // 防止(left+right)超过整型的最大范围
  int middle = left + (right - left) / 2;
  if (target < nums[middle]) {
    right = middle - 1;
  } else if (target > nums[middle]) {
    left = middle + 1;
  } else {
    return middle;
  }
  return -1;
}

左闭又开查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int left = 0;
int right = size;
while (left < right) {
  // 防止(left+right)超过整型的最大范围
  int middle = left + (right - left) / 2;
  if (target < nums[middle]) {
    right = middle;
  } else if (target > nums[middle]) {
    left = middle + 1;
  } else {
    return middle;
  }
  return -1;
}

二维数组中的查找

https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=23256&ru=%2Fpractice%2F29311ff7404d44e0b07077f4201418f5&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

从右上角或这最小角开始

右上角：

如果右上角元素比目标值大，说明该列都比目标值大，剔除该列，column–

如果右上角元素比目标值小，说明该行都比目标值小，提出该行，row++

左下角：

如果左下角元素比比目标值大，说明该行都比目标值大，剔除该行，row–；

如果最小角元素比目标值小，说明该列都比目标值小，剔除该列，column++；

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

数字在升序数组中出现的次数

https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=13&tqId=23274&ru=%2Fpractice%2Fabc3fe2ce8e146608e868a70efebf62e&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 二分查找
    利用二分查找查找重复数字的下界:重复数字的第一个 上界最后一个重复数字的下一个

利用如下函数返回左边界，当目标值存在的时候会返回第一个目标值的索引，当目标值不存在的时候

如果目标值比数组最小值小的时候，会一直移动右指针，一直移动到索引0的位置，和left相等，返回left=0

如果目标值比最大值还要大的时候，一直移动右指针，一直移动到left与right相等，返回left=length

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private int binarySearch(int[] array, int target) {
    int left = 0;
    int right = array.length;
    while (left < right) {
        int middle = left + (right - left) / 2;
        if (target <= array[middle]) {
            // 第二种查找方式的变体，中间值等于目标值的时候不返回，而是移动右指针
            right = middle;
        } else {
            left = middle + 1;
        }
    }
    return left;
}

target不存在的时候，说明重复次数为0，要返回零，通过num[left] != k 与 left==length判断出不存在target，但是要先判断left==length，不然num[left]会越界
如果数组中有k+1，会返回第一个k+1，正好是k的下一个

如果数组中没有k+1

k+1比数组元素都大时，返回size

有比k+1大的数时，返回第一个比k+1大的数的索引

1
2
3
4
5
6
7
8
9
public int GetNumberOfK(int [] array , int k) {
    int left = this.binarySearch(array, k);
    int right = this.binarySearch(array, k+1);
    if (left==array.length || array[left]!=k) {
        return 0;
    } else {
        return right - left;
    }
}

旋转数组的最小值

https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=23269&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 暴力法
  • 二分法
    思路：把右端点当target与middle比较

图片

旋转数组大小关系如上图

如果midde比右端点大，说明middle在①处，最小值在middle右边，left=middle+1

如果middle比右端点小，说明middle在②处，最小值在middle左边，包括middle，right=middle

如果middle与右端点相等，无法确定，可能在③或④，不能确定最小值在middle的哪一侧，只能让right慢慢移动

图片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int left = 0;
int right = array.length-1;
while (left < right) {
    if(array[left] < array[right]) {
        return array[left];
    }
    int middle = left + (right - left) / 2;
    if (array[middle] < arryay[right]) {
        right = middle;
    } else if (array[middle] > array[right]) {
        left = middle + 1;
    } else {
        right--;
    }
    return array[left];
}

数字序列中某一位数字

https://www.nowcoder.com/practice/29311ff7404d44e0b07077f4201418f5?tpId=13&tqId=2285751&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

找规律

  1~9 9个数

  10~99 90个数

  100~999 900个数

  1000~9999 9000个数

如果写成digit * start * 9L，digit * start仍然可能溢出，不会升级为long，遇到第一个long后才会升级

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
public int findNthDigit (int n) {
    // write code here
    int digit = 1;
    int start = 1;
    long sum = 9;
    /*
        1~9 9个数
        10~99 90个数
        100~999 900个数
        1000~9999 9000个数
    */
    // 当n取10亿的时候，start取10亿，digit为10，sum会超过n，循环会停止，start不会继续增大，所以start不会溢出int的范围
    while (n > sum) {
        n -= sum;
        digit++;
        start *= 10;
        // start digit 9 都是整型，计算的结果会保存在int的变量中，
        // 即使最终的结果赋值给long类型的sum，计算结果也只是在int类型中
        // 需要把计算的第一个数变成long类型，后面中间计算结果才会在long类型中
        // 如果写成digit * start * 9L，digit * start仍然可能溢出，不会升级为long，遇到第一个long后才会升级
        sum = 9L * digit * start;
    }
    // n - 1是因为前面没有算0，应该把0减去，就是从start以及start后面的数
    String currentNumber = start + (n - 1) / digit + "";
    int currentDigit = (n - 1) % digit;
    return currentNumber.charAt(currentDigit) - '0';
}

回溯

回溯算法，全称是回溯搜索算法，通过递归嵌套多层遍历，寻找可能的答案。

回溯三部曲

1.确定函数的返回值和参数，一般为void

void backtrack(参数)

2.确定回溯的终止条件

if（终止条件）{

保存结果

return；

}

3.确定回溯搜索的遍历

for（选择本层结集合的元素）{

处理节点；

backtrack（路径，选择列表）；

回溯，撤销处理结果；

}

组合问题

一般组合

https://leetcode-cn.com/problems/combinations/

注意startIndex是索引，从0开始，for循环遍历i<n-remaining+1，小于号，不含等于

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
// 定义全局的result和path，result保存最终的结果，path存储单一的结果
private List<List<Integer>> result = new LinkedList<>();
private List<Integer> path = new LinkedList<>();

public List<List<Integer>> combine(int n, int k) {
    this.backtrack(n, k, 0);
    return this.result;
}

// 组合问题的参数固定，n集合总大小，k组合大小，startIndex，元素开始索引
private void backtrack(int n, int k, int startIndex) {
    // 终止条件，当达到组合大小后，保存结果
    if (this.path.size() == k) {
        this.result.add(new LinkedList(this.path));
        // return很关键，不然保存结果后仍会继续遍历
        return;
    }
    // 计算还需要多少元素，当后续集合元素不够时，不再继续遍历，剪枝
    int remaining = k - this.path.size();
    for (int i=startIndex; i<n-remaining+1; i++) {
        this.path.add(i+1);
        backtrack(n, k, i+1);
        this.path.remove(this.path.size()-1);
    }
}

组合总和Ⅲ

https://leetcode-cn.com/problems/combination-sum-iii/

本题与一般组合题基本一致，只不过集合总大小固定为9，多出了一个总和n，在一开始结题的时候犯了错误，使用path.size()==k && sum==n作为终止条件，这样是不对的，只要当size()==k时，便可以终止遍历，因为已经组合需要的元素个数已经足够了，继续遍历只会增加组合的个数，肯定不满足大小k。所以只要size()==k时，便可以终止遍历。而结果还要求sum==n，所以再进行判断，满足条件加入结果，不满足不加入，但仍要返回。

由于有剪枝判断，i<9-remaining+1有越界并无限递归的风险，即，当path.size()>=k时，

k-path.size()<=0，9-remaining+1>=10，且随着递归深度增加，path尺寸增加，9-remaining+1也在增加，每次递归startIndex为i+1，只增加1，与9-remaining+1增加的速度相同，for循环无法停止，无限递归

但是幸好前面有递归终止条件，一定要写对，当path达到要求的组合数目后要返回

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
private List<List<Integer>> result = new LinkedList<>();
private List<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
    this.backtrack(k, n, 0);
    return this.result;
}

private void backtrack(int k, int n, int startIndex) {
    int sum = 0;
    sum = this.getSum();
    if (path.size() == k) {
        if (sum == n) {
            this.result.add(new LinkedList(this.path));
        }
        return;
    }
    int remaining = k - this.path.size();
    for (int i=startIndex; i<9-remaining+1; i++) {
        this.path.add(i+1);
        backtrack(k, n, i+1);
        this.path.remove(this.path.size()-1);
    }
}

private int getSum() {
    int sum = 0;
    for (Integer item : this.path) {
        sum += item;
    }
    return sum;
}

组合总和Ⅰ
https://leetcode-cn.com/problems/combination-sum/

不含重复元素，但是同一个元素可以重复出现多次

  • 未剪枝
    思路：仍然根一般组合问题差不多，不过终止条件改为了路径和是否达到了目标值，已经startIndex 不再是i+1,而是i，因为当前数字可以无限重复，即使被选择了，仍然可以再次选择，不过由于是组合问题，不能再选之前选过的元素了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private List<List<Integer>> result = new LinkedList<>();
private List<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    this.backtrack(candidates, target, 0);
    return this.result;
}

private void backtrack(int[] candidates, int target, int startIndex) {
    // 该终止条件一定得加，因为startIdex是不会增加的，不加这个条件会导致无限递归
    if (target < 0) {
        return;
    }

    if (target == 0) {
        this.result.add(new LinkedList<>(this.path));
        return;
    }

    for (int i=startIndex; i<candidates.length; i++) {
        this.path.add(candidates[i]);
        backtrack(candidates, target-candidates[i], i);
        this.path.remove(this.path.size()-1);
    }
}
  • 剪枝
    回溯搜索以前，对数组进行了排序处理，这是可以剪枝的关键

for循环条件不满足时，会进行break操作，即立即结束循环，不是continue。

未进行剪枝前，不满足条件时，需要递归到下一层，然后立即返回，同样也会消耗时间与空间，可以在进入下一层之前，进行判断。对数组排序，如果target-candidates[i] < 0 后续candidates逐渐增大，同样不满足条件，所以可以结束循环，target-candidates[i]>=0不满足时相当于进行了break

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private List<List<Integer>> result = new LinkedList<>();
private List<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    this.backtrack(candidates, target, 0);
    return this.result;
}

private void backtrack(int[] candidates, int target, int startIndex) {
    if (target == 0) {
        this.result.add(new LinkedList<>(this.path));
        return;
    }

    for (int i=startIndex; i<candidates.length && target-candidates[i]>=0; i++) {
        this.path.add(candidates[i]);
        backtrack(candidates, target-candidates[i], i);
        this.path.remove(this.path.size()-1);
    }
}

组合总和Ⅱ

https://leetcode-cn.com/problems/combination-sum-ii/

给定的数组中有重复元素，结果中不能有重复组合

  • 可以利用set去重，但是效率太慢
  • 利用used数组，去重
    思路：先对给定的数组排序，相同元素就一定时相邻元素，相同元素在同一层上被选择过了，就不能再次选择了，需要使用continue跳过，相同元素再同一层上使用过的特征为

candidates[i]==candidates[i-1] && used[i-1]==false

前者确定了是相同元素，后者确定了是同一层的不是第一个出现的元素

该做法类似于分类求组合，比如按照第一个数是1，第一个是2，第一个数是3分成三大类，然后第二个数是1，第二个数是2，第二个数是三继续分类

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
private List<List<Integer>> result = new LinkedList<>();
private List<Integer> path = new LinkedList<>();

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    boolean[] used = new boolean[candidates.length];
    // 排序，剪枝与去重的关键
    Arrays.sort(candidates);
    this.backtrack(candidates, target, 0, used);
    return this.result;
}
// 回溯参数 候选集合 目标值 索引开始 used数组
private void backtrack(int[] candidates, int target, int startIndex, boolean[] used) {
    if (target == 0) {
        this.result.add(new LinkedList<>(this.path));
        return;
    }
    // 剪枝，for循环不满足条件，相当于break
    for (int i=startIndex; i<candidates.length && target-candidates[i]>=0; i++) {
        // 不是同层第一次出现的元素就跳过，注意有个短路与，防止越界
        if (i>0 && used[i-1]==false && candidates[i]==candidates[i-1]) {
            continue;
        }
        this.path.add(candidates[i]);
        used[i] = true;
        backtrack(candidates, target-candidates[i], i+1, used);
        this.path.remove(this.path.size()-1);
        used[i] = false;
    }
}
  • 利用startIndex判断是否是第一个出现的重复元素
    candidates[i]==candidates[i-1] && i>startIndex

关键为上述判断条件，前者确定了是重复元素，而且不是第一次出现，关键是区分开是在下一层再次出现了，还是本层再次出现了，下一层再次出现的化都有一个特定，那就是i与startIndex相等，如果不想等就说明是在本层再次出现了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private List<List<Integer>> result = new LinkedList<>();
private List<Integer> path = new LinkedList<>();

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    this.backtrack(candidates, target, 0);
    return this.result;
}

private void backtrack(int[] candidates, int target, int startIndex) {
    if (target == 0) {
        this.result.add(new LinkedList<>(this.path));
        return;
    }

    for (int i=startIndex; i<candidates.length && target-candidates[i]>=0; i++) {
        if (i>0 && i>startIndex && candidates[i]==candidates[i-1]) {
            continue;
        }
        this.path.add(candidates[i]);
        backtrack(candidates, target-candidates[i], i+1);
        this.path.remove(this.path.size()-1);
    }
}

排列问题

不重复元素的全排列

https://leetcode-cn.com/problems/permutations/

思路：与组合问题的区别是，需要used数组记录哪些元素是用过的，而且每次循环都是从0开始，而不需要从i+1遍历

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
// 全局属性，用于保存path与result
private List<List<Integer>> result = new LinkedList<>();
private List<Integer> path = new LinkedList<>();
public List<List<Integer>> permute(int[] nums) {
    boolean[] used = new boolean[nums.length];
    backtrack(nums, used);
    return this.result;
}
// 回溯算法参数，全排列的集合与used标识集合作为参数
private void backtrack(int[] nums, boolean[] used) {
    // 回溯停止条件，path数目达到全排列的数目
    if (this.path.size() == nums.length) {
        this.result.add(new LinkedList<>(this.path));
        return;
    }
    // 每次遍历从0开始
    for (int i=0; i<nums.length; i++) {
        // 标记过的直接跳过
        if (used[i] == true) {
            continue;
        }
        this.path.add(nums[i]);
        used[i] = true;
        backtrack(nums, used);
        this.path.remove(this.path.size()-1);
        used[i] = false;
    }
}

重复元素的全排列
https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=23291&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 使用set去重
    思路：

结果寻找和无重复元素一样，不过利用set去重，去重的时候要注意remove()之后，后续元素会整体向前移动，记得i–

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
private StringBuilder path = new StringBuilder();
private ArrayList<String> result = new ArrayList<>();

public ArrayList<String> Permutation(String str) {
    if (str.length() == 0) {
        return this.result;
    }
    boolean[] used = new boolean[str.length()];
    this.backtrack(str, used);
    Set<String> set = new HashSet<>();
    for (int i=0; i<this.result.size(); i++) {
        // 利用set去重，如果是重复的，移除，注意i--，因为后续元素前移了
        if (!set.add(this.result.get(i))) {
            this.result.remove(i);
            i--;
        }
    }
    return this.result;
}

// 回溯步骤1.确定返回值与参数，需要搜索的集合str，标识数组used
private void backtrack(String str, boolean[] used) {
    // 回溯步骤2.终止条件，路径长度等于集合总长度
    if (this.path.length() == str.length()) {
        this.result.add(this.path.toString());
        return;
    }
    // 回溯步骤3.确定遍历方式，每次都从0开始遍历
    for (int i=0; i<str.length(); i++) {
        if (used[i] == true) {
            continue;
        }
        used[i] = true;
        this.path.append(str.charAt(i));
        backtrack(str, used);
        used[i] = false;
        this.path.deleteCharAt(this.path.length()-1);
    }
}
  • 使用used数组
    使用used数组去重，str.charAt(i)== str.charAt(i-1) && used[i-1]==false

前者代表不是首次出现的重复元素，后者表示在同一层中再次出现的重复元素

重点步骤：排序，利用used不能重复使用同一个元素，以及去重

used数组有两个作用，首先是不能使用已经使用过的元素，还要去重

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
private StringBuilder path = new StringBuilder();
private ArrayList<String> result = new ArrayList<>();

public ArrayList<String> Permutation(String str) {
    if (str.length() == 0) {
        return this.result;
    }
    char[] charArray = str.toCharArray();
    Arrays.sort(charArray);
    str = new String(charArray);
    boolean[] used = new boolean[str.length()];
    this.backtrack(str, used);
    return this.result;
}

private void backtrack(String str, boolean[] used) {
    if (this.path.length() == str.length()) {
        this.result.add(this.path.toString());
        return;
    }
    
    for (int i=0; i<str.length(); i++) {
        if (used[i]) {
            continue;
        }
        if (i>0 && str.charAt(i) == str.charAt(i-1) && used[i-1]==false) {
            continue;
        }
        this.path.append(str.charAt(i));
        used[i] = true;
        backtrack(str, used);
        this.path.deleteCharAt(this.path.length()-1);
        used[i] = false;
    }
}

矩阵中的路径

https://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6?tpId=13&tqId=1517966&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 回溯
    思路：回溯法，遍历矩阵的每个元素，当成起点，进行搜索。每个元素下一个前进的方向都有4种，按逆时针上左下右，依次选择。选择的时候要求没有越界，并且没有被访问过，进一步可以加上剪枝操作，待选择的字符是否和下一个字符相等

1.回溯函数返回值与参数

待搜索的矩阵，要匹配的字符串，

void backtrack(char[][] matrix, String word, int row, int column, boolean[][] used)

2.确定终止条件

a. 当元素的四周都无法访问时终止

b. 当路径的长度和字符串的长度相等时需要终止，然后如果匹配上了，要把result设置为true

c. 为了在找到结果后，终止不必要的搜索，可以在递归函数的第一行判断是否找到了结果，但是这其实会多一层递归，可以在每种情况的递归执行完判断，不用递归到下一层判断。

经分析发现a条件可以不用写，隐藏在了下面的if判断中

3.确定回溯搜索的遍历

上左下右四周的搜索不好使用for循环遍历，只有四种情况，可以直接罗列出来。每种情况是否可以选择时，需要满足没有越界，并且没有被访问过，还要加入剪枝操作，待加入的字符是否和下一个字符匹配

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
private StringBuilder path = new StringBuilder();
private boolean result = false;
private int rows;
private int columns;
// 用于判断待加入的字符与下一个字符是否相等
private int counter=0;
public boolean hasPath (char[][] matrix, String word) {
    // 判断矩阵是否是空的，注意判断的顺序与短路或的作用，防止越界
    if (matrix.length==0 || matrix[0].length==0) {
        return false;
    }
    this.rows = matrix.length;
    this.columns = matrix[0].length;
    boolean[][] used = new boolean[this.rows][this.columns];
    for (int row=0; row<this.rows && !this.result; row++) {
        for (int column=0; column<this.columns && !this.result; column++) {
            if (word.charAt(this.counter) == matrix[row][column]) {
                // 遍历第一个元素的时候也要加入path，并且回溯撤销操作
                this.path.append(matrix[row][column]);
                backtrack(matrix, word, row, column, used);  
                this.path.deleteCharAt(0);
            }
        }
    }
    return this.result;
}

private void backtrack(char[][] matrix, String word, int row, int column, boolean[][] used) {
    // 匹配后立即返回，不再继续遍历
    if (this.result) {
        return;
    }
    // 搜索的长度与加入的字符长度一致时终止
    if (this.counter >= word.length()-1) {
        if (word.equals(this.path.toString())) {
            this.result = true;
        }
        return;
    }
    // 搜索左边，不能越界，且不能访问过
    if (row-1>=0 && !used[row-1][column]) {
        // counter++，判断字符串的下一个字符
        this.counter++;
        // 如果待加入的字符与下一个字符相等才进入到下一层
        if (word.charAt(this.counter) == matrix[row-1][column]) {
            this.path.append(matrix[row-1][column]);
            used[row-1][column] = true;
            backtrack(matrix, word, row-1, column, used);
            this.path.deleteCharAt(this.path.length()-1);
            used[row-1][column] = false; 
        }
        this.counter--;
    }
    
    // 搜索下边
    if (column-1>=0 && !used[row][column-1]) {
        this.counter++;
        if (word.charAt(this.counter) == matrix[row][column-1]) {
            this.path.append(matrix[row][column-1]);
            used[row][column-1] = true;
            backtrack(matrix, word, row, column-1, used);
            this.path.deleteCharAt(this.path.length()-1);
            used[row][column-1] = false;
         }
        this.counter--;
    }
    // 搜索右边
    if (row+1<this.rows && !used[row+1][column]) {
        this.counter++;
        if (word.charAt(this.counter) == matrix[row+1][column]) {
            this.path.append(matrix[row+1][column]);
            used[row+1][column] = true;
            backtrack(matrix, word, row+1, column, used);
            this.path.deleteCharAt(this.path.length()-1);
            used[row+1][column] = false;
        }
        this.counter--;
    }
    // 搜索右边
    if (column+1<this.columns && !used[row][column+1]) {
        this.counter++;
        if (word.charAt(this.counter) == matrix[row][column+1]) {
            this.path.append(matrix[row][column+1]);
            used[row][column+1] = true;
            backtrack(matrix, word, row, column+1, used);
            this.path.deleteCharAt(this.path.length()-1);
            used[row][column+1] = false;
        }
        this.counter--;
    }
}
  • 算法改进
    发现只要path的长度等于word的长度，就表示已经找到了，因为只有相等时才加入path，无需path与word比较，那也不需要path记录了

终止条件变为了

1
2
3
4
if (this.counter == word.length()-1) {
    this.result = true;
    return;
}

另外，可以利用短路或剪枝，不再进行后续搜索
写代码的时候要全神贯注，认真仔细，不然一个bug找半天

row-1 写成了row+1，递归不好调试，利用好print，打印查看每次调用的path

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
private int rows;
private int columns;
// 用于判断待加入的字符与下一个字符是否相等
private int counter=0;
public boolean hasPath (char[][] matrix, String word) {
    // 判断矩阵是否是空的，注意判断的顺序与短路或的作用，防止越界
    if (matrix.length==0 || matrix[0].length==0) {
        return false;
    }
    this.rows = matrix.length;
    this.columns = matrix[0].length;
    boolean[][] used = new boolean[this.rows][this.columns];
    for (int row=0; row<this.rows; row++) {
        for (int column=0; column<this.columns; column++) {
            if (this.backtrack(matrix, word, row, column, used)) {
                return true;
            }
        }
    }
    return false;
}

private boolean backtrack(char[][] matrix, String word, int row, int column, boolean[][] used) {
    if (this.counter == word.length()) {
        return true;
    }
    boolean result = false;
    if (row>=0 && row<this.rows && column>=0 && column<this.columns && matrix[row][column]==word.charAt(this.counter) && !used[row][column]) {
        this.counter++;
        used[row][column] = true;
        result = backtrack(matrix, word, row-1, column, used) || backtrack(matrix, word, row, column-1, used) || backtrack(matrix, word, row+1, column, used) || backtrack(matrix, word, row, column+1, used);
        if (!result) {
            this.counter--;
            used[row][column] = false;   
        }
    }
    return result;
}

机器人的运动范围

https://www.nowcoder.com/practice/6e5207314b5241fb83f2329e89fdecc8?tpId=13&tqId=23460&ru=%2Fpractice%2F2a49359695a544b8939c77358d29b7e6&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • dfs
    思路：使用visited数组标记到过的位置，不需要回溯，因为是求总和，需要记录所有路径的总和，而不是记录一种路径。从(0,0)开始移动，每个位置都有4个方向供选择，只要选择的方向没有越界，且没有被到访过，就可以向此方向移动

递归三部曲

1.确定返回类型与参数

void dfs(int threshhold, int row, int col, int rows, int cols, boolean[][] visited)

2.确定终止条件

终止条件是四周都没有路可以走了，通过单层递归逻辑if即可实现，不用单独写终止条件

3.确定单层递归逻辑

如果没有越界，且没有被访问过，总和增加1，标记当前位置，向周围四个方向递归

本层只包含处理当前节点的逻辑，而不提前处理下一层节点，这样逻辑比较清晰，代码比较简洁

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
// 定义全局变量
private int result = 0;
public int movingCount(int threshold, int rows, int cols) {
    boolean[][] visited = new boolean[rows][cols];
    // 从(0,0)开始移动
    dfs(threshold, 0, 0, rows, cols, visited);
    return this.result;
}

private void dfs(int threshold, int row, int col, int rows, int cols, boolean[][] visited) {
    // 计算和
    int sum = this.getSum(row) + this.getSum(col);
    // 判断是否越界和是否被访问过，递归时，不要提前判断，可以递归到下一层判断，这样代码比较简介
    if (row>=0 && row<rows && col>=0 && col<cols && sum<=threshold && !visited[row][col]) {
        // 做标记，总和加1
        visited[row][col] = true;
        this.result++;
        // 四个方向依次递归
        dfs(threshold, row-1, col, rows, cols, visited);
        dfs(threshold, row, col-1, rows, cols, visited);
        dfs(threshold, row+1, col, rows, cols, visited);
        dfs(threshold, row, col+1, rows, cols, visited);
    }
}
private int getSum(int num) {
    int sum = 0;
    while (num != 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

美团笔试-路径中最少未探明的区域

最少的未探明区域

oxo

oox

ooo

从(0,0)到(m, n)经过最短的x的数量

回溯法不是最优的，但是在本题使用回溯法，对回溯法又有了新的感受

在下方的backtrack中，在本层递归中处理了下一层递归访问的元素，代码逻辑复杂

在改进的backtrackImproved中，本层递归中只处理本层当前元素，不同于一般的回溯问题，使用for横向遍历，本问题横向只有固定两种情况，可以直接写出来，而且横向的所有情况当前

元素的值相同，可以只用回溯一次即可。在横向遍历前更改状态，在横向遍历后复原状态。

另外还可以把path当成参数，path + currentValue，这样每次调用函数，都会回溯一次，相当于

path += currentValue

backtrack()

path -= currentValue

path += currentValue

backtrack()

path -= currentValue

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
import java.util.*;
public class Main {
    private List<Integer> result = new ArrayList<>();
    private int path;
    public static void main(String[] args) {
        int[][] matrix = {{0, 1, 1, 1, 1}, {1, 1, 0, 0, 1},{0, 0, 0, 1, 0}, {1, 1, 1, 1, 0},{0, 0, 0, 0, 1}};
        Main main = new Main();
        main.path = matrix[0][0];
        main.backtrackImproved(matrix, 5, 5, 0, 0);
        System.out.println(main.result);
        main.path = 0;
        main.result.clear();
        main.backtrack(matrix, 5, 5, 0, 0);
        System.out.println(main.result);
    }
    private void backtrack(int[][] matrix, int rows, int cols, int row, int col) {
        if (row == rows-1 && col == cols-1) {
            this.result.add(this.path);
            return;
        }
        if (row + 1 < rows) {
            this.path += matrix[row + 1][col];
            backtrack(matrix, rows, cols, row + 1, col);
            this.path -= matrix[row + 1][col];
        }
        if (col + 1 < cols) {
            this.path += matrix[row][col + 1];
            backtrack(matrix, rows, cols, row, col + 1);
            this.path -= matrix[row][col + 1];
        }
    }
    private void backtrackImproved(int[][] matrix, int rows, int cols, int row, int col) {
        if (row == rows-1 && col == cols-1) {
            this.path +=  matrix[row][col];
            this.result.add(this.path);
            this.path -= matrix[row][col];
            return;
        }
        if (row < rows && col < cols) {
            this.path += matrix[row][col];
            backtrackImproved(matrix, rows, cols, row+1, col);
            backtrackImproved(matrix, rows, cols, row, col+1);
            this.path -= matrix[row][col];
        }
    }
}

赏

谢谢你请我喝杯可乐

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

北科大计算机在读<br><br>爱好编程<br><br>热爱技术<br><br>喜欢折腾