JLUVicent

738单调递增的数字&51N皇后

 
  • 2023年 03月23日
  • 0 阅读

day37

738.单调递增的数字

题目链接：738. 单调递增的数字

解题思路：参考 视频

先将数字转为字符串，判断前一个和当前字符大小，如果前一个大于当前字符，将之后所有的数字变为9，最终返回一个数字 stoi()函数

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string s = to_string(n);
        int flag = s.size();   //定义标志位 最开始指向最后一个的后一个位置
        for( int i =s.size()-1 ; i > 0; i--){
            if( s[i] < s[i-1]){
                flag = i;
                //前一个数要-1
                s[i-1]--;
            }
        }
        for( int i = flag; i < s.size(); i++){
            s[i] = '9';
        }
        return stoi(s);
    }
};

51.N皇后

题目链接：51. N 皇后

解题思路：参考 视频

难点在于遍历N皇后，暴力明显不可行，需要遍历N次，N个for循环

51.N皇后

通过回溯，for循环控制行的每一列，递归控制列的每一行，然后使用回溯方法进行解决。

class Solution {
public:

    //判断合法规则：不能同行，不能同列，不能同斜线
    bool isVaild( int row, int col, vector<string>& chessboard, int n){
        //不用检查同行的元素，其在递归中已经去掉
        //检查列
        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;
    }

    vector<vector<string>> result;
    // 递归
    void backtracking(vector<string>&chessboard, int n, int row){
        if( row == n){
            result.push_back(chessboard);
            return;
        }
        for( int col = 0; col < n; col++){
            if( isVaild( row,col,chessboard,n)){
                chessboard[row][col] = 'Q';
                backtracking( chessboard,n,row+1);
                chessboard[row][col] = '.'; //回溯，撤回皇后
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        std::vector<std::string> chessboard(n,std::string(n,'.'));
        backtracking(chessboard,n,0);
        return result;
    }
};
搜索