# myLeetCode

**Repository Path**: rainbowwave/my-leet-code

## Basic Information

- **Project Name**: myLeetCode
- **Description**: LeetCode刷题日记
- **Primary Language**: C++
- **License**: MulanPSL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2023-10-30
- **Last Updated**: 2024-01-16

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 贪心算法

## 题目1：分割数组为连续子序列[659]
给你一个按 非递减顺序 排列的整数数组 nums 。

请你判断是否能在将 nums 分割成 一个或多个子序列 的同时满足下述 两个 条件：

+ 每个子序列都是一个 连续递增序列（即，每个整数 恰好 比前一个整数大 1 ）。
+ 所有子序列的长度 至少 为 3 。

如果可以分割 nums 并满足上述条件，则返回 true ；否则，返回 false 。

### 方法一 贪心算法

#### 算法思路

我们维护两个哈希表，其中一个哈希表命名为nc，用于存储数组nums中的每个元素num的个数。另一个哈希表命名为tail，用于存储以num结尾的连续子序列。

1. 首先将数组nums中的每个元素作为键值存入哈希表nc中，代表了nums中每个元素的个数。
2. 之后遍历数组nums，如果nums中的某个元素num的个数大于0，num+1的个数大于0以及num+2的个数大于0。可以认定合适一个长度至少为三的连续递增子序列。然后，以num+2结尾的连续递增子序列的个数可以加1，即tail[num+2]++。同时，由于已经用掉了num,num+1和num+2，因此，nc中的对应的num、num+1和num+2的个数要减掉1。
3. 如果某个num的个数已经为0，那就跳过这个数，看下个数开始是否有连续的递增子序列。
4. 如果某个num的个数大于0，同时，以num-1结尾的递增子序列至少有一个，那么，我们就可以把这个num添加到tail[num-1]后，形成更长长度的递增子序列（这个原来的递增子序列的长度一定是大于3的，因为只有长度大于3的递增子序列tail才会加1）。添加完之后，相应的nums[num]要减1（因为这个数已经被用过了），同时tail[num-1]也要减1（因为已经有了更长的连续递增子序列，原来的就要舍弃，毕竟题目要求至少有一个递增子序列就够了）。理所当然，tail[num+1]也要加1。
5. 如果上述条件都不能满足，那自然就只能返回false了。

这里的贪心思想是尽量彼岸建立新的连续递增子序列，始终优先考虑能否在原来的基础上增加其长度。如果无法在原来的基础上增加长度，看看能否与后面的数组成连续递增子序列，如果都不满足，直接返回false。

因为如果整个数组是连续递增的，我们至少能得到一个连续递增的子序列。

#### 代码

```cpp
/*
 * @lc app=leetcode.cn id=659 lang=cpp
 *
 * [659] 分割数组为连续子序列
 */

// @lc code=start
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;
class Solution {
public:
  /**
   * @brief 长度为3的上升子序列
   *
   * @param nums
   * @return true
   * @return false
   */
  bool isPossible(vector<int> &nums) {
    unordered_map<int, int> nc, tail;
    for (auto num : nums) {
      nc[num]++;
    }

    for (auto num : nums) {
      if (nc[num] == 0) {//< 被用完的数直接跳过
        continue;
      } else if (nc[num] > 0 && tail[num - 1] > 0) {
        nc[num]--;
        tail[num - 1]--;
        tail[num]++;
      } else if (nc[num] > 0 && nc[num + 1] > 0 && nc[num + 2] > 0) {
        nc[num]--;
        nc[num + 1]--;
        nc[num + 2]--;
        tail[num + 2]++;
      } else {
        return false;
      }
    }

    return true;
  }
};
```

## 题目2：买卖股票最佳时期含手续费[714]

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

### 方法一 贪心算法

#### 算法思路

这道题目有点像脑筋急转弯，这道题的贪心思想在于每一次购买股票都要有收益（收益=卖出的价格-买进的价格-手续费），如果没有收益，那这一次就不购买股票。首先，每一次交易的手续费是固定的，因此这个手续费也可以算作买进时的成本，在第一次的时候，我们手上没有股票，因此我们买入的成本就等于股票的价格加上手续费（即股票的价格+手续费）。但是这只股票我们不一定要一直留在手上，如果说我们碰到一只成本更低的股票，那么就要毫不犹豫的换掉这只股票（注意，这里说的是换掉这只股票，而不是抛掉这只股票，相当于先看上这只股票后观望一下，然后遇到成本更低的股票就忘记之前那只，看之后的股票交易有没有收益）。如果说碰到一只股票交易有利润，立马进行交易。保证每一次都有收益。

