【算法系列篇】递归、搜索和回溯（三）

在这里插入图片描述

文章目录

  • 前言
  • 什么是决策树
  • 1. 全排列
    • 1.1 题目要求
    • 1.2 做题思路
    • 1.3 代码实现
  • 2. 子集
    • 2.1 题目要求
    • 2.2 做题思路
    • 2.3 代码实现
  • 3. 找出所有子集的异或总和再求和
    • 3.1 题目要求
    • 3.2 做题思路
    • 3.3 代码实现
  • 4. 全排列II
    • 4.1 题目要求
    • 4.2 做题思路
    • 4.3 代码实现

前言

前面我们通过几个题目基本了解了解决递归类问题的基本思路和步骤，相信大家对于递归多多少少有了更加深入的了解。那么本篇文章我将为大家分享结合决策树来解决递归、搜索和回溯相关的问题。

什么是决策树

决策树是一种基本的分类与回归方法。在分类问题中，决策树通过构建一棵树形图来对数据进行分类。树的每个节点表示一个特征属性，每个分支代表一个特征属性上的判断条件，每个叶节点代表一个类别。在回归问题中，决策树可以预测一个实数值。

下面是一个简单的决策树：
在这里插入图片描述
知道了什么是决策树，下面我们将运用决策树来解决实际问题。

1. 全排列

https://leetcode.cn/problems/permutations/

1.1 题目要求

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

class Solution {
    public List<List<Integer>> permute(int[] nums) {

    }
}

1.2 做题思路

相信大家肯定做过跟排列相关的问题，就是三个人坐座位的问题。第一座位可以坐A、B、C 任何一个人，如果第一个座位坐的是 A 的话，那么第二个位子 A 就不能再坐了，第二个位子就只能在 B、C 之间选择了，如果 B 选择了第二个位子，那么第三个位置就只能 C 选择了。所以这个问题通过决策树来体现的话就是这样的：

在这里插入图片描述
但是上面的图我们会发现这几种情况会有重复的情况，那么我们如何筛选掉这些重复的情况呢？可以使用一个标记数组来记录已经选择过的元素，当下一次选择的时候就选择这个标记数组中没有被选择的剩下的元素的其中一个。这道题目跟上面的例子的思路是一样的，这里我就不为大家再画一个图了。

那么这道题使用代码的思想该如何解决呢？每次递归我们还是将数组中的所有元素都给列举出来，不过我们需要根据标记数组中元素的使用情况来选择是否可以选择这个元素，如果某个元素没有被选择，那么这次就选择这个元素，将这个元素标记为已使用，然后继续递归，当当前情况列举完成之后就需要恢复现场，当路径集合中记录的元素的个数和数组中的元素个数相同的时候，就说明一种情况已经列举完成，就可以将当前情况添加进ret集合中，返回。

1.3 代码实现

class Solution {
    List<Integer> path;
    List<List<Integer>> ret;
    boolean[] vis;
    public List<List<Integer>> permute(int[] nums) {
        //对全局变量进行初始化
        path = new ArrayList<>();
        ret = new ArrayList<>();
        vis = new boolean[nums.length];
        dfs(nums);
        return ret;
    }

    private void dfs(int[] nums) {
    	//当path中元素的大小等于数组的大小，就说明一种情况已经列举完成，这事需要我们将当前path中的数据添加进ret中，并且返回
        if (path.size() == nums.length) {
            ret.add(new ArrayList<>(path));
            return;
        }
       for (int i = 0; i < nums.length; i++) {
           if (vis[i] == false) {
               path.add(nums[i]);
               //将当前元素标记为已使用
               vis[i] = true;
               //考虑该位置之后的其他元素的选择
               dfs(nums);
               //恢复现场
               path.remove(path.size() - 1);
               vis[i] = false;
           }
       }
    }
}

在这里插入图片描述

2. 子集

https://leetcode.cn/problems/subsets/

2.1 题目要求

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

class Solution {
    public List<List<Integer>> subsets(int[] nums) {

    }
}

2.2 做题思路

前面全排列中是当路径集合中的元素个数和数组中的元素的个数相同的时候视为一种情况，这道题目就不一样了，这个是数组的子集，也就是说每一种情况的元素的个数可能是不一样的，所以我们路径集合每新添加一个元素就可以视为一种情况，就需要将路径中的元素添加进ret集合中，思路跟上一道题目是类似的，都是通过决策树递归来实现的，但是呢？仔细看题目可以发现，就是集合[1,2]，[2,1]是一种情况，也就是说子集的选择跟顺序无关，那么我们又该如何避免出现重复的情况呢？

这其实也不难，想想如果是在数学中我们会怎样思考？如果当前位置我们选择了某个元素，那么后面的位置我们就从这个元素的后面元素中去选择。

