【leetcode】深搜、暴搜、回溯、剪枝（C++）2

深搜、暴搜、回溯、剪枝（C++）2

  • 一、括号生成
    • 1、题目描述
    • 2、代码
    • 3、解析
  • 二、组合
    • 1、题目描述
    • 2、代码
    • 3、解析
  • 三、目标和
    • 1、题目描述
    • 2、代码
    • 3、解析
  • 四、组合总和
    • 1、题目描述
    • 2、代码
    • 3、解析
  • 五、字母大小写全排列
    • 1、题目描述
    • 2、代码
    • 3、解析
  • 六、优美的排列
    • 1、题目描述
    • 2、代码
    • 3、解析
  • 七、N皇后
    • 1、题目描述
    • 2、代码
    • 3、解析
  • 八、有效的数独
    • 1、题目描述
    • 2、代码
    • 3、解析

一、括号生成

1、题目描述

leetcode链接
在这里插入图片描述

2、代码

class Solution 
{
public:
    // 1、全局变量
    string path;
    vector<string> ret;
    int right = 0, left = 0, n = 0;
    vector<string> generateParenthesis(int _n) 
    {
        n = _n;
        dfs();
        return ret;
    }
    void dfs()
    {
        // 1、出口
        if(right == n)
        {
            ret.push_back(path);
            return;
        }
        // 2、添加左括号
        if(left < n)
        {
            path.push_back('(');
            left++;
            dfs();
            path.pop_back(); // 恢复现场
            left--;
        }
        if(right < left) // 3、添加右括号
        {
            path.push_back(')');
            right++;
            dfs();
            path.pop_back(); // 恢复现场
            right--;
        }
    }
};

3、解析

在这里插入图片描述

二、组合

1、题目描述

leetcode链接

在这里插入图片描述

2、代码

class Solution 
{
public:
    // 1、全局变量
    int n = 0; // 1-n
    int k = 0; // 几个数
    vector<int> path; // 路径
    vector<vector<int>> ret; // 增加的路径函数
    vector<vector<int>> combine(int _n, int _k) 
    {
        n = _n;
        k = _k;
        dfs(1); // 2、dfs
        return ret;
    }
    void dfs(int _pos)
    {
        // 1、函数递归出口
        if(path.size() == k)
        {
            ret.push_back(path);
            return;
        }
        // 2、遍历--剪枝
        for(int pos = _pos; pos <= n; pos++)
        {
            path.push_back(pos);
            dfs(pos + 1); // pos下一个数进行递归实现剪枝
            path.pop_back(); // 回溯--恢复现场         
        }
    }
};

3、解析

在这里插入图片描述

三、目标和

1、题目描述

leetcode链接
在这里插入图片描述

2、代码

全局变量的超时代码：
原因在于nums的长度最长有20，其2^20次方太大了。但是leetcode居然通过了。

class Solution 
{
public:
    // 1、全局变量
    int ret; // 返回
    int aim; // 目标值
    int path; // 路径
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        aim = target;
        dfs(nums, 0);
        return ret;
    }
    void dfs(vector<int>& nums, int pos)
    {
        // 1、递归出口
        if(pos == nums.size())
        {
            if(path == aim)
            {
                ret++;
            }
            return;
        }
        // 2、加法
        path += nums[pos];
        dfs(nums, pos + 1);
        path -= nums[pos]; // 恢复现场
        // 3、减法
        path -= nums[pos];
        dfs(nums, pos + 1);
        path += nums[pos]; // 恢复现场
    }
};

path作为参数的正确代码：

class Solution 
{
public:
    // 1、全局变量
    int ret; // 返回
    int aim; // 目标值
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        aim = target;
        dfs(nums, 0, 0);
        return ret;
    }
    void dfs(vector<int>& nums, int pos, int path)
    {
        // 1、递归出口
        if(pos == nums.size())
        {
            if(path == aim)
            {
                ret++;
            }
            return;
        }
        // 2、加法
        path += nums[pos];
        dfs(nums, pos + 1, path);
        path -= nums[pos]; // 恢复现场
        // 3、减法
        path -= nums[pos];
        dfs(nums, pos + 1, path);
        path += nums[pos]; // 恢复现场
    }
};

