重写N皇后和分割回文串,发现会想不明白path.remove(path.size() - 1)是在if里面还是if外面,问了GPT感觉很清楚
题目
N皇后
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<String>> solveNQueens(int n) {dfs(n, 0);List<List<String>> resStr = new ArrayList<>();for (int i = 0; i < res.size(); i++) {List<String> tmp = new ArrayList<>();List<Integer> tmpPath = res.get(i);for (int j = 0; j < tmpPath.size(); j++) {StringBuilder sb = new StringBuilder();for (int k = 0; k < n; k++) {if (k == tmpPath.get(j)) {sb.append('Q');}else {sb.append('.');}}tmp.add(sb.toString());}resStr.add(tmp);}return resStr;}public void dfs(int n, int row) {if (row == n) {res.add(new ArrayList(path));return;}for(int col = 0; col < n; col++) {path.add(col);if (isValis(path)) {dfs(n, row + 1);}path.remove(path.size() - 1);}}public boolean isValis(List<Integer> path) {int row_size = path.size() - 1;for (int i = 0; i < row_size; i++) {int diff = Math.abs(path.get(i) - path.get(row_size));if (diff == 0 || diff == row_size - i) {return false;}}return true;}
}
分割回文串
class Solution {List<List<String>> res = new ArrayList<>();List<String> path = new ArrayList<>();public List<List<String>> partition(String s) {dfs(s, 0);return res;}public void dfs(String s, int start) {if (start == s.length()) {res.add(new ArrayList<>(path));return;}for (int i = start; i < s.length(); i++) {if (isParition(s, start, i)) {path.add(s.substring(start, i + 1));dfs(s, i + 1);path.remove(path.size() - 1);}}}public boolean isParition(String s, int i, int j) {while (i < j) {if (s.charAt(i) != s.charAt(j)) {return false;}i++;j--;}return true;}
}
总结
N皇后问题:每次尝试都需要回溯,无论是否成功,因此 path.remove() 在 for 循环内、if 语句外。
分割回文子串问题:只有在成功分割出回文子串后才需要回溯,因此 path.remove() 在 if 语句内。
这两个问题的回溯逻辑不同,导致 path.remove() 的位置不同。确保回溯操作能正确撤销当前的选择,以便探索其他可能的解决方案,是放置 path.remove() 的关键。