在这里插入图片描述
所以通过代码体现的话，就是我们可以使用一个 pos 变量来记录当前位置选择的元素的下标，然后下一个位置选择元素递归的话，我们就从 pos 的下一个位置开始选择。

2.3 代码实现

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

    private void dfs(int[] nums, int pos) {
        //进入这个函数就可以将path中的结果添加进ret中，这样就可以将空集的情况给考虑上
        ret.add(new ArrayList<>(path));
        //循环的话，就从pos位置开始遍历
        for (int i = pos; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

在这里插入图片描述

3. 找出所有子集的异或总和再求和

https://leetcode.cn/problems/sum-of-all-subset-xor-totals/

3.1 题目要求

一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。

例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。
给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。

注意：在本题中，元素 相同 的不同子集应 多次 计数。

数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。

示例 1：

输入：nums = [1,3]
输出：6
解释：[1,3] 共有 4 个子集：
- 空子集的异或总和是 0 。
- [1] 的异或总和为 1 。
- [3] 的异或总和为 3 。
- [1,3] 的异或总和为 1 XOR 3 = 2 。
0 + 1 + 3 + 2 = 6

示例 2：

输入：nums = [5,1,6]
输出：28
解释：[5,1,6] 共有 8 个子集：
- 空子集的异或总和是 0 。
- [5] 的异或总和为 5 。
- [1] 的异或总和为 1 。
- [6] 的异或总和为 6 。
- [5,1] 的异或总和为 5 XOR 1 = 4 。
- [5,6] 的异或总和为 5 XOR 6 = 3 。
- [1,6] 的异或总和为 1 XOR 6 = 7 。
- [5,1,6] 的异或总和为 5 XOR 1 XOR 6 = 2 。
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

示例 3：

输入：nums = [3,4,5,6,7,8]
输出：480
解释：每个子集的全部异或总和值之和为 480 。

提示：

1 <= nums.length <= 12
1 <= nums[i] <= 20

class Solution {
    public int subsetXORSum(int[] nums) {

    }
}

3.2 做题思路

这道题目跟上面的子集思路基本上没什么区别，之不过上面的子集是要求出所有子集的情况，而这道题目是求出所有子集异或之后的总和。因为思路基本跟上个题一样，所以我们直接来看代码。

3.3 代码实现

class Solution {
    int path;
    int ret;
    public int subsetXORSum(int[] nums) {
        dfs(nums, 0);
        return ret;
    }

    private void dfs(int[] nums, int pos) {
        //前面是将集合添加进ret中，这里我们是将每种情况加进ret中
        ret += path;
        for (int i = pos; i < nums.length; i++) {
            //这里我们不是将新加入的元素加入到path集合中，而是将新加入的元素和之前path元素的异或的结果异或
            path ^= nums[i];
            dfs(nums, i + 1);
            //恢复现场（两个相同的元素异或，结果为0）
            path ^= nums[i];
        }
    }
}

在这里插入图片描述

4. 全排列II

https://leetcode.cn/problems/permutations-ii/

4.1 题目要求

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {

    }
}

4.2 做题思路

这道题目跟 全排列I 是不一样的，全排列I 中不存在重复的元素，但是这道题目中存在重复的元素，也就是说[1, 1, 2] 和 [1, 1, 2] 是同一个排列，这不看起来就是同一个排列吗？难道还能不同吗？其实这里的 1 不是同一个1，[1(下标为0), 1(下标为1), 2]，[1(下标为1), 1(下标为0), 2]，全排列I 中我们只需要使用一个标记数组来避免同一个元素被重复使用的情况，而这个 全排列II 中，我们还需要筛选出因元素相同而导致的相同排列的情况。那么如何筛选呢？我们来看个例子：

在这里插入图片描述

4.3 代码实现

class Solution {
    List<Integer> path;
    List<List<Integer>> ret;
    boolean[] vis;
    public List<List<Integer>> permuteUnique(int[] nums) {
        path = new ArrayList<>();
        ret = new ArrayList<>();
        vis = new boolean[nums.length];
        //首先将重复元素给排序到一起
        Arrays.sort(nums);
        dfs(nums);
        return ret;
    }

    private void dfs(int[] nums) {
        if (path.size() == nums.length) {
            ret.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (vis[i] == false && (i == 0 || (nums[i - 1] != nums[i]) || vis[i - 1] == true)) {
                path.add(nums[i]);
                vis[i] = true;
                dfs(nums);
                //恢复现场
                path.remove(path.size() - 1);
                vis[i] = false;
            }
        }
    }
}

在这里插入图片描述

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

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

相关文章

蚂蚁集团5大开源项目获开放原子 “2023快速成长开源项目”

蚂蚁集团5大开源项目获开放原子 “2023快速成长开源项目”

12月16日&#xff0c;在开放原子开源基金会主办的“2023开放原子开发者大会”上&#xff0c;蚂蚁集团主导开源的图数据库TuGraph、时序数据库CeresDB、隐私计算框架隐语SecretFlow、前端框架OpenSumi、数据域大模型开源框架DB-GPT入选“2023快速成长开源项目”。 &#xff08;图…
阅读更多...
Kafka中Ack应答级别和数据去重

Kafka中Ack应答级别和数据去重

在Kafka中&#xff0c;保证数据安全可靠的条件是&#xff1a; 数据完全可靠条件 ACK级别设置为-1 分区副本大于等于2 ISR里应答的最小副本数量大于等于2&#xff1b; Ack应答级别 可靠性总结&#xff1a; acks0&#xff0c;生产者发送过来数据就不管了&#xff0c;可靠性差…
阅读更多...
2023年国赛高教杯数学建模D题圈养湖羊的空间利用率解题全过程文档及程序

2023年国赛高教杯数学建模D题圈养湖羊的空间利用率解题全过程文档及程序

2023年国赛高教杯数学建模 D题 圈养湖羊的空间利用率 原题再现 规模化的圈养养殖场通常根据牲畜的性别和生长阶段分群饲养&#xff0c;适应不同种类、不同阶段的牲畜对空间的不同要求&#xff0c;以保障牲畜安全和健康&#xff1b;与此同时&#xff0c;也要尽量减少空间闲置所…
阅读更多...
人工智能深度学习：探索智能的深邃奥秘

人工智能深度学习：探索智能的深邃奥秘

导言 人工智能深度学习作为当今科技领域的明星&#xff0c;正引领着智能时代的浪潮。深度学习和机器学习作为人工智能领域的两大支柱&#xff0c;它们之间的关系既有协同合作&#xff0c;又存在着显著的区别。本文将深入研究深度学习在人工智能领域的角色&#xff0c;以及其在各…
阅读更多...
Android Termux安装MySQL数据库并通过内网穿透实现公网远程访问

Android Termux安装MySQL数据库并通过内网穿透实现公网远程访问

文章目录 前言1.安装MariaDB2.安装cpolar内网穿透工具3. 创建安全隧道映射mysql4. 公网远程连接5. 固定远程连接地址 前言 Android作为移动设备&#xff0c;尽管最初并非设计为服务器&#xff0c;但是随着技术的进步我们可以将Android配置为生产力工具&#xff0c;变成一个随身…
阅读更多...
鸿蒙端H5容器化建设——JSB通信机制建设

鸿蒙端H5容器化建设——JSB通信机制建设

1. 背景 2023年鸿蒙开发者大会上&#xff0c;华为宣布为了应对国外技术封锁的潜在风险&#xff0c;2024年的HarmonyOS NEXT版本中将不再兼容Android&#xff0c;并推出鸿蒙系统以及其自研的开发框架&#xff0c;形成开发生态闭环。同时&#xff0c;在更高维度上华为希望将鸿蒙…
阅读更多...
GPT-4V被超越？SEED-Bench多模态大模型测评基准更新

GPT-4V被超越？SEED-Bench多模态大模型测评基准更新

&#x1f4d6; 技术报告 SEED-Bench-1&#xff1a;https://arxiv.org/abs/2307.16125 SEED-Bench-2&#xff1a;https://arxiv.org/abs/2311.17092 &#x1f917; 测评数据 SEED-Bench-1&#xff1a;https://huggingface.co/datasets/AILab-CVC/SEED-Bench SEED-Bench-2&…
阅读更多...
基于主动安全的AIGC数据安全建设

基于主动安全的AIGC数据安全建设

面对AIGC带来的数据安全新问题&#xff0c;是不是就应该一刀切禁止AIGC的研究利用呢&#xff1f;答案是否定的。要发展AIGC&#xff0c;也要主动积极地对AIGC的数据安全进行建设。让AIGC更加安全、可靠的为用户服务。为达到此目的&#xff0c;应该从三个方面来开展AIGC的数据安…
阅读更多...
C++中的并发多线程网络通讯

C++中的并发多线程网络通讯

C中的并发多线程网络通讯 一、引言 C作为一种高效且功能强大的编程语言&#xff0c;为开发者提供了多种工具来处理多线程和网络通信。多线程编程允许多个任务同时执行&#xff0c;而网络通信则是现代应用程序的基石。本文将深入探讨如何使用C实现并发多线程网络通信&#xff…
阅读更多...
【Netty】Netty核心概念

【Netty】Netty核心概念

目录 NIO编程NIO介绍NIO和BIO的比较缓冲区(Buffer)基本介绍常用API缓冲区对象创建添加数据读取数据 通道(Channel)基本介绍Channel常用类ServerSocketChannelSocketChannel Selector (选择器)基本介绍常用API介绍示例代码 NIO 三大核心原理 Netty核心概念Netty 介绍原生 NIO 存…
阅读更多...
verilog基础语法-计数器

verilog基础语法-计数器

概述&#xff1a; 计数器是FPGA开发中最常用的电路&#xff0c;列如通讯中记录时钟个数&#xff0c;跑马灯中时间记录&#xff0c;存储器中地址的控制等等。本节给出向上计数器&#xff0c;上下计数器以及双向计数器案例。 内容 1. 向上计数器 2.向下计数器 3.向上向下计数…
阅读更多...
Minio文件服务器（上传文件）

Minio文件服务器（上传文件）

官网&#xff1a;https://www.minio.org.cn/ 开源的分布式对象存储服务器 Window安装 用户名和密码相同 创建bucket&#xff0c;并且将策略改成public 一、添加依赖 二、代码 public class FileUploadTest{public static void main(String[] args) throws Exception{//…
阅读更多...
RHEL8_Linux_Ansible常用模块的使用

RHEL8_Linux_Ansible常用模块的使用

本章主要介绍Ansible中最常见模块的使用 shell模块文件管理模块软件包管理模块服务管理模块磁盘管理模块用户管理模块防火墙管理模块 ansible的基本用法如下。 ansible 机器名 -m 模块x -a "模块的参数" 对被管理机器执行不同的操作&#xff0c;只需要调用不同的模块…
阅读更多...
做计算，找天玑算！

做计算，找天玑算！

天玑算科研服务_DFT计算_MD模拟_FEA_ML_相图计算200余位计算工程师均来自己TOP高校及科研院所&#xff0c;涉及第一性原理&#xff0c;分子动力学&#xff0c;有限元&#xff0c;机器学习&#xff0c;可为催化、电池、能源、化工、生物等重多领域提供技术支持&#xff0c;计算软…
阅读更多...
基于Springboot的旅游网站设计与实现（论文+调试+源码）

基于Springboot的旅游网站设计与实现（论文+调试+源码）

项目描述 临近学期结束&#xff0c;还是毕业设计&#xff0c;你还在做java程序网络编程&#xff0c;期末作业&#xff0c;老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。这里根据疫情当下&#xff0c;你想解决的问…
阅读更多...
虚幻学习笔记18—C++委托（多播）和事件

虚幻学习笔记18—C++委托（多播）和事件

一、前言 委托分单播和多播&#xff0c;多播就是可以绑定多个回调函数&#xff0c;然后一次性执行。这样也可以理解为啥多播没有返回值&#xff0c;多个回调函数执行后返回哪一个都是问题啊。而事件呢官方官方文档说法是“对于事件而言&#xff0c;只有定义事件的类才能调用 Br…
阅读更多...
专属配方重磅发布，蒙牛悠瑞开创中老年奶粉新征程

专属配方重磅发布，蒙牛悠瑞开创中老年奶粉新征程

随着中国老龄化现象日益加剧&#xff0c;中老年人群营养需求市场不断扩容&#xff0c;蒙牛集团2024全球合作伙伴大会奶粉事业部分会成为了备受行业关注的一个焦点&#xff0c;会上蒙牛旗下高端中老年奶粉品牌悠瑞联合中山大学发布了《中国中老年人健康状况及专属营养解决方案》…
阅读更多...
SpringCloud微服务之间如何进行调用通信的？

SpringCloud微服务之间如何进行调用通信的？

1.同步通信 RESTful API&#xff1a;RESTful 通信使用 HTTP 协议&#xff0c;以 JSON格式来传输数据&#xff0c;具有轻量级、高效、可扩展性等优势&#xff0c;是许多系统之间接口通信的首选方式。&#xff08;springcloud使用&#xff09; RPC&#xff1a;RPC&#xff08;远…
阅读更多...
羊大师之冷天喝羊的好处大揭秘！

羊大师之冷天喝羊的好处大揭秘！

最近&#xff0c;冷天喝羊已经成为了一种趋势&#xff0c;受到了越来越多人的关注与喜爱。你可能会好奇&#xff0c;为什么冷天喝羊有那么多的好处呢&#xff1f;今天小编羊大师将带大家一起探索这个问题&#xff0c;揭秘冷天喝羊带来的种种益处。 冷天喝羊对于保持身体温暖是…
阅读更多...
HarmonyOS--基础组件Button

HarmonyOS--基础组件Button

Button组件 可以包含单个子组件。 Button(label?: ResourceStr, options?: { type?: ButtonType, stateEffect?: boolean }) 1&#xff1a;文字按钮 Button(‘点击’) 2&#xff1a;自定义按钮,嵌套其它组件 Button() {Image(https://) }.type(ButtonType.Circle)
阅读更多...
最新文章

Copyright @ 2022~2023