程序员经验分享-hwhale

LeetCode之回溯算法

2023-05-16

文章目录

  • 思想&框架
    • 1.组合/子集和排列问题
    • 2.组合应用问题
  • 组合/子集问题
    • 1. lc77 组合
    • 2. lc216 组合总和III
    • 3. lc39 组合总和
    • 4. lc40 组合总和II
    • 5. lc78 子集
    • 6. lc90 子集II
  • 排列
    • 1. 全排列I
    • 2. 全排列II
  • 组合问题的应用
    • 1.lc17 电话号码的字母组合
    • 2.lc131 分割回文串
    • 3. lc19 复原IP地址
  • 岛屿问题&棋盘问题

思想&框架

首先统一的框架是：

result = []
def dfs(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
       dfs(路径, 选择列表)
        撤销选择

其实就是把回溯问题看成一个多叉树，for循环去遍历树的宽度，dfs回溯去深度遍历

主要有这么几类问题：组合/子集和排列，岛屿问题，分割问题，棋盘问题

1.组合/子集和排列问题

第一个大类就是组合/子集和排列问题，围绕着元素重不重复，可不可以复选来
基本技巧就是：
组合/ 子集：startIndex
排列：used数组&排序

具体点的关键代码（来点投机取巧速记的）
组合/子集

  • 元素不重复且不可重复选：dfs(n,k,i+1)
  • 元素不重复且可重复选：dfs(n,k,i)
  • 元素重复且不可重复选：排序 & nums[i]==nums[i-1]判断

排列

  • 元素不重复：used数组，
  • 元素重复：排序+nums[i]==nums[i-1]判断+used数组

2.组合应用问题

需要灵活运用，不单单是上面几种的变种，更多的是回溯思维的提升

组合/子集问题

子集和组合问题基本一致，唯一不同就是子集收集的是树的所有节点，而组合收集的是叶子节点。

1. lc77 组合

力扣链接

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合
输入：n = 4, k = 2
输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]

Solution
（记住下面这个基本的板子！）

    // 两个全局变量（也可以放进递归的参数中）
    List<List<Integer>> list = new ArrayList<>(); // 存放结果集
    LinkedList<Integer> path = new LinkedList<>();  // 存放每次的结果
     
    public  List<List<Integer>> combine(int n, int k) {
        backTracking(n,k,1);
        return list;
    }

    public void  backTracking(int n,int k,int startIndex)
    {
        if(path.size()==k)
        {
            // 注意这里要新建ArrayList的path
            list.add(new ArrayList<>(path));
            return;
        }
        //for(int i=startIndex;i<=n;i++)，i<=n-(k-path.size())+1 是剪枝操作
        for(int i=startIndex;i<=n-(k-path.size())+1;i++)
        {
            path.add(i);
            backTracking(n,k,i+1);
            path.removeLast();
        }
    }

两个细节：
（1） 一个是list.add(new ArrayList<>(path));，为什么不能直接add(path)？
因为变量 path 所指向的列表 在深度优先遍历的过程中只有一份 ，深度优先遍历完成以后，回到了根结点，成为空列表。
在 Java 中，参数传递是 值传递，对象类型变量在传参的过程中，复制的是变量的地址。这些地址被添加到 res 变量，但实际上指向的是同一块内存地址，因此我们会看到 66 个空的列表对象。解决的方法很简单，在 res.add(path); 这里做一次拷贝即可。
（链接：https://leetcode.cn/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/）

(2) 另一个就是剪枝，怎么判断剪枝条件？
可以这么想，i是有搜索上界的，i越大，剩下可选的数就越少，这样就不满足k的要求，也就没必要再搜索下去。
要组成大小为k的path，此时还需要k - path.size()个数，如果[i, n]这个区间内，(有n - i + 1个数)不足这么多，则肯定没有结果，直接剪枝。则 k-path.size()<n-i+1，所以i=n-(k-path.size())+1，也就是i的上界。

2. lc216 组合总和III

lc216 链接

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：只使用数字1到9,每个数字 最多使用一次 .返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次
输入: k = 3, n = 9 输出: [ [1,2,6], [1,3,5], [2,3,4] ]

