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

引言

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

复习

数组中的第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个元素，每一个元素都要遍历
    • 单次迭代内容：当前元素选择零次，或者若干次

其实如果能够从树的角度分析，效果会更好，树的深度就是总的迭代次数，单个节点的子节点数也就是树的宽度，就是单次迭代需要考虑的内容

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));