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

  • 开发
  • 16

文章目录

引言

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

复习

数组中的第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));
            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。
阅读全部

相关推荐

  2. 秋招突击——6/11——复习{（树形DP）树的最长路径、电话号码的字母组合}——新作{重复序列中前最小的数字}

    2024-07-22 06:04:03       21 阅读

  7. Day 25 | 回溯 216.组合总和III 、17.电话号码的字母组合

    2024-07-22 06:04:03       49 阅读

  8. Day25｜回溯算法part02：216.组合总和III、17.电话号码的字母组合

    2024-07-22 06:04:03       29 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-22 06:04:03       49 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-22 06:04:03       53 阅读

  9. 在Django里面运行非项目文件

    2024-07-22 06:04:03       42 阅读

  19. Python语言-面向对象

    2024-07-22 06:04:03       53 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-22 06:04:03       49 阅读

热门阅读

  5. python多进程库（multiprocessing）

    2024-07-22 06:04:03       15 阅读

  6. 过滤器、同步异步、跨域问题、json数据格式字符串

    2024-07-22 06:04:03       16 阅读

  18. python每日学习9：正则表达式

    2024-07-22 06:04:03       19 阅读
  20. Linux

    Linux

    2024-07-22 06:04:03      17 阅读

  24. 树上启发加点分治思想

    2024-07-22 06:04:03       16 阅读

  26. 做ui自动化测试需要对页面所有元素进行可见作断言吗？还是说只需要断言一个元素存在

    2024-07-22 06:04:03       16 阅读