Solution:
与上题相似，多了一个对sum的判断。可以选择的数字是1-9

 List<List<Integer>> res= new ArrayList<>();
 LinkedList<Integer> path = new LinkedList<>();
 public List<List<Integer>> combinationSum3(int k, int n) {
     backTrack(k,n,1,0);
     return res;
 }

 void backTrack(int k,int n,int startIndex,int sum)
 {
     // 剪枝操作，如果sum已经大于n，直接返回
     if(sum>n)
         return;
     
     // 终止条件
     if(path.size()==k)
     {
         if(sum==n)
             res.add(new ArrayList<>(path));

         return;
     }
     // 当然，这里也可以模仿上面再剪枝，写成i<=9-(k-path.size())+1
     for(int i=startIndex;i<=9;i++)
     {
         path.add(i);
         sum += i;
         backTrack(k,n,i+1,sum);
         path.removeLast();
         sum -= i;
     }
 }

3. lc39 组合总和

lc39 链接

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。
输入: candidates = [2,3,5], target = 8 输出: [ [2,2,2,2],[2,3,3],[3,5] ]

Solution:
与前两题组合不同（特别是组合总和III），这里选取的数字的可以重复的，想一想前两题是怎么控制不重复选的，startIndex！每次dfs时都加一，这样就确定了遍历起点。所以，当可以重复时，就不用加一了！
（如果要问为什么还需要startIndex，因为这还是组合问题啊，也就是不能走回头路，比如[1,2,3]，目标和是4，你可以选[1,1,2]，如果没有startIndex，当你到2的时候，又会有[2,1,1]的可能！）

 List<List<Integer>> res = new ArrayList<>();
 LinkedList<Integer> path  =new LinkedList<>();
 public List<List<Integer>> combinationSum(int[] candidates, int target) {
     backTrack(candidates,target,0,0);
     return res;
    
 }
 void backTrack(int[] candidates,int target,int sum,int startIndex)
 {     
     if(sum>=target)
     {
         if(sum==target)
            res.add(new ArrayList<>(path));
         return ;
     }
     for(int i=startIndex;i<candidates.length;i++)
     {
         path.add(candidates[i]);
         sum+=candidates[i];
         // 注意这里，因为可以重复，所以不需要i+1了
         backTrack(candidates,target,sum,i);
         sum-=candidates[i];
         path.removeLast();
     }
 }

4. lc40 组合总和II

lc40链接

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用 一次
输入: candidates = [2,5,2,1,2], target = 5,
输出: [ [1,2,2], [5] ]

Solution:
与上一题的区别在于如何去重，因为原始的候选集有重复元素，如果还是按照上面的思路的话，结果集肯定有重复的。解决方法是排序＋相邻相等判断！

  class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates); // 注意这里先排序
        dfs(candidates,target,0,0);
        return res;
    }
     public void dfs(int[] nums,int target,int sum,int startIndex)
    {
        if(sum>target) return;
        if(sum==target)
        {
            res.add(new LinkedList<>(path));
            return;
        }
        for(int i=startIndex;i<nums.length;i++)
        {
        // 注意这里的去重，当i不是startIndex时，要判断与前一个数字是否相同
            if(i>startIndex && nums[i]==nums[i-1])
               continue;
            path.add(nums[i]);
            sum+=nums[i];
            dfs(nums,target,sum,i+1);
            sum-=nums[i];
            path.removeLast();
        }
    }
}

可以用[1,2,2’]来区分，通过画回溯树理解

在这里插入图片描述

5. lc78 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集
输入：nums = [1,2,3]
输出：[ [],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3] ]

Solution：
与组合题目不同的是，求子集实际上求的是树的所有节点（而非叶子节点）

 List<List<Integer>> res  =new ArrayList<>();
 LinkedList<Integer> path = new LinkedList<>();
  public List<List<Integer>> subsets(int[] nums) {
      backTrack(nums,0);
      return res;

  }
  void backTrack(int[] nums,int startIndex)
  {
      // 注意这里是直接添加，因为要添加的是所有节点（而非前面题目的叶子节点）
      res.add(new ArrayList<>(path));

      // 终止条件可加可不加（因为下面的for循环结束回溯就结束了）
     /* if (startIndex >= nums.length){
          return;
      }*/

      for(int i=startIndex;i<nums.length;i++)
      {
          path.add(nums[i]);
          backTrack(nums,i+1);
          path.removeLast();
      }
  }

