泰安名众网络科技有限公司,网站优化标签,wordpress 大流量,核酸检测收费1.汉诺塔问题
在经典汉诺塔问题中#xff0c;有 3 根柱子及 N 个不同大小的穿孔圆盘#xff0c;盘子可以滑入任意一根柱子。一开始#xff0c;所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动…1.汉诺塔问题
在经典汉诺塔问题中有 3 根柱子及 N 个不同大小的穿孔圆盘盘子可以滑入任意一根柱子。一开始所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出移到下一根柱子; (3) 盘子只能叠在比它大的盘子上。
//确定子问题处理方式是相同的
//确定递归函数的函数头传参
//确定函数体也就子问题的处理方式
//判断函数出口class Solution {
public:void hanota(vectorint A, vectorint B, vectorint C) {int nA.size();dfs(A,B,C,n);}void dfs(vectorint A,vectorintB ,vectorint C,int n){if(n1){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* newHeadmerge(list1,list2);return newHead;}ListNode* merge(ListNode* l1,ListNode* l2){if(l1nullptr) return l2;if(l2nullptr) return l1;if(l1-vall2-val){l1-nextmerge(l1-next,l2);return l1;//返回拼好的头节点}else{l2-nextmerge(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(headnullptr||head-nextnullptr)return head;ListNode* newheadreverseList(head-next);//认为一定可以返回一个已经逆序的子链表head-next-nexthead;//让已经逆序的子序列的头节点指向子序列的上一个头节点head-nextnullptr;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(headnullptr||head-nextnullptr){return head;}ListNode* new_headhead-next;ListNode* tmphead-next-next;//小心中途修改的问题head-next-nexthead;head-nextswapPairs(tmp);return new_head;}
}; 5. Powx,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(n0) return 1.0;double retpow(x,n/2);if(n%20){return ret*ret;}else{return ret*ret*x;}}
}; 6. 布尔逻辑二叉树
class Solution {
public:bool evaluateTree(TreeNode* root) {if(root-leftnullptr){if(root-val1)return true; else return false;}bool leftevaluateTree(root-left);bool rightevaluateTree(root-right);if(root-val2){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(rootnullptr)// {// return presum;题目给的一定是有一个节点// }presumpresum*10root-val;std::coutpresumstd::endl;int ret0;//因为函数的功能是用来计算之和并返回所以不能直接presum传入此处presum只是用于记录已经遍历了的数字。if(root-leftnullptrroot-rightnullptr){return presum;}if(root-left) retdfs(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(rootnullptr)// {// return nullptr;// }if(root-left) root-leftpruneTree(root-left);if(root-right) root-rightpruneTree(root-right);if(root-leftnullptrroot-rightnullptrroot-val0)//走到头才算是树枝当树枝被剪完了自己也就是树枝的。{//delete root;rootnullptr;// 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_valLONG_MIN;bool isValidBST(TreeNode* root) {if(rootnullptr){return true;}bool leftisValidBST(root-left);if(leftfalse) return false;//剪枝bool curfalse;if(root-valprev_val){prev_valroot-val;curtrue;}if(rightfalse) return false;//剪枝bool rightisValidBST(root-right);//cout root-val;return leftrightcur;}
}; 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) {countk;return dfs(root);}int dfs(TreeNode* root){if(rootnullptr){return ret;}retdfs(root-left);if(count0){return ret;}retroot-val;count--;retdfs(root-right);return ret;}
}; 11. 二叉树的所有路径 12. 全排列
1.此处path设置为全局变量更好虽然回溯时需要修改但是节省一些空间并且效率更高。
class Solution {
public:vectorvectorint ret;vectorbool check;//用于记录哪些数字使用过了而达到剪枝的效果回溯的时候需要把使用过的数字还回去vectorint path;//这里的path最好使用全局变量vectorvectorint permute(vectorint nums) {check.resize(nums.size());dfs(nums,path);return ret;}void dfs(vectorint nums,vectorint path){if(nums.size()path.size()){ret.push_back(path);return ;}for(int i0;inums.size();i){if(check[i]true){continue;}check[i]true;vectorint tmppath;tmp.push_back(nums[i]);dfs(nums,tmp);check[i]false;}}
};
2. 修改后
class Solution {
public:vectorvectorint ret;vectorbool check;//用于记录哪些数字使用过了而达到剪枝的效果回溯的时候需要把使用过的数字还回去vectorint path;//这里的path最好使用全局变量vectorvectorint permute(vectorint nums) {check.resize(nums.size());dfs(nums,path);return ret;}void dfs(vectorint nums,vectorint path){if(nums.size()path.size()){ret.push_back(path);return ;}for(int i0;inums.size();i){if(check[i]true){continue;}check[i]true;// vectorint tmppath;// 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:vectorstring ret;string path;int i0;vectorstring binaryTreePaths(TreeNode* root) {if(rootnullptr) return ret;//假设会传入空最好不要写在dfs函数里面dfs(root,path);return ret;}void dfs(TreeNode* root,string path){pathto_string(root-val);if(root-leftnullptrroot-rightnullptr){ret.push_back(path);return;}path-;if(root-left) dfs(root-left,path);if(root-right) dfs(root-right,path);//剪枝并且达到了不会传入空的效果}
}; 14. 子集
class Solution {
public:vectorvectorint ret;vectorint path;//vectorbool check;vectorvectorint subsets(vectorint nums) {dfs(nums,0);return ret;}void dfs(vectorint nums ,int pos){ret.push_back(path);for(int ipos;inums.size();i){path.push_back(nums[i]);dfs(nums,i1);path.pop_back();}}
}; 15. 异或和按位或分清楚
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 class Solution {
public:int ret;//返回值总和int tmp0;//记录当前层异或的值int subsetXORSum(vectorint nums) {dfs(nums,0);return ret;}void dfs(vectorint nums,int pos){rettmp;for(int ipos;inums.size();i){tmp^nums[i];dfs(nums,i1);tmp^nums[i];}}
}; 16. 全排列 ||
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 class Solution {
public:vectorvectorint ret;vectorbool check;vectorint path;vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(),nums.end());check.resize(nums.size(),false);//没有上句会报错Line 84: Char 2: runtime error: store to null pointer of type std::_Bit_type (aka unsigned long) (stl_bvector.h)dfs(nums);return ret;}void dfs(vectorint nums){if(path.size()nums.size()){ret.push_back(path);return;}for(int i0;inums.size();i){if(check[i]true ||( i!0 nums[i]nums[i-1] check[i-1] false ))//check[i-1]false;说明nums[i]和nums[i-1]同层进行判断比较。{continue;}check[i]true;path.push_back(nums[i]);dfs(nums);check[i]false;path.pop_back();}}
}; 17. 电话号码
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 class Solution {
public:vectorstring ret;string path;vectorstring hash{ , , abc, def, ghi,jkl,mno,pqrs,tuv,wxyz};vectorstring letterCombinations(string digits) {if(digits.size()0){return ret;}dfs(digits,0);return ret;}void dfs(string digits,int pos){if(path.size()digits.size()){ret.push_back(path);return;}for(auto a: hash[digits[pos]-0] ){path.push_back(a);dfs(digits,pos1);path.pop_back();}}
}; 18. 括号生成
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 class Solution {
public:int max;int left,right;vectorstring ret;string path;vectorstring generateParenthesis(int n){maxn;dfs();return ret;}void dfs(){if(right max){ret.push_back(path);return;}if(left max){path.push_back(();left;dfs();--left;path.pop_back();}if(right left){path.push_back());right;dfs();right--;path.pop_back();}}
}; 19. 组合
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 class Solution {
public:int max;vectorint path;vectorvectorint ret;vectorvectorint combine(int n, int k) {maxk;dfs(1,n);return ret;}void dfs(int pos,int n){if(path.size() max ){ret.push_back(path);return;}for(int ipos;in1;i){path.push_back(i);dfs(i1,n);//是要传入i1而不是pos1path.pop_back();}}
}; 20.目标和
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
注意单单int的反复加加减减还是非常耗时的这里不是拷贝一个vector之类的对象所以反而恢复现场的操作会更慢从而超时。 class Solution {
public:// int ret0;// int path;// int now_target;// int findTargetSumWays(vectorint nums, int target) // {// now_targettarget;// dfs(0,1,nums);// return ret;// }// void dfs(int pos,int level,vectorint nums)// {// if(nums.size()1 level)// {// if(pathnow_target)// {// ret;// }// return;// }// {// pathnums[pos];// dfs(pos1,level1,nums);// path-nums[pos];// }// {// path-nums[pos];// dfs(pos1,level1,nums);// pathnums[pos];// }// }int ret0;//int path;int now_target;int findTargetSumWays(vectorint nums, int target) {int path0;now_targettarget;dfs(0,1,nums,path);return ret;}void dfs(int pos,int level,vectorint nums,int path){if(nums.size()1 level){if(pathnow_target){ret;}return;}{//pathnums[pos];dfs(pos1,level1,nums,pathnums[pos]);//path-nums[pos];}{dfs(pos1,level1,nums,path-nums[pos]);}}};
