社区 › 业界 › hot100之回溯下

赖娅闺 发表于 2025-6-22 23:32:52

hot100之回溯下

单词搜索(079)

class Solution {
    int m, n;
    public boolean exist(char[][] board, String word) {
      m = board.length;
      n = board.length;
      char[] words = word.toCharArray();
      for(int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (backTrace(0, i, j, board, words)) return true;
            }
      }
      return false;
    }
    private boolean backTrace(int idx, int row, int col, char[][] board, char[] words){
      if (row < 0 || row >= m || col < 0 || col >= n || board != words) return false;
      if (idx == words.length -1) return true;
      board = '0';
      boolean status = backTrace(idx+1, row+1, col, board, words) || backTrace(idx+1, row, col+1, board, words)||
                         backTrace(idx+1, row-1, col, board, words) || backTrace(idx+1, row, col-1, board, words);
      board = words;
      return status;
    }
}

[*]分析
简单回溯, 开开胃
分割回文串(131)

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
      backTrace(0, s);
      return res;   
    }

    private void backTrace(int idx, String s){
      if (idx == s.length()){
            res.add(new ArrayList(path));
            return;
      }
      for (int j = idx; j < s.length(); j++){
            if (isPalindrome(idx, j, s)){
                path.add(s.substring(idx, j+1));
                backTrace(j+1, s);
                path.remove(path.size()-1);
            }
      }
    }

    private boolean isPalindrome(int lef, int rig, String s){
      while(lef < rig){
            if (s.charAt(lef++) != s.charAt(rig--)) returnfalse;
      }
      return true;
    }

}

[*]分析
判断是否为回文串, 若是则分割
N皇后(051)

class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
      int[] queens = new int;
      boolean[] column = new boolean;
      boolean[] attaRig = new boolean;
      boolean[] attaLef = new boolean;
      backTrace(0, queens, column, attaLef, attaRig);
      return res;
    }

    private void backTrace(int row, int[] queens, boolean[] column, boolean[] attaLef, boolean[] attaRig ){
      int n = column.length;
      if (row == n){
            List<String> temp = new ArrayList<>(n);
            for(int col : queens){
                char[] rowArray = new char;
                Arrays.fill(rowArray, '.');
                rowArray = 'Q';
                temp.add(new String(rowArray));
            }
            res.add(temp);
            return;
      }

      for (int col = 0; col < n; col++){
            int attaLefIdx = row - col + n -1;
            if (!column && !attaLef && !attaRig ){
                queens = col;
                column = attaLef = attaRig = true;
                backTrace(row+1, queens, column, attaLef, attaRig);
                column = attaLef = attaRig = false;
            }
      }
    }
}

[*]分析
N皇后带来了一个条件 →

[*]行不相容 →以行遍历, 一行只插入一个元素
[*]列, 对角线不相容 → Boolean数组来标记
灵神太强大了

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

师悠逸 发表于 2025-10-20 10:00:22

感谢，下载保存了

高清宁 发表于 2025-11-11 04:07:14

东西不错很实用谢谢分享

贺蛟亡 发表于 2025-11-13 23:21:34

谢谢分享，试用一下

呈步 发表于 2025-12-24 10:16:07

过来提前占个楼

飧沾 发表于 2025-12-25 15:13:04

很好很强大我过来先占个楼 待编辑

轮达 发表于 2026-1-16 02:47:36

感谢发布原创作品，程序园因你更精彩

秦晓曼 发表于 2026-1-18 03:02:54

感谢，下载保存了

摹熹 发表于 2026-1-21 03:29:09

感谢分享，学习下。

吉娅寿 发表于 2026-1-21 16:49:36

感谢发布原创作品，程序园因你更精彩

驼娑 发表于 2026-1-22 12:46:53

新版吗？好像是停更了吧。

痕厄 发表于 2026-1-23 03:26:11

感谢分享，学习下。

但婆 发表于 2026-1-24 01:42:41

喜欢鼓捣这些软件，现在用得少，谢谢分享！

后仲舒 发表于 2026-1-24 03:27:03

前排留名，哈哈哈

喳谍 发表于 2026-1-27 08:39:35

很好很强大我过来先占个楼 待编辑

琦谓 发表于 2026-1-30 07:39:48

过来提前占个楼

喳谍 发表于 2026-2-3 08:08:22

这个有用。

魁睥 发表于 2026-2-4 05:41:12

感谢分享

揿纰潦 发表于 2026-2-6 06:54:37

感谢分享，学习下。

姜删懔 发表于 2026-2-9 18:10:42

喜欢鼓捣这些软件，现在用得少，谢谢分享！

查看完整版本: hot100之回溯下