3、解析

在这里插入图片描述

四、组合总和

1、题目描述

leetcode链接
在这里插入图片描述

2、代码

解法一：

class Solution 
{
public:
    // 1、全局变量
    vector<vector<int>> ret; // 返回
    vector<int> path; // 路径
    int aim; // 记录target
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        aim = target;
        dfs(candidates, 0, 0);
        return ret;
    }
    void dfs(vector<int>& nums, int pos, int sum)
    {
        // 1、递归出口
        if(sum == aim)
        {
            ret.push_back(path);
            return;
        }
        if(sum > aim)
        {
            return;
        }
        // 循环
        for(int i = pos; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            sum += nums[i];
            dfs(nums, i, sum); // 还是从开始
            path.pop_back(); // 恢复现场
            sum -= nums[i];
        }
    }
};

解法二：

class Solution 
{
public:
    // 1、全局变量
    vector<vector<int>> ret; // 返回
    vector<int> path; // 路径
    int aim; // 记录target
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        aim = target;
        dfs(candidates, 0, 0);
        return ret;
    }
    void dfs(vector<int>& nums, int pos, int sum)
    {
        // 1、递归出口
        if(sum == aim)
        {
            ret.push_back(path);
            return;
        }
        if(sum > aim || pos == nums.size())
        {
            return;
        }
        // 循环
        for(int k = 0; k * nums[pos] + sum <= aim; k++)
        {
            if(k)
            {
                path.push_back(nums[pos]);
            }
            dfs(nums, pos + 1, sum + k * nums[pos]);
        }
        // 恢复现场
        for(int k = 1; k * nums[pos] + sum <= aim; k++)
        {
            path.pop_back();
        }
    }
};

3、解析

解法一：
在这里插入图片描述
解法二：
在这里插入图片描述

五、字母大小写全排列

1、题目描述

leetcode链接
在这里插入图片描述

2、代码

class Solution 
{
public:
    // 全局变量
    string path; // 路径
    vector<string> ret; // 返回
    vector<string> letterCasePermutation(string s) 
    {
        dfs(s, 0); // 将s这个字符串的第0个位置进行传参
        return ret;
    }
    void dfs(string s, int pos)
    {
        // 递归出口
        if(pos == s.length())
        {
            ret.push_back(path);
            return;
        }
        // 先记录一下当前的字母
        char ch = s[pos];
        // 不改变
        path.push_back(ch);
        dfs(s, pos + 1);
        path.pop_back(); // 恢复现场
        // 改变
        if(ch < '0' || ch > '9')
        {
            // 进行改变大小写函数
            ch = Change(ch);
            path.push_back(ch);
            dfs(s, pos + 1); // 往下一层递归
            path.pop_back(); // 恢复现场
        }
    }
    char Change(char ch)
    {
        if(ch >= 'a' && ch <= 'z')
        {
            ch -= 32;
        }
        else
        {
            ch += 32;
        }
        return ch;
    }
};

3、解析

在这里插入图片描述

六、优美的排列

1、题目描述

leetcode链接
在这里插入图片描述

2、代码

class Solution 
{
public:
    // 全局变量
    int ret; // 返回
    bool check[16]; // 判断相对应位置是true还是false
    int countArrangement(int n) 
    {
        dfs(1, n); // 下标从1开始
        return ret;
    }
    void dfs(int pos, int n)
    {
        // 递归出口
        if(pos == n + 1) // 因为是从1开始的
        {
            ret++; // 只用做数的统计即可
            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; // 恢复现场
            }
        }
    }
};

3、解析

在这里插入图片描述

七、N皇后

1、题目描述

leetcode链接

在这里插入图片描述

2、代码

