39. Combination Sum

39. Combination Sum

在dfs搜索题中,形象化一个dfs搜索树是一个非常有趣的,形象的描述方法。比如下面这个没有剪枝的dfs搜索树。也可以比较一下,下面两种解法的dfs搜索树的不同之处。

img

Read more

51. N-Queens

51. N-Queens

思路:

八皇后问题,经典问题。回溯解决。

代码:

class Solution {
public:
    
    void generate(vector<vector<string>> &outs, vector<int> &chess, vector<int> &hashorpos, int depth, int n){
        if(n == depth){
            
            vector<string> res(n, string(n, '.'));
            for(int i = 0; i < n; ++i){
                res[i].replace(chess[i], 1, "Q"); 
                //  cout << chess[i] << ' ' ;
            }
            // cout << endl;
            outs.emplace_back(res);
            return;
        }
    
        for(int i = 0; i < n; ++i){
            int flag = 1;
            if(!hashorpos[i]){
                #这部分判断代码可以优化,但是很麻烦,可以用hasverpos代表一层中被禁止的位置,需要标记左右方向,很麻烦。考虑到n的数量直接遍历就行,可以当做一个不变量。
                for(int j = 1; j <= depth ; ++j){
                    if(chess[depth - j] == i - j || chess[depth - j] == i + j){
                        flag = 0;
                        break;
                    }                                        
                }
                if(!flag) continue;

                chess[depth] = i;
                hashorpos[i] = 1;
                
                generate(outs, chess, hashorpos, depth + 1, n);
                                
                chess[depth] = -1;
                hashorpos[i] = 0;
                
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> outs;
        vector<int> chess(n, -1), hashorpos(n, 0);
        generate(outs, chess, hashorpos, 0, n);
        return outs;
    }
};

37.解数独

37 解数独 - 位运算 回溯

编写一个程序,通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则:

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。

Read more

面试题-回溯DFs

收集回溯相关题目

面13

面12和13很相似,不重复写了。

题面:

在一个字符矩阵中寻找一条路径,路径上的字符从头到尾排列起来是给定的字符串s。判断有无这么一条路径。

思路:

DFS或者说和回朔直接暴力搜。

代码:

bool hasPathCore(char *matrix, int rows, int cols, int row, int col, char *str, int strIdx, int &isFound){
    if(strIdx < 0){
        isFound = 1;
        return true;
    }
    if(isFound) return true;
    
    visited[row * cols + col] = 1;
    int dX[] = {0, 0, -1, 1}, dY[] = {-1, 1, 0, 0};
    for(int i = 0; i < 4; ++i){
		int nX = dX[i] + row, nY = dY[i] + col, p = row * cols + col;
        if( nX >= 0 && nY >= 0 && nX < rows && nY < cols && !visited[p] && str[strIdx] ==  matrix[p])
            hashPathCore(matrix, rows, cols, row, col, str, strIdx - 1);        
    }
}

bool hasPath(char *matrix, int rows, int cols, char *str, int length){
	if(str == nullptr || matrix == nullptr)
        throw new std::exception("Invalid parameters.");
    int visited = new int[rows * cols], isFound = 0;
    memset(visited, 0, sizeof(visited));
    for(int i = 0; i < rows; ++i)
        for(int j = 0; j < cols; ++j)
            if( hasPathCore(matrix, rows, cols, i, j, str, length - 1, isFound)){//倒着搜    
            	del[] visited;            
                return true;    
            }
}