当前位置: 首页 > article >正文

穷举vs暴搜vs深搜vs回溯vs剪枝 算法专题

一. 全排列

全排列

class Solution {
    List<List<Integer>> ret;
    List<Integer> path;
    boolean[] check;
    public List<List<Integer>> permute(int[] nums) {
        ret = new ArrayList<>();//存放结果
        path = new ArrayList<>();存放每个路径的path
        check = new boolean[nums.length];//记录是否被使用, 对应是下标

        dfs(nums);
        return ret;
    }

    public void dfs(int[] nums){
        if(path.size() == nums.length){//全部遍历完
            ret.add(new ArrayList<>(path));//添加结果
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(!check[i]){
                path.add(nums[i]);
                check[i] = true;
                dfs(nums);
                //还原现场
                check[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}

二. 子集

子集
先画决策树, 再设计代码
解法一:

class Solution {
    List<List<Integer>> ret;
    List<Integer> path;
    public List<List<Integer>> subsets(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();

        dfs(nums, 0);
        return ret;
    }

    public void dfs(int[] nums, int i){//要选择的下标
        if(i == nums.length){
            ret.add(new ArrayList<>(path));
            return ;
        }
        //选
        path.add(nums[i]);
        dfs(nums, i + 1);
        //恢复现场
        path.remove(path.size() - 1);
        //不选
        dfs(nums, i + 1);
    }
}

解法二: 按照数量添加

class Solution {
    List<List<Integer>> ret;
    List<Integer> path;

    public List<List<Integer>> subsets(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();

        dfs(nums, 0);
        return ret;
    }

    public void dfs(int[] nums, int pos) {
        ret.add(new ArrayList<>(path));//每个节点全部加入
        for(int i = pos; i < nums.length; i++){
            path.add(nums[i]);
            dfs(nums, i + 1);//只能添加此时下标后面的, 防止重复
            path.remove(path.size() - 1);//恢复现场
        }

    }
}

http://www.kler.cn/a/375576.html

相关文章:

  • kafka相关面试题
  • CSS例子: 横向排列的格子
  • Pinpoint(APM)进阶--插件开发
  • 05-07实现面向对象领域模型-停车案例
  • java项目中如何有效提高List集合的读写速度?
  • tensorflow案例4--人脸识别(损失函数选取,调用VGG16模型以及改进写法)
  • #渗透测试#SRC漏洞挖掘# 操作系统-windows系统
  • C++设计模式结构型模式———桥接模式
  • watch 和 computed 的区别 - 2024最新版前端秋招面试短期突击面试题【100道】
  • MySQL锁——针对实习面试
  • 【华为HCIP实战课程二十九】中间到中间系统协议IS-IS邻居关系建立和LSP详解,网络工程师
  • 关于武汉芯景科技有限公司的马达驱动芯片AT6237开发指南(兼容DRV8837)
  • BO-Transformer-LSTM多特征分类预测/故障诊断(Matlab实现)
  • Spring Boot 跨域解决方案
  • 星光校园之恋
  • leetcode day8 动态规划篇 3259+746+198
  • 高级java每日一道面试题-2024年10月25日-JVM篇-你是如何排查线上OOM问题的?
  • (python)如何进行加密
  • 输出特殊图案,请在c环境中运行
  • wpf设置全局字体大小,可以配置
  • 点评项目-13-附近商铺、用户签到、UV统计
  • React04 State变量 组件渲染
  • Kali Linux
  • Windows 10 安装使用Docker踩过的坑和解决-31/10/2024
  • InnoDB: corruption in the InnoDB tablespace
  • 动态规划之两个数组的 dp(下)