/秋招突击——7/21——复习{堆——数组中的第K大元素}——新作{回溯——全排列、子集、电话号码的字母组合、组合总和、括号生成}

引言

• 昨天的科大讯飞笔试做的稀烂，今天回来好好练习一下，主要是针对下述两种题型，分别是对顶堆还有回溯，对顶堆的题目并不多，主要是回溯。下次再遇到这种题目，直接背模板，然后开始做！

复习

数组中的第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;}
}

新作

回溯模板

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 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$

具体实现如下
这里刚好练习一下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控制

括号生成

• 题目链接
• 第一次学习链接

复习实现

class Solution {// define the structure to store the resultList<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 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 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。