LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 动态规划，dp[i] 表示以 nums[i] 结尾的最长子序列长度

class Solution {
 public:
  int lengthOfLIS(vector<int>& nums) {
    if (empty(nums)) {
      return 0;
    }
    vector<int> dp(size(nums), 1);
    int res = 1;
    for (int i = 0; i < size(dp); ++i) {
      for (int j = 0; j < i; ++j) {
        if (nums[i] > nums[j]) {
          dp[i] = max(dp[i], dp[j] + 1);
        }
      }
      res = max(res, dp[i]);
    }
    return res;
  }
};

• 构造序列，遍历数组，当元素比当前序列值都大则加入序列，否则用它替换序列中的第一个比它大的元素。最终这个序列的长度与最长子序列相同

1645780293

1
16
14
145
1457
14578
04578
02578
025789
023789 => 长度与最长子序列（145789）相同

该过程实际是把序列分组
当新元素比最右侧组最小的元素大时，才可以新增一组
最终能分的组数就是最长子序列长度

AB（每列为一组）
16

AB
16
 4

ABC
165
 4

ABCDE
16578
 4

ABCDE
16578
04

ABCDE
16578
04
 2

ABCDEF
165789
04
 2

ABCDEF => 最长子序列长度为 6
165789
043
 2

• 实现如下

class Solution {
 public:
  int lengthOfLIS(vector<int>& nums) {
    if (empty(nums)) {
      return 0;
    }
    vector<int> v{nums[0]};
    for (int i = 1; i < size(nums); ++i) {
      if (nums[i] > v.back()) {
        v.emplace_back(nums[i]);
      } else {
        *lower_bound(begin(v), end(v), nums[i]) = nums[i];
      }
    }
    return size(v);
  }
};