1.字母大小写全排列784. 字母大小写全排列 - 力扣LeetCodehttps://leetcode.cn/problems/letter-case-permutation/description/如a 1 B 2如果原来是小写字母可以选择不变或把它变成一个大写字母如果是大写字母也有两种选择数字字符直接无视。所以开始后如果碰到字母可以选择变或不变遇到数字没有分支就一条路再遇到B一样两种选择最后也一样对树做一次深度优先遍历叶子结点那统计结果就行。下面实现2.优美的排列526. 优美的排列 - 力扣LeetCodehttps://leetcode.cn/problems/beautiful-arrangement/description/如n3相当于我们此时有1 2 3这三个数字把3个数填_ _ _三个格子哪种填法能让这格子是优美的排列。开始后第一个位置可填1、2、3填之前看看要么填的数能整除下标要么下标能整除填的数这都可以。第一个填完基础上依旧可填1、2、3选过的数剪了其余判断每一层是把数组中的数从头到尾枚举一遍只要这个数没用过就放到对应格子上试一试。下面实现3.N皇后51. N 皇后 - 力扣LeetCodehttps://leetcode.cn/problems/n-queens/description/如N3每次考虑时只考虑一行考虑第0行皇后放哪里第1行皇后放哪里第2行皇后放哪里。开始时是拿着一个空盘子首先考虑第一行可以放哪里这样有三种情况接下来考虑第2行第2行依旧有3种情况这里出现了减枝情况因为有皇后互相攻击。然后考虑最后一行依旧3种情况发现每一层干的事情是告诉我一个行数就把这一行每个格子尝试放一个皇后如果能放就放好后去考虑下一行。当行数越界时说明收集了一个合法情况把合法情况加入到结果中就可以了。那如何剪枝呢考虑当前这个位置能否放上皇后1.无脑循环考虑当前这个位置能不能放时我无脑来4个循环分别循环4个位置看能不能放(时间复杂度高)。2.类似哈希表的策略判断某一列是否有皇后时弄个bool类型数组比如第0列某个位置放过皇后时让col[0]为true就行当考虑?位置时看col[0]是否为true就行为true说明有一个皇后就不考虑该位置了。对角线怎么考虑主对角线写公式是yxb所以y-xb。比如红色对角线上的点纵坐标减横坐标是个定值所以再弄个bool类型数组bool dig1[2*N](h的范围)考虑一个点时当y-x是true证明对角线里有皇后。但y-x 可能是负数数组下标没负数所以左右添个偏移量y-xnbn统一向上平移n个单位。再考虑负对角线y-xbxyb再弄个bool dig2[2*N]这里没有越界情况。下面来实现(ret里放的是一个个棋盘path里某一个成立棋盘可先把path初始化一下里面都放上点)4.有效的数独36. 有效的数独 - 力扣LeetCodehttps://leetcode.cn/problems/valid-sudoku/description/先搞定行和列判断一行有没有出现重复的元素前弄个哈西表弄个bool类型数组大小为9row[9]仅存一个值不够要看里面有没有出现重复数字得再多开个空间bool row[9][10]其中row[2][4]表示第2行是否出现了4。同理判断列时弄个bool col[9][10]其中col[7][9]表示第7列是否存在9这个数true表示存在false表示不存在。行和列就解决了下面来弄一下3×3方格我们也可以利用哈希表让画的那一坨当成下标0 1 2先弄一个grid[3][3]其中grid[0][0]表示第一个小方格依次类推这样用bool grid[3][3]可把所有小方格表示出来。然后我依旧要看小方格中是否所有数出现过因此弄个bool grid[3][3][10]随便找个位置想确定在哪个九宫格的话直接拿下标除3[x/3][y/3]就可找到在哪个小方格里面。所以弄了个bool类型数组可再O(1)内检查这一行、一列、小方格中有没有出现重复的数这里典型的用空间代替时间。下面来实现5.解数独37. 解数独 - 力扣LeetCodehttps://leetcode.cn/problems/sudoku-solver/description/刚开始时只拿到一个棋盘遍历一下棋盘有空位置时就往上填数直到格子填完就拿到结果了。开始便利后遇到第一个空格其实有9个分支但有一些情况肯定要剪了。因此填之前先判断一下填的数合不合适剪完后有这样一些情况其实现在就可以总结出递归在干什么拿到棋盘时开始遍历扫描哪个格子是空的就填填时判断一下但递归下去可能会出现得不到有效分支情况有一个格子1~9全都填不了就向上返回false表示第三个位置填1递归下来有问题要换个数重新试所以dfs是有返回值的参数把棋盘传下去。下面实现(board里开始有数要先统计到哈西表里1~9都没有说明决策是错误的最后两层结束填完了也返回true)6.单词搜索79. 单词搜索 - 力扣LeetCodehttps://leetcode.cn/problems/word-search/description/比如是这样在矩阵中依次找到ABCDE首先找到A从矩阵每行挨着扫当匹配到第一个字符时就从这个字符开始依次匹配BCDE找到A后从这个A开始上下左右匹配B发现并没有字符B说明这是个失败尝试。继续试当扫到第二行时又找到了A开始后有两条路径可以找到B先走下面的B然后开始匹配C这个字符从这个B开始上下左右没有字符C所以是错误尝试返回后走左右边的B。找到B后匹配C找到C后匹配DD也有2条路径那就一个个试。走到下面不能匹配E是个错误尝试那就去右边D找匹配找到E说明此时是个合法路径。这可抽象为深度优先遍历开始后有两种选择要么走(02)这个A要么走(10)这个A。(0,2)这没有分支匹配不到B(1,0)这有两个分支要么走到(2,0)这个位置要么走到(1,1)这个位置(2,0)匹配不到c没分支了(1,1)这有一个分支(1,2)。(1,2)有两个分支(2,2)和(1,3)(2,2)没有有分支(1,3)有分支(0,3)此时走到头了。我们就是对决策树进行深度遍历失败了没有关系向上回溯就行。那dfs怎么设计看每一层干嘛每个节点在从这个节点开始尝试匹配下一个字符(上下左右)所以dfs参数里要有表格和节点位置从节点位置开始上下左右匹配pos位置的字符:走某条路时可能失败上面调用要知道成功还是失败了所以返回值类型是bool。这里有个二维矩阵搜索中经常要注意的细节不能走重复的路。如第一个A找右边A右边A找左边A左边A又会找第一个A。1.所以弄个bool型的和原始矩阵同等规模的数组bool vist[][]用它来标记当前位置是否被用过。比如第一个A开始把它标为true走到第二个A时上下左右考虑时看是否被标记标记过不考虑。2.修改原始矩阵的值比如从第一个A走到第二个A时把第一个A修改为点(不推荐)。下面来实现匹配的地方可以传4次函数寻找还可用向量方式定义上下左右四个位置要匹配的位置单看i要么不变要么1-1所以弄个数组int dx[4]{0,0,1,-1}同理j也是int dy[4]{-1,1,0,0}凑一起使用也就是dx[0]dy[0]就是让i0, j-1这样7.黄金矿工1219. 黄金矿工 - 力扣LeetCodehttps://leetcode.cn/problems/path-with-maximum-gold/description/如找一个路径使这个路径上所有元素和最大其中0位置不能选过的位置不能选。可以一行行扫描扫到非0位置的时候就以该位置为起点来一次深度优先遍历从6开始上下左右只能走下面从8开始有三种走法可以把三种情况都搜一遍。先走5发现没地方走了此时找到685。回到8后走到7不能走了找到687后返回到8。往下走走到9找到689这样以6为切入点的所有情况都枚举到了此时最长的是689。但算法不要停还可以以其他位置为起点重复上面过程。下面来实现7.不同路径III980. 不同路径 III - 力扣LeetCodehttps://leetcode.cn/problems/unique-paths-iii/description/如图目的是从1走到2把所有合法路径统计出来就行。先扫描一下数组找到起始位置然后从起始位置开始深度优先遍历。不管怎么走只要走到2判断一下这条路径是否合法就行了。怎么判断用count变量记录行走步数当走到2的时候看看count和实际step是否一样。合法就记录不合法就重新搜。下面实现