文章目录
- 引言
- 复习
- 数组中的第K大的最大元素
- 复习实现
- 参考实现
- 新作
- 回溯模板
- 46 全排列
- 个人实现
- 参考实现
- 子集
- 个人实现
- 参考实现
- 电话号码的字母组合
- 复习实现
- 组合总和
- 个人实现
- 参考实现
- 括号生成
- 复习实现
- 总结
引言
- 昨天的科大讯飞笔试做的稀烂，今天回来好好练习一下，主要是针对下述两种题型，分别是对顶堆还有回溯，对顶堆的题目并不多，主要是回溯。下次再遇到这种题目，直接背模板，然后开始做！
复习
数组中的第K大的最大元素
-
题目链接
-
第一次做
-
第二次做
-
不知不觉已经是第三次做了，感觉还是有点懵，O（N）的时间复杂度，说明可以遍历多次，但是不能嵌套遍历！想想看哈
复习实现
- 我还是会使用堆实现，并且发现了如果第一次不会做，那么后续会一直不会做，记不住！这里还是要总结.
- 这里还是使用了堆排序时间，虽然时间复杂度不满足要求，但是单纯为了练习一下！
class Solution {
public int findKthLargest(int[] nums, int k) {
//define m is lenght ,and pq to sort the num
int m = nums.length;
Queue<Integer> pq = new PriorityQueue<>();
// traverse the nums
for(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 num
int m = nums.length;
// traverse the nums
int 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个对象，终止条件所有元素都决策过了。
- 单次迭代内容：当前元素是否选中两种情况，选中当前元素，不选中当前元素，
- n个对象，其中选择任意一个有几种选择方法，遍历每一个元素，然后根据每一个元素决定是否选中，所以
-
组合总和
- n个对象，选择其中若干个若干次，形成目标值，所以
- 总的迭代次数：n个元素，每一个元素都要遍历
- 单次迭代内容：当前元素选择零次，或者若干次
- n个对象，选择其中若干个若干次，形成目标值，所以
其实如果能够从树的角度分析，效果会更好，树的深度就是总的迭代次数，单个节点的子节点数也就是树的宽度，就是单次迭代需要考虑的内容
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 condition
for(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 condition
if(idx == nums.length){
res.add(new ArrayList(list));
return ;
}
// traverse all the condition
// get the idx num
list.add(nums[idx]);
dfs(nums,idx + 1);
list.remove(list.size() - 1);
// do not get the idx num
dfs(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 num
for(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 1
if(((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 problem
void 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控制
括号生成
- 题目链接
- 第一次学习链接
复习实现
class Solution {
// define the structure to store the result
List<String> 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 situation
if(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 List<String> generateParenthesis(int n) {
dfs(0,n,0,0);
return res;
}
}
上一次写的真丝滑！
vector<string> 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 + ")");
}
}
vector<string> generateParenthesis(int n){
dfs(n,0,0,"");
return res;
}
总结
- 今天这几道题做完了，算是对于深度有了更加深刻的认识！最好能够画出对应的树形结构，树的高度就是总的迭代次数，树的宽度就是单次迭代需要迭代的内容！
- 写回溯，还是比写其他算法要轻松很多！
- 写回溯，一定要画图！写算法一定要画图，转成对应的数据结构！回溯就是可以转成对应的树形结构！
- 一定要要记得恢复现场，每一步都要恢复现场，因为你的编程习惯是共用一个StringBuilder。