class Solution 
{
public:
    // 全局变量
    bool checkcol[10]; // 列
    bool checkG1[20]; // 主对角线
    bool checkG2[20]; // 副对角线
    vector<string> path; // 路径
    vector<vector<string>> ret; // 返回
    int n; // 全局变量n
    vector<vector<string>> solveNQueens(int _n) 
    {
        n = _n;
        // 初始化棋盘
        path.resize(n);
        for(int i = 0; i < n; i++)
        {
            path[i].append(n, '.');
        }
        dfs(0);
        return ret;
    }
    void dfs(int row) // 行
    {
        // 递归出口
        if(row == n)
        {
            ret.push_back(path);
            return;
        }
        for(int col = 0; col < n; col++) // 每一行所在的列位置
        {
            if(checkcol[col] == false/*一整列*/ && checkG1[row - col + n] == false/*y-x+n*/ && checkG2[row + col] == false/*y+x*/) // 判断条件进入
            {
                path[row][col] = 'Q';
                checkcol[col] = checkG1[row - col + n] = checkG2[row + col] = true;
                dfs(row + 1);
                // 恢复现场
                path[row][col] = '.';
                checkcol[col] = checkG1[row - col + n] = checkG2[row + col] = false;
            }
        }
    }
};

3、解析

这里我们着重在剪枝方面上面的讲解，我们重点需要明白N皇后剪枝的作用，因为皇后是能吃横的一整行，竖的一整列，主对角线和副对角线一整个，这里原本是要循环四次，但是我们经过想法发现其实只需要判断三个位置即可，第一个位置是竖着的，第二个位置是主对角线，第三个位置是副对角线，因为横着的一行是不需要进行判断的，因为我们的思路是以一整行为一个视角，从左往右依次填的！我们根据简单的数学原理，主对角线是y=x+b的，而由于会出现负数情况，我们左右两边各加一个n即可，我们此时b就为：y-x+n。我们副对角线是y=-x+b，我们的b为y+x即可！那我们接下来的思路画出决策树以后只需要考虑回溯的问题，我们恢复现场只需要将用过的全部变成没用过的即可。
在这里插入图片描述

八、有效的数独

1、题目描述

leetcode链接
在这里插入图片描述

2、代码

class Solution 
{
public:
    // 全局变量
    bool row[9][10]; // 行坐标加值
    bool col[9][10]; // 列坐标加值
    bool grid[3][3][10]; // 棋盘坐标加值
    bool isValidSudoku(vector<vector<char>>& board) 
    {
        for(int i = 0; i < 9; i++) // 行
        {
            for(int j = 0; j < 9; j++) // 列
            {
                if(board[i][j] != '.') // 数字的时候
                {
                    int num = board[i][j] - '0'; // 记录一下数
                    if(row[i][num] == true || col[j][num] == true || grid[i / 3][j / 3][num] == true)
                    {
                        return false;
                    }
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                }
            }
        }
        return true;
    }
};

3、解析

在这里插入图片描述

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

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

相关文章

《合成孔径雷达成像算法与实现》Figure6.13

《合成孔径雷达成像算法与实现》Figure6.13

clc clear close all参数设置 距离向参数设置 R_eta_c 20e3; % 景中心斜距 Tr 2.5e-6; % 发射脉冲时宽 Kr 20e12; % 距离向调频率 alpha_os_r 1.2; % 距离过采样率 Nrg 320; % 距离线采样数 距离向…
阅读更多...
ChatGPT重大升级：能自动记住用户的习惯和喜好，用户有权决定是否共享数据给OpenAI

ChatGPT重大升级：能自动记住用户的习惯和喜好，用户有权决定是否共享数据给OpenAI

OpenAI刚刚宣布了ChatGPT的一项激动人心的更新&#xff01; OpenAI在ChatGPT中新加了记忆功能和用户控制选项&#xff0c;这意味着GPT能够在与用户的互动中记住之前的对话内容&#xff0c;并利用这些信息在后续的交谈中提供更加相关和定制化的回答。 这一功能目前正处于测试阶…
阅读更多...
六、Mybatis注解开发

六、Mybatis注解开发

1.MyBatis的常用注解 注解开发越来越流行&#xff0c; Mybatis也可以使用注解开发方式&#xff0c;这样就可以减少编写Mapper映射文件。Insert&#xff1a;实现新增Update&#xff1a;实现更新Delete&#xff1a;实现删除Select&#xff1a;实现查询Result&#xff1a;实现结果…
阅读更多...
BigDecimal的常用API

