[C++ Code] Arrange itinerary, N Queen, Solve Sudoku – Code Random Notes

Title: Rearrange itinerary

Give you a list of routes tickets, where tickets[i] = [fromi, toi] represents the airport locations where the plane departs and lands. Please re-schedule this itinerary. All of these tickets belong to a gentleman traveling from JFK (JFK International Airport), so the trip must start at JFK. If there are multiple valid itineraries, please sort them lexicographically to return the smallest itinerary combination. All of these tickets belong to a gentleman traveling from JFK (JFK International Airport), so the trip must start at JFK. If there are multiple valid itineraries, please sort them lexicographically to return the smallest itinerary combination.
For example, the itinerary ["JFK", "LGA"] is smaller than ["JFK", "LGB"]. Sort higher. It is assumed that there is at least one reasonable itinerary for all tickets. All tickets must be used once and can only be used once.
There are several difficulties with this question:
- If the flight is not handled well during a trip, it can easily turn into a circle and an infinite loop.
- There are many solutions. The alphabetical order is first, which makes many students retreat. How to record the mapping relationship?
- If you use the backtracking method (you can also say deep search), what is the termination condition?
- During the search process, how to traverse all airports corresponding to an airport.
One airport maps multiple airports, and the airports must be arranged in alphabetical order. If one airport maps multiple airports, you can use std::unordered_map. If you want to have an order between multiple airports, use std::map or std ::multimap or std::multiset. The mapping relationship stored in this way can be defined as unordered_map> targets or unordered_map> targets.
- unordered_map targets: unordered_map targets; unordered_map> targets: unordered_map> targets
- Of these two structures, I chose the latter, because if you use unordered_map> targets when traversing the multiset, you cannot delete elements. Once the element is deleted, the iterator will become invalid. **The departure airport and arrival airport will be repeated, and the search process will be an endless loop if the destination airport is not deleted in time. **So during the search process, elements in the multiset must be continuously deleted, so it is recommended to use unordered_map> targets.
- In the process of traversing unordered_map> targets, you can use the number in the “number of flights” field to increase or decrease accordingly to mark Have you used it upon arrival at the airport? **If the “number of flights” is greater than zero, it means that the destination can still be flown. If the “number of flights” is equal to zero, it means that the destination cannot be flown. There is no need to delete elements or add elements to the collection.

class Solution {
public:
    // unordered_map<departure airport, map<arrival airport, number of flights>> targets
    unordered_map<string,map<string,int>> targets;
    bool track(int ticNUM,vector<string> & amp;res){
        if(res.size()==ticNUM + 1){//ticketNum is also required in the parameter, indicating how many flights there are (the termination condition will be used).
            return true;
        }
        // Be sure to add a reference, that is, & amp; target, because target.second will be subtracted later. If there is no reference and simple copying, the result will not be recorded, and the final result will be wrong.
        for(pair<const string,int> & amp; target:targets[res[res.size()-1]]){
            if(target.second>0){ // Record whether the arrival airport has been flown by
                res.push_back(target.first);
                target.second--;
                if(track(ticNUM,res)) return true;
                res.pop_back();
                target.second + + ;
            }
        }
        return false;
    }
    vector<string> findItinerary(vector<vector<string>> & amp; tickets) {
        targets.clear();
        vector<string> res;
        for(const vector<string> & amp; vec : tickets){
            targets[vec[0]][vec[1]] + + ;
        }
        res.push_back("JFK");
        track(tickets.size(),res);
        return res;
    }
};

Title: N Queen

According to the rules of chess, a queen can attack a piece on the same row or column or on the same diagonal. The n queen problem studies how to place n queens on a n×n chessboard so that the queens cannot attack each other. . Given an integer n, return all the different solutions to the n Queens Problem. Each solution consists of a different chess placement scheme for the n Queens Problem, in which 'Q' and '.' represent the queen and the empty seat respectively.
After determining the constraints, let’s see how to search for the positions of the queens. In fact, searching for the positions of the queens can be abstracted into a tree.
From the figure, it can be seen that the height of the matrix in the two-dimensional matrix is the height of the tree, and the width of the matrix is the width of each node in the tree structure. Then we use the constraints of the queens to backtrack and search the tree. As long as the leaf nodes of the tree are searched, it means that the reasonable positions of the queens have been found.

