算法相关


链表翻转

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

×

喜欢就点赞,疼爱就打赏