代码随想录算法训练营第三十天 | 332.重新安排行程，51. N皇后，37. 解数独

在这里插入图片描述

在这里插入图片描述
这道题是一道欧拉路径/ 欧拉回路的一笔画问题，需要找出开销最小的一笔画方案

这种一笔画的问题，以前学数据结构的时候我们习惯把图放进二维数组中存储，但对于这种无规律的图结构，我们可以使用二维的哈希表来存储，这样可以方便的记录下每个节点的邻接节点和访问情况，相当于一次完成了二维数组中存储时的graph和visit二维数组 本处使用的存储结构为unordered_map<string,map<string,int>>

unordered_map的key是起点，作为value的map存储邻接节点和节点当前的可用计数
使用map主要是可以做一个自动的字典序节点排序（红黑树）

本题使用回溯法来解答，其实就是一个每层节点按照字典排序的DFS，有点小贪心的思路在里面

class Solution {
public:
    vector<string> res;
    unordered_map<string,map<string,int>> ticketMap;
    void resInit(vector<vector<string>>& tickets){
        ticketMap.clear();
        for(auto i : tickets){
           ticketMap[i[0]][i[1]]++;
        }

        res.push_back("JFK");
    }
    bool DFS(vector<vector<string>>& tickets,int ticketNum){
         if(ticketNum == tickets.size()){
            return true;
         }

         for(pair<const string,int> & des : ticketMap[res[res.size()-1]]){
                if(des.second > 0){
                    res.push_back(des.first);
                    des.second--;
                    if(DFS(tickets,ticketNum+1)) return true;
                    res.pop_back();
                    des.second++;
                }
         }
         return false;
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
         resInit(tickets);
         DFS(tickets,0);
         return res;
    }
};

在这里插入图片描述

经典N皇后问题，看起来像是一个二维的递归问题，其实不是（或者说是一个在某一维度受限的二维递归），因为它每一层只需要考虑一个位置放皇后，然后就可以继续向下考虑了，所以说，他的选择列表不是二维的

class Solution {
public:
    vector<vector<string>> res;
    vector<vector<bool>> resMatrix;
    vector<string> resVec;
    void resInit(int & n){
        for(int i = 0;i< n;i++){
            vector<bool> resBool(n,false);
            resMatrix.push_back(resBool);
        }
    }
    bool isValid(vector<vector<bool>> resMatrix,int &n,int line,int row){
        for(int i = line;i>= 0;i--){
           if(resMatrix[i][row]){
              return false;
           }
           if(row + (line - i) < n && resMatrix[i][row + (line - i)]){
              return false;
           }
           if(row - (line - i) >=0 && resMatrix[i][row - (line - i)]){
              return false;
           }
        }
        return true;
    }
    void traceback( vector<string> resVec,int & n,int line,vector<vector<bool>> resMatrix){
         if(resVec.size() == n || line > n){
            res.push_back(resVec);
            return;
         }
         for(int i = 0;i< n;i++){
            if(!isValid(resMatrix,n,line,i)){
               continue;
            }
            string s = "";
            for(int j = 0;j < n;j++){
               if(j == i){
                  s.push_back('Q');
               }else{
                s.push_back('.');
               }              
            }
            resVec.push_back(s);
            resMatrix[line][i] = true;
            traceback(resVec,n,line+1,resMatrix);
            resMatrix[line][i] = false;
            resVec.pop_back();
         }
    }
    vector<vector<string>> solveNQueens(int n) {
             resInit(n);
             traceback(resVec,n,0,resMatrix);
             return res;
    }
};

在这里插入图片描述

class Solution {
public:
    void resInit();
    bool isValid(vector<vector<char>>& board,int &i,int &j,char &c){
         for(int row = 0;row< board[0].size();row++){
            if((board[i][row]) == c){
                return false;
            }
         }
          for(int line = 0;line< board.size();line++){
            if((board[line][j]) == c){
                return false;
            }
         }

         int startX = (i / 3) * 3;
         int startY = (j / 3) * 3;
         for(int xIdx = startX;xIdx< startX+3;xIdx++){
             for(int yIdx = startY;yIdx< startY+3;yIdx++){
                 if(board[xIdx][yIdx] == c){
                     return false;
                 }
             }
         }
         return true;
    }
    bool traceback(vector<vector<char>>& board){
        for(int i = 0;i< board.size();i++){
            for(int j = 0;j< board[0].size();j++){
               if(board[i][j] != '.'){
                  continue;
               }

               for(char c = '1';c<= '9';c++){
                  if(!isValid(board,i,j,c)){
                      continue;
                  }
                  board[i][j] = c;
                  if(traceback(board)){
                    return true;
                  }
                  board[i][j] = '.';
               }
               return false;
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
        traceback(board);
    }
};