LeetCode热题100刷题10:46. 全排列、78. 子集、17. 电话号码的字母组合、39. 组合总和、138. 随机链表的复制

回溯问题

46. 全排列

全排列问题:
path
递归终止条件:path中是否已存储所有元素;
for循环处理节点集合:used=0未被使用的元素

class Solution {
public:vector<int> path;vector<vector<int>> res;void backtracking(vector<int>& nums,vector<bool>& used) {if(path.size() == nums.size()){res.push_back(path);return;}for(int i=0;i<nums.size();i++) {if(used[i]==true)continue;path.push_back(nums[i]);used[i]=true;backtracking(nums,used);used[i]=false;path.pop_back();}}vector<vector<int>> permute(vector<int>& nums) {vector<bool> used(nums.size(),false);backtracking(nums,used);return res;}
};

78. 子集

子集问题:
每个集合都需要存储到res中,
递归终止条件:可以省略,startIndex下标到达数组末尾 与for循环的条件判断一致
for循环处理的元素集合,startIndex-数组最后一个元素

class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& nums,int startIndex) {res.push_back(path);for(int i=startIndex;i<nums.size();i++) {path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums,0);return res;}
};

17. 电话号码的字母组合

这个题根据digits中给出的数字字符,从而锁定对应的字符串,对字符串中的字母进行组合,前面复习过两遍,对这个题的印象还不是很清晰,故再写一次题解:
在这里插入图片描述

