算法系列--递归,回溯,剪枝的综合应用(2)

在这里插入图片描述

💕"对相爱的人来说,对方的心意,才是最好的房子。"💕
作者:Lvzi
文章主要内容:算法系列–递归,回溯,剪枝的综合应用(2)
在这里插入图片描述

大家好,今天为大家带来的是算法系列--递归,回溯,剪枝的综合应用(2)

一.括号⽣成

题目链接

括号生成

题目描述

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且有效的括号组合。

示例:

  • 输入:n = 3
    输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

  • 输入:n = 1
    输出:[“()”]

提示:

  • 1 <= n <= 8

分析:
在这里插入图片描述

代码:

class Solution {
    List<String> ret;// 返回值
    StringBuffer path;// 记录搜索路径
    int maxLevel, lcnt, rcnt;// max表示最大层数  lcnt表示左括号的数量  rcnt表示右括号的数量
    public List<String> generateParenthesis(int n) {
        ret = new ArrayList<>();
        path = new StringBuffer();
        if (n == 0) return ret;

        maxLevel = 2 * n;
        dfs(1, lcnt, rcnt,n);
        return ret;
    }

    private void dfs(int level, int lcnt, int rcnt,int n) {
        // 递归出口
        if(level > maxLevel) {
            ret.add(path.toString());
            return;
        }
    
        if(lcnt < n) {
            path.append("(");
            dfs(level + 1,lcnt+1, rcnt,n);
            path.deleteCharAt(path.length() - 1);// 回溯
        }

        if(rcnt < n && lcnt > rcnt) {
            path.append(")");
            dfs(level + 1, lcnt, rcnt+1,n);
            path.deleteCharAt(path.length() - 1);// 回溯
        }
    }
}

二.目标和

题目链接

目标和

题目描述

给你一个非负整数数组 nums 和一个整数 target

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ,然后串联起所有整数,可以构造一个表达式:

例如,nums = [2, 1] ,可以在 2 之前添加 ‘+’ ,在 1 之前添加 ‘-’ ,然后串联起来得到表达式 "+2-1"

返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

示例:

  • 输入:nums = [1,1,1,1,1], target = 3
    输出:5
    解释:一共有 5 种方法让最终目标和为 3
    -1 + 1 + 1 + 1 + 1 = 3
    +1 - 1 + 1 + 1 + 1 = 3
    +1 + 1 - 1 + 1 + 1 = 3
    +1 + 1 + 1 - 1 + 1 = 3
    +1 + 1 + 1 + 1 - 1 = 3

  • 输入:nums = [1], target = 1
    输出:1

提示:

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

分析:

思路同子集相同,子集中我们的决策策略是选不选当前的数,本题采用+当前数/-当前数

在这里插入图片描述

代码:

class Solution {
    int path, ret, target;
    public int findTargetSumWays(int[] nums, int _target) {
        target = _target;
        dfs(nums,0);
        return ret;
    }

    private void dfs(int[] nums, int pos) {
        if(pos == nums.length) {
            if(path == target)  ret += 1;
            return;
        }
        // +
        path += nums[pos];
        dfs(nums,pos + 1);
        path -= nums[pos];//回溯

        // -
        path -= nums[pos];
        dfs(nums,pos + 1);
        path += nums[pos];// 回溯
    }
}

本题的最优解法其实是动态规划,具体可见我的这篇文章
算法系列–动态规划–背包问题(2)–01背包拓展题目

(有限制条件下的组合问题,且一个数只能选择一次–01背包问题)


3.组合总和

题目链接

组合总和

题目描述

给你一个无重复元素的整数数组 candidates 和一个目标整数 target,找出 candidates 中可以使数字和为目标数 target 的所有不同组合,并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同,则两种组合是不同的。

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

示例:

  • 输入:candidates = [2,3,6,7], target = 7
    输出:[[2,2,3],[7]]
    解释:
    2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
    7 也是一个候选, 7 = 7 。
    仅有这两种组合。

  • 输入: candidates = [2,3,5], target = 8
    输出: [[2,2,2,2],[2,3,3],[3,5]]

  • 输入: candidates = [2], target = 1
    输出: []

提示:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素互不相同
  • 1 <= target <= 40

分析:
在这里插入图片描述

(如果本题是要求组合总和的最多组合数就是一个完全背包问题)

代码:

