代码随想录算法训练营day51|309.最佳买卖股票时机含冷冻期714.买卖股票的最佳时机含手续费 剑指offer34、36、54面试题45、61

309.最佳买卖股票时机含冷冻期

题目链接

思路：本题多了一个冷冻期，冷冻期前一天一定是具体的做卖出的操作，如果只定义了不持股的状态，就分不清具体是哪一天卖出的。

//dp[i][0]:持有股票（一、延续之前的状态 二、当天买入股票1、前一天是冷冻期2、前一天是保持卖出股票状态）这几个取max
//dp[i][1]:保持卖出股票(1、延续之前的状态2、前一天是冷冻期)取max
//dp[i][2]:卖出股票（前一天一定是持有股票的状态，然后当天做卖出的操作）
//dp[i][3]:冷冻期（前一天一定是做卖出股票的操作）
class Solution {
public:int maxProfit(vector<int>& prices) {int len=prices.size();vector<vector<int>> dp(len,vector<int>(4));dp[0][0]=-prices[0];dp[0][1]=0;dp[0][2]=0;//可以理解为当天买入当天卖出dp[0][3]=0;for(int i=1;i<len;i++){dp[i][0]=max(dp[i-1][0],max(dp[i-1][3]-prices[i],dp[i-1][1]-prices[i]));dp[i][1]=max(dp[i-1][1],dp[i-1][3]);dp[i][2]=dp[i-1][0]+prices[i];dp[i][3]=dp[i-1][2];}return max(dp[len-1][1],max(dp[len-1][2],dp[len-1][3]));}
};

本题还需要多练习。

714.买卖股票的最佳时机含手续费 

题目链接

本题和买卖股票最佳时机II的唯一的区别就是，本题的不持有股票的递推公式中，在当天做卖出操作时需要减去手续费，其他都一样。

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int len=prices.size();vector<vector<int>> dp(len,vector<int>(2));dp[0][0]=-prices[0];dp[0][1]=max(0,-fee);for(int i=1;i<len;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);}return dp[len-1][1];}
};

剑指 Offer 34. 二叉树中和为某一值的路径

题目链接

之前刷过这道题了，在二叉树中用了回溯，纠结的点有：1、主函数里要先把根节点放到path中再进行递归吗2、传入递归函数中的值是减去孩子节点值的数值吗

class Solution {
public:vector<vector<int>> result;vector<int> path;void traversal(TreeNode* root, int target){if(root->left==NULL&&root->right==NULL&&target==0){result.push_back(path);//这里显然没有进行path的收集，所以要先把节点放到路径里面return;}if(!root->left&&!root->right) return;if(root->left){path.push_back(root->left->val);target-=root->left->val;traversal(root->left,target);target+=root->left->val;path.pop_back();}if(root->right){path.push_back(root->right->val);target-=root->right->val;traversal(root->right,target);target+=root->right->val;path.pop_back();}return;}vector<vector<int>> pathSum(TreeNode* root, int target) {path.clear();result.clear();if(!root) return result;path.push_back(root->val);traversal(root,target-root->val);return result;}
};

还需要多理解，多练习。

剑指 Offer 36. 二叉搜索树与双向链表

题目链接

思路：借助一个辅助队列，将二叉搜索树中序遍历的结果放入队列中，然后依次弹出并修改指针指向即可。

class Solution {
public:void inorder(Node* node,queue<Node*>& que){if(node==NULL) return;inorder(node->left,que);que.push(node);inorder(node->right,que);}Node* treeToDoublyList(Node* root) {if(root==NULL) return root;queue<Node*> que;inorder(root,que);Node* head=que.front();que.pop();Node* pre=head;while(!que.empty()){Node* cur=que.front();que.pop();cur->left=pre;pre->right=cur;pre=cur;}pre->right=head;head->left=pre;return head;}
};

错因：开始队列里放的是节点对象本身，这时存储的是地址。我感觉这种题只要记住存储指向节点的指针就可以了，具体还有待研究。

剑指 Offer 54. 二叉搜索树的第k大节点

题目链接

方法一：提到二叉搜索树应该马上想到中序遍历，所以本题就是中序（但是是右中左）遍历二叉搜索树，将结果放入数组中，最后直接返回下标为k-1的元素即可。

class Solution {
public:void inorder(TreeNode* node,vector<int>& vec){if(node==NULL) return;inorder(node->right,vec);vec.push_back(node->val);inorder(node->left,vec);return;}int kthLargest(TreeNode* root, int k) {vector<int> vec;inorder(root,vec);return vec[k-1];}
};

方法二：直接通过k进行控制，中间节点的处理逻辑改成k--，如果k变成0了，那就不用往下递归了，直接记录res值，返回即可。（可以代入具体的值理解一下，比如k=1，那遍历到右下角最大的叶子结点后，右子树为空返回，然后进行中间结点的处理逻辑，k--，这时k变成0了，是不是应该直接记录这个值，直接返回即可，没必要继续往下递归了）

class Solution {
public:int res;void inorder(TreeNode* node,int& k){if(!node) return;inorder(node->right,k);k--;if(k==0){res=node->val;return;}inorder(node->left,k);return;}int kthLargest(TreeNode* root, int k) {inorder(root,k);return res;}
};

面试题45. 把数组排成最小的数

题目链接

自定义了一个排序规则，如果x+y<y+x，就把x排在前面（注意排序是和cmp参数的传入顺序有关），+代表拼接，不是数值相加。

class Solution {
public:static bool cmp(int a,int b){//排序和参数的传入顺序有关string as=to_string(a);string bs=to_string(b);return as+bs<bs+as;}string minNumber(vector<int>& nums) {sort(nums.begin(),nums.end(),cmp);string res;for(int x:nums) res+=to_string(x);return res;}
};

本题的具体数学推导还需继续研究。

面试题61. 扑克牌中的顺子

题目链接

思路就是对数组进行排序，从非0元素开始遍历，如果有对子的话，直接返回false。

但是本题为什么只要非零元素的最大值-最小值<=4就返回true，还是不太理解。

class Solution {
public:bool isStraight(vector<int>& nums) {if(nums.empty()) return false;//先进行排序sort(nums.begin(),nums.end());int k=0;while(nums[k]==0) k++;//如果有对子，直接返回falsefor(int i=k+1;i<nums.size();i++){if(nums[i]==nums[i-1]) return false;}return (nums.back()-nums[k])<=4;}
};