#### 代码
```cpp
/*
 * @lc app=leetcode.cn id=714 lang=cpp
 *
 * [714] 买卖股票的最佳时机含手续费
 */

// @lc code=start
#include <iostream>
#include <vector>

using namespace std;
class Solution {
public:
  int maxProfit(vector<int> &prices, int fee) {
    int buy = prices[0] + fee; // 这里提前将手续费算入买入是的成本而不是卖出时的成本
    int profit = 0;
    for (int i = 1; i < prices.size(); i++) {
      if (prices[i] + fee < buy) { // 如果遇到一只股票成本更低，”换成“这只股票
        buy = prices[i] + fee;  // 更新新的股票成本
      } else if (prices[i] > buy) { // 如果有利润，抛掉这只股票
        profit += prices[i] - buy; // 计算利润
        buy = prices[i]; // 这里是理解的关键，问题在于，为什么这里的成本不是prices+fee？
                         // 因为在于如果后一个的股票价格更高，那么仍然是回到这里，以更高的价格卖出这个股票，由于已经减过一个手续费了，因此不用再减了。
                         // 如果后续的股票价格跌了，跌倒这个价格已经小于buy-fee之下了，那么我们可以把这只股票再”买下来”（并不是真的买下来）。
                         // 如果这只股票没有跌的很惨，也米有说涨，那其实可以不用考虑这只股票，反正也没有收益。
      }
    }
    return profit;
  }
};
```
### 方法二 动态规划
这道题其实还是有一定的理解难度的，因为他其实和我们现实生活中的股票交易不是一致的，它可以“反悔”。也就是说，当我看重一只股票，我不一定非要买它，当我卖出一只股票，我也不一定是一定要卖它。我可以观察，如果卖出他有收益，我马上卖（不是真的卖），如果后续股票价格高了，我也可以再按照这个价格卖。如果说后续有价格更低的股票（即价格加手续费比现在价格低的股票）我就一定抛出，购入（不是真的购入）这只股票。后续股票涨价了，我有收益，没有涨价，当我没买，利润还是没亏。如果说有一只股票它的价格也没涨，也没低到我可以我愿意换成这只股票，那我就不考虑它，反正也收益。
这道题如果没有股票两个字的话，可以看成求一个最长递增子序列。计算子序列最后一个和第一个值之间的差值，就可以得到最大利润。求最长递增子序列可以用动态规划的方法。（动态规划又是一个大坑o(￣┰￣*)ゞ）。不过这里不是求最长递增子序列的长度，而是最长递增子序列中最后一个和第一个的元素。这样的话问题其实更为复杂，笔者暂时不给出求解，不过可以给出一遍参考文章([求解给定序列的最长递增子序列](https://zhuanlan.zhihu.com/p/63416821 "求解给定序列的最长递增子序列"))，有兴趣的同学可以参考。

## 题目3：单调递增的数字[738]

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

### 方法一 暴力求解

没什么好说的，而且会超时。

```cpp
/*
 * @lc app=leetcode.cn id=738 lang=cpp
 *
 * [738] 单调递增的数字
 */

// @lc code=start
#include <iostream>
#include <string>

using namespace std;
class Solution {
public:
  int monotoneIncreasingDigits(int n) {
    int ans = 0;
    for (int i = n; i >= 0; i--) {
      if (isContinuous(i)) {
        ans = i;
        break;
      }
    }
    return ans;
  }
  bool isContinuous(int n) {
    string sn = to_string(n);
    for (int i = 1; i < sn.size(); i++) {
      if (sn[i] < sn[i - 1])
        return false;
    }
    return true;
  }
};
```

### 方法二 贪心算法

这套题目的贪心思想在于尽量不要更改高位的数字，从低位的数字开始改。因此，我们从低位到高位开始判断。将第一个不满足高位大于低位的值减一。这里比较难理解的在于为什么是减一？因为首先我们要满足str[i]大于str[i-1]，同时这个数又要最大，又不能大于等于原来的数。就只能先让str[i-1]减小一位才能满足这个数不大于原来的数，此外，这个数又要尽可能的大，那么str[i]就只能等于9了。

```cpp
/*
 * @lc app=leetcode.cn id=738 lang=cpp
 *
 * [738] 单调递增的数字
 */

// @lc code=start
#include <iostream>
#include <string>

using namespace std;
class Solution {
public:
  int monotoneIncreasingDigits(int n) {
    string ns = to_string(n);
    int index = ns.size();
    for (int i = ns.size() - 1; i > 0; i--) {
      if (ns[i - 1] > ns[i]) {
        ns[i - 1]--;
        index = i;
      }
    }
    for (int i = index; i < ns.size(); i++) {
      ns[i] = '9';
    }
    return stoi(ns);
  }
};
```

说实话我觉得这个题目出的不是很好，不知大家怎么看。

## 题目3：最长数对链[646]

给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。

现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。

找出并返回能够形成的 最长数对链的长度 。

你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

### 方法一 贪心

这道题目的贪心思想在于按pairs[i][1]进行排序。因为pairs[i][1]肯定是大于pairs[i][0]的。将其按pairs[i][1]进行排序后，就只需要再比较pairs[i][1]与pairs[i+1][0]之间的大小关系即可。只用关系这两个数之间的大小关系，就可得到全局最优。而只用关心这两个数之间的大小关系其关键在于排序。

### 代码

```cpp
/*
 * @lc app=leetcode.cn id=646 lang=cpp
 *
 * [646] 最长数对链
 */

// @lc code=start
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
static bool cmp(vector<int> a, vector<int> b) { return a[1] < b[1]; }
class Solution {
public:
  int findLongestChain(vector<vector<int>> &pairs) {
    int ans = 0;
    /// 排序
    sort(pairs.begin(), pairs.end(), cmp);
    int cur = INT_MIN;
    for (int i = 0; i < pairs.size(); i++) {
      if (cur < pairs[i][0]) {
        cur = pairs[i][1];
        ans++;
      }
    }
    return ans;
  }
};
```
## 题目4 一手顺子

Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。

给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌上的数值。如果她可能重新排列这些牌，返回 true ；否则，返回 false 。

### 方法一 贪心

这道题的贪心思想在于：如果尚未分组的最小数字是x，如果x存在于某个group中，那么x一定是这个group中最小的数字。因此可以将[x,x+groupsize]中的数分入一个组中。然后继续利用贪心策略。为了每次都能找到最小的数字，首先对hand进行分组。

```cpp
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution
{
public:
  bool
  isNStraightHand (vector<int> &hand, int groupSize)
  {
    int n = hand.size ();
    sort (hand.begin (),
          hand.end ()); // 这里排序的目的在于始终从最小的数开始找
    unordered_map<int, int> map_hand;
    for (int i = 0; i < n; i++)
      {
        map_hand[hand[i]]++;
      }
    for (int x : hand)
      {
        if (map_hand.count (x) == 0)
          {
            continue;
          }
        for (int i = 0; i < groupSize; i++)
          {
            if (map_hand[x + i] == 0)
              {
                return false;
              }
            else
              {
                map_hand[x + i]--;
                if (map_hand[x + i] == 0)
                  {
                    map_hand.erase (x + i);
                  }
              }
          }
      }
    return true;
  }
};
```
## 题目 5 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

### 方法一 贪心算法

这个题目想了想，觉得也可以用贪心的思想解释。即：定义首位两个指针，每次移动较小的那块板便可以得到局部最优，因为移动较短的板虽然宽度肯定减小了，但是长度有可能增加，而如果移动较长的板，那么宽度肯定减小了，而长度却有可能更短，即使变长也没有用，因为容器的体积是由最短的板决定的。

```cpp
#include <vector>
using namespace std;
class Solution
{
public:
  int
  maxArea (vector<int> &height)
  {
    int left = 0;
    int right = height.size () - 1;
    int area = 0;
    while (left < right)
      {
        int w = right - left;
        int h = min (height[right], height[left]);
        area = max (w * h, area);
        if (height[left] < height[right])
          {
            left++;
          }
        else
          {
            right--;
          }
      }
    return area;
  }
};
```

## 题目6：有效的括号字符串

### 方法一 贪心算法

想了很久都没想明白这道题的题的贪心思想是什么。

```cpp
#include <string>
#include <vector>
using namespace std;
class Solution
{
public:
  bool
  checkValidString (string s)
  {
    int maxCount = 0;
    int minCount = 0;
    for (auto c : s)
      {
        if (c == '(')
          {
            maxCount++;
            minCount++;
          }
        else if (c == ')')
          {
            maxCount--;
            minCount = max (0, minCount - 1);
            if (maxCount < 0)
              {
                return false;
              }
          }
        else
          {
            maxCount++;
            minCount = max (0, minCount - 1); 
            // 遇到右括号maxCount要减1；但是遇到*号把他当成左括号，maxCount就加1，把他当成右括号，maxCount就减1，把它当成空字符，那就不做任何操作。
          }
      }
    return minCount == 0;//如果minCount不等于0，说明没有足够的*去匹配左括号。
  }
};
```

# 双指针

## 题目1：有效三角形的个数[611]

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

### 方法一 双指针

#### 算法思路

#### 代码

```cpp
/*
 * @lc app=leetcode.cn id=611 lang=cpp
 *
 * [611] 有效三角形的个数
 */

// @lc code=start
#include <algorithm>
#include <vector>

using namespace std;
class Solution {
public:
  int triangleNumber(vector<int> &nums) {
    /// 两边之和大于第三边
    /// 两边之差小于第三边
    int left = 0;
    int right = nums.size() - 1;
    int count = 0;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++) {
      int k = i;
      for (int j = i + 1; j < nums.size(); j++) {
        while (k + 1 < nums.size() && nums[k + 1] < nums[i] + nums[j]) {
          ++k;
        }
        count += max(k - j, 0);
      }
    }
    return count;
  }
};
```