单词搜索
使用 回溯法 来解决。回溯法适合用于这种路径搜索问题，我们需要在网格中寻找单词，并且每个字符都只能使用一次。
思路：
-
递归搜索：我们可以从网格中的每个单元格开始，进行深度优先搜索（DFS），并通过递归逐个匹配单词中的字符。每次匹配时，我们需要检查当前位置是否符合条件，并标记访问过的单元格，避免重复使用。
-
方向控制：相邻的单元格可以是上下左右四个方向。因此，我们需要在四个方向上进行递归搜索。
-
回溯：当在某个方向无法继续时，需要回溯并尝试其他方向。
具体步骤：
- 从网格的每个单元格开始搜索。
- 每次递归时，检查当前字符是否与单词的当前字符匹配。
- 递归到下一个字符时，需要标记当前单元格为已访问，并确保不重复使用该单元格。
- 如果找到整个单词，返回
true，否则继续尝试其他路径。 - 如果无法找到单词，则返回
false。
class Solution {
public boolean exist(char[][] board, String word) {
if(board == null || board.length == 0 || word == null || word.length() == 0){
return false;
}
//遍历每一个点，尝试从该点开始搜索
for(int i = 0;i < board.length;i++){
for(int j = 0;j < board[0].length;j++){
if(dfs(board,word,i,j,0)){
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board,String word,int i,int j,int index){
//如果已经找到所有的字符
if(index == word.length()){
return true;
}
//边界条件：检查当前位置是否越界，或者字符是否匹配
if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)){
return false;
}
//标记当前位置为已访问，避免重复使用
char temp = board[i][j];
board[i][j] = '#';//用一个不可能的字符标记已访问
//向四个方向递归搜索
boolean found = dfs(board,word,i + 1,j,index + 1) ||
dfs(board,word,i - 1,j,index + 1) ||
dfs(board,word,i,j + 1,index + 1) ||
dfs(board,word,i,j - 1,index + 1);
//恢复当前状态
board[i][j] = temp;
return found;
}
}分割回文串
思路：
-
回文判断：首先需要能够判断一个字符串是否为回文串。一个字符串是回文串当且仅当它从前往后和从后往前的字符顺序相同。
-
递归与回溯：可以使用递归的方式来进行分割，递归的过程中将字符串分割成多个子串。如果某个子串是回文串，那么继续对剩余部分进行分割，直到整个字符串都被分割完。
-
剪枝优化：在递归过程中，如果某个子串不是回文串，则不继续往下搜索，直接回溯。
解决步骤：
- 判断回文：在递归过程中，我们需要一个函数来判断当前子串是否为回文。
- 回溯分割：从字符串的第一个字符开始，尝试每个位置作为分割点，检查每个子串是否是回文。如果是回文，则将其加入到当前路径中，递归处理剩余部分。
- 终止条件：当处理到字符串的末尾时，当前路径中的所有子串都是回文串，加入到结果列表中。
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
List<String> current = new ArrayList<>();
backtrack(result,current,s,0);
return result;
}
private void backtrack(List<List<String>> result,List<String> current,String s,int start){
//递归的终止条件：如果start已经遍历到字符串的末尾，说明当前的分割已经完成
if(start == s.length()){
result.add(new ArrayList<>(current));
return;
}
//从每一个位置判断是否是回文
for(int end = start + 1;end <= s.length();end++){
String substring = s.substring(start,end);
if(isPalindrome(substring)){
current.add(substring);//如果是回文，将子串加入当前路径
backtrack(result,current,s,end);//递归处理剩余部分
current.remove(current.size() - 1);//回溯，移除最后一个子串
}
}
}
//判断一个字符串是否是回文串
private boolean isPalindrome(String str){
int left = 0,right = str.length() - 1;
while(left < right){
if(str.charAt(left) != str.charAt(right)){
return false;
}
left++;
right--;
}
return true;
}
}N皇后
-
回溯法：我们可以使用回溯法来逐行放置皇后，确保每次放置时不会和之前放置的皇后发生冲突。
-
冲突检测：
- 每一行只能有一个皇后。
- 每一列只能有一个皇后。
- 每条对角线只能有一个皇后。可以通过行列坐标的差和和来区分两条对角线。
-
约束条件：
- 我们使用三个集合来记录哪些列、哪些主对角线（
row - col）、哪些副对角线（row + col）被占用。 - 每次递归时，尝试在当前行的每一列放置皇后，如果没有冲突，则继续在下一行放置，直到所有行都被填满。
- 我们使用三个集合来记录哪些列、哪些主对角线（
-
回溯过程：
- 通过递归尝试不同的列位置放置皇后，确保每个皇后不会和其他皇后发生冲突。
- 当所有皇后都成功放置后，将当前的棋盘状态加入结果列表。
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
//用来记录哪些列、主对角线、副对角线已经被占用
Set<Integer> cols = new HashSet<>();
Set<Integer> diag1 = new HashSet<>();
Set<Integer> diag2 = new HashSet<>();
//当前棋盘的状态
List<String> board = new ArrayList<>();
backtrack(n,0,cols,diag1,diag2,board,result);
return result;
}
private void backtrack(int n,int row,Set<Integer> cols,Set<Integer> diag1,Set<Integer> diag2,List<String> board,List<List<String>> result){
//如果所有行都已经放置了一个皇后，说明找到一个解法
if(row == n){
result.add(new ArrayList<>(board));
return;
}
//尝试在当前行的每一列放置皇后
for(int col = 0;col < n;col++){
//检查是否冲突：列、主对角线、副对角线
if(cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col)){
continue;
}
//放置皇后
cols.add(col);
diag1.add(row - col);
diag2.add(row + col);
//构建当前行的棋盘状态
StringBuilder currentRow = new StringBuilder();
for(int i = 0;i < n;i++){
if(i == col){
currentRow.append('Q');
}else{
currentRow.append('.');
}
}
board.add(currentRow.toString());
//递归放置下一行的皇后
backtrack(n,row + 1,cols,diag1,diag2,board,result);
//回溯，撤销选择
cols.remove(col);
diag1.remove(row - col);
diag2.remove(row + col);
board.remove(board.size() - 1);
}
}
}搜索插入位置
思路：
- 二分查找：由于数组已经排序，可以使用二分查找来定位目标值。如果找到了目标值，返回其索引；如果没有找到，则返回目标值应该插入的位置。
- 插入位置：二分查找会帮助我们找到一个合适的位置，使得目标值可以插入数组中，且保持数组的排序。插入位置是指目标值应插入的最小位置，确保数组仍然有序。
步骤：
- 初始化两个指针
left和right，分别指向数组的开始和结束。 - 在每次迭代时，计算中间索引
mid，并与目标值进行比较：- 如果
nums[mid] == target，说明找到了目标值，直接返回mid。 - 如果
nums[mid] < target，说明目标值在右半部分，更新left为mid + 1。 - 如果
nums[mid] > target，说明目标值在左半部分，更新right为mid - 1。
- 如果
- 如果循环结束时没有找到目标值，
left将是目标值应该插入的位置。
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0,right = nums.length - 1;
//二分查找
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){
return mid;//找到目标值
}else if(nums[mid] < target){
left = mid + 1;//目标值在右边
}else{
right = mid - 1;//目标值在左边
}
}
//如果没有找到目标值，left是插入位置
return left;
}
}搜索二维矩阵
-
行和列的结构：
- 由于每行是按非严格递增排列的，因此我们可以对每行进行二分查找，或者使用其他方法逐行查找。
- 由于每行的第一个元素大于前一行的最后一个元素，矩阵实际上满足一个类似 "升序排列" 的条件，整个矩阵可以看作一个有序的数组。
-
优化的二分查找：
- 我们可以将二维矩阵转换为一个一维的排序数组，通过二分查找来快速定位目标值。
- 假设矩阵有
m行n列，那么元素可以被看作一个有m * n个元素的数组，索引i对应的矩阵元素是matrix[i / n][i % n]。这样可以把二维查找转化为一维查找。
时间复杂度为 O(log(m * n))。
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int low = 0, high = m * n - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
int x = matrix[mid / n][mid % n];
if (x < target) {
low = mid + 1;
} else if (x > target) {
high = mid - 1;
} else {
return true;
}
}
return false;
}
}