6. lc90 子集II

力扣90链接

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集
输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

Solution：
对比上题可以看出，这里需要考虑去重，所以与lc40 组合总和II 基本相同

    class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        dfs(nums,n,0);
        return res;
    }
    public void dfs(int[] nums,int n,int startIndex)
    {
        res.add(new LinkedList<>(path));

        for(int i=startIndex;i<n;i++)
        {
            if(i>startIndex && nums[i]==nums[i-1])
              continue;

            path.add(nums[i]);
            dfs(nums,n,i+1);
            path.removeLast();
        }
    }
}

排列

1. 全排列I

力扣46链接

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Solution：
终于来到排列了，排列和子集以及组合最大的不同就是排列可以位置不同，直接点，不需要startIndex！因为抽象成一个回溯树时，搜索起点只要没被选过就都可以，例如[1,2,3]选1，还剩[2,3],然后[1,2,3]选2，还剩[1,3]，这时肯定就不用startIndex，而是直接for循环从0索引开始。
但这时又有个问题，你怎么知道选过的元素，如果知道的话，直接跳过就好了，所以used数组应运而生，标记一下哪些元素用过了。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        int[] used = new int[nums.length]; // 也可以用bool类型
        Arrays.fill(used,0); // 0代表元素没有使用过
        dfs(nums,used);
        return res;
    }
    public void dfs(int[] nums,int[] used)
    {
        
        if(path.size()==nums.length)
        {
            res.add(new LinkedList<>(path));
            return;
        }
        for(int i=0;i<nums.length;i++)
        {
            // 注意这里的去重，佛如、循环只会傻傻的从头遍历，但是有些元素已经访问过了，直接跳过
            if(used[i]==1) continue;
            
            path.add(nums[i]);
            used[i]=1; // 用过了要记得标记一下哦！
            dfs(nums,used);
            used[i] = 0; // 回溯之后要还原
            path.removeLast();
        }
    }
}

2. 全排列II

力扣47链接

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列
输入：nums = [1,1,2]
输出：
[ [1,1,2],[1,2,1],[2,1,1] ]

Solution:
相比于上一题，又难了点。主要还是去重逻辑。联系上面的组合去重，肯定也可以排序＋相邻判断，另外还需要used数组，判断前一个元素是否被选择。为什么会多这一步呢？
当出现重复元素时，比如输入 nums = [1,2,2’,2’‘]，2’ 只有在 2 已经被使用的情况下才会被选择，同理，2’’ 只有在 2’ 已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        int[] used = new int[nums.length];
        Arrays.fill(used,0);
        Arrays.sort(nums);
        dfs(nums,used);
        return res;

    }
     public void dfs(int[] nums,int[] used)
    {
        if(path.size()==nums.length)
        {
            res.add(new LinkedList<>(path));
            return;
        }
        for(int i=0;i<nums.length;i++)
        {
            if(used[i]==1) continue;

            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1]==0) {
                continue;
                }
            path.add(nums[i]);
            used[i]=1;
            dfs(nums,used);
            used[i] = 0;
            path.removeLast();
        }
    }
}

组合问题的应用

1.lc17 电话号码的字母组合

lc17 链接

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合
输入：digits = “23” 输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

Solution:
与组合问题最大的区别在于结果集来自“不同的组合”
首先需要建立一个映射，从字符2-9映射到字母，可以hash可以数组。注意本题的回溯树，第一层是第一个数字对应的字母。第二层是第一二数字对应的字母（有几个数字就有几层—深度），树的宽度却取决于数字对应的字母长度。

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if(digits.length()==0) return res;
        String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        dfs(map,digits,0);
        return res;

    }
    StringBuilder sb = new StringBuilder();
    public void dfs(String[] map,String s,int index)
    {
        if(sb.length()==s.length())
        {
             res.add(sb.toString());
             return;
        }
        int digit = s.charAt(index)-'0'; // 对应的数字
        String str = map[digit];
        for(int i=0;i<str.length();i++)
        {
            sb.append(str.charAt(i));
            dfs(map,s,index+1);
            sb.deleteCharAt(sb.length()-1);
        }
        }   
}

