day 25|491.递增子序列，46.全排列，47.全排列 II，332.重新安排行程，51.N皇后，37，解数独

强度有点高 

491.递增子序列

491. 非递减子序列 - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> result;
    void findSubsequences(vector<int>& nums, int start, vector<int> &group){
        int n = group.size();
        if(group.size() >= 2){
            result.push_back(group);
        }
        int numsBack = INT_MIN;
        int mark[201] = {0};   // 用于防止出现相同元素
        for(int i = start; i < nums.size(); i++){
            if((group.size() > 0 && nums[i] < group[n - 1]) || mark[nums[i] + 100] == 1){
                continue;
            }
            group.push_back(nums[i]);
            findSubsequences(nums, i + 1, group);
            mark[nums[i] + 100] = 1;
            group.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<int> group;
        findSubsequences(nums, 0, group);
        return result;
    }
};

46.全排列

46. 全排列 - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> result;
    void permute(vector<int>& nums, unordered_set<int>& group, vector<int>& groupVec){
        if(groupVec.size() == nums.size()){
            result.push_back(groupVec);
            return ;
        }
        for(int i = 0; i < nums.size(); i++){  
            if(group.empty() || !group.count(nums[i])){  // 判断是否重复
                group.insert(nums[i]);
                groupVec.push_back(nums[i]);
                permute(nums, group, groupVec);
                group.erase(nums[i]);
                groupVec.pop_back();
            }

        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        unordered_set<int> group;
        vector<int> groupVec;
        permute(nums, group, groupVec);
        return result;
    }
};

47.全排列 II

47. 全排列 II - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> results;
    vector<int> visited, group;  // 用于记录每一个选择是否重复
    void permuteUnique(vector<int>& nums, int start){
        if(start >= nums.size()){
            results.push_back(group);
        }
        for(int i = 0; i < nums.size(); i++){
            if(visited[i] == 1 || (i > 0 && nums[i - 1] == nums[i] && visited[i - 1] == 0)){
                continue ;
            }
            group.push_back(nums[i]);
            visited[i] = 1;
            permuteUnique(nums, start + 1);
            visited[i] = 0;
            group.pop_back();
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        visited.resize(nums.size());
        permuteUnique(nums, 0);
        return results;
    }
};

332.重新安排行程

332. 重新安排行程 - 力扣（LeetCode）

超时了，害得练

class Solution
{
public:
    vector<string> findItinerary(vector<vector<string>> &tickets)
    {
        unordered_map<string, unordered_map<string, int>> paths;
        unordered_map<string, string> mp;
        vector<string> result, flight;
        for (vector<string> ticket : tickets)
        {
            paths[ticket[0]][ticket[1]]++;
            counts++;
        }
        traverse(paths, 0, "JFK", flight);
        result = minPath();
        return result;
    }

private:
    vector<vector<string>> flights;
    int counts = 0;
    void traverse(unordered_map<string, unordered_map<string, int>> paths, int cost, string start, vector<string> flight)
    {
        flight.push_back(start);
        if (paths[start].empty() && cost != counts)
        { // 起点无终点了，到角落了
            return;
        }
        if (cost == counts)
        { // 完整航班
            flights.push_back(flight);
            return;
        }
        vector<string> ends;
        for (pair path : paths[start])
        {
            ends.push_back(path.first);
        }
        cout << endl;
        for (string end : ends)
        { // 遍历以star为起点的所有航班
            paths[start][end]--;
            if(paths[start][end] == 0){
                paths[start].erase(end);
            }
            traverse(paths, cost + 1, end, flight);
            paths[start][end]++; // 回溯
        }
    }

    vector<string> lessPath(vector<string> path1, vector<string> path2)
    {
        int n = path1.size();
        for (int i = 0; i < n; i++)
        {
            if (path1[i] < path2[i])
            {
                return path1;
            }
            if (path1[i] > path2[i])
            {
                return path2;
            }
        }
        return path1;
    }

    vector<string> minPath()
    { // 求最小路径
        vector<string> minPath = flights[0];
        for (vector<string> path : flights)
        {
            cout << endl;
            minPath = lessPath(minPath, path);
        }
        return minPath;
    }
};

