赞
踩
1.路经总和III 没太看懂
题目描述:给定一颗二叉树,和一个整数,要求找出路径中节点和为target的路径种数。
给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。
思路:深度优先遍历!!!套路都是抽出来dfs,选择需要传的参数,在原函数中定义结果,并返回。
1.定义种类数,传入dfs
2.定义dfs函数
1.根为空,返回res
2.把根的值存入res数组。
3.定义左子树中的路径 = dfs递归左子树。 定义右子树中的路径 = dfs递归右子树。
4.对于左子树中的路径,向res中压入相加后的值,对于右子树中的路径,向res中压入相加后的值
对于res中的值,count是否要加一,取决于x是否会等于给定的sum.
递归:
1.根为空,返回0;
2.返回左右子树的递归相加,再加上当前节点的path函数调用
3.path函数,实现找路径,返回路径种数。递归左右,参数为左右子节点和除去这俩节点值的剩下值。
- //dfs 击败%5.13的对手
- class Solution {
- public:
- vector<int> dfs(TreeNode* root, int sum,int& count){
- vector<int> temp;
- if(!root) return temp;
- temp.push_back({root->val});
- auto left = dfs(root->left,sum,count);
- auto right = dfs(root->right,sum,count);
- for(auto x:left) temp.push_back(x+root->val);
- for(auto x:right) temp.push_back(x+root->val);
- for(auto x:temp) count+= x == sum;
- return temp;
- }
- int pathSum(TreeNode* root, int sum) {
- int res = 0;
- dfs(root, sum, res);
- return res;
- }
- };
-
-
-
-
-
- int path(TreeNode* root,int sum){
- if(root == nullptr) return 0;
- return (root->val == sum)
- +path(root->left,sum-root->val)
- +path(root->right,sum-root->val);
- }
- int pathSum(TreeNode* root,int sum){
- if(root == nullptr) return 0;
- return path(root,sum)
- +pathSum(root->left,sum)
- +pathSum(root->right,sum);
- }
2.买卖股票的最佳时机
题目描述:给定一个数组,每个元素分别代表该天股票价格,只买卖一次的情况下,求收益最大!
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
思路:定义diff(i)表示在第i天卖出时,股票最大收益。显然卖出价固定时,买入价越低,利润越大。
也就是说,在扫面到第i个数字时,只要能记住前i-1个数字的最小值,就可以找到最大利润。
1. 参数判断
2. 定义最小为第一个元素,最大利润为第二个元素减去最小。
3.从第三个元素起,遍历,如果第i-1个元素小于最小的,那就更新最小值。
4.定义当前最大利润,与已保存的最大利润相比较,更新!
- class Solution {
- public:
- int maxProfit(vector<int>& prices) {
- if(prices.size()<2) return 0;
- int min = prices[0];
- int maxProfit = prices[1] - min;
- maxProfit = max(maxProfit,0);
- for(int i = 2;i<prices.size();++i){
- if(prices[i-1] <min) min = prices[i-1];
- int maxTemp = prices[i] - min;
- if(maxProfit<maxTemp) maxProfit = maxTemp;
- }
- return maxProfit;
- }
- };
3.最小栈
题目描述:设计一个栈,支持push,pop,top,min操作,o(1)的时间复杂度!
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
思路:设置一个辅助栈
- class MinStack {
- public:
- /** initialize your data structure here. */
- MinStack() {
- deque<int> mindata;
- deque<int> data;
- }
-
- void push(int x) {
- data.push_back(x);
- if(mindata.size()>0&&mindata.back()<x) mindata.push_back(mindata.back());
- else mindata.push_back(x);
- }
-
- void pop() {
- if(data.size()>0&&mindata.size()>0){
- data.pop_back();
- mindata.pop_back();
- }
- }
-
- int top() {
- if(data.size()>0) return data.back();
- return -1;
- }
-
- int getMin() {
- if(data.size()>0&&mindata.size()>0){
- return mindata.back();
- }
- return -1;
- }
- private:
- deque<int> mindata;
- deque<int> data;
- };
4.对称二叉树
题目描述:给定一棵二叉树,判断它是不是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
说明:
如果你可以运用递归和迭代两种方法解决这个问题,会很加分。
思路:中序遍历LDR,而镜像中序遍历RDL,判断这两个序列是否相等!一定要考虑nullptr
1.定义一个函数,传两个一样的root
2.核心中,底层三个判断:两根都为空&&,返回true。。两根有一个为空||,返回false,两根值不相等,返回false。
3.最后递归返回,(第一个左节点,第二个右节点)&&(第一个右节点,第二个左节点);
- bool isSymmetric(TreeNode* root) {
- return isSymmetriccore(root,root);
- }
- bool isSymmetriccore(TreeNode* root1,TreeNode* root2){
- if(root1 == nullptr && root2 == nullptr) return true;
- if(root1 == nullptr || nullptr == root2) return false;
- if(root1->val != root2->val) return false;
- return isSymmetriccore(root1->left,root2->right)&&isSymmetriccore(root1->right,root2->left);
-
- }
5相交链表
题目描述:给定两个链表,找出两个链表相交的第一个节点
如下面的两个链表:
在节点 c1 开始相交。
示例 1:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
示例 2:
输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 2 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。
示例 3:
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
输入解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
解释:这两个链表不相交,因此返回 null。
注意:
如果两个链表没有交点,返回 null.
在返回结果后,两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。
思路:剑指offer面试题52
1.先得到两个链表的长度
2.再长链表上先走出多的部分
3.只要(长不为空&&短不为空&&长不等于短),那么长短同时后移。
4.得到第一个公共节点
- /**
- * Definition for singly-linked list.
- * struct ListNode {
- * int val;
- * ListNode *next;
- * ListNode(int x) : val(x), next(NULL) {}
- * };
- */
- class Solution {
- public:
- ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
- int sizeA = 0;
- int sizeB = 0;
- ListNode* p = headA;
- ListNode* q = headB;
- while(p != nullptr){sizeA++;p = p->next;} p = headA;
- while(q != nullptr){sizeB++;q = q->next;} q = headB;
- if(sizeA>sizeB){
- int k = sizeA-sizeB;
- while(k--&&p!=nullptr) p = p->next;
- while((p!=nullptr)&&(q!=nullptr)&&(p!=q)){p = p->next;q= q->next;}
- }
- else{
- int k = sizeB-sizeA;
- while(k--&&q!=nullptr) {q = q->next;}
- while((p!=nullptr)&&(q!=nullptr)&&(p!=q)){p = p->next;q= q->next;}
- }
- ListNode* temp = p;
- if(temp==nullptr) return nullptr;
- else return temp;
- }
- };
6.爬楼梯
题目描述:假设正在爬楼梯,共n阶,每次可以爬1或者2个台阶,试问共有多少种方法爬到楼顶?
示例 1:
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2:
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
思路:剑指offer上原题,动态规划dp[i] = dp[i-1]+dp[i-2]
1.三个变量解决
- class Solution {
- public:
- int climbStairs(int n) {
- if(n==1) return 1;
- if(n ==2) return 2;
- int a = 1;
- int b = 2;
- int c = a+b;
- while(n-2>0){
- c = a+b;
- a = b;
- b = c;
- n--;
- }
- return c;
- }
- };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。