BigDecimal的常用API

BigDecimal用于解决浮点型运算时结果出现失真的问题。 这里0.20.1等于0.3就出现了失真 import java.math.BigDecimal; import java.math.RoundingMode;public class Test {public static void main(String[] args) {//BigDeciaml的使用&#xff1a;解决小数运算失真的问题doub…
阅读更多...
【HarmonyOS 4.0 应用开发实战】ArkTS 快速入门之常用属性(3)

【HarmonyOS 4.0 应用开发实战】ArkTS 快速入门之常用属性(3)

个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名大三在校生&#xff0c;喜欢AI编程&#x1f38b; &#x1f43b;‍❄️个人主页&#x1f947;&#xff1a;落798. &#x1f43c;个人WeChat&#xff1a;hmmwx53 &#x1f54a;️系列专栏&#xff1a;&#x1f5bc;️…
阅读更多...
【每日一题】 2024年2月汇编（上）

【每日一题】 2024年2月汇编（上）

&#x1f525;博客主页&#xff1a; A_SHOWY&#x1f3a5;系列专栏&#xff1a;力扣刷题总结录 数据结构 云计算 数字图像处理 力扣每日一题_ 【2.1】LCP 24.数字游戏 LCP 24. 数字游戏https://leetcode.cn/problems/5TxKeK/ 这个题目可以变换一下就是将一个递增的需求经过…
阅读更多...
Python-web自动化-Playwright的学习

Python-web自动化-Playwright的学习

Python-web自动化-Playwright的学习 1. 安装playwright2. 界面等待3. 自动化代码助手4. 定位元素1. css selector定位2. xpath定位3. get_by_XXX定位 5. 操作元素1. 单选框、复选框2. select下拉框3. 网页操作4. 框架页 frame5. 窗口切换6. 截屏 1. 安装playwright pip命令 pi…
阅读更多...
全闭环直播推流桌面分享远控系统

全闭环直播推流桌面分享远控系统

直播推流涉及多协议&#xff0c;多端技术栈和知识点&#xff0c;&#xff0c;想要做好并不容易&#xff0c;经过几年时间的迭代&#xff0c;终于小有成就&#xff0c;聚集了媒体服务器&#xff0c;实时会议sfu&#xff0c;远控kvm等功能。可以做一个音视频应用的瑞士小军刀。主…
阅读更多...
【MySQL】学习外键约束处理员工数据

【MySQL】学习外键约束处理员工数据

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 ​&#x1f4ab;个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-g4glZPIY0IKhiTfe {font-family:"trebuchet ms",verdana,arial,sans-serif;font-siz…
阅读更多...
每日五道java面试题之java基础篇（九）

每日五道java面试题之java基础篇（九）

目录&#xff1a; 第一题 你们项⽬如何排查JVM问题第二题 ⼀个对象从加载到JVM&#xff0c;再到被GC清除&#xff0c;都经历了什么过程&#xff1f;第三题 怎么确定⼀个对象到底是不是垃圾&#xff1f;第四题 JVM有哪些垃圾回收算法&#xff1f;第五题 什么是STW&#xff1f; 第…
阅读更多...
(14)Hive调优——合并小文件

(14)Hive调优——合并小文件

目录 一、小文件产生的原因 二、小文件的危害 三、小文件的解决方案 3.1 小文件的预防 3.1.1 减少Map数量 3.1.2 减少Reduce的数量 3.2 已存在的小文件合并 3.2.1 方式一&#xff1a;insert overwrite (推荐) 3.2.2 方式二&#xff1a;concatenate 3.2.3 方式三&#xff…
阅读更多...
VS Code中的JDK设置

VS Code中的JDK设置

在VS Code使用中&#xff0c;如果机器只安装了一个版本的JDK版本&#xff0c;一般不需要特别关注JDK 的配置&#xff0c;但是在以下状况下&#xff0c;需要对JDK进行特别的配置&#xff1a; 机器有多个JDK版本&#xff0c;不同的项目使用不同的JDK版本项目使用的JDK版本较低&a…
阅读更多...
【C/C++】2024春晚刘谦春晚魔术步骤模拟+暴力破解

【C/C++】2024春晚刘谦春晚魔术步骤模拟+暴力破解

在这个特别的除夕夜&#xff0c;我们不仅享受了与家人的温馨团聚&#xff0c;还被电视机前的春节联欢晚会深深吸引。特别是&#xff0c;魔术师刘谦的精彩表演&#xff0c;为我们带来了一场视觉和心灵的盛宴。在我的博客“【C/C】2024春晚刘谦春晚魔术步骤模拟暴力破解”中&…
阅读更多...
洛谷C++简单题小练习day12—寻找最小值小程序

洛谷C++简单题小练习day12—寻找最小值小程序

day12--寻找最小值--2.16 习题概述 题目描述 给出 n 和 n 个整数 ai​&#xff0c;求这 n 个整数中最小值是什么。 输入格式 第一行输入一个正整数 n&#xff0c;表示数字个数。 第二行输入 n 个非负整数&#xff0c;表示 1,2…a1​,a2​…an​&#xff0c;以空格隔开。 …
阅读更多...
leetcode:343.整数拆分

leetcode:343.整数拆分

解题思路&#xff1a; 拆分的越多越好&#xff08;暂且认为&#xff09;&#xff0c;尽可能拆成m个近似相等的数&#xff0c;会使得乘积最大 dp含义&#xff1a;将i进行拆分得到最大的积为dp[i] 递推公式&#xff1a;j x dp[i-j](固定j&#xff0c;只通过凑dp[i-j]进而实现所…
阅读更多...
报警产生器

报警产生器

1&#xff0e; 　实验任务 用P1.0输出1KHz和500Hz的音频信号驱动扬声器&#xff0c;作报警信号&#xff0c;要求1KHz信号响100ms&#xff0c;500Hz信号响200ms,交替进行&#xff0c;P1.7接一开关进行控制&#xff0c;当开关合上响报警信号&#xff0c;当开关断开告警信号停止&…
阅读更多...
SPI控制8_8点阵屏

SPI控制8_8点阵屏

协议与硬件概述 SPI SPI是串行外设接口&#xff08;Serial Peripheral Interface&#xff09;的缩写。是一种高速的&#xff08;10Mbps&#xff09;的&#xff0c;全双工&#xff0c;同步的通信总线&#xff0c;并且在芯片的管脚上只占用四根线。 引脚介绍 SCLK&#xff1a;…
阅读更多...
2024年【安徽省安全员C证】考试题库及安徽省安全员C证免费试题

2024年【安徽省安全员C证】考试题库及安徽省安全员C证免费试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 安徽省安全员C证考试题库根据新安徽省安全员C证考试大纲要求&#xff0c;安全生产模拟考试一点通将安徽省安全员C证模拟考试试题进行汇编&#xff0c;组成一套安徽省安全员C证全真模拟考试试题&#xff0c;学员可通过…
阅读更多...
ChatGPT高效提问—prompt实践（教师助手）

ChatGPT高效提问—prompt实践（教师助手）

ChatGPT高效提问—prompt实践&#xff08;教师助手&#xff09; 下面来看看ChatGPT在教育领域有什么用途。 首先设定ChatGPT的角色为高中教师助手。 输入prompt: ChatGPT输出&#xff1a; ​ 教师助手的角色已经设置完成。下面通过几种不同的情景演示如何使用。 1.1.1 制定…
阅读更多...
专业130+总分420+厦门大学847信号与系统考研经验厦大信息系统与通信工程，真题，大纲，参考书。

专业130+总分420+厦门大学847信号与系统考研经验厦大信息系统与通信工程，真题，大纲，参考书。

今年很幸运被厦门大学录取&#xff0c;考研专业课847信号与系统130&#xff0c;数二130&#xff0c;总分420&#xff0c;回头看这将近一年的复习&#xff0c;还是有不少经验和大家分享&#xff0c;希望对大家复习有帮助。专业课&#xff1a; 厦门大学847信号与系统在全国各高校…
阅读更多...
最新文章

Copyright @ 2022~2023