class Solution {
    List<List<Integer>> ret;
    List<Integer> path;// 保存搜索路径
    int sum, target;// sum记录搜索路径上的和
    public List<List<Integer>> combinationSum(int[] nums, int _target) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        target = _target;
        dfs(nums,0);
        return ret;
    }

    private void dfs(int[] nums, int pos) {
        if(sum >= target) {// 递归出口
            if(sum == target) {
                ret.add(new ArrayList<>(path));
            }

            return;
        }
        for(int i = pos; i < nums.length; i++) {
            path.add(nums[i]); sum += nums[i];
            dfs(nums,i);// 递归
            path.remove(path.size() - 1); sum -= nums[i];// 回溯
        }
    }
}

4.字⺟⼤⼩写全排列

题目链接

字⺟⼤⼩写全排列

题目描述

784. 字母大小写全排列

给定一个字符串 s,通过将字符串 s 中的每个字母转变大小写,我们可以获得一个新的字符串。

返回所有可能得到的字符串集合。以任意顺序返回输出。

示例:

  • 输入:s = “a1b2”
    输出:[“a1b2”, “a1B2”, “A1b2”, “A1B2”]

  • 输入: s = “3z4”
    输出: [“3z4”,“3Z4”]

提示:

  • 1 <= s.length <= 12
  • s 由小写英文字母、大写英文字母和数字组成

解题思路

这道题可以使用回溯算法来解决。我们可以逐个遍历字符串中的每个字符,然后对于每个字符有两种选择:保持原大小写或者转换大小写。通过递归实现所有可能的组合。

代码实现(Java)

class Solution {
    List<String> ret;
    StringBuffer path;
    public List<String> letterCasePermutation(String s) {
        ret = new ArrayList<>();
        path = new StringBuffer();

        dfs(s,0);
        return ret;
    }

