南昌天和建设有限公司网站,传媒公司官网,后端开发是什么,长沙网络开发公司一)字母大小写全排列 784. 字母大小写全排列 - 力扣#xff08;LeetCode#xff09; 1)从每一个字符开始进行枚举#xff0c;如果枚举的是一个数字字符#xff0c;直接忽视 如果是字母的话#xff0c;进行选择是变还是不变 2)当进行遍历到叶子结点的时候#xff0c;直接将… 一)字母大小写全排列 784. 字母大小写全排列 - 力扣LeetCode 1)从每一个字符开始进行枚举如果枚举的是一个数字字符直接忽视 如果是字母的话进行选择是变还是不变 2)当进行遍历到叶子结点的时候直接将结果存放到ret里面即可 3)相对于是对于这个决策树做一个深度优先遍历 class Solution {ListString retnew ArrayList();StringBuilder pathnew StringBuilder();public ListString letterCasePermutation(String s) {char[] arrays.toCharArray();dfs(array,0);return ret;}public void dfs(char[] array,int index){if(path.length()array.length){ret.add(path.toString());return;}if(indexarray.length) return;//选if(array[index]0array[index]9){path.append(array[index]);dfs(array,index1);path.deleteCharAt(path.length()-1);}else{path.append(array[index]);dfs(array,index1);path.deleteCharAt(path.length()-1);if(array[index]aarray[index]z)path.append((char)(array[index]-32));elsepath.append((char)(array[index]32));dfs(array,index1);path.deleteCharAt(path.length()-1);}}
} 二)优美的排列 526. 优美的排列 - 力扣LeetCode 1)每一层开始就是从第一个数开始将所有的数进行枚举一遍只要这个数没有使用过就可以把这个数放在这里面试一试 2)还是需要判断一下这个数能否整除下标或者是能够被下标整除只要上面的条件有一种情况不满足那么就进行剪枝操作 3)函数的递归出口:当遇到叶子节点的时候直接返回结果 class Solution {ListListInteger retnew ArrayList();ListInteger pathnew ArrayList();boolean[] check;public int countArrangement(int n) {checknew boolean[n1];dfs(n,1);return ret.size();}public void dfs(int n,int pos){if(path.size()n){ret.add(new ArrayList(path));return;}for(int i1;in;i){if((i%pos0||pos%i0)check[i]false){path.add(i);check[i]true;dfs(n,pos1);path.remove(path.size()-1);check[i]false;}}}
} 三)N皇后: 51. N 皇后 - 力扣LeetCode 第一种画决策树的方法: 先考虑第一个格子能不能进行存放当进行考虑下一个格子的时候是进行挨着考虑的一个格子一个格子看看能不能进行存放 第二种画决策树的方法:是通过一行一行的来进行考虑的 此时我不是一个格子一个格子的进行考虑这一次我一次考虑一行我只考虑第0行的皇后应该摆放在那里应该只考虑第一行的皇后摆放在哪里第二行的皇后应该摆放在那里第三行的皇后应该摆放在那里下面我们进行考虑一下当N3的时候: 1)首先我们第一步应该考虑一下第0行的皇后可以放在哪里这个时候又出现三种情况可以放在(00)可以放在(01)还可以放在(02) 2)然后再次进行考虑当我们第0行的三个皇后已经放好的情况下那么此时再来进行考虑第一行正常情况下如果不出现剪枝的情况第一行也是可以存放三个位置的分别是(10)(11)和(12)但是此时考虑剪枝这个时候就出现了某一个行上面有两个皇后对角线上面有两个皇后 每一层在做的事情:你给我一个行数我在这一行内每一个格子存放一个皇后如果我能够存放我就把这个皇后放在这里没然后进行考虑下一行 递归出口:当我们枚举行数发生越界的时候此时说明就已经得到了合法的情况此时就可以把这个合法的情况加入到我们最终的结果中即可 如何剪枝:剪枝的目的就是考虑当前这个位置是否可以能够放上皇后 1)无脑循环:假设当前这个这个位置可以存放皇后首先来判断这一行有没有放皇后这一列有没有放皇后这个皇后的左对角线有没有放皇后这个皇后的右对角线有没有放皇后时间复杂度是4n*2^n 在这种决策树的画法里面我们是每一行每一行的来进行列举的所以当我们进行列举这一行上面的三个位置的时候是一定不会出现在这一行上面的 2)类似于哈希表的策略:在这里面只是需要搞一个boolean数组就可以搞定这个题了 boolean checkcol[]new boolean[n]如果在第一列上放了一个皇后那么只是需要让这一列变成true即可那么就是checkcol[1]true说明这一列已经有皇后了所以使用布尔数组可以快速判断某一列是否有皇后了 3)判断对角线以及副对角线的策略:使用布尔数组数学来进行解决 四)有效的数独: 36. 有效的数独 - 力扣LeetCode
