【算法】回溯法四步走 (14)

回溯还原现场：这里现场破坏就破坏了，没必要还原。

class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> list = new ArrayList<>(); f(matrix, 0, 0, 0, list); return list; } // 试试递归，参数有 数组，开始位置x，y，方向，存储的List，返回方向 /** * * @param matrix：数组 * @param x：当前行位置 * @param y：当前列位置 * @param direction：0右，1下，2左，3上 * @param list：用来存放记录我们经过的元素，结果数据 * @return：返回方向，用来给下一次遍历指明方向 */ public int f(int[][] matrix, int x, int y, int direction, List<Integer> list) { if (x >= matrix.length || x < 0 || y >= matrix[x].length || y < 0 || matrix[x][y] == Integer.MAX_VALUE) { //碰壁，或者为0遍历过了 return (direction + 1) % 4; } // System.out.print(matrix[x][y]); list.add(matrix[x][y]); matrix[x][y] = Integer.MAX_VALUE; // 特别注意：这里需要遍历两次 // 第一次遍历是为了确定一直前进的方向 // 第二次遍历是为了及时修改方向继续前进 // 比如说向上的时候遇到了遍历过的元素，然后回溯回退，结果到了最后return了，所以我们得在它回溯回退回来的时候，加一层前进方向，看看有没有遍历完，能不能继续前进 for (int i = 0; i < 2; i++) { switch (direction) { case 0: direction = f(matrix, x, y + 1, direction, list); break; case 1: direction = f(matrix, x + 1, y, direction, list); break; case 2: direction = f(matrix, x, y - 1, direction, list); break; case 3: direction = f(matrix, x - 1, y, direction, list); break; } } return direction; } }

迭代答案：

// 试试迭代 class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> result = new ArrayList<Integer>(); if (matrix.length == 0) { return result; } // 设置上下左右边界 int left = 0, right = matrix[0].length - 1, up = 0, down = matrix.length - 1; // 当前位置 int x = 0, y = 0; while (left <= right && up <= down) { for (y = left; y <= right && avoid(left,right,up,down); y++) { result.add(matrix[x][y]); } y--; up++; for (x = up; x <= down && avoid(left,right,up,down); x++) { result.add(matrix[x][y]); } x--; right--; for (y = right; y >= left && avoid(left,right,up,down); y--) { result.add(matrix[x][y]); } y++; down--; for (x = down; x >= up && avoid(left,right,up,down); x--) { result.add(matrix[x][y]); } x++; left++; } return result; } // up <= down && left <= right，这是避免碰壁的条件 public boolean avoid(int left, int right, int up, int down) { return up <= down && left <= right; } } 剑指 Offer 13. 机器人的运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

输入：m = 2, n = 3, k = 1 输出：3

示例 2：

输入：m = 3, n = 1, k = 0 输出：1 答案 class Solution { public int m; public int n; public int k; public int res = 0; public boolean[][] used; public int movingCount(int m, int n, int k) { this.m = m; this.n = n; this.k = k; used = new boolean[m][n]; dfs(0, 0); return res; } public void dfs(int x, int y) { if (x >= m || y >= n || sum(x) + sum(y) > k || used[x][y]) { return; } used[x][y] = true; res++; dfs(x, y + 1); dfs(x + 1, y); // 只用向右、向下走即可遍历完所有，不需要向左、向上 // dfs(x, y - 1); // dfs(x - 1, y); } public int sum(int x) { int sum = 0; while (x != 0) { sum += x % 10; x /= 10; } return sum; } } 剑指 Offer 38. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"] 答案 class Solution { public Set<String> set = new HashSet<>(); public StringBuilder sb = new StringBuilder(); public int[] used = null; // 记录遍历过的字符索引，遍历过为1，没遍历过为0 public String[] permutation(String s) { if (s == null) { return new String[0]; } used = new int[s.length()]; f(s, 0); return new ArrayList<String>(set).toArray(new String[set.size()]); } // 递归回溯 // 状态参数：当前在字符串哪一个位置index，当前字符串 public void f(String s, int index) { if (index > s.length() - 1) { set.add(sb.toString()); return; } // 明确所有路径 // 遍历字符串中所有字符，一个一个放入该index位置 for (int i = 0; i < s.length(); i++) { if (used[i] > 0) { continue; } // 加入字符 sb.append(s.charAt(i)); used[i]++; f(s, index + 1); // 还原现场 used[i]--; sb.deleteCharAt(sb.length() - 1); } } } 剑指 Offer 12. 矩阵中的路径