链表翻转
1、终止条件
2、本级递归需要做什么
3、 返回值
ListNode* reverseList(ListNode* head, ListNode* prev=nullptr) {
if (!head) {
return prev;
}
ListNode* next = head->next;
head->next = prev;
return reverseList(next, head);
}
合并链表
终止条件:当两个链表都为空时,表示我们对链表已合并完成。
如何递归:我们判断 l1 和 l2 头结点哪个更小,然后较小结点的 next 指针指向其余结点的合并结果。(调用递归)
返回值:每一层调用都返回排序好的链表头
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
if (l1->val <= l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
};
层次遍历模板
// 二叉树层次遍历代码模板
class Solution {
public:
vector<vector<int>> treeLevOrd(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<vector<int>> result;
while (!que.empty()) {
int size = que.size();
vector<int> vec; //使用vector 动态扩容
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
}
前中后序模板
// 中序
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> S;
vector<int> v;
TreeNode* rt = root;
while(rt || S.size()){
while(rt){
S.push(rt);
rt=rt->left;
}
rt=S.top();S.pop();
v.push_back(rt->val);
rt=rt->right;
}
return v;
}
//后序
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> S;
vector<int> v;
TreeNode* rt = root;
while(rt || S.size()){
while(rt){
S.push(rt->left);
v.push_back(rt->val);
rt=rt->right;
}
rt=S.top();S.pop();
}
reverse(v.begin(),v.end());
return v;
}
为何左闭右开 (链表或者二分法)
为什么要设定「左闭右开」的关系?由于题目中给定的链表为单向链表,访问后继元素十分容易,但无法直接访问前驱元素。因此在找出链表的中位数节点 \textit{mid}mid 之后,如果设定「左闭右开」的关系,我们就可以直接用 (\textit{left}, \textit{mid})(left,mid) 以及 (\textit{mid}.\textit{next}, \textit{right})(mid.next,right) 来表示左右子树对应的列表了。并且,初始的列表也可以用 (\textit{head}, \textit{null})(head,null) 方便地进行表示,其中 \textit{null}null 表示空节点。
滑动窗口模板
动态规划—股票相关问题
121、买卖股票的最佳时机 (1次交易) | 暴力解法、动态规划 |
122、买卖股票的最佳时机 II (无限次交易) | 暴力搜索、贪心算法、动态规划 |
309、最佳买卖股票时机含冷冻期 (无限次交易) | 动态规划 |
714、买卖股票的最佳时机含手续费 (无限次交易) | 动态规划 |
123、买卖股票的最佳时机 III (2次交易) | 动态规划 |
188、买卖股票的最佳时机 IV (k次交易) | 动态规划 |
上面4题可用一个通用模板, 下面2题可用一个通用模板。
思路:题目只问最大利润,没有问这几天具体哪一天买、哪一天卖,因此可以考虑使用 动态规划 的方法来解决。
买卖股票有约束,根据题目意思,有以下两个约束条件:
条件 1:你不能在买入股票前卖出股票;
条件 2:最多只允许完成一笔交易或者无限次交易。
因此 当天是否持股 是一个很重要的因素,而当前是否持股和昨天是否持股有关系,为此我们需要把 是否持股 设计到状态数组中。
状态定义:
dp[i][j]
:下标为 i 这一天结束的时候,手上持股状态为 j 时,我们持有的现金数。换种说法:dp[i][j]
表示天数 [0, i] 区间里,下标 i 这一天状态为 j 的时候能够获得的最大利润。其中:
j = 0,表示当前不持股;
j = 1,表示当前持股。
注意:下标为 i 的这一天的计算结果包含了区间 [0, i] 所有的信息,因此最后输出 dp[n- 1][0]。
dp[i][0]
:规定了今天不持股,有以下两种情况:
昨天不持股,今天什么都不做;
昨天持股,今天卖出股票(现金数增加),dp[i][1]
:规定了今天持股,有以下两种情况:
昨天持股,今天什么都不做(现金数与昨天一样);
昨天不持股,今天买入股票(注意:只允许交易一次,因此手上的现金数就是当天的股价的相反数)。
121、买卖股票的最佳时机 (1次交易)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n,vector<int>(2));
// dp[][] 第一位是从0...i天范围内 第二位是持股状态 0-不持股 1-持股 =利润
//初始化第一天 买- 卖+
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i = 1;i<n;++i)
{
// 0..i天内不持股 1. i-1天内不持股 2. i天刚好卖出
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]);
//0..i天持股 1. i-1天持股 2.i-1天不持股.
dp[i][1] = max(dp[i-1][1], -prices[i]); //(注意,只交易一次的话仅当天买,不能dp[i-1][0]-prices[i])
}
return dp[n-1][0];
}
};
122、买卖股票的最佳时机 II (无限次交易)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n =prices.size();
vector<vector<int>> dp(n,vector<int>(2));
//dp[][] 0...i内 0--不持股 1-持股 =利润
//初始化 第一天持否? //买- 卖+
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i =1;i<n;++i)
{
// 0...i内不持股 1.0..i-1内不持股 2. i-1天持股
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
// 0...i内持股
dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i]);
}
return dp[n-1][0];
}
};
309、最佳买卖股票时机含冷冻期 (无限次交易)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n,vector<int>(3));
//[][0]--持股 [][1]--不持股冷冻期 [][2]--不持股非冷冻期 =利润
// 买- 卖+
dp[0][0]=-prices[0];
dp[0][1]=0;
dp[0][2]=0;
for(int i = 1;i<n;++i)
{
//持股情况
dp[i][0]=max(dp[i-1][0],dp[i-1][2]-prices[i]);
//说明今天卖了
dp[i][1]=prices[i]+dp[i-1][0];
dp[i][2]=max(dp[i-1][2],dp[i-1][1]);
}
return max(dp[n-1][1],dp[n-1][2]);
}
};
714、买卖股票的最佳时机含手续费 (无限次交易)(与122题基本一致)
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
vector<vector<int>> dp(n,vector<int>(2));
//买- 卖+
//不持股
dp[0][0]=0;
//持股
dp[0][1]=-prices[0];
for(int i = 1;i<n;++i)
{
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
}
return dp[n-1][0];
}
};
交易2次或者交易k次的问题
123、买卖股票的最佳时机 III (2次交易)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int buy1=prices[0],sell1=0;
int buy2=prices[0],sell2=0;
for(int i = 0;i<prices.size();++i)
{
buy1 = min(buy1,prices[i]); //第一次最小buy
sell1=max(sell1,prices[i]-buy1); //第一次最大sell
buy2 = min(buy2,prices[i]-sell1); //第二次最小buy,注意要从第一次sell中减去
sell2=max(sell2,prices[i]-buy2); //第二次最大sell
}
return sell2;
}
};
188、买卖股票的最佳时机 IV (k次交易)
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
if(n < 1 || k == 0) return 0;
vector<int> buy(k,prices[0]);
vector<int> sell(k);
for(int i =1;i<n;++i)
{
buy[0] = min(buy[0],prices[i]); //每次初始化最小buy
sell[0] = max(sell[0],prices[i] - buy[0]); //每次初始化最大sell
for(int j = 1;j<k;++j) //k次交易
{
buy[j] = min(buy[j],prices[i]-sell[j-1]);
sell[j]= max(sell[j],prices[i]-buy[j]);
}
}
return sell[k-1];
}
};
91.解码方法
感觉官解有点绕的地方就是 dp 的 i 和下标的 i 相差 1,我在写的时候直接按下标来写的。其实可以这样考虑,当前位若不为 0,一定可以独立编码,所以 dp[i] = dp[i - 1],然后再去考虑能不能后两位联合编码,后两位联合编码要满足两个条件:1.前一位不为字符 ‘0’; 2.这两位构成的数小于等于 26 。如果这两个条件都满足,就在原来的基础加上联合编码的种类 dp[i] += dp[i - 2],等等!还要考虑越界的问题,也就是 i = 1 时怎么办 ?很简单,就是在前面的基础上加一,这个一指的就是后两位联合编码。
public:
int numDecodings(string s) {
int n = s.size();
if (s[0] == '0') {
return 0;
}
vector<int> dp(n);
dp[0] = 1;
for (int i = 1; i < n; ++i) {
if (s[i] != '0') {
dp[i] = dp[i - 1];
}
if (s[i - 1] != '0' && (s[i - 1] - '0') * 10 + s[i] - '0' <= 26) {
if (i > 1) {
dp[i] += dp[i - 2];
}
else {
dp[i] += 1;
}
}
}
return dp[n - 1];
}
};
646.最长数对链
很多题目的方法 通解 coin change
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
int n = pairs.size();
sort(pairs.begin(),pairs.end(),[](vector<int>& a , vector<int>& b){return a[0] == b[0] ? a[1] < b[1] : a[0] <b[0];});
vector<int> dp(n,1);
int cnt = 1;
for(int i = 1 ; i<n;++i)
{
//dp[i] = 1;
for(int j = 0 ; j <i ;++j)
{
if( pairs[i][0] > pairs[j][1])
{
dp[i] = max( dp[i] , dp[j]+1);
}
}
cnt = max ( cnt, dp[i]);
}
return cnt;
}
};
转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 351134995@qq.com