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数组来标记
灵神太强大了
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]