登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 业界 ›hot100之回溯下

hot100之回溯下

赖娅闺 2025-6-22 23:32:52
单词搜索(079)
  1. class Solution {
  2.     int m, n;
  3.     public boolean exist(char[][] board, String word) {
  4.         m = board.length;
  5.         n = board[0].length;
  6.         char[] words = word.toCharArray();
  7.         for(int i = 0; i < m; i++){
  8.             for (int j = 0; j < n; j++){
  9.                 if (backTrace(0, i, j, board, words)) return true;
  10.             }
  11.         }
  12.         return false;
  13.     }
  14.     private boolean backTrace(int idx, int row, int col, char[][] board, char[] words){
  15.         if (row < 0 || row >= m || col < 0 || col >= n || board[row][col] != words[idx]) return false;
  16.         if (idx == words.length -1) return true;
  17.         board[row][col] = '0';
  18.         boolean status = backTrace(idx+1, row+1, col, board, words) || backTrace(idx+1, row, col+1, board, words)||
  19.                          backTrace(idx+1, row-1, col, board, words) || backTrace(idx+1, row, col-1, board, words);
  20.         board[row][col] = words[idx];
  21.         return status;
  22.     }
  23. }
复制代码

  • 分析
简单回溯, 开开胃
分割回文串(131)
  1. class Solution {
  2.     List<List<String>> res = new ArrayList<>();
  3.     List<String> path = new ArrayList<>();
  4.     public List<List<String>> partition(String s) {
  5.         backTrace(0, s);
  6.         return res;   
  7.     }
  9.     private void backTrace(int idx, String s){
  10.         if (idx == s.length()){
  11.             res.add(new ArrayList(path));
  12.             return;
  13.         }
  14.         for (int j = idx; j < s.length(); j++){
  15.             if (isPalindrome(idx, j, s)){
  16.                 path.add(s.substring(idx, j+1));
  17.                 backTrace(j+1, s);
  18.                 path.remove(path.size()-1);
  19.             }
  20.         }
  21.     }
  23.     private boolean isPalindrome(int lef, int rig, String s){
  24.         while(lef < rig){
  25.             if (s.charAt(lef++) != s.charAt(rig--)) return  false;
  26.         }
  27.         return true;
  28.     }
  30. }
复制代码

  • 分析
判断是否为回文串, 若是则分割
N皇后(051)
  1. class Solution {
  2.     List<List<String>> res = new ArrayList<>();
  3.     public List<List<String>> solveNQueens(int n) {
  4.         int[] queens = new int[n];
  5.         boolean[] column = new boolean[n];
  6.         boolean[] attaRig = new boolean[2*n];
  7.         boolean[] attaLef = new boolean[2*n];
  8.         backTrace(0, queens, column, attaLef, attaRig);
  9.         return res;
  10.     }
  12.     private void backTrace(int row, int[] queens, boolean[] column, boolean[] attaLef, boolean[] attaRig ){
  13.         int n = column.length;
  14.         if (row == n){
  15.             List<String> temp = new ArrayList<>(n);
  16.             for(int col : queens){
  17.                 char[] rowArray = new char[n];
  18.                 Arrays.fill(rowArray, '.');
  19.                 rowArray[col] = 'Q';
  20.                 temp.add(new String(rowArray));
  21.             }
  22.             res.add(temp);
  23.             return;
  24.         }
  26.         for (int col = 0; col < n; col++){
  27.             int attaLefIdx = row - col + n -1;
  28.             if (!column[col] && !attaLef[attaLefIdx] && !attaRig[row + col] ){
  29.                 queens[row] = col;
  30.                 column[col] = attaLef[attaLefIdx] = attaRig[row + col] = true;
  31.                 backTrace(row+1, queens, column, attaLef, attaRig);
  32.                 column[col] = attaLef[attaLefIdx] = attaRig[row + col] = false;
  33.             }
  34.         }
  35.     }
  36. }
复制代码

  • 分析
N皇后带来了一个条件 →

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

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

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
赖娅闺
2025-6-22 23:32:52

0

粉丝关注

9

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