8.30 leetcode刷题（2）

递归和回溯：
17 电话号码

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        string letters[10] = { "", "",
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz" };
        ret.clear();
        if (digits.size() == 0)
            return ret;
        getLetters(digits, 0, "", letters);
        return ret;
    }
private:

    vector<string> ret;
    void getLetters(string &digits, int index, const string temp, string letters[]){
        if (index == digits.size()){
            cout << "push: " << temp << endl;
            ret.push_back(temp);
            return;
        }

        int dig = digits[index] - '0';
        string letter = letters[dig];
        int n = letter.size();
        for (int i = 0; i<n; i++){
            char ch = letter[i];
            cout << "recurse: " << digits[index + 1] << endl;
            getLetters(digits, index + 1, temp + ch, letters);
        }
        if (n == 0)
            getLetters(digits, index + 1, temp, letters);
    };
};

思路：
运用递归去实现回溯算法的思想。
回溯算法本质上是一种暴力搜索，通过递归调用去实现，回溯思想与深度搜索思想一致。
对于本题，解法设计思路：
首先定义一个查找表去映射数字和字母之间的关系。
之后运用回溯的算法思想，通过递归去设计，解题思路可以通过画一个树形图来梳理，每次取出digits中的一个元素，然后分别讨论每一种选择（for循环选中每一次选择），然后递归。
与广度优先搜索的区别是深搜是一条路跑到黑的，除非找到最后，否则回一直找下去。
最后添加一个if是为了处理取数字1的时候字符串为空的情况，不实现这部分leetcode上也可以通过，但是输入“12”的话不会返回“abc”，因为此时没有进入递归

另外就是cpp不支持类中的变量初始化定义,所以把letters其做成了一个参数

---

练习：93 131

---

46 全排列

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        int n=nums.size();
        ret.clear();
        if(n==0)
            return ret;
        used=vector<bool>(n+1,false);
        vector<int> temp;
        getPermute(nums,used,temp);
        return ret;
    };
private:
    vector<vector<int>> ret;
    vector<bool> used;
    void getPermute(vector<int> &nums,vector<bool> &used,vector<int> &temp){
        if(temp.size()==nums.size()){
            ret.push_back(temp);
            return ;
        }
        
        int n=nums.size();
        for(int i=0;i<n;i++){
            if(used[i]==false){
                used[i]=true;
                temp.push_back(nums[i]);
                getPermute(nums,used,temp);
                temp.pop_back();
                used[i]=false;
            }
        }
    }
};

思路：
利用回溯法：
先画一个树形图，来判断需要用到哪些状态变量去控制。
通过画树形图，可以知道，首先我们要判断当前选择的元素之前有没有使用过，因此需要used集合来记录状态。每一次选择后再之后便不再选择，因此在递归调用的时候需要使用if语句进行判断。

---

练习：47

---

77 组合

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        ret.clear();
        if(n==0)
            return ret;
        vector<int > temp;
        getCombine(n,1,k,temp);
        return ret;
    };
private:
    vector<vector<int>> ret;
    void getCombine(int n,int index,int k,vector<int> &temp){
        //找到了一个组合，将其记录下来，退出递归
        if(temp.size()==k){
            ret.push_back(temp);
            return;
        }
        //递归已经达到了边界，依然没有找到组合，直接退出递归，其实不写也没事
        if(index==n+1)
            return;
        //每一层的选项，从index开始依次往后选，index前面的不用再考虑了，否则会有重复,另外i<=n可以优化为n-i+1>=k-temp.size()，进行剪枝操作，提高算法效率
        for(int i=index;i<=n;i++){
            temp.push_back(i);
            getCombine(n,i+1,k,temp);
            temp.pop_back();
        }
    }
};

思路：
利用回溯法：

1. 画树形图，找出需要辅助实现算法的变量，每一层的选项，递归关系，终止条件
2. 关键点已在代码中进行了注释

---

练习：39 40 216 78 90 401