    private void dfs(String s, int pos) {
        if(pos == s.length()) {
            ret.add(path.toString());
            return;
        }

        // 不改变
        char ch = s.charAt(pos);
        path.append(ch);
        dfs(s, pos + 1);
        path.deleteCharAt(path.length() - 1);

        // 改变(非数字字符)
        if(ch < '0' || ch > '9') {
            char tmp = change(ch);
            path.append(tmp);
            dfs(s, pos + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }

    private char change(char ch) {
        if(ch >= 'a' && ch <= 'z') return ch -= 32;
        else return ch += 32;
    }
}

5.优美的排列

题目链接

优美的排列

题目描述

526. 优美的排列

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm(下标从 1 开始),只要满足下述条件之一,该数组就是一个优美的排列:

  1. perm[i] 能够被 i 整除
  2. i 能够被 perm[i] 整除

给你一个整数 n ,返回可以构造的优美排列的数量。

示例:

输入:n = 2

输出:2

解释:

  • 第 1 个优美的排列是 [1,2]:
    • perm[1] = 1 能被 i = 1 整除
    • perm[2] = 2 能被 i = 2 整除
  • 第 2 个优美的排列是 [2,1]:
    • perm[1] = 2 能被 i = 1 整除
    • i = 2 能被 perm[2] = 1 整除

解题思路

这道题可以使用回溯算法来解决。我们可以尝试将数字填充到数组的每个位置上,同时检查当前位置是否满足条件。如果满足条件,继续递归处理下一个位置;否则,回溯到上一个位置重新尝试其他数字。

  • check[i]:用于标记数字是否被使用过
  • ret:返回值

代码实现(Java)

class Solution {
    int ret;// 返回值
    boolean[] check;// 用于标记已经使用过的数字
    public int countArrangement(int n) {
        check = new boolean[n + 1];
        dfs(1,n);
        return ret;
    }

    private void dfs(int pos, int n) {// pos是下标
        if(pos == n + 1) {// 递归出口
            ret += 1;
            return;
        }

        for(int i = 1; i <= n; i++) {
            if(check[i] == false && (pos % i == 0 || i % pos == 0)) {
                check[i] = true;// 将使用过的数字标记
                dfs(pos + 1, n);// 递归下一个位置
                check[i] = false;// 回溯
            }
        }
    }
}

在这段代码中:

  • pos 表示当前递归到的位置,也就是在填充数组时当前正在考虑的位置。
  • i 则表示尝试填充到当前位置 pos 上的数字。

具体来说:

  • pos 从1开始,代表数组中的位置,递归函数会尝试将数字填充到这些位置上。
  • i 从1到n,代表可以填充到当前位置的数字,即数组中的元素。

6. 组合

题目链接

组合

题目描述

给定两个整数 nk,返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按任何顺序返回答案。

示例 1:

输入:n = 4, k = 2
输出:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2:

输入:n = 1, k = 1
输出:[[1]]

提示:

  • 1 <= n <= 20
  • 1 <= k <= n

分析:
在这里插入图片描述

代码:

class Solution {
    List<List<Integer>> ret;
    List<Integer> path;
    int k, n;
    public List<List<Integer>> combine(int nn, int kk) {
        n = nn; k = kk;
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(1);
        return ret;
    }

    private void dfs(int start) {
        if(path.size() == k) {
            ret.add(new ArrayList<>(path));
            return;
        }

        for(int i = start; i <= n; i++) {
            path.add(i);// 添加当前数字
            dfs(i + 1);// 递归下一个数字
            path.remove(path.size() - 1);// 回溯
        }
    }
}

总结:

  • 对于递归回溯这样的问题,一定要把决策树画的详细,要明确每一步的目的是什么,是根据什么进行递归的

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/506572.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

揭秘阿里面试必问:Tomcat类加载机制解析

各位小米的小伙伴们,大家好呀!今天小米要和大家聊聊一个很有趣的话题——阿里巴巴面试题:Tomcat的类加载机制。作为一个技术爱好者,小米深知技术分享的重要性,希望通过这篇文章与大家一起深入了解Tomcat的类加载机制,加深对Java Web开发的理解,也希望能够帮助到正在准备…

五款常用在线JavaScript加密混淆工具详解:jscrambler、JShaman、jsfack、ipaguard和jjencode

摘要 本篇技术博客将介绍五款常用且好用的在线JavaScript加密混淆工具&#xff0c;包括 jscrambler、JShaman、jsfack、freejsobfuscator 和 jjencode。通过对这些工具的功能及使用方法进行详细解析&#xff0c;帮助开发人员更好地保护和加密其 JavaScript 代码&#xff0c;提…

希亦、洁盟、大宇超声波清洗机好用吗?比拼谁是性价比之王

在追求高效生活品质的今天&#xff0c;超声波清洗机以其独特的清洁技术和便捷的操作方式&#xff0c;成为了家用和商用清洁领域的新宠。尤其对于眼镜用户而言&#xff0c;一台高效的超声波清洗机不仅能够轻松去除镜片上的污渍和细菌&#xff0c;更能保护镜片不受损伤&#xff0…

一款完全免费无广告的浏览器插件

界面上的图标都支持拖拽移动位置 一、官网 官方网站 www.brtab.top 二、功能 精美的小组件 天气组件&#xff1a;可以查看不同城市的当前以及未来7天的天气变化&#xff0c;并了解当前的所有天气指数 日历组件&#xff1a;可以显示当前的日期&#xff0c;包含农历日期&…

不可不知的,数字孪生在智慧城市中的八大应用。

数字孪生是一种将物理世界和数字世界相结合的技术&#xff0c;其在新型智慧城市建设中有着广泛的应用&#xff0c;主要包括以下几个方面&#xff1a; 城市规划和设计&#xff1a; 数字孪生技术可以将城市的三维数据模型与实际场景相结合&#xff0c;帮助城市规划师和设计师更…

ROS2从入门到精通1-2:详解ROS2服务通信机制与自定义服务

目录 0 专栏介绍1 服务通信模型2 服务模型实现(C)3 服务模型实现(Python)4 自定义服务5 话题、服务通信的异同 0 专栏介绍 本专栏旨在通过对ROS2的系统学习&#xff0c;掌握ROS2底层基本分布式原理&#xff0c;并具有机器人建模和应用ROS2进行实际项目的开发和调试的工程能力。…

Linux(CentOS7)配置系统服务以及开机自启动

目录 前言 两种方式 /etc/systemd/system/ 进入 /etc/systemd/system/ 文件夹 创建 nginx.service 文件 重新加载 systemd 配置文件 ​编辑 配置开机自启 /etc/init.d/ 进入 /etc/init.d/ 文件夹 创建 mysql 文件 编写脚本内容 添加/删除系统服务 配置开机自启 …

【官方推荐】华清远见Hi3861鸿蒙开发板助力全国大学生嵌入式芯片与系统设计竞赛(海思赛道)

为提高全国高校学生在嵌入式芯片及系统设计领域和可编程逻辑器件应用领域的自主创新设计与工程实践能力&#xff0c;培养具有创新思维、具备解决复杂工程问题能力且拥有团队合作精神的优秀人才&#xff0c;全国大学生嵌入式芯片与系统设计竞赛组织委员会举办第七届&#xff08;…

唐山一日游归来

这是学习笔记的第 2481篇文章 春天了&#xff0c;开始了躁动。去哪里玩呢&#xff1f;发现大模型是个很不错的选择&#xff0c;我哥在豆包上发了需求&#xff0c;然后自动生成了如下的旅行安排&#xff0c;说实话&#xff0c;这安排还是很细致的&#xff0c;可以把原本手工搜索…

如何在电脑上录屏?简单几步轻松搞定

随着信息技术的快速发展&#xff0c;电脑录屏已经成为一项必备技能。无论是录制游戏精彩时刻、制作教程、还是保存线上会议记录&#xff0c;录屏都可以帮助你更高效地完成任务。可是如何在电脑上录屏呢&#xff1f;本文将介绍两种在电脑上录屏的方法&#xff0c;这两种方法各有…

Redis超好用可视化工具--RedisInsight工具安装

RedisInsight 保姆级安装 RedisInsight 是Redis官方出品的可视化redis管理工具&#xff0c;具有很强大的功能。接下来&#xff0c;让我们一起去完成这款炫酷工具的安装 1. RedisInsight 下载 RedisInsight 官方下载地址&#xff0c;https://redis.io/docs/connect/insight/ …

Notepad++:格式化json字符串(带转义)

目录 一、效果呈现 二、去除json字符串转义 三、格式化json字符串 一、效果呈现 格式化前 带字符串转义&#xff0c;带unicode编码字符 格式化后 二、去除json字符串转义 方法&#xff1a;采用Notepad的普通替换 第一&#xff1a;\"替换为" 第二&#xff1a;\\…

大数据-TXT文本重复行计数工具

支持系统类型&#xff1a;Windows 64位系统 Linux 64位系统 苹果64位系统 硬盘要求&#xff1a;固态硬盘&#xff08;有效剩余磁盘空间大小最低3倍于大数据文件的大小&#xff09; 内存要求&#xff1a;最低8G&#xff08;例如只有几百G数据&#xff09; 如果处理TB级大数据文…

调用第三方服务组件改造+Jmeter5.x性能压测实践

调用第三方服务组件改造Jmeter5.x性能压测实践

【opencv】教程代码 —ShapeDescriptors

检测和显示图像的轮廓 在图像中搜索并显示轮廓边缘多边形、轮廓矩形和包围圆 获取包含检测到的轮廓的椭圆和旋转的矩形 图像轮廓检测和轮廓凸包 计算图像中的轮廓的矩&#xff08;包括面积、重心等&#xff09;并进行显示 创建和绘制一个多边形图像然后计算并显示图像上每个点到…

浮点数(小数)在计算机中如何用二进制存储?

【版权声明】未经博主同意&#xff0c;谢绝转载&#xff01;&#xff08;请尊重原创&#xff0c;博主保留追究权&#xff09; https://blog.csdn.net/m0_69908381/article/details/137182814 出自【进步*于辰的博客】 注&#xff1a;为了阐述更加严谨&#xff0c;本篇文章中将使…

c语言例题,计算字符串长度,递归思想

c语言中&#xff0c;计算字符串长度算是一个比较经典的题了&#xff0c;而今天我们运用两种不同的求解方法来写出不同的程序来实现计算字符串的功能。 主函数 先看到主函数&#xff0c;主函数中设置了一串7个字符的字符串&#xff0c;而后面接下来定义了两个变量len1和len2&am…

【键值皆有序map 线段树 数学 】100240. 最小化曼哈顿距离

本文涉及知识点 键值皆有序map 线段树 数学 LeetCode100240. 最小化曼哈顿距离 给你一个下标从 0 开始的数组 points &#xff0c;它表示二维平面上一些点的整数坐标&#xff0c;其中 points[i] [xi, yi] 。 两点之间的距离定义为它们的曼哈顿距离。 请你恰好移除一个点&am…

【蓝桥杯第十三届省赛B】(部分详解)

九进制转十进制 #include <iostream> #include<math.h> using namespace std; int main() {cout << 2*pow(9,3)0*pow(9,2)2*pow(9,1)2*pow(9,0) << endl;return 0; }顺子日期 #include <iostream> using namespace std; int main() {// 请在此…

SOC内部集成网络MAC外设+ PHY网络芯片方案:MII/RMII 接口与 MDIO 接口

一. 简介 本文来了解一下常用的一种网络硬件方案&#xff1a;SOC内部集成网络MAC外设 PHY网络芯片方案。 其中涉及的 MII接口&#xff0c;RMII接口&#xff08;MII接口与RMII接口二选一&#xff09;&#xff0c;MDIO接口&#xff0c;RJ45。 二. MII/RMII 接口&#xff0c;M…