2.lc131 分割回文串

描述：

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串

示例：

输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

Solution：

List<List<String>> res = new ArrayList<>();
LinkedList<String> path = new LinkedList<>();

public List<List<String>> partition(String s) {
        backTrack(s,0);
        return res;
}

 void backTrack(String s,int index)
    {
        // 终止条件
        if(index >= s.length())
        {
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i=index;i<s.length();i++)
        {
            if(isPalindrome(s,index,i))
            {
                String str = s.substring(index,i+1);
                path.add(str);
            }
            else
            continue;

            backTrack(s,i+1);
            path.removeLast();
        }
 }
 
// 判断是否是回文，用双指针的方法
boolean isPalindrome(String s, int start, int end)
    {
        while(start <=end)
        {
            if(s.charAt(start)!=s.charAt(end))
            {
                return false;
            }
            start++;
            end--;
        }
        return true;
}

3. lc19 复原IP地址

描述：

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成

示例：

输入：s = “25525511135”
输出：[“255.255.11.135”,“255.255.111.35”]

Solution：

在这里插入代码片

岛屿问题&棋盘问题

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

LeetCode

之回溯算法

LeetCode之回溯算法 的相关文章

  • jvm复习：主动产生fullGC

    一 jdk8参数 Xms100m Xmx100m Xmn30m XX 43 PrintGCDetails 二 代码 xff1a package cn edu tju test public class GcTest01 public sta

  • Zookeeper机制和应用场景

    Zookeeper简介 Zookeeper 分布式服务框架是 Apache Hadoop 的一个子项目 xff0c 它主要是用来解决分布式应用中经常遇到的一些数据管理问题 xff0c 如 xff1a 统一命名服务 状态同步服务 集群管理 分

  • crontab定时器

    crontab定时器 linux下的定时任务 1 编辑使用crontab e 一共6列 xff0c 分别是 xff1a 分 时 日 月 周 命令 2 查看使用crontab l 3 删除任务crontab r 4 查看crontab执行日志

  • Linux后台运行程序

    在我们平常的时候运行程序的时候会产生很多的信息 xff0c 这些信息有时候有用 xff0c 有时候没用 xff0c 不过这些数据都会在该程序的log中保存 xff0c 所以把这些信息放在前台就不是很好 我们可以将脚本放在后台运行 xff0c