---

二维平面上的回溯法：
79 搜索单词
错误代码，没有检查出哪里错误，会超时

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        row=board.size();
        if(row==0)
            return false;
        col=board[0].size();
        if(col==0)
            return false;
        
        used=vector<vector<bool>>(row,vector<bool>(col,false));
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++){
                if(getRet(board,word,0,i,j))
                    return true;
            }
        
        return false;
    }
private:
    int row,col;
    vector<vector<bool>> used;
    bool inArea(int x,int y){
        return x>=0 && x<=row-1 && y>=0 && y<=col-1;
    }
    bool getRet(vector<vector<char>> &board,string &word,int index,int x,int y){
        if(index==word.size()-1)            
            {
            cout<<"return final: "<<word[index]<<"=="<<board[x][y]<<endl;
            return word[index]==board[x][y];}
        if(word[index]!=board[x][y])
          {
            cout<<"return interrput: "<<index<<" pos:"<<x<<","<<y<<" "<<word[index]<<"!="<<board[x][y]<<endl;
            return false;}
        if(index==0)
            cout<<"start as "<<x<<","<<y<<endl;
        used[x][y]=true; 
        cout<<"pos:"<<x<<","<<y<<"  target:"<<word[index]<<"  cur:"<<board[x][y]<<endl;
        
        
        if(inArea(x,y-1) && used[x][y-1]==false && getRet(board,word,index+1,x,y-1))
            return true;
        
        if(inArea(x,y+1) && used[x][y+1]==false && getRet(board,word,index+1,x,y+1))           
            return true;
        if(inArea(x-1,y) && used[x-1][y]==false && getRet(board,word,index+1,x-1,y))
            return true;
        if(inArea(x+1,y) && used[x+1][y]==false && getRet(board,word,index+1,x+1,y)) 
            return true;
        used[x][y]=false;
       return false;
    }
};

正确代码

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        m=board.size();
        
        if(m==0)
            return false;
        n=board[0].size();
        used=vector<vector<bool>>(m,vector<bool>(n,false));
        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j){
                if(search(board,word,0,i,j))
                    return true;
            }
        
        return false;
    }
    
private:
    int m,n;
    vector<vector<bool>> used;
    bool inArea(int x,int y){
        return x>=0 && x<m && y>=0 && y<n;
    };
    int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
    bool search(vector<vector<char>> &board,string &word,int index,int posX,int posY){
        if(index+1==word.size())
            return board[posX][posY]==word[index];
        
        if(board[posX][posY]==word[index]){
            used[posX][posY]=true;
            for(int i=0;i<4;++i){
                int newX=posX+d[i][0];
                int newY=posY+d[i][1]; 
                if(inArea(newX,newY)==false || used[newX][newY]==true)
                    continue;
                if(search(board,word,index+1,newX,newY))
                        return true;                          
                                
            }
            used[posX][posY]=false;
        }
        
        return false;
    }
};

思路：
二维平面采用回溯算法利用一个二维数组即可，一般来讲需要判断边界
本题解题思路：
先设计一个函数getWord，用来判断board从x，y开始，是否有匹配word从index开始算起的单词。
之后通过双重循环去遍历二维平面，考虑每一个点作为起点的情况。
getWord的设计思路：
采用递归来设计，或者说回溯的算法思想，回溯的算法思想可以分为2部分，1部分是递归，1部分是复原状态遍历，因为回溯就是回滚状态，每深搜完一个路径往回回溯的时候状态也要回滚。
递归的话要有终止条件和递归过程。
首先我们可以画一个树形图，去整体上查看递归的调用链。
通过画图可以明确，我们需要判断边界，需要记录要探索的点是否已被访问过，需要判断当前点是否符合要求，终止条件是index达到最后word的最大下标的时候。
getWord流程：
先判是不是达到终止条件，是则返回
再判当前点是否符合要求，不符合则返回
当前点符合要求，那么记录访问状态，开始递归相邻点（共4种情况，需要考虑边界约束和访问约束，对符合条件的相邻点进行深搜递归，），若有1个符合要求，即可返回true
遍历完所有相邻节点后若都不符合，则回复访问状态，返回false（进行回溯）

