hot100之回溯下

单词搜索(079)

class Solution {
 int m, n;
 public boolean exist(char[][] board, String word) {
 m = board.length;
 n = board[0].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[row][col] != words[idx]) return false;
 if (idx == words.length -1) return true;
 board[row][col] = '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[row][col] = words[idx];
 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--)) return false;
 }
 return true;
 }
}

• 分析

判断是否为回文串, 若是则分割

N皇后(051)

class Solution {
 List<List<String>> res = new ArrayList<>();
 public List<List<String>> solveNQueens(int n) {
 int[] queens = new int[n];
 boolean[] column = new boolean[n];
 boolean[] attaRig = new boolean[2*n];
 boolean[] attaLef = new boolean[2*n];
 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[n];
 Arrays.fill(rowArray, '.');
 rowArray[col] = '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[col] && !attaLef[attaLefIdx] && !attaRig[row + col] ){
 queens[row] = col;
 column[col] = attaLef[attaLefIdx] = attaRig[row + col] = true;
 backTrace(row+1, queens, column, attaLef, attaRig);
 column[col] = attaLef[attaLefIdx] = attaRig[row + col] = false;
 }
 }
 }
}

• 分析

N皇后带来了一个条件 →<插入元素”行””列””对角线”不相容>

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

灵神太强大了