51.N皇后

51. N 皇后 - 力扣（LeetCode）

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        string s(n, '.');
        vector<string> boards(n, s);  // 皇后位置
        solveNQueens(0, boards, n, 0);
        return indexs;
    }
private:
    vector<vector<string>> indexs;
    void solveNQueens(int x, vector<string> &boards, int n, int countQ){ 
        if(countQ == n){
            indexs.push_back(boards);
        } 
        if(x >= n){
            return ;
        }
        for(int i = 0; i < n; i++){
            if(ifVisited(x, i, boards, n)){
                boards[x][i] = 'Q';
                solveNQueens(x + 1, boards, n, countQ + 1);
                boards[x][i] = '.';               
            }
        }
    }
    bool ifVisited(int x, int y, vector<string>& boards, int n){
        for(int i = 0; i < n; i++){
            if(boards[x][i] == 'Q'){
                return false;
            }
        }
        for(int j = 0; j < n; j++){
            if(boards[j][y] == 'Q'){
                return false;
            }
        }
        int xDiff0 = x, xDiffn = n - x - 1, yDiff0 = y, yDiffn = n - y - 1;
        for(int i = 0; i < n; i++){
            if(x - i >= 0 && y - i >= 0){
                if(boards[x - i][y - i] == 'Q'){
                    return false;
                } 
            }
            if(x - i >= 0 && y + i < n){
                if(boards[x - i][y + i] == 'Q'){
                    return false;
                }
            }
            if(x + i < n && y - i >= 0){
                if(boards[x + i][y - i] == 'Q'){
                    return false;
                }
            }
            if(x + i < n && y + i < n){
                if(boards[x + i][y + i] == 'Q'){
                    return false;
                }
            }
        }
        return true;
    }
};

37，解数独

37. 解数独 - 力扣（LeetCode）

太搞了

class Solution
{
public:
    void solveSudoku(vector<vector<char>> &board)
    {
        vector<vector<char>> result = board;
        int counts = 0;
        for (vector<char> b : board)
        {
            for (char ca : b)
            {
                if (ca == '.')
                {
                    counts++;
                }
            }
        }
        solveSudoku(0, 0, result, 9, board, counts, 0);
    }

private:
    void solveSudoku(int x, int y, vector<vector<char>> &result, int n, vector<vector<char>> &board, int counts, int cost)
    {
        if(counts == cost){
            cout << counts << "\t" << cost << endl;
        }
        if (cost == counts)
        {
            board = result;
        }
        if (x >= n || y >= n)
        {
            return;
        }
        for (int i = 1; i < 10; i++)
        {
            if (result[x][y] == '.' && ifVaild(x, y, result, i, n))
            {
                result[x][y] = '0' + i;
                if (y == n - 1)
                {
                    solveSudoku(x + 1, 0, result, n, board, counts, cost + 1);
                }
                else
                {
                    solveSudoku(x, y + 1, result, n, board, counts, cost + 1);
                }
                result[x][y] = '.';
            }
            else if (result[x][y] != '.')
            {

                if (y == n - 1)
                {
                    i--;
                    x = x + 1;
                    if(x >= n){
                        return ;
                    }
                    y = 0;
                }
                else
                {
                    i--;
                    y++;
                    if(y >= n){
                        return ;
                    }
                }
            }
        }
    }

    bool ifVaild(int x, int y, vector<vector<char>> board, int input, int n)
    {
        for (int i = 0; i < n; i++)
        {
            if (board[x][i] == '0' + input)
            {
                return false;
            }
        }
        for (int j = 0; j < n; j++)
        {
            if (board[j][y] == '0' + input)
            {
                return false;
            }
        }
        int minX = x / 3, minY = y / 3;
        for (int i = 3 * minX; i < 3 * minX + 3; i++)
        {
            for (int j = 3 * minY; j < 3 * minY + 3; j++)
            {
                if (board[i][j] == '0' + input){
                    return false;
                }
            }
        }
        return true;
    }
};