文章目录
- 引言
- 复习
- 数组中的第K大的最大元素
- 复习实现
- 参考实现
- 新作
- 46 全排列
- 个人实现
- 参考实现
- 子集
- 个人实现
- 参考实现
- 电话号码的字母组合
- 复习实现
- 组合总和
- 个人实现
- 参考实现
- 总结
引言
- 昨天的科大讯飞笔试做的稀烂,今天回来好好练习一下,主要是针对下述两种题型,分别是对顶堆还有回溯,对顶堆的题目并不多,主要是回溯。下次再遇到这种题目,直接背模板,然后开始做!
复习
数组中的第K大的最大元素
-
题目链接
-
第一次做
-
第二次做
-
不知不觉已经是第三次做了,感觉还是有点懵,O(N)的时间复杂度,说明可以遍历多次,但是不能嵌套遍历!想想看哈
复习实现
- 我还是会使用堆实现,并且发现了如果第一次不会做,那么后续会一直不会做,记不住!这里还是要总结.
- 这里还是使用了堆排序时间,虽然时间复杂度不满足要求,但是单纯为了练习一下!
class Solution {public int findKthLargest(int[] nums, int k) {//define m is lenght ,and pq to sort the numint m = nums.length;Queue<Integer> 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);
}
- 这样背!虽然很蹩脚,但是能记住就行了,记住了就好些了!
- 左右相交就返回
- 左左右右是 ij
- i加小 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;}
}
新作
46 全排列
- 题目链接
注意 - 所有整数互不相同,不用处理特殊情况。
- 数组的长度会出现的一的情况,边界情况,需要特殊处理!
个人实现
- 标准回溯,确定一个模板直接开始写。
- 终止条件:idx = 0,并将结果加入到res中
- 迭代条件:遍历剩余的元素,随机加入到临时列表中
class Solution {public List<List<Integer>> res = new ArrayList<>();void dfs(int[] nums,int idx,List<Integer> list,Set<Integer> 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 List<List<Integer>> permute(int[] nums) {List<Integer> list = new ArrayList<>();Set<Integer> set = new HashSet<>();dfs(nums,nums.length,list,set);return res;}
}
觉得写的有点繁琐,看看参考的教程是怎么写的
- 注意,在Java中res.add方法是引用传递,需要创建一个同元素变量的副本才行,不然会越界!
参考实现
-
明确需要记录的状态
- 每一个位置具体的位置保存的数字,也就是list
- 每一个数字的使用情况,使用set
- 递归到了第几步
-
他是使用全局变量来声明,没有使用形参传递对应
这里就不写了,基本上都是一致的
子集
- 题目链接
注意 - 存在数组为1的特殊情况,可能需要特殊处理
- 各个元素互不相同
- 元素有负数的情况
个人实现
- 刚才那道题目是所有的排列情况,这道题目是所有的组合情况,应该也可以使用回溯实现。这个和刚才相同,不过是在每一次的改变环境的时候,就将结果进行保存!
class Solution {List<Integer> list = new ArrayList<>();Set<Integer> set = new HashSet<>();Set<List<Integer>> res = new HashSet<>();void dfs(int[] nums,int idx){if(idx == nums.length){List<Integer> 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);List<Integer> temp = new ArrayList<>(list);Collections.sort(temp);res.add(temp);dfs(nums,idx + 1);set.remove(x);list.remove(list.size() - 1);}}}public List<List<Integer>> subsets(int[] nums) {res.add(Arrays.asList());dfs(nums,0);List<List<Integer>> resList = new ArrayList<>();for(List<Integer> x:res){resList.add(x);}return resList;}
}
上面这样做就不对,得再想想,如果是回溯的话,得更新一下状态的改变,不能直愣愣的添加对应的元素!出来结果了,然后再添加!
- 好蠢呀,没想到,没想到,既然没想到,记下来,下次肯定能够想到!
参考实现
方法一、DFS
递归的条件
- 每一个元素只有两种情况,放或者不放,所以遍历这两种情况就行了!
class Solution {List<Integer> list = new ArrayList<>();List<List<Integer>> 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 List<List<Integer>> subsets(int[] nums) {dfs(nums,0);return res;}
}
方法二、位运算
- 将这个问题转化为对应的二进制表示,每一个物体只有放或者不放两种情况,对应就是不同的二进制数,而且全排列的最终结果数量就是 2 n 2^n 2n
具体实现如下
这里刚好练习一下Java中的二进制数是怎么操作的!
class Solution {public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> res = new ArrayList<>();int n = nums.length;// traverse all the binary numfor(int i = 0;i < (1 << n);i ++){List<Integer> 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 {Map<Character,List<Character>> map = new HashMap<>();StringBuilder str = new StringBuilder();List<String> 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 List<String> 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 {List<Integer> list = new ArrayList<>();List<List<Integer>> resList = new ArrayList<>();Set<List<Integer>> res = new HashSet<>();// brute dfs to solve the problemvoid dfs(int[] candi,int tar,int temp){if(temp == tar){List<Integer> 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 List<List<Integer>> combinationSum(int[] candidates, int target) {dfs(candidates,target,0);for(List<Integer> x:res){resList.add(x);}return resList;}
}
我靠,这个居然能过,也是离谱了!
完全背包问题
class Solution {List<Integer> list = new ArrayList<>();List<List<Integer>> resList = new ArrayList<>();public List<List<Integer>> 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 {List<Integer> list = new ArrayList<>();List<List<Integer>> 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 List<List<Integer>> combinationSum(int[] candidates, int target) {dfs(candidates,0,target);return resList;}
}
实现起来确实更优!如果放或者不放,还是需要使用的深度进行控制!
无论怎么样,都需要加上的对应idx控制
总结
- 今天这几道题做完了,算是对于深度有了更加深刻的认识,主要是控制的遍历的内容,然后每一层迭代控制的始终是idx,然后需要额外的条件进行控制和判定!
- 写回溯,还是比写其他算法要轻松很多!