随机推荐

  • vnc的两种配置方法及解决vnc连不上的情况

    1 vnc连不上的现象 xff1a Timed out waiting for a response from the computer 解决方法 xff1a sudo sbin iptables I INPUT 1 p TCP dport

  • 【随写笔记】TouchGFX

    https www cnblogs com firege p 5805823 html https blog csdn net u013766436 article details 50805808 LTDC STM32F429系列芯片内部

  • BGP路由协议

    特点 BGP是一种外部网关协议 xff08 EGP xff09 xff0c 不擅长路由计算 xff0c 擅长路由控制 OSPF ISIS等内部网关协议 xff08 IGP xff09 xff0c 擅长路由计算 xff0c 不擅长路由控制 B

  • sed命令的使用(合并行)

    1 把所有不以句号结尾的行 xff0c 和下一行合并 span class token function sed span i span class token string 39 N s n 39 span abc txt 2 把两行合并

  • Mybatis常见面试题及答案

    文章目录 1 什么是Mybatis xff1f 2 Mybaits的优缺点 xff1a 3 和 的区别是什么 xff1f 4 通常一个mapper xml文件 xff0c 都会对应一个Dao接口 xff0c 这个Dao接口的工作原理是什么

  • HDFS排查路径

    遇到HDFS的问题 xff0c 首先需要排除可用类问题 可用类问题按影响 紧急程度不同 xff0c 可继续分为HDFS功能性受损 lt 61 HDFS高可靠性 高可用性受损 按照以下步骤进行排查 xff0c 以下任意一项有异常 xff0c

  • Docker复习： jar包打成docker

    FROM openjdk 8 ARG JAR FILE COPY springbootmybatis 1 0 SNAPSHOT jar app jar EXPOSE 9012 ENTRYPOINT 34 sh 34 34 c 34 34 j

  • iscsi磁盘挂载并设置为开机自动挂载

    前提准备 xff1a 安装iscsi客户端软件 yum y install iscsi initiator utils 第一步 xff1a 发现ISCSI设备 root 64 sdw4 iscsiadm m discovery t st p

  • 关于华为AC6507S能ping通web和ssh却登录不上排障记录（管理面隔离）

    一 客户描述PC和服务器能ping通AC但是web却登录不上 测试 xff1a 设置服务器地址为192 168 0 100 24 AC地址192 168 0 2 24 用0 100去ping0 2可以ping通 xff0c web登录连接失

  • tensor 和 numpy 的互相转换

    为什么要相互转换 xff1a 简单一句话 numpy操作多样 简单 但网络前向只能是tensor类型 各有优势 所以需要相互转换补充 convert Tensor x of torch to array y of numpy y 61 x

  • 图像畸变矫正算法实现 matlab版

    真正的相机镜头不理想 xff0c 并在图像中引入一些失真 为了解释这些非理想性 xff0c 有必要在透视投影的方程中添加失真模型 一 原图如下 xff1a 二 实现的效果图 三 算法具体实现 function undistorted img

  • Pytorch学习笔记（六）之完整的模型训练（以Cifar10为例）

    文章目录 前言 xff1a 数据集介绍0 准备工作 xff1a 首先导入相关包 xff0c 设置参数等1 数据预处理之增强 transforms等 2 数据的读取 Dataset amp Dataloader 3 模型的搭建 nn mode

  • 对抗攻击（Adversarial Attack）

    文章目录 对抗攻击对抗防御 对抗攻击 图片可以看成一个很长的向量 xff0c 如果在图片的每个像素上都加上一个很小的pertubation 扰动 杂讯 xff0c 再把它输入到神经网络 xff0c 这个时候分类器可能就会误判 没有被攻击的图

  • 【对抗攻击论文笔记】对抗迁移性：Delving Into Transferable Adversarial Examples And Black-Box Attacks

    文章目录 论文概述ideamethod 详细内容摘要1 介绍2 对抗深度学习和可迁移性2 1 对抗深度学习问题2 2 对抗样本生成的方法2 3 评估方法 3 非定向对抗样本3 1 基于优化3 2 基于FGSM 4 定向对抗样本5 集成的方法

  • CoCo数据集下载

    文章目录 1 介绍2 下载2 1 官网2 2 百度网盘2 3 下载到linux服务器 1 介绍 MS COCO的全称是Microsoft Common Objects in Context xff0c 起源于微软2014年的Microsof

  • 最新win10重装系统官方纯净版——2022家庭版多图详细

    文章目录 前言 xff08 碎碎念 xff09 0 设备规格1 备份2 制作启动盘2 1 准备U盘2 2 下载win10 安装包 3 重装系统3 1 插入系统安装盘 xff08 U盘 xff09 3 2 将固态硬盘分区 4 重装之后4 1

  • Java SE（十一）之异常处理（Exception）

    文章目录 异常概述1 什么是异常 xff1f 2 为什么要异常 xff1f 异常体系及分类1 运行时异常2 编译时异常 异常处理1 JVM默认处理方案2 try catch 3 throw amp throws xff08 1 xff09

  • k8s: pod volume的用法

    k8s版本 xff1a 1 22 apiVersion v1 kind Pod metadata name volume hostpath namespace dev spec containers name nginx image ngi

  • Java SE（十四）之 Java 8新特性（Lambda，Stream流，方法引用等）

    文章目录 Java 8Lambda1 概述2 应用场景3 省略规则 Stream流1 简介2 Stream流的创建3 常用中间方法4 常用终结方法5 收集Stream流 方法引用1 方法引用符 2 引用类方法 Java 8 Java8可以是

  • LeetCode之回溯算法

    文章目录 思想 amp 框架1 组合 子集和排列问题2 组合应用问题 组合 子集问题1 lc77 组合2 lc216 组合总和III3 lc39 组合总和4 lc40 组合总和II5 lc78 子集6 lc90 子集II 排列1 全排列I2

热门标签