网站大全免黄,酒业公司网站模板,wordpress模板汉化教程,dw制作家乡网页的步骤教程目录
17.电话号码的字母组合 77.组合
46.全排列
52.N皇后Ⅱ 17.电话号码的字母组合 题意#xff1a; 给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下#xff08;与电话按键相同#xf…目录
17.电话号码的字母组合 77.组合
46.全排列
52.N皇后Ⅱ 17.电话号码的字母组合 题意 给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 【输入样例】digits23 【输出样例】[ad,ae,af,bd,be,bf,cd,ce,cf] class Solution {public ListString letterCombinations(String digits) {ListString ans new ArrayListString();if(digits.length() 0){return ans;}MapCharacter,String phoneMap new HashMapCharacter,String(){{put(2,abc);put(3,def);put(4,ghi);put(5,jkl);put(6,mno);put(7,pqrs);put(8,tuv);put(9,wxyz);}};findString(ans,phoneMap,digits,0,new StringBuffer());return ans;}public void findString(ListString ans, MapCharacter,String phoneMap,String digits,int index,StringBuffer curAns){if(index digits.length()){//证明全部遍历完比ans.add(curAns.toString());//把找到的答案转成String类型存到列表中}else{char digit digits.charAt(index);//取出字符到map中获取对应的值String letters phoneMap.get(digit);for(int i0;iletters.length();i){curAns.append(letters.charAt(i));//递归调用主要是用于找到下一位可能的字符findString(ans,phoneMap,digits,index1,curAns);//递归回来进行回溯把当前的字符删掉寻找更多可能curAns.deleteCharAt(index);}}}
} 时间 击败了46.35% 内存 击败了26.39% 77.组合 题意 给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 【输入样例】n4,k2 【输出样例】 [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
] class Solution {ListListInteger ans new ArrayListListInteger();public ListListInteger combine(int n, int k) {findAns(1,n,k,new ArrayList());//从1开始找return ans;}public void findAns(int index,int n,int k,ListInteger list){if(k 0){//找到正确的答案添加ans.add(new ArrayList(list));return;}for(int iindex;in-k1;i){list.add(i);findAns(i1,n,k-1,list);list.remove(list.size()-1);}}
} 时间 击败了56.50% 内存 击败了5.94% 46.全排列 题意 给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 【输入样例】nums[1,2,3] 【输出样例】[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 解题思路递归回溯哈希表 1. 构建一个哈希map用来存放当前那一些数字可以用那一些数字不可以用 2. 递归函数的作用是找到第index位上可以是那个数字数字是位于数字中所以对数组进行枚举来获得第i位的值之后用哈希map判断此位数字是否已经被用过。被用过继续找没被用过则添加到list中并修改标志位继续寻找第index1位 3.回溯的时候除了要移开最后一位数字还需要重新修改标志位。 class Solution {ListListInteger ans new ArrayListListInteger();public ListListInteger permute(int[] nums) {//构造map初始化所有数字现在都可以用int len nums.length;MapInteger,Boolean useMap new HashMapInteger,Boolean();for(int i0;ilen;i){useMap.put(nums[i],true);}searchOrder(1,nums,len,useMap,new ArrayList());//从第一位开始找return ans;}public void searchOrder(int index,int[] nums,int len,MapInteger,Boolean useMap,ListInteger list){if(index len1){//找到正确的答案添加ans.add(new ArrayList(list));return;}for(int i0; i len;i){//从第一位到最后一位可以选择那一些int num nums[i];if(useMap.get(num) true){list.add(num);//修改标志位useMap.put(num,false);searchOrder(index1,nums,len,useMap,list);list.remove(list.size()-1);useMap.put(num,true);}}}
} 时间 击败了78.23% 内存 击败了48.52% 52.N皇后Ⅱ 题意 n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上并且使皇后彼此之间不能相互攻击。 给你一个整数 n 返回 n 皇后问题 不同的解决方案的数量。 【输入样例】n4 【输出样例】2 解题思路递归回溯布尔数组 为什么是!row[i] !dia[index-in] !assDia[indexi] row[i]好理解同一列已经有值 but,dia和assDia中的取值为什么是这样书写的呢 class Solution {int ans 0;public int totalNQueens(int n) {//n皇后问题//任意两个皇后不能在同一横轴纵轴,对角线上//三个数组表示当前纵轴正对角线副对角线上是否有值默认falseboolean[] row new boolean[n1];boolean[] dia new boolean[2*n1];boolean[] assDia new boolean[2*n1];search(1,n,row,dia,assDia);//从第一行开始判断return ans;}private void search(int index,int n, boolean[] row, boolean[] dia, boolean[] assDia){if(index n1){ans;return;}//index表示当前查找第几行所以遍历遍历列就可以了for(int i1;in;i){if(!row[i] !dia[index-in] !assDia[indexi]){row[i] dia[index-in] assDia[indexi] true;//已经有值search(index1,n,row,dia,assDia);//回溯row[i] dia[index-in] assDia[indexi] false;}}}
} 时间 击败了100.00% 内存 击败了74.08%
