算法相关

C C++

发布时间 : 2022-08-11 22:40

字数:2.5k 阅读 :

链表翻转
合并链表
层次遍历模板
前中后序模板
为何左闭右开（链表或者二分法）
滑动窗口模板
动态规划—股票相关问题

链表翻转

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