---

200 岛屿数量
思路：

1. dfs
2. 回溯法，利用深度优先搜索进行遍历并标记，最后统计

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        row=grid.size();
        if(row==0)
            return 0;
        col=grid[0].size();
        if(col==0)
            return 0;
        int ret=0;
        
        vector<vector<bool>> used=vector<vector<bool>>(row,vector<bool>(col,false));
        
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(used[i][j]==false && grid[i][j]=='1'){
                    dfs(grid,i,j,used);                    
                    ret++;
                }
            }
        }
        
        return ret;
    }
private: 
    int row,col;
    vector<vector<bool>> used;
    bool isContain(int x,int y){
        return x>=0 && x<row && y>=0 && y<col;
    }
    
    void dfs(vector<vector<char>> &grid,int x,int y,vector<vector<bool>> &used){
        used[x][y]=true;
        
        int d[4][2]={
            {0,1},
            {0,-1},
            {1,0},
            {-1,0}
        };
        
        for(int i=0;i<4;i++){
            int newX=d[i][0];
            int newY=d[i][1];
            newX+=x;
            newY+=y;
            if(isContain(newX,newY) && used[newX][newY]==false && grid[newX][newY]=='1')
                dfs(grid,newX,newY,used);
        }
        
    };
};

代码解释：

1. 首先主函数通过调用dfs来标记岛屿
2. 写了2个子函数，isContain用来判断是否坐标越界，dfs用来使用深度优先搜索遍历整片岛屿并标记
3. 主函数开始遍历整个grid，一旦发现代表岛屿的格子‘1’，就利用dfs遍历整片岛屿并标记（遍历条件，未越界，之前未访问过，‘1’，），然后计数（ret++）

经验：

1. 编写算法可以主函数、子函数交替进行，这样逻辑更加清晰。
2. 注意数据类型，比如本题grid存的是char，若写代码时忘记加单引号，会出bug，得不到正确的结果

---

练习 130 417

---

51 八皇后

思路：

1. 找到判断条件（同行、同列，主对角线，副对角线的判定方式）
2. 回溯法（dfs，去遍历各种组合）

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        ret.clear();
        div=vector<bool>(2*n,false);
        ndiv=vector<bool>(2*n,false);
        col=vector<bool>(n,false);
        m=n;
        vector<string> temp;
        string line;
        for(int i=0;i<m;i++)
            line.push_back('.');
        for(int i=0;i<m;i++)
            temp.push_back(line);
        pos(0,temp);
        return ret;
    };
private:
    vector<vector<string>> ret;
    vector<bool> div,ndiv,col;
    int m;
    void pos(int row,vector<string> &temp){
        if(row==m){
            ret.push_back(temp);
            return; 
        }
        
        for(int i=0;i<m;i++){
            if(div[row+i]==false && ndiv[i-row+m]==false && col[i]==false){
                div[row+i]=true;
                ndiv[i-row+m]=true;
                col[i]=true;
                temp[row][i]='Q';
                pos(row+1,temp);
                temp[row][i]='.';
                col[i]=false;
                ndiv[i-row+m]=false;
                div[row+i]=false;
            }
        }
    }
};

代码设计详解：

1. 已经决定使用回溯法去解决该问题，回溯法其实就是dfs，分支是下一步的备选方案，每次会从根节点到叶子节点处递归一条路径
2. 通过div，ndiv，col来判断当前位置是否与已放置棋子的地方有冲突（分别判断主对角线，副对角线，列），行不用判断是因为每次都放的是不同行，一定不会冲突。
3. 注意递归调用下一步时进行状态更新，回溯时记得恢复状态。另外就是递归思路的设计，设计好退出条件。

---

练习 52 37

---