class Solution {const string strSet[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:string s;vector<string> res;void backtracking(const string& digits,int index) {if(index == digits.size()) {res.push_back(s);return;}int digit = digits[index]-'0';string str = strSet[digit];for(int i=0;i<str.size();i++) {s.push_back(str[i]);backtracking(digits,index+1);s.pop_back();}}vector<string> letterCombinations(string digits) {if(digits.size()==0)return res;backtracking(digits,0);return res;}
};

39. 组合总和

元素可以多次使用,下一次元素集合的开始位置可以还是startIndex

class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& candidates,int target,int sum,int startIndex) {if(sum > target)return;if(sum == target) {res.push_back(path);return;}for(int i=startIndex;i<candidates.size();i++) {path.push_back(candidates[i]);sum+=candidates[i];backtracking(candidates,target,sum,i);sum-=candidates[i];path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {int sum=0;backtracking(candidates,target,sum,0);return res;}
};

138. 随机链表的复制

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/class Solution {
public:unordered_map<Node*,Node*> cachedNode;Node* copyRandomList(Node* head) {if(head == nullptr)return nullptr;//如果当前节点没有被拷贝if(!cachedNode.count(head)) {//新定义节点headNew保存val,Node* headNew = new Node(head->val);cachedNode[head] = headNew;//head->next 和head->random要先存在了才能指过去//利用递归完成headNew的后继节点next和随机指向节点random的拷贝headNew->next = copyRandomList(head->next);headNew->random = copyRandomList(head->random);}return cachedNode[head];}
};

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

HTML 标签简写和全称及其对应的中文说明和实例

<!DOCTYPE html> <html lang"zh-CN"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>HTML 标签简写及全称</title><style>…

Linux udp编程

我最近开了几个专栏&#xff0c;诚信互三&#xff01; > |||《算法专栏》&#xff1a;&#xff1a;刷题教程来自网站《代码随想录》。||| > |||《C专栏》&#xff1a;&#xff1a;记录我学习C的经历&#xff0c;看完你一定会有收获。||| > |||《Linux专栏》&#xff1…

效果惊人!LivePortrait开源数字人技术,让静态照片生动起来

不得了了,快手已经不是众人所知的那个短视频娱乐平台了。 可灵AI视频的风口尚未过去,又推出了LivePortrait--开源的数字人项目。LivePortrait让你的照片动起来,合成逼真的动态人像视频,阿里通义EMO不再是唯一选择。 让图像动起来 LivePortrait 主要提供了对眼睛和嘴唇动作的…

20_Inception V3深度学习图像分类算法

回顾GoogleNet:传送门 1.1 介绍 InceptionV3是Google开发的一种深度卷积神经网络架构&#xff0c;它是Inception系列网络中的第三代模型&#xff0c;由Christian Szegedy等人在论文《Rethinking the Inception Architecture for Computer Vision》中提出&#xff0c;该论文发…

gitee上传和下载idea项目的流程

环境&#xff1a;idea2022 一、上传项目 1、在gitee中新建一个仓库。 2、打开所要上传的项目的文件夹&#xff0c;点击Git Bash&#xff0c;生成.git文件夹。 3、在idea中打开所要上传的项目&#xff0c;在控制台的Terminal菜单中&#xff0c;输入git add . (注意&#xf…

解决分布式环境下session共享问题

在分布式环境下&#xff0c;session会存在两个问题 第一个问题:不同域名下&#xff0c;浏览器存储的jsessionid是没有存储的。比如登录时认证服务auth.gulimall.com存储了session&#xff0c;但是搜索服务search.gulimall.com是没有这个session的&#xff1b; 第二个问题&…

鸟类领域超大规模检测实践,基于YOLOv8轻量级检测模型开发构建超大规模生活场景下500种鸟类检测识别分析系统

关于鸟类的检测、识别相关的开发实践在前面的系列博文中也有不少的实践记录&#xff0c;感兴趣的话可以自行移步阅读即可&#xff1a; 【检测类】 《AI识鸟&#xff0c;基于YOLOv5【n/s/m/l/x】全系列参数模型开发构建工业野外场景下鸟类检测识别分析系统》 《基于轻量级YOL…

Eyes Wide Shut Exploring the Visual Shortcomings of Multimodal LLMs

Eyes Wide Shut? Exploring the Visual Shortcomings of Multimodal LLMs 近两年多模态大模型&#xff08;Multimodal LLM&#xff0c;MLLM&#xff09;取得了巨大的进展&#xff0c;能够基于图片与人类对话&#xff0c;展现出强大的识别甚至推理能力。然而&#xff0c;在某些…

游戏AI的创造思路-技术基础-蒙特卡洛树搜索(2)

接上一篇&#xff0c;让我们来看更多的例子 目录 7. 更多例子 7.1. 国际象棋实例 7.2. RTS类游戏实例 7.3. FPS类游戏实例 7. 更多例子 蒙特卡洛树搜索&#xff08;Monte Carlo Tree Search&#xff0c;MCTS&#xff09;在游戏AI中有着广泛的应用&#xff0c;尤其是在那些…

孟德尔随机化--代谢生活方式与消化道癌

写在前面 今天阅读的文献是多种暴露与某结局的孟德尔随机化&#xff0c;算是以量取胜了。 The effect of metabolism-related lifestyle and clinical risk factors on digestive system cancers in East Asian populations: a two-sample Mendelian randomization analysis …

使用tkinter拖入excel文件并显示

使用tkinter拖入excel文件并显示 效果代码 效果 代码 import tkinter as tk from tkinter import ttk from tkinterdnd2 import TkinterDnD, DND_FILES import pandas as pdclass ExcelViewerApp(TkinterDnD.Tk):def __init__(self):super().__init__()self.title("Excel…

谷歌摸鱼神器来了:推出AI会议替身,一键总结提问发言_会议预约 ai对话

饱受会议折磨的打工人&#xff0c;终于可以解放了&#xff01; 就在刚刚举办的Google Cloud Next’23大会上&#xff0c;谷歌宣布了一系列科技新进展&#xff0c;最瞩目的要属其中的“开会AI替身”了。 只需要一句“帮我参加”&#xff0c;AI就能替你开会&#xff0c;并在合适…

设计模式探索:装饰器模式

1. 装饰器模式定义 装饰器模式&#xff08;Decorator Pattern&#xff09; 装饰器模式是一种结构型设计模式&#xff0c;允许向一个对象动态添加行为。在不改变类的接口的情况下&#xff0c;装饰器模式在原始类上增加额外的职责&#xff0c;并且支持多个装饰器嵌套使用。 装…

车载聚合路由器应用场景分析

乾元通QYT-X1z车载式1U多卡聚合路由器&#xff0c;支持最多8路聚合&#xff0c;无论是应急救援&#xff0c;还是车载交通&#xff0c;任何宽带服务商无法覆盖的区域&#xff0c;聚合路由器可提供现场需要的稳定、流畅、安全的视频传输网络&#xff0c;聚合路由器可无缝接入应急…

安装nodejs | npm报错

nodejs安装步骤: 官网&#xff1a;https://nodejs.org/en/ 在官网下载nodejs: 双击下载下来的msi安装包&#xff0c;一直点next&#xff0c;我选的安装目录是默认的: 测试是否安装成功&#xff1a; 输入cmd打开命令提示符&#xff0c;输入node -v可以看到版本&#xff0c;说…

idea创建dynamic web project

由于网课老师用的是eclipse,所以又得自己找教程了…… 解决方案&#xff1a; https://blog.csdn.net/Awt_FuDongLai/article/details/115523552

有没有适合全体质猫咪的主食冻干?全价冻干:希喂大橙罐实测分享

作为一个注重猫咪身体健康和幸福感的铲屎官&#xff0c;怎么会不喂主食冻干。毕竟&#xff0c;除了猫咪爱吃外&#xff0c;高含肉量、高营养的主食冻干也能给猫咪的健康带来一系列的好处。 最近&#xff0c;我给我家猫猫们入手了一款性价比超高的主食冻干&#xff1a;希喂CPMR2…

mybatis中的标签

在MyBatis中&#xff0c;除了基本的SQL映射功能外&#xff0c;还有许多用于动态SQL构建的标签。这些标签允许我们根据不同的条件和需求构建复杂的SQL语句。主要的动态SQL标签包括<if>, <choose>, <when>, <otherwise>, <trim>, <set>, <…

deepstream段错误

&#x1f610; 错误&#xff1a; 探针中由于使用了pyds.get_nvds_buf_surface(hash(gst_buffer), frame_meta.batch_id)导致的段错误&#xff08;segmentation fault&#xff09;。 解决方式&#xff1a;

彩带插画:成都亚恒丰创教育科技有限公司

彩带插画&#xff1a;色彩斑斓的艺术世界 在浩瀚的艺术海洋中&#xff0c;彩带插画以其独特的魅力&#xff0c;如同一条绚烂的彩绸&#xff0c;轻轻拂过人们的心田&#xff0c;留下一抹抹难以忘怀的色彩。成都亚恒丰创教育科技有限公司它不仅仅是一种视觉上的享受&#xff0c;…