递归，搜索与回溯

1.汉诺塔问题

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

//确定子问题处理方式是相同的
//确定递归函数的函数头传参
//确定函数体也就子问题的处理方式
//判断函数出口class Solution {
public:void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {int n=A.size();dfs(A,B,C,n);}void dfs(vector<int>& A,vector<int>&B ,vector<int>& C,int n){if(n==1){C.push_back(A.back());//这里一定是要A.back(),可以画一下递归展开图A.pop_back();return;}//函数出口dfs(A,C,B,n-1);//不关心如何递归下去的，认为该函数一定能够帮我做到把a上的n-1数据借助c挪动b上C.push_back(A.back());//这里一定是要A.back(),可以画一下递归展开图A.pop_back();dfs(B,A,C,n-1);//同样认为该函数一定能把b上残留的n-1个数据借助a放到c上面}
};

2.合并升序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* newHead=merge(list1,list2);return newHead;}ListNode* merge(ListNode* l1,ListNode* l2){if(l1==nullptr) return l2;if(l2==nullptr) return l1;if(l1->val<l2->val){l1->next=merge(l1->next,l2);return l1;//返回拼好的头节点}else{l2->next=merge(l2->next,l1);return l2;}}
};

3. 反转链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {if(head==nullptr||head->next==nullptr)return head;ListNode* newhead=reverseList(head->next);//认为一定可以返回一个已经逆序的子链表head->next->next=head;//让已经逆序的子序列的头节点指向子序列的上一个头节点head->next=nullptr;return newhead;//这里newhead一直是没有移动过的，一直都是新的链表的头结点。}
};

4. 两两交换链表中的节点

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* swapPairs(ListNode* head) {if(head==nullptr||head->next==nullptr){return head;}ListNode* new_head=head->next;ListNode* tmp=head->next->next;//小心中途修改的问题head->next->next=head;head->next=swapPairs(tmp);return new_head;}
};

5. Pow（x,n）

  • -100.0 < x < 100.0
  • -2^31 <= n <= 2^31-1
  • -10^4 <= x^n <= 10^4

本题需要注意负数的情况和超int取值范围的情况

这样会语法报错。。。

class Solution {
public:double myPow(double x, int n) {return n > 0 ?pow(x,n) : 1.0/pow(x,-(long long)n );}double pow(double x,long long n){if(n==0) return 1.0;double ret=pow(x,n/2);if(n%2==0){return ret*ret;}else{return ret*ret*x;}}
};

6. 布尔逻辑二叉树

class Solution {
public:bool evaluateTree(TreeNode* root) {if(root->left==nullptr){if(root->val==1)return true; else return false;}bool left=evaluateTree(root->left);bool right=evaluateTree(root->right);if(root->val==2){return left || right;}else {return left && right;}}
};

7.根到叶子之和 

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

  • 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*///函数头设计，我们认为传入一个节点，那么就会算出此节点到所有节点的数字之和
//函数体：从上一层获得此前的所有数字组合再拼上此层，所以需要多设计一个参数来记录
//函数出口：当没有孩子的时候
class Solution {
public:int sumNumbers(TreeNode* root) {return dfs(root,0);}int dfs(TreeNode* root,int presum){// if(root==nullptr)// {//     return presum;题目给的一定是有一个节点// }presum=presum*10+root->val;std::cout<<presum<<std::endl;int ret=0;//因为函数的功能是用来计算之和并返回，所以不能直接presum传入，此处presum只是用于记录已经遍历了的数字。if(root->left==nullptr&&root->right==nullptr){return presum;}if(root->left) ret+=dfs(root->left,presum);if(root->right) ret+= dfs(root->right,presum);return ret;}
};

8.二叉树剪枝

给定一个二叉树 根节点 root ，树的每个节点的值要么是 0，要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。

节点 node 的子树为 node 本身，以及所有 node 的后代。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
//函数体设计
//返回一个已经剪枝的根节点//函数出口：当自己是空的时候返回空，处理动作一致class Solution {
public:TreeNode* pruneTree(TreeNode* root) {// if(root==nullptr)// {//     return nullptr;// }if(root->left) root->left=pruneTree(root->left);if(root->right) root->right=pruneTree(root->right);if(root->left==nullptr&&root->right==nullptr&&root->val==0)//走到头才算是树枝当树枝被剪完了自己也就是树枝的。{//delete root;root=nullptr;// return nullptr;}return root;}
};

9.验证二叉搜索树（注意剪枝）

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:
long long prev_val=LONG_MIN;bool isValidBST(TreeNode* root) {if(root==nullptr){return true;}bool left=isValidBST(root->left);if(left==false) return false;//剪枝bool cur=false;if(root->val>prev_val){prev_val=root->val;cur=true;}if(right==false) return false;//剪枝bool right=isValidBST(root->right);//cout<< root->val;return left&&right&&cur;}
};

10. 二叉搜索树第k小的元素（二叉搜索树中序遍历是一个有序序列）

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int count;int ret;int kthSmallest(TreeNode* root, int k) {count=k;return dfs(root);}int dfs(TreeNode* root){if(root==nullptr){return ret;}ret=dfs(root->left);if(count==0){return ret;}ret=root->val;count--;ret=dfs(root->right);return ret;}
};

11. 二叉树的所有路径

12. 全排列

1.此处path设置为全局变量更好，虽然回溯时需要修改，但是节省一些空间并且效率更高。：

class Solution {
public:vector<vector<int>> ret;vector<bool> check;//用于记录哪些数字使用过了而达到剪枝的效果，回溯的时候需要把使用过的数字还回去vector<int> path;//这里的path最好使用全局变量vector<vector<int>> permute(vector<int>& nums) {check.resize(nums.size());dfs(nums,path);return ret;}void dfs(vector<int>& nums,vector<int> path){if(nums.size()==path.size()){ret.push_back(path);return ;}for(int i=0;i<nums.size();i++){if(check[i]==true){continue;}check[i]=true;vector<int> tmp=path;tmp.push_back(nums[i]);dfs(nums,tmp);check[i]=false;}}
};

2. 修改后：

class Solution {
public:vector<vector<int>> ret;vector<bool> check;//用于记录哪些数字使用过了而达到剪枝的效果，回溯的时候需要把使用过的数字还回去vector<int> path;//这里的path最好使用全局变量vector<vector<int>> permute(vector<int>& nums) {check.resize(nums.size());dfs(nums,path);return ret;}void dfs(vector<int>& nums,vector<int>& path){if(nums.size()==path.size()){ret.push_back(path);return ;}for(int i=0;i<nums.size();i++){if(check[i]==true){continue;}check[i]=true;// vector<int> tmp=path;// tmp.push_back(nums[i]);path.push_back(nums[i]);dfs(nums,path);check[i]=false;//向下递归完后恢复现场path.pop_back();}}
};

13. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

13. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<string> ret;string path;int i=0;vector<string> binaryTreePaths(TreeNode* root) {if(root==nullptr) return ret;//假设会传入空，最好不要写在dfs函数里面dfs(root,path);return ret;}void dfs(TreeNode* root,string path){path+=to_string(root->val);if(root->left==nullptr&&root->right==nullptr){ret.push_back(path);return;}path+="->";if(root->left) dfs(root->left,path);if(root->right) dfs(root->right,path);//剪枝，并且达到了不会传入空的效果}
};

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

VOP —— Noise

VOP —— Noise

目录 Turbulent Noise —— 计算1D/3D类型的Noise Anti-Aliased Flow Noise —— 生成抗锯齿噪波 Anti-Aliased Noise —— 生成抗锯齿噪波 Curl Noise —— 创建divergence-free 3D噪波 Curl Noise 2D —— 创建divergence-free 2D噪波 Flow Noise —— 生成1D/3D Perli…
阅读更多...
人力资源HR 怎么选择在线人才测评工具

人力资源HR 怎么选择在线人才测评工具

测评已经是普及度很好了&#xff0c;不仅仅是大企业&#xff0c;中小企业也都在启用人才测评&#xff0c;也有叫素质测评等等&#xff0c;内容多样化。但是根本形式是一样的&#xff0c;那就是在线测评&#xff0c;目的也是一样的&#xff0c;就是为了招来最适合的职员。 而市…
阅读更多...
以太坊智能合约的历史里程碑: 从DAO到数据隐私的技术演进

以太坊智能合约的历史里程碑: 从DAO到数据隐私的技术演进

文章目录 系列文章目录前言一、时间线 项目介绍总结 前言 在短短的几年内&#xff0c;以太坊不仅成为了去中心化应用和智能合约的主导平台&#xff0c;而且也见证了区块链技术和应用的多次重大革命。本文详细回顾了自2016年至今&#xff0c;以太坊生态所经历的几个关键时刻与技…
阅读更多...
阿里云产品试用系列-容器镜像服务 ACR

阿里云产品试用系列-容器镜像服务 ACR

阿里云容器镜像服务&#xff08;简称 ACR&#xff09;是面向容器镜像、Helm Chart 等符合 OCI 标准的云原生制品安全托管及高效分发平台。 ACR 支持全球同步加速、大规模/大镜像分发加速、多代码源构建加速等全链路提效&#xff0c;与容器服务 ACK 无缝集成&#xff0c;帮助企业…
阅读更多...
Windows 基于Visual Studio 开发Qt 6 注意事项

Windows 基于Visual Studio 开发Qt 6 注意事项

前提条件&#xff1a; 1、Visual Studio 2022 社区版(免费版) 2、Qt-6.5.1版本 Qt Vistual Studio Tools下载 先打开Visual Studio 2022 社区版 &#xff1a; 点击扩展-》管理拓展按钮后&#xff0c;在搜索框中输入Qt&#xff0c;点击这里第一个扩展安装。 Qt Visual Stud…
阅读更多...
iterator和generator

iterator和generator

iterator和generator iterator es6: let/const ...展开 迭代器 是一种机制&#xff0c;比如在控制台输出Iterator是没有这个类的&#xff0c;为不同的数据结构提供迭代循环的机制。 迭代器对象&#xff1a;具备next方法&#xff0c;next能够对你指定的数据进行迭代循环&#x…
阅读更多...
gogs git 服务器极速搭建

gogs git 服务器极速搭建

背景 小型团队合作中&#xff0c;需要代码托管在内网&#xff0c;gitlab 等搭建比较复杂&#xff0c;经过一番搜寻发现gogs满足需求 基本用户管理后台管理面板&#xff0c;能在web端查看管理安装配置极简 安装配置 gogs是支持多个平台&#xff0c;这里我们选择ubuntu 1.下载git…
阅读更多...
2023-9-23 合并果子

2023-9-23 合并果子

题目链接&#xff1a;合并果子 #include <iostream> #include <algorithm> #include <queue>using namespace std;int main() {int n;cin >> n;priority_queue<int, vector<int>, greater<int>> heap;for(int i 0; i < n; i){in…
阅读更多...
Tomcat部署、优化、以及操作练习

Tomcat部署、优化、以及操作练习

一.Tomcat的基本介绍 1.1.Tomcat是什么&#xff1f; Tomcat服务器是一个免费的开放源代码的Web应用服务器&#xff0c;属于轻量级应用服务器&#xff0c;在中小型系统和并发访问用户不是很多的场合下被普遍使用&#xff0c;是开发和调试JSP程序的首选。一般来说&#xff0c;T…
阅读更多...
BUUCTF：[MRCTF2020]套娃

BUUCTF：[MRCTF2020]套娃

查看源码发现 PHP非法参数名传参问题&#xff0c;详细请参考我的这篇文章&#xff1a;谈一谈PHP中关于非法参数名传参问题 正则这里绕过使用%0a换行符绕过&#xff0c;payload: /?b.u.p.t23333%0a 得到下一步信息&#xff1a;secrettw.php 注释中的是JsFuck&#xff0c;用这…
阅读更多...
【李沐深度学习笔记】数据操作实现

【李沐深度学习笔记】数据操作实现

课程地址 数据操作实现p2 数据操作 首先导入PyTorch包&#xff08;import torch)&#xff0c;虽然叫PyTorch&#xff0c;但实际上要导入torch。 import torch张量 张量表示的是一个数值组成的数组&#xff0c;这个数组可以有很多个维度。 # 生成0-11的顺序序列构成的一维…
阅读更多...
一篇文章让你学会什么是哈希

一篇文章让你学会什么是哈希

一篇文章让你学会什么是哈希 哈希概念哈希冲突哈希函数1. 直接定址法2. 除留余数法3. 平方取中法4. 折叠法5. 随机数法6. 数学分析法 哈希冲突解决1. 闭散列1.1 线性探测1.2 二次探测 2. 开散列 开散列和闭散列对比 哈希概念 哈希在C中有广泛的应用&#xff0c;它是一种用于快…
阅读更多...
【算法与数据结构】JavaScript实现十大排序算法（二）

【算法与数据结构】JavaScript实现十大排序算法（二）

文章目录 关于排序算法快速排序堆排序计数排序桶排序基数排序 关于排序算法 稳定排序&#xff1a; 在排序过程中具有相同键值的元素&#xff0c;在排序之后仍然保持相对的原始顺序。意思就是说&#xff0c;现在有两个元素a和b&#xff0c;a排在b的前面&#xff0c;且ab&#xf…
阅读更多...
外包干了2个月，技术退步明显.......

外包干了2个月，技术退步明显.......

先说一下自己的情况&#xff0c;大专生&#xff0c;18年通过校招进入武汉某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落! 而我已经在一个企业干了四年的功能测…
阅读更多...
竞赛选题 基于深度学习的行人重识别(person reid)

竞赛选题 基于深度学习的行人重识别(person reid)

文章目录 0 前言1 技术背景2 技术介绍3 重识别技术实现3.1 数据集3.2 Person REID3.2.1 算法原理3.2.2 算法流程图 4 实现效果5 部分代码6 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 基于深度学习的行人重识别 该项目较为新颖&#xff0c;适合…
阅读更多...
前端JavaScript入门到精通，javascript核心进阶ES6语法、API、js高级等基础知识和实战 —— JS基础（四）

前端JavaScript入门到精通，javascript核心进阶ES6语法、API、js高级等基础知识和实战 —— JS基础（四）

开始吧&#xff0c;做时间的主人&#xff01; 把时间分给睡眠&#xff0c;分给书籍&#xff0c;分给运动&#xff0c; 分给花鸟树木和山川湖海&#xff0c; 分给你对这个世界的热爱&#xff0c; 而不是将自己浪费在无聊的人和事上。 思维导图 函数 为什么需要函数 <!DO…
阅读更多...
C++之类和函数权限访问总结(二百二十七)

C++之类和函数权限访问总结(二百二十七)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 人生格言&#xff1a; 人生…
阅读更多...
黑马JVM总结（十七）

黑马JVM总结（十七）

&#xff08;1&#xff09;G1_简介 下面介绍一种Grabage one的垃圾回收器&#xff0c;在jdk9的时候称为默认的回收器&#xff0c;废除了之前的CMS垃圾回收器&#xff0c;它的内部也是并发的垃圾回收器 我们可以想到堆内存过大&#xff0c;肯定会导致回收速度变慢&#xff0c;因…
阅读更多...
时序预测 | MATLAB实现NGO-GRU北方苍鹰算法优化门控循环单元时间序列预测

时序预测 | MATLAB实现NGO-GRU北方苍鹰算法优化门控循环单元时间序列预测

时序预测 | MATLAB实现NGO-GRU北方苍鹰算法优化门控循环单元时间序列预测 目录 时序预测 | MATLAB实现NGO-GRU北方苍鹰算法优化门控循环单元时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 MATLAB实现NGO-GRU北方苍鹰算法优化门控循环单元时间序列预测&#…
阅读更多...
Matlab编程中函数的重命名方法

Matlab编程中函数的重命名方法

Matlab编程中函数的重命名方法 在进行matlab编程时候&#xff0c;有时需要根据自己的习惯&#xff0c;需要对函数重命名。本文简要介绍重命名的方法。 一、重命名的方法 通过和赋值号实现&#xff0c;如下所示&#xff1a; 新函数名原函数名二、具体举例 clc clear all %将…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023