如何做装修网站,vpsputty做网站,加强企业门户网站建设,池州市建设厅官方网站文章目录 引言复习数组中的第K大的最大元素复习实现参考实现 新作回溯模板46 全排列个人实现参考实现 子集个人实现参考实现 电话号码的字母组合复习实现 组合总和个人实现参考实现 括号生成复习实现 总结 引言
昨天的科大讯飞笔试做的稀烂#xff0c;今天回来好好练习一下今天回来好好练习一下主要是针对下述两种题型分别是对顶堆还有回溯对顶堆的题目并不多主要是回溯。下次再遇到这种题目直接背模板然后开始做
复习
数组中的第K大的最大元素 题目链接 第一次做 第二次做 不知不觉已经是第三次做了感觉还是有点懵ON的时间复杂度说明可以遍历多次但是不能嵌套遍历想想看哈
复习实现
我还是会使用堆实现并且发现了如果第一次不会做那么后续会一直不会做记不住这里还是要总结.这里还是使用了堆排序时间虽然时间复杂度不满足要求但是单纯为了练习一下
class Solution {public int findKthLargest(int[] nums, int k) {//define m is lenght ,and pq to sort the numint m nums.length;QueueInteger pq new PriorityQueue();// traverse the numsfor(int i 0;i m;i ){if(pq.size() k) pq.add(nums[i]);else{if(nums[i] pq.peek()){pq.poll();pq.add(nums[i]);}}}return pq.peek();}
}参考实现
这里正确的做法是使用快排进行修改这里先回顾一下快排的模板
void quickSort(nums q,int l ,int r){if(l r) return;int i l - 1,j r 1,x q[(l r)1];while(i j){do i ;while(q[i] x);do j ;while(q[j] x);if(i j) swap(q[i],q[j]);}quickSort(q,l,j),quickSort(q,j 1,r);
}这样背虽然很蹩脚但是能记住就行了记住了就好些了 左右相交就返回左左右右是 iji加小 j减大i小j大做交换j做划分两边排
这里是要求第K大的数字所以得改变一下i和j交换的方向最后的序列应该是从大到小然后再是找第k大的元素这道题是记住了修改的话就从最后的终止条件开始
具体实现
class Solution {public int quickSort(int[] nums,int l ,int r,int k){if(l r) return nums[k];int i l - 1,j r 1,x nums[(l r) 1];while(i j){do i ;while(nums[i] x);do j --;while(nums[j] x);if(i j) {int temp nums[i];nums[i] nums[j];nums[j] temp;}}if(j k) return quickSort(nums,l,j,k);else return quickSort(nums,j 1,r,k);}public int findKthLargest(int[] nums, int k) {//define m is lenght ,and pq to sort the numint m nums.length;// traverse the numsint x quickSort(nums,0,m - 1,k - 1 );return x;}
}新作
回溯模板
void dfs(int[] nums,int idx){// 终止条件if(idx termination){// 目标操作return;}//迭代内容for(){dfs(nums,idx 1);// 恢复现场}
} 这里要确定两个东西一个是总的迭代对象还有一个是单次迭代的修改内容下面把下面几个题按照这个模板都分析一下 全排列 n个对象排在n个位置每一个位置都要迭代一次然后每一次都要从剩下没有排的对象中选出来的所以 总的迭代次数n个位置终止条件就是迭代n次单次迭代内容在可选的选项中随机选择一个。 子集 n个对象其中选择任意一个有几种选择方法遍历每一个元素然后根据每一个元素决定是否选中所以 总的迭代次数n个对象终止条件所有元素都决策过了。单次迭代内容当前元素是否选中两种情况选中当前元素不选中当前元素 组合总和 n个对象选择其中若干个若干次形成目标值所以 总的迭代次数n个元素每一个元素都要遍历单次迭代内容当前元素选择零次或者若干次
其实如果能够从树的角度分析效果会更好树的深度就是总的迭代次数单个节点的子节点数也就是树的宽度就是单次迭代需要考虑的内容
46 全排列
题目链接 注意所有整数互不相同不用处理特殊情况。数组的长度会出现的一的情况边界情况需要特殊处理
个人实现
标准回溯确定一个模板直接开始写。 终止条件idx 0并将结果加入到res中迭代条件遍历剩余的元素随机加入到临时列表中
class Solution {public ListListInteger res new ArrayList();void dfs(int[] nums,int idx,ListInteger list,SetInteger set){if(idx 0){res.add(new ArrayList(list));return;}// iterator conditionfor(int i 0;i nums.length;i ){int x nums[i];if(!set.contains(x)){list.add(x);set.add(x);dfs(nums,idx - 1,list,set);list.remove(list.size() - 1);set.remove(x);}}}public ListListInteger permute(int[] nums) {ListInteger list new ArrayList();SetInteger set new HashSet();dfs(nums,nums.length,list,set);return res;}
}觉得写的有点繁琐看看参考的教程是怎么写的
注意在Java中res.add方法是引用传递需要创建一个同元素变量的副本才行不然会越界
参考实现 明确需要记录的状态 每一个位置具体的位置保存的数字也就是list每一个数字的使用情况使用set递归到了第几步 他是使用全局变量来声明没有使用形参传递对应
这里就不写了基本上都是一致的
子集
题目链接 注意存在数组为1的特殊情况可能需要特殊处理各个元素互不相同元素有负数的情况
个人实现
刚才那道题目是所有的排列情况这道题目是所有的组合情况应该也可以使用回溯实现。这个和刚才相同不过是在每一次的改变环境的时候就将结果进行保存
class Solution {ListInteger list new ArrayList();SetInteger set new HashSet();SetListInteger res new HashSet();void dfs(int[] nums,int idx){if(idx nums.length){ListInteger temp new ArrayList(list);Collections.sort(temp);res.add(temp);}for(int i 0;i nums.length;i ){int x nums[i];if(!set.contains(x)){set.add(x);list.add(x);ListInteger temp new ArrayList(list);Collections.sort(temp);res.add(temp);dfs(nums,idx 1);set.remove(x);list.remove(list.size() - 1);}}}public ListListInteger subsets(int[] nums) {res.add(Arrays.asList());dfs(nums,0);ListListInteger resList new ArrayList();for(ListInteger x:res){resList.add(x);}return resList;}
}上面这样做就不对得再想想如果是回溯的话得更新一下状态的改变不能直愣愣的添加对应的元素出来结果了然后再添加
好蠢呀没想到没想到既然没想到记下来下次肯定能够想到
参考实现
方法一、DFS 递归的条件
每一个元素只有两种情况放或者不放所以遍历这两种情况就行了
class Solution {ListInteger list new ArrayList();ListListInteger res new ArrayList();void dfs(int[] nums,int idx){// termiante conditionif(idx nums.length){res.add(new ArrayList(list));return ;}// traverse all the condition// get the idx numlist.add(nums[idx]);dfs(nums,idx 1);list.remove(list.size() - 1);// do not get the idx numdfs(nums,idx 1);}public ListListInteger subsets(int[] nums) {dfs(nums,0);return res;}
}方法二、位运算
将这个问题转化为对应的二进制表示每一个物体只有放或者不放两种情况对应就是不同的二进制数而且全排列的最终结果数量就是 2 n 2^n 2n
具体实现如下 这里刚好练习一下Java中的二进制数是怎么操作的
class Solution {public ListListInteger subsets(int[] nums) {ListListInteger res new ArrayList();int n nums.length;// traverse all the binary numfor(int i 0;i (1 n);i ){ListInteger temp new ArrayList();for(int j 0;j n;j ){// judge the j is 0 or 1if(((i j) 1) 1){temp.add(nums[j]);}}res.add(temp);}return res;}
}电话号码的字母组合
题目链接第一次做
复习实现
class Solution {MapCharacter,ListCharacter map new HashMap();StringBuilder str new StringBuilder();ListString res new ArrayList();void dfs(String digits,int idx){if(idx digits.length()){//System.out.println(str.toString());res.add(str.toString());return;}for(char x:map.get(digits.charAt(idx))){str.append(x);dfs(digits,idx 1);str.deleteCharAt(str.length() - 1);}}public ListString letterCombinations(String d) {map.put(2,Arrays.asList(a,b,c));map.put(3,Arrays.asList(d,e,f));map.put(4,Arrays.asList(g,h,i));map.put(5,Arrays.asList(j,k,l));map.put(6,Arrays.asList(m,n,o));map.put(7,Arrays.asList(p,q,r,s));map.put(8,Arrays.asList(t,u,v));map.put(9,Arrays.asList(w,x,y,z)); if(d.length() 0) return res;dfs(d,0);return res;}
}没以前使用C实现起来那么快写起来也没有那么方便
组合总和
题目链接 注意所有元素互不相同每一个元素可以放很多次
个人实现
这题可以使用两种方式实现 完全背包问题不过需要记录对应的背包状态时间复杂度比较低但是不知道怎么记录满足条件的状态 随便选一个装满为止F-V加上价值这里价值为零 暴力回溯时间复杂度高
暴力回溯
class Solution {ListInteger list new ArrayList();ListListInteger resList new ArrayList();SetListInteger res new HashSet();// brute dfs to solve the problemvoid dfs(int[] candi,int tar,int temp){if(temp tar){ListInteger tempList new ArrayList(list);Collections.sort(tempList);res.add(tempList);return;}for(int i 0;i candi.length;i ){if(temp candi[i] tar){// put//System.out.println(candi[i]);list.add(candi[i]);dfs(candi,tar,temp candi[i]);list.remove(list.size() - 1);}}}public ListListInteger combinationSum(int[] candidates, int target) {dfs(candidates,target,0);for(ListInteger x:res){resList.add(x);}return resList;}
}我靠这个居然能过也是离谱了
完全背包问题
class Solution {ListInteger list new ArrayList();ListListInteger resList new ArrayList();public ListListInteger combinationSum(int[] candidates, int target) {int[] f new int[target 1];f[0] 1;for(int i 0;i candidates;i ){for(int j candidates[i];j target;j ){f[j] f[j] f[j - candidates[i]];}}return f[target - 1];}
}这里只能写成这样因为我并不知道怎么保存中间状态
不能用完全背包完全背包并不能获取中间状态
参考实现
只能说我对于的回溯的理解还是不够深刻两种存放方式 是否放当前的数字要用深度u控制防止出现死循环当前物体一定要放但是顺序不同需要set控制是否出现
class Solution {ListInteger list new ArrayList();ListListInteger resList new ArrayList();void dfs(int[] candidates,int dpt,int tar){if(tar 0){resList.add(new ArrayList(list));return;}if(dpt candidates.length) return;for(int i 0;i * candidates[dpt] tar ;i ){dfs(candidates,dpt 1,tar - i * candidates[dpt]);list.add(candidates[dpt]);} for(int i 0; i * candidates[dpt] tar ;i )list.remove(list.size() - 1);}public ListListInteger combinationSum(int[] candidates, int target) {dfs(candidates,0,target);return resList;}
}实现起来确实更优如果放或者不放还是需要使用的深度进行控制 无论怎么样都需要加上的对应idx控制
括号生成
题目链接第一次学习链接
复习实现
class Solution {// define the structure to store the resultListString res new ArrayList();StringBuilder str new StringBuilder();void dfs(int idx,int n,int l,int r){if(idx 2 * n l r){if(l r)res.add(str.toString());return ;}// remove the special situationif(r l || l n || r n) return;str.append(();dfs(idx 1,n,l 1,r);str.deleteCharAt(str.length() - 1);str.append());dfs(idx 1,n,l ,r 1);str.deleteCharAt(str.length() - 1);}public ListString generateParenthesis(int n) {dfs(0,n,0,0);return res;}
}上一次写的真丝滑
vectorstring res;
void dfs(int n,int lc,int rc,string s){/** n表示括号数量lc表示左括号数量rc表示右括号数量s表示字符串*/// 判定什么时候加左括号if (lc n rc n) res.push_back(s); else{// 什么时候加右括号if (lc n) dfs(n,lc 1,rc,s ();if (lc rc rc n) dfs(n,lc,rc 1,s ));}
}vectorstring generateParenthesis(int n){dfs(n,0,0,);return res;
}总结
今天这几道题做完了算是对于深度有了更加深刻的认识最好能够画出对应的树形结构树的高度就是总的迭代次数树的宽度就是单次迭代需要迭代的内容写回溯还是比写其他算法要轻松很多写回溯一定要画图写算法一定要画图转成对应的数据结构回溯就是可以转成对应的树形结构一定要要记得恢复现场每一步都要恢复现场因为你的编程习惯是共用一个StringBuilder。
