百度站长平台网站验证,免费制作文字图片,网站建设外文文献翻译,做同城信息网站怎么赚钱本系列为笔者的 Leetcode 刷题记录#xff0c;顺序为 Hot 100 题官方顺序#xff0c;根据标签命名#xff0c;记录笔者总结的做题思路#xff0c;附部分代码解释和疑问解答#xff0c;01~07为C语言#xff0c;08及以后为Java语言。
01 全排列 class Solution {public Li…本系列为笔者的 Leetcode 刷题记录顺序为 Hot 100 题官方顺序根据标签命名记录笔者总结的做题思路附部分代码解释和疑问解答01~07为C语言08及以后为Java语言。
01 全排列 class Solution {public ListListInteger permute(int[] nums) {}
}预备知识
回溯法一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解或者至少不是最后一个解回溯算法会通过在上一步进行一些变化抛弃该解即回溯并且再次尝试。 class Solution {public ListListInteger permute(int[] nums) {ListListInteger result new ArrayList();ListInteger output new ArrayList();for(int num : nums){output.add(num);}int n nums.length;myFunction(n, result, output, 0);return result;}/*** 回溯方法递归生成全排列* param n 数组长度* param output 当前排列的列表状态* param res 存储所有排列的结果列表* param first 当前固定元素的位置从0开始*/public void myFunction(int n, ListListInteger result, ListInteger output, int first){if(first n){result.add(new ArrayList(output));return;}for(int ifirst; in; i){Collections.swap(output, first, i);myFunction(n, result, output, first 1);Collections.swap(output, first, i);}}
}① Collections是啥
Collections 是 Java 标准库中 java.util 包下的一个工具类提供了一系列静态方法用来操作或返回集合Collection类型的对象比如 List、Set 等。
常用功能包括
排序Collections.sort(ListT list) 可以对列表进行排序交换元素Collections.swap(List? list, int i, int j) 用于交换列表中指定位置的两个元素查找Collections.max()、Collections.min() 找最大值、最小值填充、复制、反转fill()、copy()、reverse() 等
02 子集 class Solution {public ListListInteger subsets(int[] nums) {}
}方法一神奇二进制
class Solution {public ListListInteger subsets(int[] nums) {ListListInteger result new ArrayList();ListInteger output new ArrayList();int n nums.length;for(int mask0; mask(1n); mask){ //遍历0~2^n-1之间的数output.clear();for(int i0; in; i){ //遍历0~n-1之间的位if((mask (1i)) ! 0){output.add(nums[i]);}}result.add(new ArrayList(output));}return result;}
}方法二深度优先搜索
class Solution {ListListInteger result new ArrayList();ListInteger output new ArrayList();public ListListInteger subsets(int[] nums) {myFunction(0, nums);return result;}public void myFunction(int curr, int[] nums){if(curr nums.length){result.add(new ArrayList(output));return;}output.add(nums[curr]);myFunction(curr1, nums);output.remove(output.size()-1);myFunction(curr1, nums);}
}① t.add(nums[cur]);是头添加还是尾添加t.remove(t.size() - 1);是头删除还是尾删除
t.add(nums[cur]); 是尾部添加而 t.remove(t.size() - 1); 是尾部删除。
② ListListInteger result new ArrayList();默认访问权限是啥public还是protected还是private
变量声明时如果不写访问修饰符默认就是“包访问权限”package-private即默认访问权限。
③ output.remove(output.size()-1);为啥是output.size()-1而不是nums[curr]
output.size() - 1 是列表中最后一个元素的索引。output.remove(index) 是根据索引删除指定位置的元素。
为什么一般不用 output.remove(nums[curr])
考虑场景
nums [1, 2, 2]递归过程中output 可能是 [1, 2, 2]。
当想撤销回溯删除最后一个2时如果用 output.remove(nums[curr])会删除列表中第一个2而不是刚刚加进去的那个尾部元素。导致撤销操作不正确破坏递归的状态维护。
03 电话号码的字母组合 class Solution {public ListString letterCombinations(String digits) {//1.创建 ListString 和 MapCharacter, StringListString combinations new ArrayList();if(digits.length() 0){return combinations;}MapCharacter, String phoneMap new HashMap(){{put(2, abc);put(3, def);put(4, ghi);put(5, jkl);put(6, mno);put(7, pqrs);put(8, tuv);put(9, wxyz);}};myFunction(combinations, phoneMap, digits, 0, new StringBuffer());return combinations;}public void myFunction(ListString combinations, MapCharacter, String phoneMap, String digits, int index, StringBuffer combination){//2.核心操作if(index digits.length()){combinations.add(combination.toString());}else{//3.递归回溯char digit digits.charAt(index); //2String letters phoneMap.get(digit); //abcint count letters.length(); //3for(int i0; icount; i){combination.append(letters.charAt(i));myFunction(combinations, phoneMap, digits, index1, combination);combination.deleteCharAt(index); //⭐}}}
}① new StringBuffer()啥意思
new StringBuffer()表示创建一个空的、可以修改的字符串缓冲区对象。
在回溯算法中利用StringBuffer可以高效地构建和修改当前的字符串组合比如append添加字符deleteCharAt删除字符实现回溯过程中的“选择”和“撤销选择”。
② MapCharacter, String phoneMap为啥要加双大括号并写一堆put
内层的{{ ... }}是一个匿名内部类的实例初始化块。
具体来说
第一对大括号{}是匿名内部类的定义体第二对大括号{}是匿名内部类的实例初始化块放构造过程中要执行的代码
③ combination.toString()啥意思
combination.toString() 的意思是将 combination 这个对象转换成一个普通的 String 类型这一步是必要的因为 combinations 是 ListString需要的是不可变的字符串。
04 组合总和 自己写的
class Solution {ListListInteger result new ArrayList();ListInteger output new ArrayList();public ListListInteger combinationSum(int[] candidates, int target) {//1.创建/*ListListInteger result new ArrayList();ListInteger output new ArrayList();*/myFunction(0, 0, target, candidates);return result;//2.核心步骤/*if(sum target){result.add(new ArrayList(output));}*///3.递归回溯/*myFunction(int curr, int sum, int target, int[] candidates); //当前数组当前位置*/}public void myFunction(int curr, int sum, int target, int[] candidates){//特殊情况判断①if(curr candidates.length){return;}//特殊情况判断②if(sum target){result.add(new ArrayList(output));return;}if(sum candidates[curr] target){output.add(candidates[curr]);myFunction(curr, sum candidates[curr], target, candidates);output.remove(output.size() - 1);}myFunction(curr 1, sum, target, candidates);}
}05 括号总和 class Solution {ListString result new ArrayList();public ListString generateParenthesis(int n) {//1.创建/*ListString result new ArrayList();StringBuffer output*/myFunction(n, 0, 0, new StringBuffer());return result;//2.核心操作/*if(output.length() n * 2){result.add(output.toString());return;}*///3.递归回溯/*n: 括号对数indexLeft: 左括号当前下标indexRight: 右括号当前下标output: 可变长度 String 字符串myFunction(int n, int indexLeft, int indexRight, StringBuffer output)*/}public void myFunction(int n, int indexLeft, int indexRight, StringBuffer output){if(output.length() n * 2){result.add(output.toString());return;}if(indexLeft n){output.append(();myFunction(n, indexLeft 1, indexRight, output);output.deleteCharAt(output.length() - 1);}if(indexLeft indexRight){output.append());myFunction(n, indexLeft, indexRight 1, output);output.deleteCharAt(output.length() - 1);}}
}06 单词搜索 自己写的
class Solution {boolean flag false;public boolean exist(char[][] board, String word) {//1.创建/*boolean flagStringBuffer output*/myFunction(0, 0, board, word, new StringBuffer());return flag;//2.核心操作/*if(output word){flag true;return;}*///3.递归回溯/*myFunction(int row, int column, char[][] board, String word, StringBuffer output)*/}public void myFunction(int row, int column, char[][] board, String word, StringBuffer output){if(output word){flag true;return;}output.append(board[row][column]);if(row1 board.length){myFunction(row1, column, board, word);}if(column1 board[0].length){myFunction(row, column1, board, word);}output.deleteCharAt(output.size()-1);}
}参考答案
class Solution {public boolean exist(char[][] board, String word) {int h board.length, w board[0].length;boolean[][] visited new boolean[h][w];for (int i 0; i h; i) {for (int j 0; j w; j) {boolean flag check(board, visited, i, j, word, 0);if (flag) {return true;}}}return false;}public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {if (board[i][j] ! s.charAt(k)) {return false;} else if (k s.length() - 1) {return true;}visited[i][j] true;int[][] directions {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};boolean result false;for (int[] dir : directions) {int newi i dir[0], newj j dir[1];if (newi 0 newi board.length newj 0 newj board[0].length) {if (!visited[newi][newj]) {boolean flag check(board, visited, newi, newj, s, k 1);if (flag) {result true;break;}}}}visited[i][j] false;return result;}
}07 分割回文串 class Solution {public ListListString partition(String s) {}
}① Arrays.fill(f[i], true); 是什么意思
f 是一个二维布尔数组f[i] 表示二维数组 f 的第 i 行也是一个布尔数组。Arrays.fill 是Java标准库中用于快速给数组填充值的方法。Arrays.fill(f[i], true); 的意思是将数组 f[i] 中的每个元素都赋值为 true。
② 为什么这样遍历
for (int i n - 1; i 0; --i) {for (int j i 1; j n; j) {f[i][j] (s.charAt(i) s.charAt(j)) f[i 1][j - 1];}
}动态规划的状态转移是
f[i][j] (s.charAt(i) s.charAt(j)) f[i1][j-1];也就是说
子串[i, j]是否是回文取决于
s[i] 和 s[j] 是否相等中间的子串 [i1, j-1] 是否是回文即 f[i1][j-1]
因此需要先保证f[i1][j-1]已经被计算出来才能正确计算f[i][j]。
假如从前往后遍历 i那f[i1][j-1]还没有计算dp就没法用。
③ ans.add(s.substring(i, j 1));为什么是j1而不是j?
这是因为Java中String的substring方法的语法是
s.substring(beginIndex, endIndex)beginIndex 是子串起始索引包含。endIndex 是子串结束索引不包含。
所以substring(i, j 1)表示取得字符串从索引i开始到j结束包含位置j的字符刚好是你想要的子串s[i..j]。
④ ret.add(new ArrayList(ans)); 是什么是“深拷贝”
因为 ans 是递归过程中不断修改的同一个对象它会随着回溯加入和删除元素。如果不复制只把 ans 本身加入结果后续修改会导致结果集中所有引用都变成最后的状态结果错误。复制一份保证当前这个状态的路径是独立的不会被后续递归修改。
什么是深拷贝
浅拷贝只复制引用多个对象共享同一份内存数据比如指向同一个列表修改其中一个会影响所有。深拷贝则复制对象及其内部包含的数据生成完全独立的对象。
⑤ dfs(s, j 1);为什么新的递归起始位置是 j 1
当前选择的回文子串是 s[i..j]包含i到j。下一步需要找的是紧接着当前子串后面的部分即以 j 1 为起点的剩余字符串。因为回文分割要求子串连续且不重叠每找到一个回文子串后搜索区间从它的下一个位置开始。
class Solution {//1.创建boolean[][] f;ListListString result new ArrayList();ListString output new ArrayList();int n;public ListListString partition(String s) {n s.length();f new boolean[n][n];for(int i0; in; i){Arrays.fill(f[i], true);}for(int in-1; i0; --i){for(int ji1; jn; j){f[i][j] (s.charAt(i) s.charAt(j)) f[i1][j-1];}}myFunction(s, 0);return result;}public void myFunction(String s, int i){//2.核心操作if(i s.length()){result.add(new ArrayList(output));return;}//3.递归回溯for(int ji; jn; j){if(f[i][j]){output.add(s.substring(i, j1));myFunction(s, j1);output.remove(output.size()-1);}}}
}08 N 皇后 方法一基于集合的回溯
class Solution {public ListListString solveNQueens(int n) {//1.创建ListListString result new ArrayList();int[] queens new int[n];Arrays.fill(queens, -1);SetInteger columns new HashSet(); //列SetInteger diagonals1 new HashSet(); //主对角线 row - iSetInteger diagonals2 new HashSet(); //副对角线 row imyFunction(result, queens, n, 0, columns, diagonals1, diagonals2);return result;}public void myFunction(ListListString result, int[] queens, int n, int row,SetInteger columns, SetInteger diagonals1, SetInteger diagonals2){//2.核心操作if(n row){ListString output myFunction2(queens, n);result.add(output);}else{//遍历全列寻找插入皇后的位置for(int i0; in; i){ if(columns.contains(i)){continue;}int diagonal1 row - i;if(diagonals1.contains(diagonal1)){continue;}int diagonal2 row i;if(diagonals2.contains(diagonal2)){continue;}//3.递归回溯queens[row] i;columns.add(i);diagonals1.add(diagonal1);diagonals2.add(diagonal2);myFunction(result, queens, n, row1, columns, diagonals1, diagonals2);queens[row] -1;columns.remove(i);diagonals1.remove(diagonal1);diagonals2.remove(diagonal2);}}}public ListString myFunction2(int[] queens, int n){ListString output new ArrayList();for(int i0; in; i){char[] row new char[n];Arrays.fill(row, .);row[queens[i]] Q;output.add(new String(row));}return output;}
}方法二基于位运算的回溯
① 为什么 x (-x) 可以获得 x 的二进制表示中的最低位的 1 的位置
x 是一个二进制数如 01011000。-x 是 x 的补码表示计算方式是对 x 取反后加 1-x ~x 1二进制中最低的那个 1 保持位置不变之后的位变成了 0。
② 为什么 x (x - 1) 可以将 x 的二进制表示中的最低位的 1 置成 0
举例
假设 x 01011000最低位的 1 是倒数第 4 位。
x 01011000x - 1 01010111减 1 会把最低位的 1 减为 0后面的 0 变成 1
然后计算 x 01011000x-1 01010111
x (x - 1) 01010000可以看到最低位的 1第 4 位被成功清除。
③ int availablePositions ((1 n) - 1) (~(columns | diagonals1 | diagonals2));啥意思
(1 n) - 1相当于让低n位变成1高位是0。比如n4时 (1 4) - 1 15二进制是1111生成一个低n位为1的掩码限制后续的位运算结果不超过n位范围。(columns | diagonals1 | diagonals2)这是把3个已有占用位置的状态进行“或运算”得到所有被占用的位置集合。~(columns | diagonals1 | diagonals2)取反操作表示所有没有被占用的位置即可用位置。与前面((1 n) - 1)进行“与运算”保证结果只在低n位防止高位的误差。
④ int column Integer.bitCount(position - 1);啥意思
position 是一个位掩码且只有1个二进制位为1我们通过availablePositions (-availablePositions)拿到的最低位1比如position 00001000。position - 1 则是将最低的那个1位变成0且该位右边的位全部置1比如 position 00001000 (第4位是1代表第3列) position - 1 00000111Integer.bitCount(x) 是Java内置函数计算x的二进制表示中有多少个1。
举例
position 00001000 (二进制)position - 1 00000111 (二进制)bitCount(7) 3说明皇后要放在第3列从0开始计数。
⑤ columns | position 中的|啥意思
它会对两个整数的二进制每一位进行“或”操作只要对应位上有1结果位就是1 否则是0。
举例
列从右到左位3位2位1位0columns0010position0100columns | position0110