class Solution {<!-- -->
public:
    vector<vector<string>> res;
    bool isV(int row,int col,vector<string> & amp; board,int n){<!-- -->
        for(int i=0;i<row;i + + ){<!-- -->//Check column
            if(board[i][col]=='Q') return false;
        }
        for(int i=row-1,j=col-1;i>=0 & amp; & amp;j>=0;i--,j--){<!-- -->
            if(board[i][j]=='Q') return false;
        }
        for(int i=row-1,j=col + 1;i>=0 & amp; & amp;j<n;i--,j + + )
            if(board[i][j]=='Q') return false;
        return true;
    }
    void track(int n,int start,vector<string> & amp; board){<!-- -->
        if(start==n){<!-- -->
            res.push_back(board);
            return ;
        }
        for(int i=0;i<n;i + + ){<!-- -->
            if(isV(start,i,board,n)){<!-- -->
                board[start][i]='Q';
                track(n,start + 1,board);
                board[start][i]='.';
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {<!-- -->
        res.clear();
        vector<string> chessboard(n,string(n,'.'));
        track(n,0,chessboard);
        return res;
    }
};

Topic: Solving Sudoku

Write a program to solve Sudoku problems by filling in the blank spaces. Some of the spaces in the Sudoku have been filled in with numbers, and the blank spaces are represented by '.'. The solution to Sudoku needs to follow the following rules:
- The numbers 1-9 can only appear once per line.
- The numbers 1-9 can only appear once in each column.
- The numbers 1-9 can only appear once in each 3x3 palace separated by a thick solid line. (please refer to the example picture)
In this question, a number must be placed in each position of the chessboard (and Queen N only places one queen in a row), and check whether the number is legal. The tree structure of the Sudoku solution is wider and deeper than Queen N . Retrospective trilogy
- Recursive function and parameters: **The return value of the recursive function needs to be of bool type, **because solving the Sudoku will return immediately if it finds a matching condition (on the leaf node of the tree), which is equivalent to finding a line from the root node to the leaf node. The only path, so you need to use bool return value.
- Recursion termination condition: There is no termination condition for recursion in this question. To solve Sudoku, you need to traverse the entire tree structure to find possible leaf nodes and return immediately. The chessboard at the next level of recursion must have one more number than the chessboard at the previous level. When the chessboard is filled with numbers, it will naturally terminate (of course it will be filled, which means the result has been found), so there is no need for a termination condition!
- Recursive single-level search logic: It can be seen from the tree diagram that what we need is a two-dimensional recursion (that is, two for loops nested with recursion);A for loop traverses the rows of the chessboard, and a for loop Traverse the columns of the chessboard. After determining each row and column, recursively traverse the possibility of placing 9 numbers in this position!

class Solution {<!-- -->
public:
    bool track(vector<vector<char>> & amp; board){<!-- -->
        for(int i=0;i<board.size();i + + ){<!-- -->
            for(int j=0;j<board[0].size();j + + ){<!-- -->
                if(board[i][j]=='.'){<!-- -->
                    for(char k='1';k<='9';k + + ){<!-- -->
                        if(isV(i,j,k,board)){<!-- -->
                            board[i][j]=k;
                            if(track(board)) return true;
                            board[i][j]='.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    bool isV(int row,int col,char k,vector<vector<char>> & amp; chessboard){<!-- -->
        for(int i=0;i<9;i + + ){<!-- -->
            if(chessboard[row][i]==k || chessboard[i][col]==k) return false;
        }
        int startR = (row/3)*3;
        int startC = (col/3)*3;
        for(int i=startR;i<startR + 3;i + + ){<!-- -->
            for(int j=startC;j<startC + 3;j + + ){<!-- -->
                if(chessboard[i][j]==k) return false;
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>> & amp; board) {<!-- -->
        track(board);
    }
};

Backtracking is a by-product of recursion. As long as there is recursion, there will be backtracking, so the backtracking method is often mixed with binary tree traversal and depth-first search, because both methods use recursion. The backtracking method is a brute force search and is not an efficient algorithm. At best, it needs to be pruned.
The backtracking algorithm can solve the following problems:
- Combination problem: Find the set of k numbers among N numbers according to certain rules
- Arrangement problem: N numbers are all arranged according to certain rules. There are several ways to arrange them.
- Cutting problem: There are several ways to cut a string according to certain rules.
- Subset problem: How many qualified subsets are there in a set of N numbers?
- Chess board problems: N queens, solving Sudoku and more
The backtracking method is indeed difficult to understand, so it is much easier to understand the backtracking method by abstracting it into a graph.In each subsequent backtracking method question, I will abstract the traversal process into a tree structure to facilitate everyone’s understanding /strong>.

Subset problem analysis:

time complexity:
O

(

2

n

)

O(2^n )

O(2n), because the status of each element is nothing more than taking or not taking, collecting the nodes of the tree

Space complexity: O(n), the recursion depth is n, so the space used by the system stack is O(n), and the space used by each level of recursion is a constant level. Note that the result and path in the code are global variables, even if It is placed in the parameter, it is also passed by reference, and no new memory space is allocated. The final space complexity is O(n)

Arrangement problem analysis:

Time complexity: O(n!). This can be clearly seen from the arranged tree diagram. There are n nodes in each layer. Each branch in the second layer extends n-1 branches, and further down. There are n-2 branches, so the total up to the leaf node is n * n-1 * n-2 * … 1 = n!.

Space complexity: O(n), the same as the subset problem.

Combination problem analysis:

time complexity:
O

(

2

n

)

O(2^n)

O(2n), the combination problem is actually a subset problem, so the worst case scenario of the combination problem will not exceed the time complexity of the subset problem.
There are n-1 branches, and then there are n-2 branches, so the total up to the leaf nodes is n * n-1 * n-2 * … 1 = n!.

Space complexity: O(n), the same as the subset problem.