当前位置：首页 > news >正文

leecode Hot100之回溯算法【C++速查】

news 来源：原创 2025/8/29 4:37:51

文章目录

- - [46. 全排列](https://leetcode.cn/problems/permutations/)
  - [78. 子集](https://leetcode.cn/problems/subsets/)
  - [17. 电话号码的字母组合](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/)
  - [39. 组合总和](https://leetcode.cn/problems/combination-sum/)
  - [22. 括号生成](https://leetcode.cn/problems/generate-parentheses/)[子集](https://leetcode.cn/problems/subsets/)
  - [79. 单词搜索](https://leetcode.cn/problems/word-search/)
  - [131. 分割回文串](https://leetcode.cn/problems/palindrome-partitioning/)
  - [51. N 皇后](https://leetcode.cn/problems/n-queens/)

46. 全排列

class Solution {
public:vector<vector<int>> res;  // 记录所有排列结果vector<int> track;        // 用于记录当前的排列vector<bool> vis;         // 标记数字是否已被使用int n;vector<vector<int>> permute(vector<int>& nums) {n = nums.size();// track.clear();//如果要用track[curr]=...就必须先给其赋初值track.assign(n, 0);vis.assign(n, false);dfs(nums, 0);  // 从第一个位置开始递归return res;}void dfs(vector<int>& nums, int curr) {// 如果当前排列已经完整if (curr == n) {res.push_back(track);  // 将当前排列加入结果return;}for (int i = 0; i < n; i++) {if (vis[i]) continue;  // 如果该元素已被使用，跳过// 做选择// track.push_back(nums[i]);track[curr]=nums[i];vis[i] = true;// 递归调用dfs(nums, curr + 1);// 回溯// track.pop_back();vis[i] = false;}}
};

78. 子集

class Solution {
public:vector<vector<int>> res;vector<int> track;vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0,track);return res;}void dfs(vector<int>& nums,int curr,vector<int>& track){if(curr==nums.size()){res.push_back(track);return;}//不选当前的元素dfs(nums,curr+1,track);//选当前的元素track.push_back(nums[curr]);dfs(nums,curr+1,track);track.pop_back();}};

17. 电话号码的字母组合

class Solution {
public:vector<string> letterCombinations(string digits) {vector<string> res;if(digits.empty()) return res;vector<string> list{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};string t;//传入数字串，当前位置，对应list，结果dfs(digits,0,t,list,res);return res;}void dfs(const string& digits,int curr,string t,const vector<string>& list,vector<string>& res){if(curr==digits.length()){res.push_back(t);return;} //得到数字对应的list下标idint idx=digits[curr]-'0'-2;for(char c:list[idx]){dfs(digits,curr+1,t+c,list,res);}}
};

39. 组合总和

class Solution {
public:vector<vector<int>> res;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());vector<int> state;//当前状态dfs(candidates,target,0,state);return res;}void dfs(vector<int>& candidates, int target,int start,vector<int>& state){if(target==0){res.push_back(state);return;}//继续选择for(int i=start;i<candidates.size();i++){if(target-candidates[i]<0) return;state.push_back(candidates[i]);dfs(candidates,target-candidates[i],i,state);state.pop_back();}}};

22. 括号生成子集

class Solution {
public:vector<string> res;vector<string> generateParenthesis(int n) {string state;dfs(n,n,state);return res;}void dfs(int left,int right,string state){if(!left&&!right){state.push_back(0);res.push_back(state);}if(left>=0){state+='(';dfs(left-1,right,state);state.pop_back();}if(right>left){state+=')';dfs(left,right-1,state);//string删除最后一个字符state.pop_back();}}
};

79. 单词搜索

class Solution {
public:bool exist(vector<vector<char>>& board, string word) {for(int i=0;i<board.size();i++){for(int j=0;j<board[0].size();j++){//多起点dfs查找if(dfs(board,word,0,i,j)) return true;}}return false;}int idx[4]={0,1,0,-1};int idy[4]={1,0,-1,0};bool dfs(vector<vector<char>>& board, string word,int curr,int x,int y){if(board[x][y]!=word[curr]) return false;if(word.size()-1==curr) return true;//标记为已访问char t=board[x][y];board[x][y]='.';for(int i=0;i<4;i++){// dfs(board,word,curr+1,x+idx[i],y+idy[i]);int a=x+idx[i],b=y+idy[i];if(a<0||a>board.size()-1||b<0||b>board[0].size()-1||board[a][b]=='.') continue;if(dfs(board,word,curr+1,a,b)) return true;}//恢复board[x][y]=t;return false;}
};

131. 分割回文串

const int N=1005;
bool f[N][N];
class Solution {
public:vector<vector<string>> res;vector<vector<string>> partition(string s) {int n = s.length();vector<string> current;// 初始化动态规划数组memset(f, 0, sizeof(f));// 每个单字符子串是回文for (int i = 0; i < n; i++) f[i][i] = 1; //枚举每个长度for (int len = 2; len <= n; len++) {for (int l = 0; l + len - 1 < n; l++) {int r = l + len - 1;if (s[l] == s[r] && (len == 2 || f[l+1][r-1])) f[l][r] = 1;}}// 回溯backtrack(s, 0, current);return res;}private:void backtrack(const string &s, int start, vector<string> &current) {if (start == s.length()) {res.push_back(current);return;}for (int i = start; i < s.length(); i++) {if (f[start][i]) {//判断是否为回文字符串current.push_back(s.substr(start, i - start + 1));  // 记录当前回文子串backtrack(s, i + 1, current);  // 继续回溯current.pop_back();  // 回溯时去掉最后一个回文子串}}}
};

51. N 皇后

class Solution {
public:vector<vector<string>> solveNQueens(int n) {vector<vector<string>> res;vector<string> board(n, string(n, '.'));vector<int> cols(n, 0); // 列的占用状态vector<int> diag1(2 * n - 1, 0); // 主对角线的占用状态vector<int> diag2(2 * n - 1, 0); // 副对角线的占用状态dfs(0, n, board, cols, diag1, diag2, res);return res;}private:void dfs(int row, int n, vector<string>& board, vector<int>& cols, vector<int>& diag1, vector<int>& diag2, vector<vector<string>>& res) {if (row == n) {res.push_back(board);  // 找到一个解，将其加入结果return;}for (int col = 0; col < n; col++) {int d1 = row - col + n - 1;  // 计算主对角线编号int d2 = row + col;  // 计算副对角线编号if (cols[col] || diag1[d1] || diag2[d2]) continue;  // 如果该位置被占用，跳过board[row][col] = 'Q';  // 放置皇后cols[col] = 1;  // 标记该列占用diag1[d1] = 1;  // 标记主对角线占用diag2[d2] = 1;  // 标记副对角线占用dfs(row + 1, n, board, cols, diag1, diag2, res);  // 递归尝试下一行board[row][col] = '.';  // 恢复棋盘cols[col] = 0;  // 恢复列占用状态diag1[d1] = 0;  // 恢复主对角线占用状态diag2[d2] = 0;  // 恢复副对角线占用状态}}
};

文章目录 [46. 全排列](https://leetcode.cn/problems/permutations/)[78. 子集](https://leetcode.cn/problems/subsets/)[17. 电话号码的字母组合](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/)[39. 组合总和](https://leetcode.cn/problems/combi…...

编程日记 2025/8/29 4:37:51

前端 main.js能做哪些事？

前端 main.js 的从入门到进阶摘要在前端开发中，main.js 文件是项目启动的关键入口，它承担着初始化应用、引入依赖、配置全局设置等重要职责。本文将全面介绍 main.js 的基础知识，包括其基本结构和作用，并深入探讨如何进行进阶开…...

编程日记 2025/8/29 4:26:26

JAVA Web_定义Servlet2_学生登录验证Servlet

题目页面StudentLogin.html中有一HTML的表单代码如下： <form action"studentLogin" method"post">学生姓名：<input type"text" name"stuName" value""><br>登录密码：…...

编程日记 2025/8/29 4:22:09

【信息系统项目管理师】高分论文：论信息系统项目的范围管理（电网公司保供电可视化系统）

更多内容请见：备考信息系统项目管理师-专栏介绍和目录文章目录论文1、规划范围管理2、收集需求3、定义范围4、创建工作分解结构(WBS)5、确认范围6、控制范围论文 2017年5月，我作为项目经理参加XX省电网公司保供电可视化系统应用项目的建设，该项目是2017年XX省电网信息化…...

编程日记 2025/8/29 4:24:53

如何高效查询订单销售情况与售罄率：从SQL到架构优化的全流程设计

在电商平台、SaaS多租户系统中，订单数据作为核心数据之一，承载了关键的运营指标，如销售额、商品售罄率、订单转化等。随着数据量的持续增长，如何在大数据量条件下快速、稳定地获取统计信息，成为系统设计的重点之一。本文将从查询目标分析入手，结合数据库设计优化与典型…...

编程日记 2025/8/26 5:08:35

RTT添加一个RTC时钟驱动，以DS1307为例

添加一个外部时钟芯片这里多了一个选项复制drv_rtc.c，重命名为drv_rtc_ds1307.c 添加到工程中 /*** @file drv_rtc_ds1307.c* @brief * @author jiache (wanghuan3037@fiberhome.com)* @version 1.0* @date 2025-01-08* * @copyright Copyright (c) 2025 58* */ #...

编程日记 2025/8/28 4:46:41

Leetcode 独一无二的出现次数

可以通过哈希集来判断是否独一无二，如果set中已经包含了count，那么set.add(count)会返回false class Solution {public boolean uniqueOccurrences(int[] arr) {Map<Integer, Integer> map new HashMap<>();for(int i 0; i < arr.leng…...

编程日记 2025/8/29 4:33:20

ubuntu上，e1000e,i1210有线网卡驱动安装

1，下载附属资源，解压对应的压缩包 tar zxf e1000e-<x.x.x>.tar.gz 2，进入压缩包src目录下 cd e1000e-<x.x.x>/src/ 3，安装 sudo make install 4，重启 reboot e1000e Intel官网下载地址 https://www.i…...

编程日记 2025/8/29 4:26:27

Xmind 2025 中文思维导图

Xmind 2025 中文思维导图一、介绍 Xmind ，是一款出色的思维导图和头脑风暴软件，拥有美观的智能配色方案，便于你轻松理清思路捕捉创意。丰富的导图模板及多种创意整合工具，可助力导图迸发更多活力。还拥有强大演说模式&#xff…...

编程日记 2025/8/28 17:12:53

搭载DeepSeek|暴雨AI教育一体机加速AI教育普及

近日，在全国智算大会上，暴雨公司展示了新一代 AI 教育一体机，通过全栈国产化技术与 DeepSeek 模型的深度适配，打造低成本、高性能的人工智能教育解决方案，助力 AI 教育普及与教育数字化转型。暴雨AI教育一体机&#…...

编程日记 2025/8/29 4:31:00

【字节跳动AI论文】Seaweed-7B：视频生成基础模型的高成本效益培训

摘要：本技术报告介绍了一种经济有效的视频生成基础模型训练策略。我们提出了一种中等规模的研究模型，大约有70亿个参数（7B），称为Seaweed-7B，使用665,000个H100 GPU小时从头开始训练。尽管使用适度的计算资…...

编程日记 2025/8/29 4:35:27

java 线程池：IO密集型的任务（CPU核数 * 2 + 1）,为什么这么设置，计算密集型任务（ CPU核数+1 ），为什么这么设置

文章目录 1. IO密集型任务：`CPU核数 2 + 1`为什么这样设置？示例场景：2. CPU密集型任务：`CPU核数 + 1`为什么这样设置？示例场景：3. 两者的核心差异4. 实际应用中的注意事项5. 总结在Java线程池的配置中， IO密集型和 CPU密集型任务的线程数设置逻辑存在显著差异，核心原…...

编程日记 2025/8/29 4:23:30

RabbitMQ消息的可靠性

生产者的可靠首先，我们一起分析一下消息丢失的可能性有哪些。消息从发送者发送消息，到消费者处理消息，需要经过的流程是这样的： 消息从生产者到消费者的每一步都可能导致消息丢失： ● 发送消息时丢失：…...

编程日记 2025/8/29 4:23:29

涵盖通算、智算、超算、量算！“四算合一”算力网络投入使用，效率提升20%

近日，由中国移动承建的全国首个“四算合一”算力网络调度平台日前正式投入使用。这座“数字三峡”的诞生，标志着我国算力基建完成从“单兵作战”到“军团协同”的跃迁。什么是“四算合一”？ “四算合一”是指将通用算力、智能算力、超级算…...

编程日记 2025/8/29 4:23:31

【Redis】数据结构和内部编码

先来复习一下之前学过的几个基本的全局命令： keys：用来查看匹配规则的keyexists：用来判定执行key是否存在del：删除指定的keyexpire：给key设置过期时间ttl：查询key的过期时间type：查询key对应的…...

编程日记 2025/8/26 0:24:33

考研数据结构之二叉树（一）（包含真题及解析）

考研数据结构之二叉树（一） 下期预告：后续文章将深入探讨二叉树的遍历算法与高频考点（如平衡二叉树、线索二叉树）。二叉树是数据结构中的核心内容之一，也是考研高频考点。本文将从定义和存储结构两方面展开…...

编程日记 2025/8/29 4:22:08

linux多线(进)程编程——番外1：内存映射与mmap

前言在修真世界之外，无数异世界，其中某个叫地球的异世界中，一群人对共享内存的第二种使用方式做出了讲解。内核空间与用户空间内存空间的划分 Linux操作系统下一个进程的虚拟地址空间被分为用户空间与内核空间 Linux 内核空间在内存管…...

编程日记 2025/8/29 4:28:45

旧版 VMware 虚拟机迁移至 KVM 平台-案例2

项目背景需将一台旧版 VMware 虚拟机（VMDK 格式）迁移至 KVM 虚拟化平台，具体要求如下： 格式转换：将 VMDK 转换为 QCOW2 格式。磁盘扩容：将原 40GB 磁盘扩展至 60GB。密码重置：修改 aiden 用户…...

编程日记 2025/8/27 19:26:27

六、adb通过Wifi连接

背景收集是荣耀X40,数据线原装全新的，USB连上之后，老是断，电脑一直叮咚叮咚的响个不停，试试WIFI 连接是否稳定，需要手机和电脑用相同的WIFI. 连接 1.通过 USB 连接手机和电脑(打开USB调试等这些都略过) adb device…...

编程日记 2025/8/29 4:33:19

Kafka使用方式与底层原理解析

一、Kafka简介 Apache Kafka是一个分布式流处理平台，由LinkedIn开发并开源，现已成为实时数据管道和流应用的核心组件。它具备高吞吐量、低延迟、高可扩展性等特点，广泛应用于日志收集、消息系统、流处理等领域。 1.1 Kafka核心概念 Topic&…...

编程日记 2025/8/26 12:16:23

【Python内置函数的深度解析与应用】id

目录前言：技术背景与价值当前技术痛点解决方案概述目标读者说明一、技术原理剖析核心概念图解关键技术模块技术选型对比二、实战演示环境配置要求核心代码实现1. 基础身份验证2. 不可变对象优化3. 对象生命周期追踪运行结果验证三、性能对比测试方法论量化数据…...

编程日记 2025/8/29 4:22:07

【Pandas】pandas DataFrame keys

Pandas2.2 DataFrame Indexing, iteration 方法描述DataFrame.head([n])用于返回 DataFrame 的前几行DataFrame.at快速访问和修改 DataFrame 中单个值的方法DataFrame.iat快速访问和修改 DataFrame 中单个值的方法DataFrame.loc用于基于标签（行标签和列标签&#…...

编程日记 2025/8/29 4:35:28

探索QEMU-KVM虚拟化：麒麟系统下传统与云镜像创建虚拟机的最佳实践

随着云计算和虚拟化技术的不断进步，虚拟化在管理服务器、隔离资源以及提升性能方面的好处越来越明显。麒麟操作系统Kylin OS是我们国家自己开发的操作系统，在政府机构和企业中用得很多。这篇文章会教你如何在麒麟操作系统上设置QEMU-KVM虚拟化环境&#…...

编程日记 2025/8/20 16:25:10

pycharm中调试功能讲解

一、调试前的准备工作 1. 准备一段测试代码先写一个简单的Python脚本（比如计算阶乘），故意留点问题： def factorial(n):result 1for i in range(n):result * ireturn resultprint(factorial(5)) # 预期输出120&#xff0…...

编程日记 2025/8/29 4:28:47

SimpleITK (sitk) 中查看 DICOM 文件的像素位深（8位或16位）

在 SimpleITK (sitk) 中查看 DICOM 文件的像素位深（8位或16位），可以通过以下方法实现： 方法一：通过图像像素数组的数据类型判断读取 DICOM 文件： 使用 sitk.ReadImage() 加载文件，生成图像对…...

编程日记 2025/8/29 4:30:58

day28图像处理OpenCV

文章目录一、图像预处理4 边缘填充4.1 边界复制（BORDER_REPLICATE）4.2 边界反射（BORDER_REFLECT）4.3 边界反射101（BORDER_REFLECT_101）4.4 边界常数（BORDER_CONSTANT）4.5 边界包裹&…...

编程日记 2025/8/29 4:35:29

【NLP】自然语言处理笔记

NLP的全称是Natuarl Language Processing，中文意思是自然语言处理，是人工智能领域的一个重要方向。自然语言处理（NLP）就是在机器语言和人类语言之间沟通的桥梁，以实现人机交流的目的。人类语言是抽象的信息符号，其中蕴含着丰富的语义信息，人类可以很轻松地理解其中的含…...

编程日记 2025/8/29 4:31:00

LaTeX 的pstricks-add宏绘图练习

练习。 \documentclass[10pt]{article} \usepackage{pstricks-add} \pagestyle{empty} \begin{document} \psset{xunit1.0cm,yunit1.0cm,algebraictrue,dimenmiddle,dotstyleo,dotsize5pt 0,linewidth2.pt,arrowsize3pt 2,arrowinset0.25} \begin{pspicture*}(-16.5581463…...

编程日记 2025/8/29 4:22:09

文章目录

相关文章：