20天 hot 100 速通计划-day13

回溯

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

判断回文字符串是原子操作

class Solution {
public:
    vector<vector<string>> res;    // 保存最终的结果
    vector<string> path;           // 保存当前的路径（一次回溯的结果）

    // 判断字符串 s 的子串 [start, end] 是否为回文串 By 首尾双指针
    bool isP(string s, int start, int end){
        for(int i = start, j = end; i <= j; i++, j--){
            if(s[i] != s[j]) return false;
        }
        return true;
    }

    // 回溯函数
  	// 参返分析：输入字符串和startIndex（分割即组合，不放回），无需返回值
  	// 终止条件：startIndex == s.size() 时，取不到 s[startIndex]，故终止
  	// 单层逻辑：判断子串是否为回文，若是则保存，不是则跳过
    void backtrack(const string &s, int startIndex){ 
      	// 如果回溯到最后一个字符的下一个位置，说明已经完成了一次回溯，将当前的路径保存到结果中
        if(startIndex >= s.size()){    
            res.push_back(path);
            return;
        }
      
      	// 带放回，遍历从 startIndex 开始的所有子串
        for(int i = startIndex; i < s.size(); i++){  
          	// 如果子串是回文串
            if(isP(s, startIndex, i)){    
                string str = s.substr(startIndex, i - startIndex + 1);    // 取出子串
                path.push_back(str);    // 将子串加入到当前路径中
                backtrack(s, i+1);    // 继续对下一个位置进行回溯
                path.pop_back();    // 回溯完成后，将子串从当前路径中移除，继续遍历其他子串
            }else continue;    // 如果子串不是回文串，跳过当前的循环，进入下一次循环
        }

    }
  
    vector<vector<string>> partition(string s) {
      //clear() 可有可无，只是为了保证初始集合为空集
        res.clear();
        path.clear();
        backtrack(s, 0);
        return res;
    }
}

51. N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

• 1 <= n <= 9

class Solution {
public:
    vector<string> chessbord; //定义一个字符串向量，存储棋盘的状态
    vector<vector<string>> res; //定义一个向量向量，存储所有合法的棋盘状态

    //判断当前位置是否可以放置皇后
    bool isValid(int row, int col, int n, vector<string>& chessboard){
        //检查列是否重复
        for(int i = 0; i < row; i++){
            if(chessboard[i][col]=='Q') return false;
        }
        //检查45度斜线是否重复
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
            if(chessboard[i][j]=='Q') return false;
        }
        //检查135度斜线是否重复
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){
            if(chessboard[i][j]=='Q') return false;
        }
        return true; //如果都没有重复，返回true
    }

    //回溯函数，逐行放置皇后
    void backtrack(int row, int n, vector<string>& chessboard){
        if(row == n){ //当所有行都放置了皇后，得到一个合法的棋盘状态
            res.push_back(chessboard); //将其存入结果集
            return;
        }
        for(int col = 0; col < n; col++){ //按列遍历当前行
            if(isValid(row, col, n, chessboard)){ //检查当前位置是否可以放置皇后
                chessboard[row][col] = 'Q'; //放置皇后
                row++; //进入下一行
                backtrack(row, n, chessboard); //递归调用下一行
                row--; //回溯，将皇后移除
                chessboard[row][col] = '.'; //将当前位置重置为空
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<string> chessboard(n, string(n, '.')); //初始化棋盘，全部为空
        backtrack(0, n, chessboard); //从第0行开始放置皇后
        return res; //返回结果集
    }
    
};

二分查找

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 104

二分法变体，原教旨主义二分法是找有序数组某一元素的下标，找不到返回 -1，这里的二分法是找得到返回下标，找不到返回被顺序插入的位置

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
      //首尾双指针，左闭右闭
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
              	//等于目标值，直接返回目标值下标
                return mid;
            } else if (nums[mid] < target) { // 小于目标值，更新 left，在右半区间找
                left = mid + 1;
            } else {  // 大于目标值，更新 right，在左半区间找
                right = mid - 1;
            }
        }
      	//双指针相遇都没找到目标值，就在相遇处的下一个位置，即在 left 插入
      	//因为跳出循环时 left 刚好大于 right，left 就表示下一个位置
        return left;
    }
};

74. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非递减顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

关键在于利用数组的特点

• 每行中的整数从左到右按非递减顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

这使得该数组虽然看上去像是二维数组，但是也可看作一个有序的一位数组，关键在于做好一维视角下的逻辑操作到二维数组的真实操作的映射

class Solution {
public:
  bool searchMatrix(vector<vector<int>>& matrix, int target) {
      int m = matrix.size();
      int n = matrix[0].size();
    
		//首尾双指针，左闭右闭的二分法模板
      int left = 0, right = m * n - 1;
      while (left <= right) {
          int mid = left + (right - left) / 2;
        
        //取中间值的操作映射，本质上就是个数学换算技巧
        // 一维视角的逻辑操作是 nums[mid]
        // 二维数组的真实操作是 matrix[mid / n][mid % n]
          int midVal = matrix[mid / n][mid % n];

          if (midVal == target) {
            //找到了返回 true
              return true;
          } else if (midVal < target) { // 中间值小于目标值，更新 left，在右半区间找
              left = mid + 1;
          } else { // 中间值大于目标值，更新 right，在左半区间找
              right = mid - 1;
          }
      }

    //找不到返回 false
      return false;
  }
};

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

此处引入两个边界二分查找函数，分别找左边界和右边界

边界二分查找与原教旨主义二分查找的区别在于处理返回的逻辑不同

• 原教旨主义二分查找一旦找到，遇见符合要求的值时立即返回下标，可能不一定扫描完整个数组
• 边界二分查找则是在遇见符合要求的值时通过引入记录，并增加边界处理的操作，来获取下标。只有当左指针等于右指针时才退出循环，一定扫描完整个数组

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 定义左右索引
        int leftIdx = binarySearchLeft(nums, target);
        int rightIdx = binarySearchRight(nums, target);

        // 判断是否找到目标值，如果找到则返回左右索引
      	// 两重限制
      	// 1.下标值不能越界
      	// 2.下标元素与目标值相等
        if (leftIdx <= rightIdx 
            && rightIdx < nums.size() 
            && nums[leftIdx] == target 
            && nums[rightIdx] == target) {
            return {leftIdx, rightIdx};
        }

        // 如果没有找到目标值，返回-1
        return {-1, -1};
    }

    // 左边界二分查找函数
    int binarySearchLeft(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1, res = nums.size();
        while (left <= right) {
            int mid = (left + right) / 2;
            // 如果中间值大于等于目标值，则缩小右边界
            if (nums[mid] >= target) {
                right = mid - 1;
                // 更新目标索引
                res = mid;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }

    // 右边界二分查找函数
    int binarySearchRight(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1, res = nums.size();
        while (left <= right) {
            int mid = (left + right) / 2;
            // 如果中间值大于目标值，则缩小右边界
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
                // 更新目标索引
                res = mid;
            }
        }
        return res;
    }
};