devbox
黑客灵魂
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode专题：贪心与动态规划（持续更新，已更38题）_leetcode贪心算法专题

作者：黑客灵魂 | 2024-07-10 05:35:32

赞

踩

leetcode贪心算法专题

目录

LeetCode455.分发饼干：

问题描述：

代码分析：

LeetCode376.摆动序列：

问题描述：

代码分析：

 LeetCode53.最大子数组和：

问题描述：

代码分析：

法一：暴力

法二：贪心

法三：动态规划

LeetCode.买卖股票的最佳时机系列：

LeetCode.I：

法一：暴力

法二：贪心

法三：动态规划

LeetCode.II：

法一：贪心

法二：动态规划

LeetCode.III（难）：

LeetCode.IV：

LeetCode. 含冷冻期：

LeetCode.含手续费：

LeetCode1005.K次取反后最大化的数组和：

问题描述：

代码分析：

LeetCode134.加油站：

问题描述：

代码分析：

法一：暴力

法二：全局选最优

法三：贪心

LeetCode135.分发糖果：

问题描述：

代码分析：

法一：两次遍历

LeetCode860.柠檬水找零：

问题描述：

代码分析：

LeetCode406.根据身高重建队列：

问题描述：

代码分析：

LeetCode452.用最少数量的箭引爆气球：

问题描述：

代码分析:

LeetCode435.无重叠区间：

问题描述：

代码分析：

LeetCode763.划分字母区间：

问题描述：

代码分析：

LeetCode56.合并区间：

问题描述：

代码分析：

LeetCode738.单调递增的数字：

问题描述：

代码分析：

LeetCode968.监控二叉树（难）：

问题描述：

代码分析：

LeetCode179.最大数：

问题描述：

代码分析：

LeetCode334.递增的三元子序列：

问题描述：

代码分析：

法一：双向遍历

法二：贪心

法三：贪心+二分

LeetCode300.最长递增子序列（LIS）：

问题描述：

代码分析：

法一：动态规划

法二：贪心+二分

LeetCode397.整数替换：

问题描述：

代码分析：

法一：DFS（记忆化）

法二：贪心+位运算

LeetCode421.数组中两个数的最大异或值（待解决）：

问题描述：

代码分析：

LeetCode553.最优除法：

问题描述：

代码分析：

法一：贪心

法二：区间dp求具体方案

LeetCode564.寻找最近的回文数（难）：

问题描述：

代码分析：

LeetCode630.课程表III：

问题描述：

代码分析：

贪心+优先队列：

LeetCode646.最长数对链：

问题描述：

代码分析：

法一：LIS动态规划

法二：贪心+二分

法三：贪心

LeetCode698.划分为k个相等的子集：

问题描述：

代码分析：

法一：DFS+剪枝

法二：状压+记忆化搜索

法三：状压+动态规划

LeetCode1723.完成所有工作的最短时间：

问题描述：

代码分析：

法一：二分+回溯+剪枝

法二：状压+动态规划

LeetCode757.设置交集大小至少为2：

问题描述：

代码分析：

贪心：

LeetCode765.情侣牵手：

问题描述：

代码分析：

法一：并查集

法二：反向索引

LeetCode768.最多能完成排序的块：

问题描述：

代码分析：

法一：辅助栈

法二：前缀与后缀

法三：排序+哈希

LeetCode781.森林中的兔子：

问题描述：

代码分析：

LeetCode807.保持城市天际线：

问题描述：

代码分析：

LeetCode870.优势洗牌：

问题描述：

代码分析：

LeetCode871.最低加油次数：

问题描述：

代码分析：

法一：动态规划

持续更新......（60000字）

LeetCode455.分发饼干：

问题描述：

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

代码分析：

        为了满足更多的小孩，就不要造成饼干尺寸的浪费。

        大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。

        局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

        可以尝试使用贪心策略，先将饼干数组和小孩数组排序。然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。

        这个例子可以看出饼干 9 只有喂给胃口为 7 的小孩，这样才是整体最优解，并想不出反例,差不多是这回事，就可以了。

  1. class Solution {
  2. public:
  3.     int findContentChildren(vector<int>& g, vector<int>& s) {
  4.         sort(g.begin(), g.end());
  5.         sort(s.begin(), s.end());
  6.         int index = s.size() - 1;
  7.         int result = 0;
  8.         for(int i = g.size() - 1; i >= 0; i--) { //for循环遍历胃口，游标index遍历饼干尺寸
  9.             if(index >= 0 && s[index] >= g[i]) {
  10.                 result++;
  11.                 index--;
  12.             }
  13.         }
  14.         return result;
  15.     }
  16. };

        时间复杂度为 O(n * logn)。注意游标 index 的使用省去了一个for循环，降低了复杂度和逻辑难度。

        能否先遍历饼干再遍历胃口？如果这样写，则必须修改贪心逻辑为【小饼干先喂饱小胃口】！

LeetCode376.摆动序列：

问题描述：

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

  • 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

  • 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1：

输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2：

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

代码分析：

        本题的贪心策略体现在：如何从原始序列中删除一些元素来使得剩余元素形成最长摆动序列。

        局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。

        整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

        本题是个简单题，所以思考简单点即可，追求细致而又透彻的可以去看代码随想录。

  1. class Solution {
  2.     public int wiggleMaxLength(int[] nums) {
  3.         if(nums == null)  return 0;
  4.         if(nums.length < 2) return nums.length;
  5.         int sum = 1;
  6.         Boolean direction = null;
  7.         for(int i = 1; i < nums.length; ++i) {
  8.             if(nums[i] == nums[i - 1]) continue;
  9.             if(nums[i] - nums[i - 1] > 0) {
  10.                 if(direction != null && direction) continue; //上一次是正值
  11.                 direction = true;    
  12.             } else {
  13.                 if(direction != null && !direction) continue; //上一次是负值
  14.                 direction = false;    
  15.             }
  16.             sum++;
  17.         }
  18.         return sum;
  19.     }
  20. }

 LeetCode53.最大子数组和：

问题描述：

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

提示：

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

代码分析：

法一：暴力

        两层for循环，第一层为设置起始位置，第二层从起始位置处遍历数组寻找区间和最大值。时间复杂度为 O(n^2)，TLE。

法二：贪心

        贪的是起点位置的选取，例如 -2 1 在一起，一定是从 1 开始计算，因为负数只会拉低总和。

        局部最优：当前“连续和”为负数时立刻放弃，从下一个元素重新计算。（相当于暴力解法中的不断调整最大子序和区间的起始位置）

        全局最优：选取最大“连续和”。

        局部最优的情况下，并记录最大的“连续和”（变相算是调整了终止位置），可以推出全局最优。

  1. class Solution {
  2. public:
  3.     int maxSubArray(vector<int>& nums) {
  4.         int result = INT32_MIN;
  5.         int count = 0;
  6.         for(int i = 0; i <= nums.size() - 1; ++i) {
  7.             count += nums[i];
  8.             if(count > result) result = count; //相当于不断确定最大子序终止位置
  9.             if(count <= 0) count = 0; //相当于重置起始位置
  10.         }
  11.         return result;
  12.     }
  13. };

        时间复杂度为 O(n) 。

        再举例子加深理解， 4 遇到 -1 ，和为 3，只要连续和还是正数就会对后面的元素起到增大总和的作用，所以只要连续和为正数我们就保留。

        那 4 + -1 之后不就变小了吗？会不会错过 4 成为最大连续和的可能性？答案是并不会！因为变量 result 一直在更新最大的连续和，只要有更大的连续和出现，result 就更新了，在此之前 result 已经把 4 更新了，后面连续和变成 3，也不会对最后结果有影响。

法三：动态规划

        也可以利用本题回顾一下动态规划哈，反正这两块内容联系得很紧密。

        我的动态规划是跟着闫总和Carl哥学的。

        上来先动态规划五部曲：

  1. 确定dp数组以及下标的含义：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]。
  2. 确定递推公式：dp[i]只有两个方面可以推出来，一是 dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和；另一是 nums[i]，即：从头开始计算当前连续子序列和。别忘了两者取最大，即 dp[i] = max(dp[i - 1] + nums[i], nums[i])。
  3. dp数组初始化：从递推公式看出来 dp[i] 依赖于 dp[i - 1]。即 dp[0] 是基础，根据定义，dp[0] = nums[0]。
  4. 确定遍历顺序：递推公式中 dp[i] 依赖于 dp[i - 1] 的状态，需要从前向后遍历。
  5. 举例推导dp数组：以示例一为例，输入：nums = [-2,1,-3,4,-1,2,1,-5,4]，对应的dp状态如下：

        最后的结果并非 dp[nums.size() - 1]，而是 dp[6]！

        回顾一下 dp 数组的定义，要找最大的连续子序列，就应该找每一个以 i 为终点的连续最大子序列。所以在递推公式的时候，就可以直接选出最大的 dp[i]。

  1. class Solution {
  2. public:
  3.     int maxSubArray(vector<int>& nums) {
  4.         if(nums.size() == 0) return 0;
  5.         vector<int> dp(nums.size());
  6.         dp[0] = nums[0];
  7.         int result = dp[0];
  8.         for(int i = 1; i <= nums.size() - 1; ++i) {
  9.             dp[i] = max(dp[i - 1] + nums[i], nums[i]);
  10.             if(dp[i] > result) result = dp[i];
  11.         }
  12.         return result;
  13.     }
  14. };

        时空复杂度均为 O(n)。

LeetCode.买卖股票的最佳时机系列：

LeetCode.I：

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

提示：

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4

法一：暴力

        找最优间距。两层for循环，不用多说，TLE。

法二：贪心

        因为股票就买卖一次，所以贪的是取左最小值和取右最大值，那么得到的差值就是最大利润。

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         int low = INT_MAX;
  5.         int result = 0;
  6.         for(int i = 0; i <= prices.size() - 1; ++i) {
  7.             low = min(low, prices[i]); //取最左最小价格
  8.             result = max(result, prices[i] - low); //直接取最大区间利润
  9.         }
  10.         return result;
  11.     }
  12. };

        时间复杂度为 O(n)。

法三：动态规划

        还是五步分析：

  1. dp[i][0]表示第 i 天持有股票所得最多现金，dp[i][1]表示第 i 天不持有股票所得最多现金。 注：“持有”不代表当天“买入”，有可能是昨天“买入”，今天保持“持有”的状态；现金可以为负数（ 例如初始现金为0，第 i 天买入股票后现金为 -prices[i] ）。
  2. dp[i][0]可由两个状态推出：一是 第 i-1 天就持有股票，则今天保持现状，dp[i][0] = dp[i-1][0]；二是 第 i 天买入，dp[i][0] = -prices[i]。别忘取最多，dp[i][0] = max(dp[i - 1][0], -prices[i])。同理可得，dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])。
  3. 由递推公式可看出，基础是 dp[0][0] = -prices[0] 和 dp[0][1] = 0。
  4. dp[i] 由 dp[i - 1] 推出，则遍历顺序是从前往后。
  5. 以示例1，输入：[7,1,5,3,6,4]为例，dp数组状态如下：

        因为本题中不持有股票状态所得金钱一定比持有状态的多，所以 dp[5][1] 为最终结果。

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         int len = prices.size();
  5.         if(len == 0) return 0;
  6.         vector<vector<int>> dp(len, vector<int>(2));
  7.         dp[0][0] = -prices[0];
  8.         dp[0][1] = 0;
  9.         for(int i = 1; i <= len - 1; ++i) {
  10.             dp[i][0] = max(dp[i - 1][0], -prices[i]);
  11.             dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
  12.         }
  13.         return dp[len - 1][1];
  14.     }
  15. };

        时空复杂度均为 O(n)。

        然后精彩的地方来了：

        既然 dp[i] 只是依赖 dp[i - 1]，那么只需要记录 当前天的 dp 状态 和 前一天的 dp 状态 即可，可以使用滚动数组来节省空间！

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         int len = prices.size();
  5.         if(len == 0) return 0;
  6.         vector<vector<int>> dp(2, vector<int>(2)); //注意只开辟了 2 * 2 大小的空间 
  7.         dp[0][0] = -prices[0];
  8.         dp[0][1] = 0;
  9.         for(int i = 1; i <= len - 1; ++i) {
  10.             dp[i % 2][0] = max(dp[(i - 1) % 2][0], -prices[i]);
  11.             dp[i % 2][1] = max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i]);
  12.         }
  13.         return dp[(len - 1) % 2][1];
  14.     }
  15. };

        这样空间复杂度降到了 O(1)。

LeetCode.II：

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。

提示：

  • 1 <= prices.length <= 3 * 10^4
  • 0 <= prices[i] <= 10^4

        本题有巧办法，可以将整个数组分为若干个单增区间，然后将每个区间的首尾元素的差值全都相加即可。

法一：贪心

        上述的巧办法其实给我们的启示是：最终利润是可分解的（分解为以单独一天为单位的维度）。例如：第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]，相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

        于是我们可以得到每天的利润序列 (prices[i] - prices[i - 1]) ..... (prices[1] - prices[0]) 如下图：

        本题中想要获得利润则至少需要两天为一个交易期，因此第一天没有利润。

        从图中可以发现，只需累计每天的正利润，收集正利润的区间，就是股票买卖的区间。

        局部最优：累计每天正利润；全局最优：求得最大利润。

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         int result = 0;
  5.         for(int i = 1; i <= prices.size() - 1; ++i) {
  6.             result += max(prices[i] - prices[i - 1], 0);
  7.         }
  8.         return result;
  9.     }
  10. };

        时间复杂度为 O(n)。

法二：动态规划

        五步曲分析下来，与121.几乎相同，此处只谈唯一的差异。

  • 推导 dp[i][0] 的时候，第 i 天买入的情况：所得现金为第 i-1 天不持有的所得现金减去今天股票价格。dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])。

        根本原因是本题的股票可以买卖多次！

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         int len = prices.size();
  5.         vector<vector<int>> dp(len, vector<int>(2));
  6.         dp[0][0] = -prices[0];
  7.         dp[0][1] = 0;
  8.         for(int i = 1; i <= len - 1; ++i) {
  9.             dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]-prices[i]);
  10.             dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
  11.         }
  12.         return dp[len - 1][1];
  13.     }
  14. };

        省去滚动数组版代码，时空复杂度均与121.一致。

LeetCode.III（难）：

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

提示：

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^5

        本题比121. 、 122. 难度大了不少，关键在于至多买卖两次，需要分三种情况（仅买卖一次、两次都买卖、都不买卖）。

        用五步曲分析：

  • 确定dp数组以及下标的含义。

        一天一共五个状态：

        0.没有任何操作（实际上也可以选择不设置这个状态）

        1.第一次持有股票

        2.第一次不持有股票

        3.第二次持有股票

        4.第二次不持有股票

        dp[i][j] 中 i 表示第 i 天，j 为 [0 ~ 4] 五个状态，dp[i][j] 表示第 i 天状态 j 所剩最大现金。（仍需要注意，“持有” 和 “买入” 的区别）

  • 确定递推公式。

        dp[i][1] 状态，有两个方面：

        一是：第 i 天买入，dp[i][1] = dp[i - 1][0] - prices[i]。

        二是：第 i 天没有操作，保持之前买入的状态，dp[i][1] = dp[i - 1][1]。

        别忘取最大，dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1])。

      

        dp[i][2]状态，有两个方面：

        一是：第 i 天卖出，dp[i][2] = dp[i - 1][1] + prices[i]。

        二是：第 i 天没有操作，保持之前卖出的状态，dp[i][2] = dp[i - 1][2]。

        dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])。

        同理可得，dp[i][3] = max(dp[i - 1][2] - prices[i], dp[i - 1][3])。

        dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4])。

  • dp数组初始化。

        第 0 天没有操作，dp[0][0] = 0；第 0 天第一次买入，dp[0][1] = -prices[0]；第 0 天第一次卖出，即当天买入后立即卖出，dp[0][2] = 0；第 0 天第二次买入，dp[0][3] = -prices[0]；第 0 天第二次卖出，dp[0][4] = 0。

  • 确定遍历顺序：从前往后。
  • 以输入[1,2,3,4,5]为例推导dp数组：

        图中红色框为最后的两次卖出的状态。

        现金最大的时候一定是卖出的状态，并且一定是第二次卖出的状态！因为 dp[4][4] 一定包含 dp[4][2] 的情况。

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         if(prices.size() == 0) return 0;
  5.         vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
  6.         dp[0][1] = dp[0][3] = -prices[0];
  7.         for(int i = 1; i <= prices.size() - 1; ++i) {
  8.             dp[i][0] = dp[i - 1][0];
  9.             dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
  10.             dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2]);
  11.             dp[i][3] = max(dp[i - 1][2] - prices[i], dp[i - 1][3]);
  12.             dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4]);
  13.         }
  14.         return dp[prices.size() - 1][4]; 
  15.     }
  16. };

        时间复杂度为 O(n)，空间复杂度为 O(5 * n)。

        力扣官解提供了一种优化空间的写法，可以理解为 dp[i][j] 中的 i 无太大的作用，可以逐层覆盖掉。

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         if(prices.size() == 0) return 0;
  5.         vector<int> dp(5, 0);
  6.         dp[1] = dp[3] = -prices[0];
  7.         for(int i = 1; i <= prices.size() - 1; ++i) {
  8.             dp[1] = max(dp[0] - prices[i], dp[1]);
  9.             dp[2] = max(dp[1] + prices[i], dp[2]);
  10.             dp[3] = max(dp[2] - prices[i], dp[3]);
  11.             dp[4] = max(dp[3] + prices[i], dp[4]);
  12.         }
  13.         return dp[4]; 
  14.     }
  15. };

        将空间复杂度降到了 O(1)。此种写法也进一步证明了“0.无任何操作”这个状态可以不设置。

LeetCode.IV：

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，和一个整型 k 。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示：

  • 0 <= k <= 100
  • 0 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000

        本题是上一题的进阶，要求至多有 k 次交易。

        按五步曲分析：

        dp[i][j]：第 i 天状态为 j 时所剩下的最大现金。

        j 的状态从 0 ~ k，并且除 0 外，偶数是卖出，奇数是买入。

        dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1])；

        dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])；

        余下的状态可以类比：

  1. for (int j = 0; j < 2 * k - 1; j += 2) { 
  2.     dp[i][j + 1] = max(dp[i - 1][j] - prices[i], dp[i - 1][j + 1]);
  3.     dp[i][j + 2] = max(dp[i - 1][j + 1] + prices[i], dp[i - 1][j + 2]);
  4. }

        dp[0][0] = 0；dp[0][1] = -prices[0]；dp[0][2] = 0；...... 同理类比出当 j 为奇数的时候都初始化为 -prices[0]。

        从前往后推导，以输入[1,2,3,4,5]，k=2为例：

        最后一次卖出，一定利润最大，dp[prices.size() - 1][2 * k]即红色部分就是最后求解。

  1. class Solution {
  2. public:
  3.     int maxProfit(int k, vector<int>& prices) {
  4.         if(prices.size() == 0) return 0;
  5.         vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
  6.         for(int j = 1; j < 2 * k; j += 2) {
  7.             dp[0][j] = -prices[0];
  8.         }
  9.         for(int i = 1; i < prices.size(); ++i) {
  10.             for(int j = 0; j < 2 * k - 1; j += 2) {
  11.                 dp[i][j + 1] = max(dp[i - 1][j] - prices[i], dp[i - 1][j + 1]);
  12.                 dp[i][j + 2] = max(dp[i - 1][j + 1] + prices[i], dp[i - 1][j + 2]);
  13.             }
  14.         }
  15.         return dp[prices.size() - 1][2 * k];
  16.     }
  17. };

        和之前一样，我们也可以优化空间：

  1. class Solution {
  2. public:
  3.     int maxProfit(int k, vector<int>& prices) {
  4.         if(prices.size() == 0) return 0;
  5.         vector<int> dp(2 * k + 1, 0);
  6.         for(int j = 1; j < 2 * k; j += 2) {
  7.             dp[j] = -prices[0];
  8.         }
  9.         for(int i = 1; i < prices.size(); ++i) {
  10.             for(int j = 0; j < 2 * k - 1; j += 2) {
  11.                 dp[j + 1] = max(dp[j] - prices[i], dp[j + 1]);
  12.                 dp[j + 2] = max(dp[j + 1] + prices[i], dp[j + 2]);
  13.             }
  14.         }
  15.         return dp[2 * k];
  16.     }
  17. };

LeetCode. 含冷冻期：

给定一个整数数组 prices，其中第  prices[i] 表示第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

提示：

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000

        相比于122.II ，本题多了一个冷冻期。122.中有两个状态：持有和不持有股票。

        五步曲分析：

        dp[i][j]：第 i 天状态为 j 所剩的最多现金。状态分析是需要小心谨慎的，一共四个状态。

        0.持有状态（今天买入或之前买入而今天无操作）。

        1.不持有状态。两天前卖出，渡过冷冻期，一直无操作。

        2.不持有状态。今天卖出。

        3.正处冷冻期。

        dp[i][0] = max(dp[i - 1][1] - prices[i], dp[i - 1][3] - prices[i], dp[i - 1][0])；

        dp[i][1] = max(dp[i - 1][3], dp[i - 1][1])；

        dp[i][2] = dp[i - 1][0] + prices[i]；

        dp[i][3] = dp[i - 1][2]；

        （自行理解和推导）

        初始化：dp[0][0] = -prices[i]；dp[0][1] = dp[0][2] = dp[0][3] = 0；

        从前往后遍历，以[1,2,3,0,2]为例如下图：

        最终结果是取 1.、2.、3.状态的最大值，别忘了冷冻期，最后一天若为冷冻期也可能是现金最大值。

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         int n = prices.size();
  5.         if(n == 0) return 0;
  6.         vector<vector<int>> dp(n, vector<int>(4, 0));
  7.         dp[0][0] = -prices[0];
  8.         for(int i = 1; i <= n - 1; ++i) {
  9.             dp[i][0] = max(dp[i - 1][1] - prices[i], max(dp[i - 1][3] - prices[i], dp[i - 1][0]));
  10.             dp[i][1] = max(dp[i - 1][3], dp[i - 1][1]);
  11.             dp[i][2] = dp[i - 1][0] + prices[i];
  12.             dp[i][3] = dp[i - 1][2]; 
  13.         }
  14.         return max(dp[n - 1][1], max(dp[n - 1][2], dp[n - 1][3]));
  15.     }
  16. };

        时空复杂度均为 O(n)。

        本题若想优化空间，不同于之前的题目，需要定义 dp[2][4] 大小保存 当前 和 前一天 的状态！

LeetCode.含手续费：

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

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

返回获得利润的最大值。

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

示例 1：

输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

提示：

  • 1 <= prices.length <= 5 * 10^4
  • 1 <= prices[i] < 5 * 10^4
  • 0 <= fee < 5 * 10^4

        本题与 II. 的区别仅为多了手续费，即在获取的利润上减去费用即可。

        五步曲分析：

        dp[i][0]：第 i 天持有股票所得最多现金。dp[i][0] = max(dp[i - 1][1] - prices[i], dp[i - 1][0])。

        dp[i][1]：第 i 天不持有股票所得最多现金。dp[i][1] = max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1])。

        初始化：dp[0][0] = -prices[0]；dp[0][1] = 0；从前向后遍历。最大值为最后一次交易完成时不持有股票状态即 dp[prices.size() - 1][1]。

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices, int fee) {
  4.         int n = prices.size();
  5.         vector<vector<int>> dp(n, vector<int>(2, 0));
  6.         dp[0][0] = -prices[0];
  7.         for(int i = 1; i <= n - 1; ++i) {
  8.             dp[i][0] = max(dp[i - 1][1] - prices[i], dp[i - 1][0]);
  9.             dp[i][1] = max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);
  10.         }
  11.         return dp[n - 1][1];
  12.     }
  13. };

        本题仍可用老办法优化空间。

LeetCode1005.K次取反后最大化的数组和：

问题描述：

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

  • 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

示例 1：

输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。

提示：

  • 1 <= nums.length <= 10^4
  • -100 <= nums[i] <= 100
  • 1 <= k <= 10^4

代码分析：

        第一次贪心，局部最优：让绝对值大的负数变正数，当前数值最大。整体最优：整个数组和达到最大。

        若已将负数全部转正，K 依然大于 0，则需要第二次贪心，局部最优：仅查找数值最小的正整数反转从而达到整体最优。

        分析到这，解题步骤呼之欲出了：

        1.将数组按照绝对值大小从大到小排序。

        2.从前向后遍历，遇到负数则反转，K --。

        3.若负数已全部反转完而 K 仍大于0，反复反转数值最小的正数，将 K 耗尽。

  1. class Solution {
  2.  
  3. static bool cmp(int a, int b) {
  4.     return abs(a) > abs(b); //绝对值从大到小
  5. }
  6.  
  7. public:
  8.     int largestSumAfterKNegations(vector<int>& nums, int k) {
  9.         sort(nums.begin(), nums.end(), cmp);
  10.         for(int i = 0; i <= nums.size() - 1; ++i) {
  11.             if(nums[i] < 0 && k > 0) {
  12.                 nums[i] *= -1;
  13.                 k--; 
  14.             }
  15.         }
  16.         if(k % 2 == 1) nums[nums.size() - 1] *= -1;
  17.         int result = 0;
  18.         for(int n : nums) result += n;
  19.         return result;
  20.     }
  21. };

        时间复杂度为 O(n * logn)。

        注意到本题数组元素的范围为[-100, 100]，可以直接使用计数数组（桶）或者哈希表，直接统计每个元素出现的次数，再升序遍历元素的范围，就省去了排序所要的时间。

  1. class Solution {
  2. public:
  3.     int largestSumAfterKNegations(vector<int>& nums, int k) {
  4.         int arr[201]; //数据范围[-100, 100]
  5.         memset(arr, 0, sizeof(arr));
  6.         for(int num : nums) {
  7.             arr[num + 100]++; //防止负数的索引
  8.         }
  9.         for(int i = 0; i < 100; ++i) { //遍历原负数的部分
  10.             if(arr[i] != 0) {
  11.                 int count = min(k, arr[i]); //取 k 和 该负数出现次数 的较小值
  12.                 arr[i] -= count;
  13.                 arr[-i + 200] += count; //该负数对应的相反数也加上相同的数量
  14.                 k -= count;
  15.                 if(k == 0) break;
  16.             }
  17.         }
  18.  
  19.         if(k % 2 != 0) { //如果 k 还有剩余且为奇数，取 最小的正数 或 零 变换一次;若为偶数，即将某数反复反转，相当于保持不变
  20.             for(int i = 100; i < 201; ++i) {
  21.                 if(arr[i] != 0) {
  22.                     arr[i]--; //次数逐步减少并当即判断检查
  23.                     arr[-i + 200]++;
  24.                     break;
  25.                 }
  26.             }
  27.         }
  28.  
  29.         int ans = 0;
  30.         for(int i = 0; i < 201; ++i) {
  31.             ans += arr[i] * (i - 100);
  32.         } 
  33.         return ans;
  34.     }
  35. };

        时间复杂度均为 O(n + C)，C为数组 nums 中元素的范围即 201。O(n) 的时间使用这两种数据结构统计每个元素出现的次数，随后 O(C) 的时间对元素进行操作。

        既然本题的关键点涵盖了排序部分，那么也可以使用优先队列 PriorityQueue<Integer> q = new PriorityQueue<>((a, b)->nums[a] - nums[b])。

LeetCode134.加油站：

问题描述：

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 1:

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

提示:

  • gas.length == n
  • cost.length == n
  • 1 <= n <= 10^5
  • 0 <= gas[i], cost[i] <= 10^4

代码分析：

法一：暴力

        遍历每个加油站为起点的情况，模拟一圈。若从该点跑了一圈后，中途没有断油并且最后油量大于等于0，则该点为所求的唯一点。

  1. class Solution {
  2. public:
  3.     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
  4.         for(int i = 0; i <= cost.size() - 1; ++i) {
  5.             int rest = gas[i] - cost[i]; //记录剩余油量
  6.             int index = (i + 1) % cost.size(); //下标用于模拟环形数组行驶一圈
  7.             while(rest > 0 && index != i) {
  8.                 rest += gas[index] - cost[index];
  9.                 index = (index + 1) % cost.size();
  10.             }
  11.             if(rest >= 0 && index == i) return i;
  12.         }
  13.         return -1;
  14.     }
  15. };

        时间复杂度为 O(n^2)。

法二：全局选最优

        直接从全局进行贪心选择，情况如下：

  • 若 gas 总和小于 cost 总和，无论从何处出发一定跑不完整圈。
  • rest[i] = gas[i] - cost[i] 为一天剩下的油。i 从 0 开始计算累加到最后一站。若累加过程中没有出现负数，说明从 0 出发，油没断过，那么 0 就是起点；
  • 若累加的最小值是负数，就要排除 0 这一节点，从后向前，看哪个节点能把该负数填平，若能则该节点为出发节点。
  1. class Solution {
  2. public:
  3.     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
  4.         int curSum = 0;
  5.         int min = INT_MAX; //从0出发，油箱里油量的最小值
  6.         for(int i = 0; i <= gas.size() - 1; ++i) {
  7.             int rest = gas[i] - cost[i];
  8.             curSum += rest;
  9.             if(curSum < min) min = curSum;
  10.         }
  11.         if(curSum < 0) return -1; //情况一
  12.         if(min >= 0) return 0; //情况二
  13.         for(int i = gas.size() - 1; i >= 0; --i) { //情况三
  14.             int rest = gas[i] - cost[i];
  15.             min += rest;
  16.             if(min >= 0) return i;
  17.         }
  18.         return -1;
  19.     }
  20. };

        时间复杂度为 O(n)。

法三：贪心

        若总油量减去总消耗大于等于0 ——> 一定可以跑完一圈 ——> 各个站点的加油站剩油量 rest[i] 相加一定大于等于0。

        i 从0开始累加 rest[i]，和记为 curSum，一旦 curSum 小于 0（此时汽车正从第 i 个站点开向第 i+1 个站点，即能到达站点 i 而无法到达站点 i+1），说明 [0, i] 区间都不能作为起始位置！（因为从区间中选择任何一个位置作为起点时，到达第 i 站的curSum，一定小于选择0作为起点的curSum！）因此，起始位置要从 i+1 算起，curSum 归零从当前位置起继续计算。

        若能从 i+1 到达 end，并且 totalSum >= 0，即能完整绕一圈！因为 curSum < 0，说明从 i+1 到 end 的所剩油量大于从 0 到 i+1 所欠的油量。

        局部最优：当前累加 rest[i] 的和 curSum 一旦小于 0，起始位置至少要是 i+1。

        全局最优：找到可以跑一圈的起始位置。

        贪心法比较巧妙但是难想。

  1. class Solution {
  2. public:
  3.     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
  4.         int curSum = 0, totalSum = 0, start = 0;
  5.         for(int i = 0; i <= gas.size() - 1; ++i) {
  6.             curSum += gas[i] - cost[i];
  7.             totalSum += gas[i] - cost[i];
  8.             if(curSum < 0) {
  9.                 start = i + 1;
  10.                 curSum = 0;
  11.             }
  12.         }
  13.         return totalSum < 0 ? -1 : start;
  14.     }
  15. };

LeetCode135.分发糖果：

问题描述：

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

  • n == ratings.length
  • 1 <= n <= 2 * 10^4
  • 0 <= ratings[i] <= 2 * 10^4

代码分析：

法一：两次遍历

        也不是很难想到，「相邻的孩子中，评分高的孩子必须获得更多的糖果」需要 从左向右 和 从右向左 两个方向，来使得每个人最终分得的糖果数量为两个不同方向所得出不同结论的最大值。

        两次局部最优：一次是从左到右，只比较右边孩子评分比左边大的情况；一次是从右到左，只比较左边孩子评分比右边大的情况。

        推出全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。

  1. class Solution {
  2.     public int candy(int[] ratings) {
  3.         int n = ratings.length;
  4.         int[] nums = new int[n];
  5.         Arrays.fill(nums, 1);
  6.         for(int i = 1; i <= n - 1; ++i) {
  7.             if(ratings[i] > ratings[i - 1]) nums[i] = nums[i - 1] + 1;
  8.         }
  9.         for(int i = n - 2; i >= 0; --i) {
  10.             if(ratings[i] > ratings[i + 1] && nums[i] <= nums[i + 1]) nums[i] = nums[i + 1] + 1;
  11.         }
  12.         int sum = 0;
  13.         for(int num : nums) {
  14.             sum += num;
  15.         }
  16.         return sum;
  17.     }
  18. }

        时空复杂度均为 O(n)。至于官方的第二种常数空间优化，根据需求自行学习。

LeetCode860.柠檬水找零：

问题描述：

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：

输入：bills = [5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

提示：

  • 1 <= bills.length <= 10^5
  • bills[i] 不是 5 就是 10 或是 20

代码分析：

        根据题意，要设计优秀的找零算法来使得尽可能给更多的顾客正确找零。而账单与找零的关系如下：

  • 情况一：账单是5，直接收下。
  • 情况二：账单是10，消耗一个5，增加一个10。
  • 情况三：账单是20，可以考虑消耗10+5，也可以消耗3 * 5。

        前两种的情况是固定策略，关键在情况三，可以采用贪心，需要优先消耗10+5！原理也很简单，因为10只能给20找零，而5可以给10、20找零，5是更万能更通用的底牌。

        因此局部最优的优先消耗策略可以推出全局最优。

  1. class Solution {
  2.     public boolean lemonadeChange(int[] bills) {
  3.         //20无法参与找零，可以不统计数量
  4.         int five = 0;
  5.         int ten = 0;
  6.         for(int i = 0; i < bills.length; ++i) {
  7.             if(bills[i] == 5) five++;
  8.             else if(bills[i] == 10) {five--; ten++;}
  9.             else if(bills[i] == 20) {
  10.                 if(ten > 0) {ten--; five--;}
  11.                 else five -= 3;
  12.             }
  13.             if(five < 0 || ten < 0) return false;
  14.         }
  15.         return true;
  16.     }
  17. }

LeetCode406.根据身高重建队列：

问题描述：

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

提示：

  • 1 <= people.length <= 2000
  • 0 <= hi <= 10^6
  • 0 <= ki < people.length
  • 题目数据确保队列可以被重建

代码分析：

        理解完题意和示例演示，推测要选用便于任意位置插入的数据结构，并且要设计局部最优的插队算法来推出全局最优。再分析，若按照遍历原数组的顺序来逐一调整，每次插入位置的可能性太多，无法保证局部最优 ——> 需要排序！然后脑补一下，从低到高依然无法保证，从高到低好像正好！

        因此局部最优：仅按照身高 h 来排序，先不管 k 大小，再依次按照 k 的大小来插入，使得满足队列属性。从而推出全局最优。

  1. class Solution {
  2. public:
  3.     static bool cmp(const vector<int> &a, const vector<int> &b) {
  4.         if(a[0] == b[0]) return a[1] < b[1]; //若身高相同，则再按 k 比较
  5.         return a[0] > b[0]; 
  6.     }
  7.  
  8.     vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
  9.         sort(people.begin(), people.end(), cmp);
  10.         vector<vector<int>> que;
  11.         for(int i = 0; i < people.size(); ++i) {
  12.             int pos = people[i][1];
  13.             que.insert(que.begin() + pos, people[i]);
  14.         }
  15.         return que;
  16.     }
  17. };

        时间复杂度为 O(n * logn + n^2 + t * n)，t 为底层扩容操作次数。由于使用 vector（可以理解为动态数组，底层是普通数组实现的，如果插入元素位置超出了预先普通数组大小，会进行扩容的操作即申请两倍于原空间的大小，然后把数据拷贝过去）非常费时，所以建议使用C++底层封装的链表。

  1. class Solution {
  2. public:
  3.     static bool cmp(const vector<int> &a, const vector<int> &b) {
  4.         if(a[0] == b[0]) return a[1] < b[1]; //若身高相同，则再按 k 比较
  5.         return a[0] > b[0]; 
  6.     }
  7.  
  8.     vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
  9.         sort(people.begin(), people.end(), cmp);
  10.         list<vector<int>> que; //list底层是链表，效率高
  11.         for(int i = 0; i < people.size(); ++i) {
  12.             int pos = people[i][1];
  13.             list<vector<int>>::iterator it = que.begin();
  14.             while(pos--) it++;
  15.             que.insert(it, people[i]);
  16.         }
  17.         return vector<vector<int>>(que.begin(), que.end());
  18.     }
  19. };

        时间复杂度为 O(n * logn + n^2)。

LeetCode452.用最少数量的箭引爆气球：

问题描述：

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中 points[i] = [x_{start}, x_{end}] 表示水平直径在 x_{start} 和 x_{end}之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x_{start}，x_{end}， 且满足  x_{start} ≤ x ≤ x_{end}，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

提示:

  • 1 <= points.length <= 10^5
  • points[i].length == 2
  • -2^31 <= x_{start} < x_{end} <= 2^31 - 1

代码分析:

        全部引爆并且箭数最少，局部最优：有重叠部分的气球一起射。

        为了让气球尽可能重叠，首先要排序，按起始位置和终止位置（左边界和右边界）排都可以（默认按照起始位置，按照左边界和右边界的代码逻辑一样）。从前向后遍历遇到重叠的气球时，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。

        以题目示例： [[10,16],[2,8],[1,6],[7,12]]为例，如图：（方便起见，已经排序）

        可以看出，第一组的重叠气球，一定需要一支箭，而气球3的左边界大于第一组重叠气球的最小右边界，所以需要额外一支箭来射气球3。

  1. class Solution {
  2. private:
  3.     static bool cmp(const vector<int> &a, const vector<int> &b) {
  4.         return a[0] < b[0];
  5.     }    
  6. public:
  7.     int findMinArrowShots(vector<vector<int>>& points) {
  8.         if(points.size() == 0) return 0;
  9.         sort(points.begin(), points.end(), cmp);
  10.         int result = 1;
  11.         for(int i = 1; i < points.size(); ++i) {
  12.             if(points[i][0] > points[i - 1][1]) result++; //气球 i 和上一组（个）相邻气球组成的集合体 之间不挨着
  13.             else {
  14.                 points[i][1] = min(points[i - 1][1], points[i][1]); //气球 i 和上一组（个）相邻气球组成的集合体 之间挨着，则当成整体看待，需要更新重叠气球部分的最小右边界
  15.             }
  16.         }
  17.         return result;
  18.     }
  19. };

        时间复杂度为 O(n * logn)，因为有一个快排。

        注意本题题干，两个气球擦边也算重叠！因此是 if(points[i][0] > points[i-1][1])大于号。

LeetCode435.无重叠区间：

问题描述：

给定一个区间的集合 intervals ，其中 intervals[i] = [start_{i}, end_{i}] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

提示:

  • 1 <= intervals.length <= 10^5
  • intervals[i].length == 2
  • -5 * 10^4 <= start_{i} < end_{i} <= 5 * 10^4

代码分析：

        本题和452.十分类似，弓箭的数量相当于是非重叠区间的数量，区别就是本题的擦边不算重叠，并且最终用总区间数减去非重叠区间数，就得到了需要移除的区间数。具体代码自行改写。

        只是为了让区间尽可能重叠，左边界和右边界排序都可以，只不过逻辑稍微不同。关键点是从左向右记录非重叠区间的数量：

        区间 [1,2,3,4,5,6] 都按照右边界排好序。

  • 如何连续确定重叠区间？即当确定 1 、2 重叠后，如何确定是否与 3 也重叠？

        取 区间1 和 区间2 右边界的最小值！（由于我们恰好是按照右边界排好序的，因此可以省去min()的操作，这也是代码中遇到重叠部分不做任何处理就直接跳过的原因）因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分，如果这个最小值也触达到区间3，那么说明 区间 1，2，3都是重合的。

  • 如何确定下一个非重叠区间？

        寻找左边界大于【确定上一个非重叠区间时记录的end】的区间。

  1. class Solution { 
  2. public:
  3.     static bool cmp(const vector<int> &a, const vector<int> &b) {
  4.         return a[1] < b[1];
  5.     }
  6.     int eraseOverlapIntervals(vector<vector<int>>& intervals) {
  7.         sort(intervals.begin(), intervals.end(), cmp);
  8.         int count = 1; //记录非重叠区间数
  9.         int end = intervals[0][1]; //记录区间分割点（这里的逻辑与452.稍微不一样，遇到与当前分割点区间重叠的就跳过，因为“一支箭”就解决了;遇到非重叠的才更新准备“下一支箭”）
  10.         for(int i = 1; i < intervals.size(); ++i) {
  11.             if(end <= intervals[i][0]) {end = intervals[i][1]; count++;}
  12.         }
  13.         return intervals.size() - count;
  14.     }
  15. };

        时间复杂度为 O(n * logn)。下面是按照左边界排序，此时是直接求重叠的区间，count记录重叠区间数：

  1. class Solution { 
  2. public:
  3.     static bool cmp(const vector<int> &a, const vector<int> &b) {
  4.         return a[0] < b[0];
  5.     }
  6.     int eraseOverlapIntervals(vector<vector<int>>& intervals) {
  7.         sort(intervals.begin(), intervals.end(), cmp);
  8.         int count = 0; //直接记录重叠区间数
  9.         int end = intervals[0][1];
  10.         for(int i = 1; i < intervals.size(); ++i) {
  11.             if(end <= intervals[i][0]) end = intervals[i][1];
  12.             else {end = min(end, intervals[i][1]); count++;}
  13.         }
  14.         return count;
  15.     }
  16. };
  17.  
  18. 精简后为：
  19.  
  20. class Solution { 
  21. public:
  22.     static bool cmp(const vector<int> &a, const vector<int> &b) {
  23.         return a[0] < b[0];
  24.     }
  25.     int eraseOverlapIntervals(vector<vector<int>>& intervals) {
  26.         sort(intervals.begin(), intervals.end(), cmp);
  27.         int count = 0; //直接记录重叠区间数
  28.         for(int i = 1; i < intervals.size(); ++i) {
  29.             if(intervals[i - 1][1] > intervals[i][0]) {intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); count++;}
  30.         }
  31.         return count;
  32.     }
  33. };

LeetCode763.划分字母区间：

问题描述：

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

提示：

  • 1 <= s.length <= 500
  • s 仅由小写英文字母组成

代码分析：

        同一字母最多出现在一个片段中，并且要把这个字符串分为尽可能多的片段。

        由于本题 s 由 26 个英文小写字母构成，我们可以往计数数组（桶）上思索。

  • 如何把同一个字母的都圈在同一个区间里呢？

        在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。

        具体操作为，首先找到第一个字母 s[0] 的边界 k 。然后在 [0, k] 的区间里遍历接下来的每个元素。若这些元素的最远边界全部都在 k 以内，那么直接分割即可；若存在元素 i 的边界超过了 k ，那么更新当前这个片段的最远边界 k ，再继续遍历即可......直至遍历的游标移至当前片段的最远边界为止，就这样，一个片段分割好了。

        本题不难，但一定要自行想象。

  1. class Solution {
  2. public:
  3.     vector<int> partitionLabels(string s) {
  4.         int a[26];
  5.         memset(a, 0, sizeof(a));
  6.         vector<int> v;
  7.         for(int i = 0; i <= s.size() - 1; ++i) {
  8.             a[s[i] - 'a'] = i;
  9.         }
  10.         int j = 0;
  11.         for(j; j <= s.size() - 1;) { //j指向每个片段的开头
  12.             for(int k = j; k <= a[s[j] - 'a']; ++k) {
  13.                 //如果期间的每个元素出现的最后位置都小于 a[s[j] - 'a'] ，continue;否则直接扩大当前片段的结束位置。
  14.                 if(a[s[k] - 'a'] > a[s[j] - 'a']) a[s[j] - 'a'] = a[s[k] - 'a'];  
  15.             }
  16.             v.push_back(a[s[j] - 'a'] - j + 1);
  17.             j = a[s[j] - 'a'] + 1;
  18.         }
  19.         return v;
  20.     }
  21. };

        时间复杂度 O(n)，空间复杂度 O(1)。

        当然， Carl哥 提供了类似于452.、435.两题思路的解法，可以题目之间互相比照：

        统计字符串中所有字符的起始和结束位置，记录这些区间（很巧妙，就是之前题目里的输入），将区间按左边界从大到小排序，找到边界将区间划分成互不重叠且相邻的组。而找到的边界即是想要的答案。

  1. class Solution {
  2. public:
  3.     static bool cmp(vector<int> &a, vector<int> &b) {
  4.         return a[0] < b[0];
  5.     }
  6.     //记录每个字母出现的区间
  7.     vector<vector<int>> countLabels(string s) {
  8.         vector<vector<int>> hash(26, vector<int>(2, INT_MIN));
  9.         vector<vector<int>> hash_filter;
  10.         for(int i = 0; i < s.size(); ++i) {
  11.             if(hash[s[i] - 'a'][0] == INT_MIN) hash[s[i] - 'a'][0] = i;
  12.             hash[s[i] - 'a'][1] = i;
  13.         }
  14.         //清除剩余空间，让返回的集合清爽
  15.         for(int i = 0; i < hash.size(); ++i) {
  16.             if(hash[i][0] != INT_MIN) {
  17.                 hash_filter.push_back(hash[i]);
  18.             }
  19.         }
  20.         return hash_filter;
  21.     }
  22.     
  23.     vector<int> partitionLabels(string s) {
  24.         vector<int> res;
  25.         //求得区间列表,左边界从小到大
  26.         vector<vector<int>> hash = countLabels(s);
  27.         sort(hash.begin(), hash.end(), cmp);
  28.         int rightBoard = hash[0][1]; //最远右边界
  29.         int leftBoard = 0;
  30.         for(int i = 1; i < hash.size(); ++i) {
  31.             if(hash[i][0] > rightBoard) { //实际上，该情况对应上面题解里【若这些元素的最远边界全部都在 k 以内，那么直接分割即可】的情况
  32.                 res.push_back(rightBoard - leftBoard + 1);
  33.                 leftBoard = hash[i][0]; //左边界的更新频率比右边界的要慢
  34.             }
  35.             rightBoard = max(rightBoard, hash[i][1]); //实际上，即else ，对应上面题解里【若存在元素 i 的边界超过了 k ，那么更新当前这个片段的最远边界 k ，再继续遍历即可】的情况
  36.         }
  37.         res.push_back(rightBoard - leftBoard + 1); //上面for循环会漏掉一个最右端的片段没放入集合
  38.         return res;
  39.     }
  40. };

LeetCode56.合并区间：

问题描述：

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_{i}, end_{i}] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]。

提示：

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start_{i} <= end_{i} <= 10^4

代码分析：

        没什么好说的，直接上代码，复习前面所学内容：

  1. class Solution {
  2. public:
  3.     static bool cmp(const vector<int> &a, const vector<int> &b) {
  4.         return a[0] < b[0];
  5.     }
  6.     vector<vector<int>> merge(vector<vector<int>>& intervals) {
  7.         vector<vector<int>> res;
  8.         vector<int> v(2, INT_MIN);
  9.         sort(intervals.begin(), intervals.end(), cmp);
  10.         int rightBoard = intervals[0][1];
  11.         int leftBoard = intervals[0][0];
  12.         for(int i = 1; i < intervals.size(); ++i) {
  13.             if(intervals[i][0] > rightBoard) {
  14.                 v[0] = leftBoard; v[1] = rightBoard; res.push_back(v);
  15.                 leftBoard = intervals[i][0];
  16.             }
  17.             rightBoard = max(rightBoard, intervals[i][1]);
  18.         }
  19.         v[0] = leftBoard; v[1] = rightBoard; res.push_back(v); 
  20.         return res;
  21.     }
  22. };

LeetCode738.单调递增的数字：

问题描述：

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

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

示例 1:

输入: n = 1234 输出: 1234
输入: n = 332 输出: 299
输入: n = 10 输出: 9

提示:

  • 0 <= n <= 10^9

代码分析：

        自己开动小脑筋，首先想到的就是暴力解法了，在 [0~n] 范围内找第一个符合单调递增条件的，O(n * m)，TLE。

        至于贪心算法的话，必须要想清楚一点：例如 98，一旦出现 strNum[i-1] > strNum[i]（非单增）的情况，首先需让 strNum[i-1]--，然后 strNum[i] 赋值为 9，得到 89。这是设计的基础。

        至于遍历顺序呢？

        若从前往后，遇到 strNum[i - 1] > strNum[i] 的情况，让 strNum[i - 1] 减一，但此时如果 strNum[i - 1] 减一了，可能又小于 strNum[i - 2]。例如：332 -> 329，正确答案应该是299。

        看来从后向前了，运用上面的结论，我们发现是可以做到正确性和普适性的。332 -> 329 ->299。

  1. class Solution {
  2. public:
  3.     int monotoneIncreasingDigits(int N) {
  4.         string strNum = to_string(N);
  5.         int flag = strNum.size(); //flag标记赋值9从哪里开始
  6.         for(int i = strNum.size() - 1; i > 0; --i) {
  7.             if(strNum[i - 1] > strNum[i]) {
  8.                 flag = i;
  9.                 strNum[i - 1]--;
  10.             }
  11.         }
  12.         for(int i = flag; i < strNum.size(); ++i) strNum[i] = '9';
  13.         return stoi(strNum);
  14.     }
  15. };

        回想一下 to_string()、stoi()函数即可。

LeetCode968.监控二叉树（难）：

问题描述：

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

示例 1：

输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

提示：

  1. 给定树的节点数的范围是 [1, 1000]。
  2. 每个节点的值都是 0。

代码分析：

        本题结合了贪心+二叉树遍历+状态转移。

        需要注意到：摄像头可以覆盖上中下三层，若把摄像头放在叶子节点上，就浪费了一层的覆盖。因此，把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。。

        为何不从头节点往下，而要从叶子节点往上？

        因为头节点是否放，仅会省下一个摄像头；而叶子节点是否放，省下的摄像头是指数级别的。

        因此局部最优：从下往上（后序遍历），让叶子节点的父节点先安装摄像头，然后隔两个节点放一个摄像头，直到二叉树头节点，这样所用数量最少。可推出全局最优。

        那么接下来工作的重心就放在了如何“隔两个节点放一个摄像头”上。

        由于复杂度二叉树枝杈繁多，所以我们需要从下往上进行状态转移，这样不重不漏效率高：

        每个节点都有如下三种状态：

        0.该节点无覆盖

        1.该节点有摄像头

        2.该节点有覆盖

        （“该节点无摄像头”这一状态是重复的！其包含了“无覆盖”和“有覆盖”两种可能。）

        再来处理特殊情况：空节点属于哪一种状态？

  1. 回归本题的解题基础【尽量让叶子节点的父节点安装摄像头】，那么空节点不能是“无覆盖”状态，否则叶子节点需要放摄像头；
  2. 也不能是“有摄像头”状态，否则叶子节点的父节点就没必要放摄像头了，反而可以把摄像头放在叶子节点的爷爷节点上；
  3. 因此综上只可能是“有覆盖”状态。

        再来看递归函数的单层逻辑处理：

  • 情况一：左右节点都“有覆盖”状态。自然此时中间节点是“无覆盖”的状态。

  • 情况二：左右节点至少有一个“无覆盖”状态。中间节点应该为“有摄像头”状态

        换句话说有且仅有如下细分的状态组合时，父节点才应该放摄像头！

        1.左右节点均无覆盖

        2.左节点无覆盖，右节点有摄像头

        3.左节点无覆盖，右节点有覆盖

        4.左节点有摄像头，右节点无覆盖

        5.左节点有覆盖，右节点无覆盖

  • 情况三：左右节点至少有一个“有摄像头”状态。再次细分情况进行分析，中间节点理应是“有覆盖”状态。
  • 情况四：递归结束后，若头结点为“有摄像头”或“有覆盖”状态还好说，若为“无覆盖”状态，那么这条信息就会被我们遗漏掉！所以我们要利用 自身返回型递归函数做一个特判！
  1. class Solution {
  2. private:
  3.     int result;
  4.     int traversal(TreeNode *cur) { //返回值是中间节点的状态字
  5.         if(!cur) return 2;
  6.         int left = traversal(cur->left);
  7.         int right = traversal(cur->right);
  8.         //情况一
  9.         if(left == 2 && right == 2) return 0;
  10.         //情况二
  11.         else if(left == 0 || right == 0) {result++; return 1;}
  12.         //情况三 if(left == 1 || right == 1)
  13.         else return 2;
  14.     }    
  15. public:
  16.     int minCameraCover(TreeNode* root) {
  17.         result = 0;
  18.         //情况四
  19.         if(traversal(root) == 0) result++;
  20.         return result;
  21.     }
  22. };

        时空复杂度均为 O(n)。

LeetCode179.最大数：

问题描述：

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1： 输入：nums = [3,30,34,5,9]

输出："9534330"

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 10^9

代码分析：

        关键点就是自定义排序的设计，若严谨点，还要牵扯到离散数学的证明，但是，贪心题，觉得举不出反例就尝试一下。

  1. class Solution {
  2. public:
  3.     static bool cmp(const string &a, const string &b) {
  4.         return a + b > b + a;
  5.     }
  6.     string largestNumber(vector<int>& nums) {
  7.         vector<string> s;
  8.         for(int num : nums) {
  9.             s.push_back(to_string(num));
  10.         }
  11.         /*
  12.         sort(s.begin(), s.end(), [](const string &a, const string &b){
  13.             return a + b > b + a;
  14.         });
  15.         */
  16.         sort(s.begin(), s.end(), cmp);
  17.         string ans;
  18.         for(string ss : s) {
  19.             ans += ss;
  20.         }
  21.         if(ans[0] == '0') return "0";
  22.         return ans;
  23.     }
  24. };

LeetCode334.递增的三元子序列：

问题描述：

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,1,5,0,4,6]
输出：true
解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

提示：

  • 1 <= nums.length <= 5 * 10^5
  • -2^31 <= nums[i] <= 2^31 - 1

代码分析：

        本题如果第一次做到，不容易想，建议自己倒腾倒腾就开始学习题解吧。

法一：双向遍历

        若数组中存在一个下标 i 满足 1 ≤ i < n−1，使得在 nums 的左边存在一个元素小于 nums[i] （等价于：nums[i] 左边的 min 值小于 nums[i]） 且在 nums[i] 的右边存在一个元素大于 nums[i] （等价于：nums[i] 右边的 max 值大于 nums[i]） ，则数组 nums 中存在递增的三元子序列。因此需要维护数组中每个元素 左边的min 和 右边的max。

        创建两个长度为 n 的数组 leftMin 和 rightMin，对于 0 ≤ i < n，leftMin 表示 nums[0] 到 nums[i] 中的最小值，rightMax[i] 表示 nums[i] 到 nums[n−1] 中的最大值（类似于前缀和以及单调栈的处理方式）。

  1. class Solution {
  2. public:
  3.     bool increasingTriplet(vector<int>& nums) {
  4.         int n = nums.size();
  5.         if(n < 3) return false;
  6.         vector<int> leftMin(n), rightMax(n);
  7.         leftMin[0] = nums[0], rightMax[n - 1] = nums[n - 1];
  8.         for(int i = 1; i < n; ++i) leftMin[i] = min(leftMin[i - 1], nums[i]);
  9.         for(int i = n - 2; i >= 0; --i) rightMax[i] = max(rightMax[i + 1], nums[i]);
  10.         for(int i = 1; i < n - 1; ++i) 
  11.             if(nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1])
  12.                 return true;
  13.         return false;        
  14.     }
  15. };

        时空复杂度均为 O(n)。

法二：贪心

        该方法可以将空间复杂度降到 O(1)。

        从左向右遍历数组，维护两个变量 first 和 second ，确保时刻都有 first < second（初始时 first 设为第一个元素值，second 尚不能确定，可以设大一点，比如 INT_MAX）。现在寻找第三个数 third。

  1. 若 third 比 second 大，找到了，返回true。
  2. 若 third 比 second 小，但比 first 大，就让second 指向 third，作废掉老 third，继续寻找新 third。
  3. 若 third 比 first 还要小，first 指向老 third，保留老 first，但是作废掉老 third，继续遍历找新 third（虽然这样 first 会跑到 second 后面，但是在 second 的前面的老 first 还是“蓄势待发”的）。

        并且，我们贪心地让 first 和 second 尽可能得小，这样寻找到递增的三元子序列的可能性更大。

  1. class Solution {
  2. public:
  3.     bool increasingTriplet(vector<int>& nums) {
  4.         int n = nums.size();
  5.         if(n < 3) return false;
  6.         vector<int> leftMin(n), rightMax(n);
  7.         leftMin[0] = nums[0], rightMax[n - 1] = nums[n - 1];
  8.         for(int i = 1; i < n; ++i) leftMin[i] = min(leftMin[i - 1], nums[i]);
  9.         for(int i = n - 2; i >= 0; --i) rightMax[i] = max(rightMax[i + 1], nums[i]);
  10.         for(int i = 1; i < n - 1; ++i) 
  11.             if(nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1])
  12.                 return true;
  13.         return false;        
  14.     }
  15. };

        本题与【最长上升子序列 LIS】、【最长公共子序列 LCS】系列问题很类似，我们之后再回过头来复习。

法三：贪心+二分

        本题要求是否存在长度为 3 的上升子序列，也可以转换成类似于下一题所用的解法：若 nums 的最长上升子序列长度大于等于 3 ，则返回 true。

  1. class Solution {
  2. public:
  3.     bool increasingTriplet(vector<int>& nums) {
  4.         vector<int> g;
  5.         for(int num : nums) {
  6.             auto it = lower_bound(g.begin(), g.end(), num);
  7.             if(it == g.end()) g.push_back(num);
  8.             else *it = num;
  9.         }
  10.         return g.size() >= 3 ? true : false;
  11.     }
  12. };

        时间复杂度为 O(n * logn)，空间复杂度为 O(n)。

        对于法三，本题还有优化，可以结合本题的法二来看。本题符合条件的最长上升子序列长度只需要为 3 即可，因此我们可以把数组 d 的大小压缩成 2。

        d[1] = x 代表长度为 1 的上升子序列最小结尾元素为 x，d[2] = y 代表长度为 2 的上升子序列的最小结尾元素为 y。由于单调性，d[1] < d[2]，相当于法二中的 first 和 second，强制确定了大小关系。

        接下来，从前往后扫描每个 nums[i]，分别于 d[1]、d[2] 比较。若 nums[i] > d[2]，返回 true；否则尝试用 nums[i] 来更新 d[1]、d[2]。

  1. class Solution {
  2. public:
  3.     bool increasingTriplet(vector<int>& nums) {
  4.         int n = nums.size();
  5.         vector<int> d(3, INT_MAX); //建议初始化为最大值
  6.         for(int i = 0; i < n; ++i) {
  7.             int num = nums[i];
  8.             if(d[2] < num) return true;
  9.             else if(d[1] < num && num < d[2]) d[2] = num;
  10.             else if(d[1] > num) d[1] = num;
  11.         }
  12.         return false;
  13.     }
  14. };

        时间复杂度为 O(n)，空间复杂度为 O(1)。

LeetCode300.最长递增子序列（LIS）：

问题描述：

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

提示：

  • 1 <= nums.length <= 2500
  • -10^4 <= nums[i] <= 10^4

代码分析：

        本题是 LIS 系列问题的经典入门题，常见方法有两种：动态规划 和 贪心二分。

法一：动态规划

        五步曲分析：

        本题中，正确定义 dp 数组的含义是关键：dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。

        状态转移方程：if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j]+1)，0 <= j <= i - 1。即 dp[i] 一定由 0 ~ i-1 的已知最长子序列长度 + 1 转换而来；

        初始化：每一个位置 i 所对应的 dp[i] 的起始长度都为 1。

        确定遍历顺序：因为 dp[i] 是从前往后推导而来，因此 i 从前往后；j 是遍历 0 ~ i-1，顺序无所谓，默认也从前往后。两层循环。

        举例 [0,1,0,3,2] ，推导结果如图：

  1. class Solution {
  2. public:
  3.     int lengthOfLIS(vector<int>& nums) {
  4.         if(nums.size() <= 1) return nums.size();
  5.         vector<int> dp(nums.size(), 1);
  6.         int res = 0;
  7.         for(int i = 1; i < nums.size(); ++i) {
  8.             for(int j = 0; j < i; ++j)
  9.                 if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
  10.             if(dp[i] > res) res = dp[i];    
  11.         }
  12.         return res;
  13.     }
  14. };

        时间复杂度为 O(n^2)。

法二：贪心+二分

        首先是一个简易的贪心前置：若要使上升子序列尽可能长，则我们需要让序列上升得尽可能缓慢，即希望每次在子序列最后加上的数字尽可能小。

        基于此，维护一个数组 d[i]，表示长度为 i 的最长上升子序列的末尾元素的最小值（这个定义是关键，要充分理解 d 的含义），用 len 记录目前最长上升子序列的长度。起始时 len = 1，d[1] = nums[0]。并且，我们发现并可以证明：d[i] 也是关于 i 单调递增的。

        依次遍历数组 nums 中的每个元素，并更新数组 d 和 len 的值。若 nums[i] > d[len] 则更新 len = len + 1，并直接加入到 d 数组末尾；否则在 d[1~len] 中找满足 d[j-1] < nums[i] < d[j] 的下标 j ，并更新 d[j] = nums[i]（换句话说，遇到小于等于 d[len] 的元素，其肯定不满足当前长度的递增子序列要求了，那么我们去前面寻找能够让 nums[i] 正好补充到末尾的 d[k]，并使得 d[k + 1] = nums[i]。）。根据 d 数组的单调性，可以使用二分寻找下标 i ，优化时间复杂度。

        以输入序列 [0,8,4,12,2] 为例：

        第一步插入 0，d=[0]；

        第二步插入 8，d=[0,8]；

        第三步插入 4，d=[0,4]；

        第四步插入 12，d=[0,4,12]；

        第五步插入 2，d=[0,2,12]。

        我们发现，真正对结果 len 有影响的是 nums[i] > d[len]，而 nums[i] < d[len] 只是不断对之前的 d 数组的修正！注意：数组 d 并非存放真正的最长子序列！而修正的目的就是维持 d 数组的特性，使得 d 数组的长度为所求答案，而数组 d 所存放的序列内容与答案无关。

  1. class Solution {
  2. public:
  3.     int lengthOfLIS(vector<int>& nums) {
  4.         int len = 1, n = nums.size();
  5.         //if(n == 0) return 0; 本题干 n >= 1
  6.         vector<int> d(n + 1, 0); // d 数组是从下标1开始的
  7.         d[len] = nums[0];
  8.         for(int i = 1; i < n; ++i) {
  9.             if(nums[i] > d[len]) d[++len] = nums[i];
  10.             else { //在单增的 d 数组中二分查找
  11.                 int l = 1, r = len, pos = 0;
  12.                 while(l <= r) {
  13.                     int mid = (l + r) >> 1;
  14.                     if(d[mid] < nums[i]) {pos = mid; l = mid + 1;}
  15.                     else r = mid - 1;
  16.                 }
  17.                 d[pos + 1] = nums[i];
  18.             } 
  19.         }
  20.         return len;
  21.     }
  22. };

        时间复杂度为 O(n * logn)。数组 nums 长度为 n，依次用数组中的元素去更新数组 d。更新数组 d 需要 O(logn) 的二分。

        当然，我们要善用C++的库，简化版如下：

  1. class Solution {
  2. public:
  3.     int lengthOfLIS(vector<int>& nums) {
  4.         vector<int> g;
  5.         for(int num : nums) {
  6.             auto it = lower_bound(g.begin(), g.end(), num);
  7.             if(it == g.end()) g.push_back(num);
  8.             else *it = num;
  9.         }
  10.         return g.size();
  11.     }
  12. };

        此外，2407. 最长递增子序列 II 由于涉及到线段树，暂时不在本专题讲解。现在我们转回头看上一题的最后一种解法。

LeetCode397.整数替换：

问题描述：

给定一个正整数 n ，你可以做如下操作：

  1. 如果 n 是偶数，则用 n / 2 替换 n 。
  2. 如果 n 是奇数，则可以用 n + 1 或 n - 1 替换 n 。

返回 n 变为 1 所需的 最小替换次数 。

提示：

  • 1 <= n <= 2^31 - 1

代码分析：

法一：DFS（记忆化）

        直接上代码，重点看记忆化：

  1. class Solution {
  2. public:
  3.     unsigned long long dfs(long n) {
  4.         if(n == 1) return 0;
  5.         if(n % 2 == 0) return dfs(n / 2) + 1;
  6.         return min(dfs(n + 1), dfs(n - 1)) + 1;
  7.     }
  8.  
  9.     int integerReplacement(int n) {
  10.         return dfs(n);
  11.     }
  12. };

        时间复杂度为 O(2^{logn})，logn 可看成树的高度，即递归的深度。空间复杂度为 O(logn)，因为每一次递归都会导致 n 减小一半。此外，官解的做法是做了一点的微调，既然 n 为奇数时，加一或减一后，在下一步都需要除 2，不妨将这两步合并到一起！并且这样的好处是，可以避免 n = 2^31 - 1 时计算 n+1 导致溢出：可以用整数除法 \left \lfloor n/2 \right \rfloor+1 和 \left \lfloor n/2 \right \rfloor 分别计算 (n+1) / 2 或 (n-1) / 2，特殊符号表示向下取整。

  1. class Solution {
  2. public:
  3.     int integerReplacement(int n) {
  4.         if(n == 1) return 0;
  5.         if(n % 2 == 0) return 1 + integerReplacement(n / 2);
  6.         return 2 + min(integerReplacement(n / 2), integerReplacement(n / 2 + 1));
  7.     }
  8. };

        时间复杂度为 O(\phi ^{logn})，特殊符号表示 1.618 黄金分割比。

        记忆化能解决之前方法的重复计算，我们可以利用辅助的数组或者哈希表等直接存放结果：

  1. class Solution {
  2. public:
  3.     int dfs(long n, unordered_map<long, int> map) {
  4.         if(n == 1) return 0;
  5.         if(map.find(n) != map.end()) return map[n];
  6.         if(n % 2 == 0) return map[n] = dfs(n / 2, map) + 1;
  7.         return map[n] = min(dfs(n + 1, map), dfs(n - 1, map)) + 1;
  8.     }
  9.  
  10.     int integerReplacement(int n) {
  11.         unordered_map<long, int> map;
  12.         return dfs(n, map);
  13.     }
  14. };

        时间空间复杂度均为 O(logn)。

法二：贪心+位运算

        观察一个数的二进制表示方式，本题意相当于消除多余的 1，直到最后只剩下最低位一个 1。对于偶数肯定只能除以 2，但是对于奇数有两种情况：

  • 若只有最低位一位是 1，做减 1 处理。因为加 1 会使得 1 跑到倒数第二位，后续除 2 后还是要处理这个 1，相当于增加了一次操作。

  • 若最低几位有连续的 1，要做加 1 处理。因为这样会向高位进位，产生连续效应，消灭好几个 1，因此加 1 更能减少操作次数。

  1. class Solution {
  2.     public int integerReplacement(int n) {
  3.         long num = n;
  4.         int ans = 0;
  5.         while (num > 1) {
  6.             if ((num & 1) == 0) {
  7.                 // 是偶数
  8.                 num >>= 1;
  9.             } else if ((num & 0b10) == 0 || num == 3) {
  10.                 // 0b表示二进制，跟0x表示十六进制一样的
  11.                 // 倒数第二位是0，说明只有最低位是1
  12.                 // 3是个特例
  13.                 num--;
  14.             } else {
  15.                 num++;
  16.             }
  17.             ans++;
  18.         }
  19.         return ans;
  20.     }
  21. }

        时间复杂度为 O(logn)。

LeetCode421.数组中两个数的最大异或值（待解决）：

问题描述：

        本题涉及二进制位运算的复杂内容，待后续更新......

代码分析：

        本题涉及二进制位运算的复杂内容，待后续更新......

LeetCode553.最优除法：

问题描述：

给定一正整数数组 nums，nums 中的相邻整数将进行浮点除法。例如， [2,3,4] -> 2 / 3 / 4 。

  • 例如，nums = [2,3,4]，我们将求表达式的值 "2/3/4"。

但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，以便计算后的表达式的值为最大值。

以字符串格式返回具有最大值的对应表达式。

注意：你的表达式不应该包含多余的括号。

示例 1：

输入: [1000,100,10,2]
输出: "1000/(100/10/2)"
解释: 1000/(100/10/2) = 1000/((100/10)/2) = 200
但是，以下加粗的括号 "1000/((100/10)/2)" 是冗余的，
因为他们并不影响操作的优先级，所以你需要返回 "1000/(100/10/2)"。

其他用例:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

说明:

  • 1 <= nums.length <= 10
  • 2 <= nums[i] <= 1000
  • 对于给定的输入只有一种最优除法。

代码分析：

法一：贪心

        本题的贪心若没有经过严谨的推理证明的话，就是直觉。

        首先，题目的数据范围设置得比较宽松，[2, 1000] ，也就是说，单纯的两个数之间作除法，结果是越来越接近 0。若数据存在 (0, 1) 区间或者为负数的，本题的难度就上了一个档次。本题的贪心也比较好想：分子固定为第一个数，其余的数连除并且全部作为分母！

  1. class Solution {
  2. public:
  3.     string optimalDivision(vector<int>& nums) {
  4.         int n = nums.size();
  5.         //因为 n = 1、2 时的构造与后面的通式不同，所以单独拎出来
  6.         if(n == 1) return to_string(nums[0]);
  7.         if(n == 2) return to_string(nums[0]) + "/" + to_string(nums[1]);
  8.         string res = to_string(nums[0]) + "/(" + to_string(nums[1]);
  9.         for(int i = 2; i < n; ++i) res.append("/" + to_string(nums[i]));
  10.         res.append(")");
  11.         return res;
  12.     }
  13. };

法二：区间dp求具体方案

        这是初次接触区间dp，比较难，但是通法。

        设 dp[i][j] 表示数组 nums 索引区间 [i, j] 通过添加不同的符号从而可以获取的最小值与最大值为 minVal_{(i,j)}，maxVal_{(i,j)}，以及它们所对应的表达式字符串为minStr_{(i,j)}，maxStr_{(i,j)}。

        可以通过枚举不同的索引 k（满足 k ∈ [i,j]），从而获取区间 [i, j] 最大值与最小值以及对应的字符串表达式。

  • 通过枚举 k（k ∈ [i,j]）将区间 [i, j] 分为 [i, k]，[k+1, j] 左右两部分，则区间 [i, j] 的最小值可以通过左边部分的最小值除以右边部分的最大值得到，以此类推最大值。

        便可知区间最大值与最小值动态规划的递推公式如下：

minVal_{(i,j)}=min(\frac{minVal_{(i,k)}}{maxVal_{(k+1,j)}}),k\in [i,j)

maxVal_{(i,j)}=max(\frac{maxVal_{(i,k)}}{minVal_{(k+1,j)}}),k\in [i,j)

  • 枚举不同的 k 时，当找到了区间最值时，还需要同时记录最值所对应的表达式字符串。不需要给左边部分添加括号，右边反之。
  1. struct Node {
  2.     double maxVal, minVal;
  3.     string minStr, maxStr;
  4.     Node() {
  5.         this->minVal = 10000.0;
  6.         this->maxVal = 0.0;
  7.     }
  8. };
  9.  
  10. class Solution {
  11. public:
  12.     string optimalDivision(vector<int>& nums) {
  13.         int n = nums.size();
  14.         vector<vector<Node>> dp(n, vector<Node>(n));
  15.         for(int i = 0; i < n; ++i) {
  16.             dp[i][i].minVal = nums[i];
  17.             dp[i][i].maxVal = nums[i];
  18.             dp[i][i].minStr = to_string(nums[i]);
  19.             dp[i][i].maxStr = to_string(nums[i]);
  20.         }
  21.         for(int i = 1; i < n; ++i) { //控制索引区间长度
  22.             for(int j = 0; j + i < n; ++j) {
  23.                 for(int k = j; k < j + i; ++k) {
  24.                     if(dp[j][j + i].maxVal < dp[j][k].maxVal / dp[k + 1][j + i].minVal) {
  25.                         dp[j][j + i].maxVal = dp[j][k].maxVal / dp[k + 1][j + i].minVal;
  26.                         if(k + 1 == j + i) dp[j][j + i].maxStr = dp[j][k].maxStr + "/" + dp[k + 1][j + i].minStr; //右边部分只含有一个数字，返回结果代码不含有冗余括号
  27.                         else dp[j][j + i].maxStr = dp[j][k].maxStr + "/(" + dp[k + 1][j + i].minStr + ")"; //右边部分包含多个数字，需要加上括号
  28.                     }
  29.                     if(dp[j][j + i].minVal > dp[j][k].minVal / dp[k + 1][j + i].maxVal) {
  30.                         dp[j][j + i].minVal = dp[j][k].minVal / dp[k + 1][j + i].maxVal;
  31.                         if(k + 1 == j + i) dp[j][j + i].minStr = dp[j][k].minStr + "/" + dp[k + 1][j + i].maxStr;
  32.                         else dp[j][j + i].minStr = dp[j][k].minStr + "/(" + dp[k + 1][j + i].maxStr + ")";
  33.                     } 
  34.                 }
  35.             }
  36.         }
  37.         return dp[0][n -1].maxStr;
  38.     }
  39. };

        时空复杂度均为 O(n^3)，n 为数组的长度。dp数组长度为 n^2，计算 dp 中每一项元素需要 O(n)，数组中元素的最长长度为 O(n)。

LeetCode564.寻找最近的回文数（难）：

问题描述：

给定一个表示整数的字符串 n ，返回与它最近的回文整数（不包括自身）。如果不止一个，返回较小的那个。

“最近的”定义为两个整数差的绝对值最小。

提示:

  • 1 <= n.length <= 18
  • n 只由数字组成
  • n 不含前导 0
  • n 代表在 [1, 10^18 - 1] 范围内的整数

代码分析：

        本题题干要求短小，但属实细节狂魔，很难把情况考虑全面，初次接触只能一点点debug补全逻辑。还有，本题一旦选择了某一条思路，就一口气走到黑，也说明了有些时候选择大于努力。

        第一遍尝试，补丁打得满天飞，代码臃肿不堪：

  1. class Solution {
  2. public:
  3.     bool isPowerOfX(int base, int num) { //base取10
  4.         int oneNum = 0;
  5.         int mod = 0;
  6.         do{
  7.             mod = num % base;
  8.             num = num / base;
  9.             if(mod != 1 && mod != 0) return false;
  10.             else if(mod == 1) ++oneNum;
  11.         } while(num > 0);
  12.         return oneNum == 1;
  13.     }
  14.     string nearestPalindromic(string n) {
  15.         int len = n.size(), mid = (len - 1) / 2;
  16.         if(len == 1) return to_string(stoi(n) - 1); //小于等于10，返回 n-1
  17.         if(isPowerOfX(10, stoi(n))) return to_string(stoi(n) - 1);
  18.         if(isPowerOfX(10, (stoi(n) - 1))) return to_string(stoi(n) - 2);
  19.         if(isPowerOfX(10, (stoi(n) + 1))) return to_string(stoi(n) + 2);
  20.         string nn = n; reverse(nn.begin(), nn.end());
  21.         string origin = n.substr(0, mid + 1) + nn.substr(len % 2 == 0 ? len - 1 - mid : len - mid, len % 2 == 0 ? mid + 1 : mid);
  22.         string low = origin, high = origin;
  23.         int lenn = origin.size(), midd = (lenn - 1) / 2;
  24.         if(lenn % 2 == 0) {low.replace(midd, 2, to_string((origin[midd] - '0') - 1) + to_string((origin[midd] - '0') - 1)); high.replace(midd, 2, to_string((origin[midd] - '0') + 1) + to_string((origin[midd] - '0') + 1));}
  25.         else {low.replace(midd, 1, to_string((origin[midd] - '0') - 1)); high.replace(midd, 1, to_string((origin[midd] - '0') + 1));}
  26.         
  27.         if(n == "100") return low;
  28.         if(n == origin) return low;
  29.         return stoi(n) - stoi(origin) > 0 ? (abs(stoi(high) - stoi(n)) < abs(stoi(n) - stoi(origin)) ? high : origin) : (abs(stoi(origin) - stoi(n)) < abs(stoi(n) - stoi(low)) ? origin : low);
  30.     }
  31. };

        第二次重新做本题，这次小心翼翼地理思路，分情况讨论，前后一天多的不连续时间段里一直调试，终于在不借助任何参考答案的情况下独立AC。评论区有人说这是某节三面的题目，属实为难人，在一小时内都近乎登天，不想要石锤了（doge）。学习本题解参考答案没有太大意义。

  1. class Solution {
  2. public:
  3.     string nearestPalindromic(string n) {
  4.         int len = n.size(), mid1 = (len - 1) / 2, mid2 = len / 2 - 1;
  5.         string origin, low, high;
  6.         if(len % 2 != 0) {
  7.             //长度为奇数的逻辑
  8.             if(len == 1) return to_string(stoll(n) - 1);
  9.             else {
  10.                 string nn = n.substr(0, mid1); reverse(nn.begin(), nn.end());
  11.                 origin = n.substr(0, mid1 + 1) + nn;
  12.                 if(n.substr(0, mid1 + 1) == to_string((long long)pow(10, mid1))) low = to_string((long long)pow(stoll(n.substr(0, mid1 + 1)), 2) - 1);
  13.                 else {
  14.                     string lown = to_string(stoll(n.substr(0, mid1 + 1)) - 1);
  15.                     low = lown;
  16.                     lown = lown.substr(0, mid1);
  17.                     reverse(lown.begin(), lown.end());
  18.                     low += lown;
  19.                 }
  20.                 if(n.substr(0, mid1 + 1) == to_string((long long)pow(10, mid1 + 1) - 1)) high = to_string((stoll(n.substr(0, mid1 + 1)) + 1) * (long long)pow(10, mid1) + 1);
  21.                 else {
  22.                     string highn = to_string(stoll(n.substr(0, mid1 + 1)) + 1);
  23.                     high = highn;
  24.                     highn = highn.substr(0, mid1);
  25.                     reverse(highn.begin(), highn.end());
  26.                     high += highn;
  27.                 }
  28.             }  
  29.         } else {
  30.             //长度为偶数的逻辑
  31.             if(len == 2 && n[0] == '1') {
  32.                 if(stoll(n) >= 10 && stoll(n) <= 11) return "9";
  33.                 else if(stoll(n) >= 12 && stoll(n) <= 16) return "11";
  34.                 else return "22";
  35.             } else {
  36.                 string nn = n.substr(0, mid2 + 1); reverse(nn.begin(), nn.end());
  37.                 origin = n.substr(0, mid2 + 1) + nn;
  38.                 if(n.substr(0, mid2 + 1) == to_string((long long)pow(10, mid2))) low = to_string((long long)pow(stoll(n.substr(0, mid2 + 1)), len - 1) - 1);
  39.                 else {
  40.                     string lown = to_string(stoll(n.substr(0, mid2 + 1)) - 1);
  41.                     low = lown;
  42.                     reverse(lown.begin(), lown.end());
  43.                     low += lown;
  44.                 }
  45.                 if(n.substr(0, mid2 + 1) == to_string((long long)pow(10, mid2 + 1) - 1)) high = to_string((long long)pow(10, len) + 1);
  46.                 else {
  47.                     string highn = to_string(stoll(n.substr(0, mid2 + 1)) + 1);
  48.                     high = highn;
  49.                     reverse(highn.begin(), highn.end());
  50.                     high += highn;
  51.                 }
  52.             }
  53.         }
  54.         //比较的逻辑
  55.         if(n == origin) return abs(stoll(high) - stoll(origin)) < abs(stoll(origin) - stoll(low)) ? high : low;
  56.         return stoll(n) - stoll(origin) > 0 ? (abs(stoll(high) - stoll(n)) < abs(stoll(n) - stoll(origin)) ? high : origin) : (abs(stoll(origin) - stoll(n)) < abs(stoll(n) - stoll(low)) ? origin : low);
  57.     }
  58. };

        总结就是：模拟题做这一题就够了（折煞人了）。

LeetCode630.课程表III：

问题描述：

这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [duration_{i}, lastDay_{i}] 表示第 i 门课将会 持续 上 duration_{i} 天课，并且必须在不晚于 lastDay_{i} 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

示例 1：

输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出：3
解释：
这里一共有 4 门课程，但是你最多可以修 3 门：
首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。

提示:

  • 1 <= courses.length <= 10^4
  • 1 <= durationi, lastDayi <= 10^4

代码分析：

贪心+优先队列：

        经典问题。

        首先上来一个贪心结论（证明看官解）：

        对于两门课 (t1,d1) 和 (t2,d2)，若后者的关闭时间较晚，即 d1 ≤ d2，那么后者不慌，先学习前者，这是当前最优的方案。但是课程塞满的时候，我们就需要后序的贪心法则来维护全局最优。

        简单说【先学习前者，再学习后者】成立不能由【先学习后者，再学习前者】成立推出；但若能【先学习前者，再学习后者】，就一定能【先学习后者，再学习前者】！

        因此，将所有课程按照结束时间的升序排列，可以保证优先考虑加入先结束的课程。当课程塞满（当前所有的课程的修读时间总和超过了当前遍历到的课程的结束时间）的时候，用当前的遍历到的（结束时间一定更晚，但耗时可能更短）替换掉耗时最长的课程（需要使用优先队列维护最大的时长）。这样做的意义在于：用更少的时间完成了相同数量的课程，可以确保后面加入更多的课程且不可能比原来单纯的【先学习前者，再学习后者】方案的课程少！

  1. class Solution {
  2.     public int scheduleCourse(int[][] courses) {
  3.         Arrays.sort(courses, (a,b)->(a[1]-b[1]));
  4.         PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->(b-a)); //之前修读课程按照时长降序维护
  5.         int t = 0; //之前课程总修读时间
  6.         for(int[] course : courses) {
  7.             if(t + course[0] > course[1] && pq.size() > 0 && pq.peek() > course[0]) t -= pq.poll();
  8.             if(t + course[0] <= course[1]) {t += course[0]; pq.offer(course[0]);}
  9.         }
  10.         return pq.size();         
  11.     }
  12. }

        时间复杂度为 O(n * logn)。开头排序 O(n * logn)，单次优先队列的操作需要 O(logn)，每个课程最多被放入和取出优先队列一次，因此优先队列这一部分也为 O(n * logn)。

LeetCode646.最长数对链：

问题描述：

给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [left_{i}, right_{i}] 且 left_{i} < right_{i} 。

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

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

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

示例 1：

输入：pairs = [[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4] 。

提示：

  • n == pairs.length
  • 1 <= n <= 1000
  • -1000 <= lefti < righti <= 1000

代码分析：

        本题和【435.无重叠区间】、【300.最长自增子序列】都有一定联系。

  1. 本题数对链中相邻的数对，前者的结束位置必须小于后者的开始位置，擦边是不被允许的。而435.中允许擦边。
  2. 本题返回最长数对的长度，435.返回最少删除的区间数（原长 - 最长数对长），300.返回最长递增子序列长度。本题的数对链也可看作是递增的序列，因此也可以用 LIS 的方法来做！

法一：LIS动态规划

        定义 dp[i] 为以 pairs[i] 结尾的最长数对链的长度。具体计算时，找出所有满足 pairs[i][0] > pairs[j][1] 的 j，则 dp[i] = max(dp[j]) + 1。因为该动归思路要求计算 dp[i] 时，所有潜在的 dp[j] 已经计算完成，所以需要将 pairs 数组排序。初始化时，dp 全赋值为 1。具体的五步曲分析不再赘述，详情参考300.。时间复杂度为 O(n^2)。

  1. class Solution {
  2. public:
  3.     int findLongestChain(vector<vector<int>>& pairs) {
  4.         int n = pairs.size();
  5.         sort(pairs.begin(), pairs.end());
  6.         vector<int> dp(n, 1);
  7.         for(int i = 0; i < n; ++i) 
  8.             for(int j = 0; j < i; ++j)
  9.                 if(pairs[i][0] > pairs[j][1])
  10.                     dp[i] = max(dp[i], dp[j] + 1);
  11.         return dp[n - 1];            
  12.     }
  13. };

法二：贪心+二分

        具体详见300.，arr[i] 表示长度为 i 的数对链的末尾可取得的最小值（arr 里肯定存放右边界）。遇到一个新数对时，先二分查找该数对可以放置的位置，再更新 arr 值。

  1. 版本一：
  2. class Solution {
  3. public:
  4.     int findLongestChain(vector<vector<int>>& pairs) {
  5.         sort(pairs.begin(), pairs.end()); //默认按pairs[0]左边界升序
  6.         vector<int> arr;
  7.         for(auto p : pairs) {
  8.             int x = p[0], y = p[1];
  9.             if(arr.size() == 0 || x > arr.back()) arr.emplace_back(y);
  10.             else {
  11.                 int idx = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
  12.                 arr[idx] = min(arr[idx], y);
  13.             }
  14.         } 
  15.         return arr.size();            
  16.     }
  17. };
  18.  
  19. 版本二：
  20. class Solution {
  21. public:
  22.     int findLongestChain(vector<vector<int>>& pairs) {
  23.         sort(pairs.begin(), pairs.end()); //默认按pairs[0]左边界升序
  24.         int len = 1, n = pairs.size();
  25.         vector<int> arr(n + 1, 0);
  26.         arr[len] = pairs[0][1];
  27.         for(int i = 1; i < n; ++i) {
  28.             if(pairs[i][0] > arr[len]) arr[++len] = pairs[i][1];
  29.             else {
  30.                 int l = 1, r = len, pos = 0;
  31.                 while(l <= r) {
  32.                     int mid = (l + r) >> 1;
  33.                     if(arr[mid] < pairs[i][1]) {pos = mid; l = mid + 1;}
  34.                     else r = mid - 1;
  35.                 }
  36.                 arr[pos + 1] = pairs[i][1];
  37.             }
  38.         }
  39.         return len;
  40.     }    
  41. };

        时间复杂度为 O(n * logn)。

法三：贪心

        贪谁的心，就按照谁进行排序，然后不停地判断 除谁之外的东西 能否满足条件。

        局部最优：每次挑选时，优先挑选 pairs[i][1] 较小的，这样能给后序挑选留下更多空间。

  1. class Solution {
  2. public:
  3.     int findLongestChain(vector<vector<int>>& pairs) {
  4.         int curr = INT_MIN, res = 0;
  5.         sort(pairs.begin(), pairs.end(), [](const vector<int> &a, const vector<int> &b){
  6.             return a[1] < b[1];
  7.         });
  8.         for(auto &p : pairs) {
  9.             if(curr < p[0]) {curr = p[1]; res++;}
  10.         }
  11.         return res;
  12.     }    
  13. };

        时间复杂度为 O(n * logn)。

LeetCode698.划分为k个相等的子集：

问题描述：

给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

示例 1：

输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

提示：

  • 1 <= k <= len(nums) <= 16
  • 0 < nums[i] < 10000
  • 每个元素的频率在 [1,4] 范围内

代码分析：

        本题难度已经很大了，至少 hard。只是因为使用搜索解法可能会稍微容易一丝，但主流做法存在一定难度值得参考。

法一：DFS+剪枝

        需要将数组 nums 划分为 k 个子集，每个子集和相等。因此先累加所有元素的和 s，若不能被 k 整除，说明无法划分，直接返回 false。

        若能被 k 整除，创建一个长度为 k 的数组 cur（桶），表示当前每个子集的和。

        对 nums 进行降序排序（优先安排大元素，尽可能减少搜索次数），然后从头开始，依次尝试将其加入到 cur 的每个子集中。这里若将 nums[i] 加入到某个子集 cur[j] 后，子集和超过 s / k，说明无法放入，可以直接跳过；另，若 cur[j] 与 cur[j-1]相等，意味着在 cur[j-1] 的时候就已经完成了搜索，也可以跳过当前搜索。

        若能将所有元素都加入 cur 中，说明可以划分为 k 个子集，返回 true。

  1. class Solution {
  2. public:
  3.     bool canPartitionKSubsets(vector<int>& nums, int k) {
  4.         int s = accumulate(nums.begin(), nums.end(), 0);
  5.         if(s % k) return false;
  6.         s /= k;
  7.         int n = nums.size();
  8.         vector<int> cur(k);
  9.         function<bool(int)> dfs = [&](int i) { //lamda表达式
  10.             if(i == n) return true;
  11.             for(int j = 0; j < k; ++j) {
  12.                 //关键剪枝。上一个桶放置失败了，当前桶的值若和上个桶一样，则也不能放。
  13.                 if(j && cur[j] == cur[j - 1]) continue;
  14.                 cur[j] += nums[i];
  15.                 if(cur[j] <= s && dfs(i + 1)) return true;
  16.                 cur[j] -= nums[i];
  17.             }
  18.             return false;
  19.         };
  20.         sort(nums.begin(), nums.end(), greater<int>());
  21.         return dfs(0);
  22.     }
  23. };

        暴力剪枝不分析时间复杂度。

法二：状压+记忆化搜索

        我们可以使用记忆化搜索这种【自顶向下】的方式来求解原始状态的可行性。首先，开头的直接判断还是老样子。我们注意到 n = nums.size() 为[1, 16]，所以可以用一个整数 state 来表示当前可用的数字集合：从低位到高位，第 i 位为 1 表示数字 nums[i] 可以使用，否则表示 nums[i] 已被划分。当然状态压缩的精髓在于位运算，若 (state >> i) & 1 == 0，表明第 i 个元素未被划分。

        目标为从全部元素中凑出 k 个和为 s 的子集，记当前子集的和为 t。则在未划分第 i 个元素时：

  • 若 t + nums[i] > s，不能添加，由于 nums 升序，后序元素也无法添加，直接返回 false。
  • 若否，则添加到当前子集中，状态变为 state | (1 << i)，然后继续对未划分的元素进行搜索。需要注意，若 t + nums[i] = s，则恰好可以得到一个完美的子集，下一步将 t 归零（(t + nums[i]) % s），并继续划分下一个子集。

        为避免重复搜索，可以使用一个长度为 2^n 的数组 f 记录每个状态下的搜索结果。数组 f 有三个可能的值：

  • 0：当前状态还未搜索过；
  • -1：当前状态下无法划分为 k 个子集；
  • 1：当前状态下可以划分为 k 个子集。
  1. class Solution {
  2. public:
  3.     bool canPartitionKSubsets(vector<int>& nums, int k) {
  4.         int s = accumulate(nums.begin(), nums.end(), 0);
  5.         if(s % k) return false;
  6.         s /= k;
  7.         sort(nums.begin(), nums.end());
  8.         int n = nums.size();
  9.         int mask = (1 << n) - 1;
  10.         vector<int> f(1 << n);
  11.         function<bool(int, int)> dfs = [&](int state, int t) { //lamda表达式
  12.             if(state == mask) return true;
  13.             if(f[state]) return f[state] == 1;
  14.             for(int i = 0; i < n; ++i) {
  15.                 if(state >> i & 1) continue;
  16.                 if(t + nums[i] > s) break;
  17.                 if(dfs(state | 1 << i, (t + nums[i]) % s)) {
  18.                     f[state] = 1;
  19.                     return true;
  20.                 }
  21.             }
  22.             f[state] = -1;
  23.             return false;
  24.         };
  25.         return dfs(0, 0);
  26.     }
  27. };

        时间复杂度为 O(n * 2^n)。对于每个状态，需要遍历数组，O(n)；状态总数为 2^n。

法三：状压+动态规划

        同样可以使用动态规划这种【自底向上】的方法来求解是否存在可行方案。其代码结构与法二差不多，时空复杂度与法二一致。

  1. class Solution {
  2. public:
  3.     bool canPartitionKSubsets(vector<int>& nums, int k) {
  4.         int s = accumulate(nums.begin(), nums.end(), 0);
  5.         if(s % k) return false;
  6.         s /= k;
  7.         sort(nums.begin(), nums.end());
  8.         int n = nums.size();
  9.         int mask = (1 << n) - 1;
  10.         vector<bool> dp(1 << n, false);
  11.         vector<int> curSum(1 << n, 0);
  12.         dp[0] = true;
  13.         for(int i = 0; i < 1 << n; ++i) {
  14.             if(!dp[i]) continue;
  15.             for(int j = 0; j < n; ++j) {
  16.                 if(curSum[i] + nums[j] > s) break;
  17.                 if(((i >> j) & 1) == 0) {
  18.                     int next = i | (1 << j);
  19.                     if(!dp[next]) {curSum[next] = (curSum[i] + nums[j]) % s; dp[next] = true;}
  20.                 }
  21.             }
  22.         }
  23.         return dp[(1 << n) - 1];
  24.     }
  25. };

        本题是初次接触状压dp，还有几道类型十分相似的题目，除了473.只需要修改参数 k = 4 外，其余两道题稍有不同，也更加有难度，只讲解一下1723.和2305.（注：1723.和2305.题目意思是一样的）

473. 火柴拼正方形 、1723. 完成所有工作的最短时间 、2305. 公平分发饼干 。

LeetCode1723.完成所有工作的最短时间：

问题描述：

给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。

请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。

返回分配方案中尽可能 最小 的 最大工作时间 。

示例 1：

输入：jobs = [1,2,4,7,8], k = 2
输出：11
解释：按下述方式分配工作：
1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11）
2 号工人：4、7（工作时间 = 4 + 7 = 11）
最大工作时间是 11 。

提示：

  • 1 <= k <= jobs.length <= 12
  • 1 <= jobs[i] <= 10^7

代码分析：

        最大工作时间最小化，意思是，安排工作时，每个人都尽量分配匀称一点，既不太多也不太少，这里容易想到平均值，但是很遗憾，示例具有迷惑性，本题与平均值之间没有任何联系的。因此难度相较上一题大了一些。

法一：二分+回溯+剪枝

        首先，你必须想到这关键的一点：如何找到这个尽可能小的最大值呢？对于 k 个人，设置一个【每个人最大运输量】的大小为 limit。若在该指标下工作能分完，那么方案可行，反则反之。而且我们可以得到 limit 的范围：最小为 jobs 中的最大值（不必多解释），最大为 jobs 之和（全分给一个人，但是这个情况取不到，因为其他人没活干，不满足题目要求）。

        用二分查找 [minlimit, maxlimit] 中第一个满足要求的 limit，即为所求！

  1. class Solution {
  2. public:
  3.     bool backtrack(vector<int> &jobs, vector<int> &workloads, int idx, int limit) {
  4.         if(idx >= jobs.size()) return true;
  5.         int cur = jobs[idx];
  6.         for(auto &workload : workloads) {
  7.             if(workload + cur <= limit) {
  8.                 workload += cur;
  9.                 if(backtrack(jobs, workloads, idx + 1, limit)) return true;
  10.                 workload -= cur;
  11.             }
  12.             //若当前工人未被分配工作，那么下一个工人也必然未被分配
  13.             //或者当前工作恰能使该工人的工作量达到了上限
  14.             //这两种情况都无需继续尝试分配工作
  15.             if(workload == 0 || workload + cur == limit) break;
  16.         }
  17.         return false;
  18.     }
  19.     bool check(vector<int> &jobs, int k, int limit) {
  20.         vector<int> workloads(k, 0); //第 i 个工人当前已被分配的工作量
  21.         return backtrack(jobs, workloads, 0, limit);
  22.     }
  23.     int minimumTimeRequired(vector<int>& jobs, int k) {
  24.         sort(jobs.begin(), jobs.end(), greater<int>());
  25.         int l = jobs[0], r = accumulate(jobs.begin(), jobs.end(), 0);
  26.         while(l < r) {
  27.             int mid = (l + r) >> 1;
  28.             if(check(jobs, k, mid)) r = mid;
  29.             else l = mid + 1;
  30.         }
  31.         return l;
  32.     }
  33. };

        时间复杂度为 O(n * logn + log(S-M) * k^n)。n 为数组 jobs 的长度，S 是 jobs 的元素之和，M 是 jobs 中元素最大值。最坏情况下每次二分需要遍历所有分配方案的排列，但经过一系列优化后避免了绝大部分不必要的计算。

法二：状压+动态规划

        按顺序给每一个工人安排工作，注意到当给第 i 个人分配时，可供选择的分配方案仅和前 i - 1 个人被分配的工作有关，因此考虑动态规划，只需要记录已经被分配了工作的工人数量以及已被分配的工作是哪些即可。

        因为工作数量较少，可以使用状态压缩的方式来表示已经被分配的工作是哪些。具体的，假设有 n 个工作需要被分配，使用一个 n 位的二进制整数来表示工作的分配情况。已被分配置位 1，未被分配置位 0。

        状态方程：f[i][j] 表示 给前 i 个人分配工作，工作的分配情况为 j （是一个二进制整数）时，完成所有工作的最短时间。

        状态转移：f[i][j]=min_{j^{'}\in j}\left \{ \left. max(f[i-1][C_{j}^{j'}],sum[j']) \right \} \right.。

        sum[j'] 表示集合 j' 中总工作量，C_{j}^{j'} 表示集合 j 中子集 j' 的补集。转移方程的含义为：枚举 j 的每一个子集 j'，作为分配给工人 i 的工作，这样就需要给前 i-1 个人分配 C_{j}^{j'} 的工作。

        在代码中，首先预处理出 sum 数组，初始化 f[0][j] = sum[j]，最终答案为 f[k-1][2^n-1]（给全部 k 个人分配全部 n 个工作所用的最短时间）。

  1. class Solution {
  2. public:
  3.     int minimumTimeRequired(vector<int>& jobs, int k) {
  4.         int n = jobs.size();
  5.         vector<int> sum(1 << n);
  6.         for(int i = 1; i < (1 << n); ++i) {
  7.             int x = __builtin_ctz(i), y = i - (1 << x); //函数返回二进制下 i 末尾 0 的个数，y 为补集
  8.             sum[i] = sum[y] + jobs[x];
  9.         }
  10.  
  11.         vector<vector<int>> dp(k, vector<int>(1 << n));
  12.         for(int i = 0; i < (1 << n); ++i) dp[0][i] = sum[i];
  13.  
  14.         for(int i = 1; i < k; ++i) {
  15.             for(int j = 0; j < (1 << n); ++j) {
  16.                 int minn = INT_MAX;
  17.                 //枚举 j 的每个子集
  18.                 for(int x = j; x; x = (x - 1) & j) minn = min(minn, max(dp[i - 1][j - x], sum[x]));
  19.                 dp[i][j] = minn;
  20.             }
  21.         }
  22.         return dp[k - 1][(1 << n) - 1];
  23.     }
  24. };

        时间复杂度为 O(n * 3^n)。

LeetCode757.设置交集大小至少为2：

问题描述：

给你一个二维整数数组 intervals ，其中 intervals[i] = [start_{i}, end_{i}] 表示从 start_{i} 到 end_{i} 的所有整数，包括 start_{i} 和 end_{i} 。

包含集合 是一个名为 nums 的数组，并满足 intervals 中的每个区间都 至少 有 两个 整数在 nums 中。

  • 例如，如果 intervals = [[1,3], [3,7], [8,9]] ，那么 [1,2,4,7,8,9] 和 [2,3,4,8,9] 都符合 包含集合 的定义。

返回包含集合可能的最小大小。

示例 1：

输入：intervals = [[1,3],[3,7],[8,9]]
输出：5
解释：nums = [2, 3, 4, 8, 9].
可以证明不存在元素数量为 4 的包含集合。

提示：

  • 1 <= intervals.length <= 3000
  • intervals[i].length == 2
  • 0 <= start_{i} < end_{i} <= 10^8

代码分析：

贪心：

        本题可以借鉴 452. 思路，兼顾一下交集的两个数。

        首先按照右端点从小到大排序，不妨让 p1 和 p2 代表目前选址中的最大两个数，那么初始值为第一个区间右端点处的两个数值（尽量选取靠右的数字以增大与后区间相交的可能性）。

        然后从第二个区间开始验证，若两个数字都在区间内，无需处理；若较大的那个数都不在区间内，那么两个数都不在区间内，把当前区间最右端的两点换成 p1、p2 并添加；若较大的在内，较小的不在内，那么只需多加一个数（这里也还分两种情况：1.此时较大的数字是右端点，那么需要把较小的数字移动到较大数字的左侧即可；2.否则，较小的数字变成此时的较大的数字，较大的数字变成区间的右端点）。

  1. class Solution {
  2.     public int intersectionSizeTwo(int[][] intervals) {
  3.         Arrays.sort(intervals, (a,b)->a[1]-b[1]);
  4.         int pre1 = intervals[0][1] - 1, pre2 = intervals[0][1], ans = 2;
  5.         for(int i = 1; i < intervals.length; ++i) {
  6.             if(pre1 >= intervals[i][0] && pre2 <= intervals[i][1]) continue;
  7.             else if(pre2 < intervals[i][0]) {
  8.                 ans += 2;
  9.                 pre1 = intervals[i][1] - 1;
  10.                 pre2 = intervals[i][1];
  11.             }
  12.             else if(pre1 < intervals[i][0]) {
  13.                 ans++;
  14.                 if(pre2 == intervals[i][1]) pre1 = pre2 - 1;
  15.                 else {
  16.                     pre1 = pre2;
  17.                     pre2 = intervals[i][1];
  18.                 }
  19.  
  20.             }
  21.         }
  22.         return ans;
  23.     }
  24. }

LeetCode765.情侣牵手：

问题描述：

n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。

人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1)。

返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起。 每次交换可选择任意两人，让他们站起来交换座位。

示例 1:

输入: row = [0,2,1,3]
输出: 1
解释: 只需要交换row[1]和row[2]的位置即可。

提示:

  • 2n == row.length
  • 2 <= n <= 30
  • n 是偶数
  • 0 <= row[i] < 2n
  • row 中所有元素均无重复

代码分析：

法一：并查集

        首先，直接一个贪心结论：假设某个连通块里有 A 对情侣，至少要交换 A - 1 次就可以让他们彼此牵手！（暂不证明）

        可以直接用并查集来做，由于0和1、2和3......互为情侣的两个编号除以 2 （向下取整）对应同一个数字，可直接作为它们的【情侣组】编号。

  1. class Solution {
  2.     public int minSwapsCouples(int[] row) {
  3.         int len = row.length;
  4.         int N = len / 2;
  5.         UnionFind unionFind = new UnionFind(N);
  6.         for(int i = 0; i < len; i += 2) unionFind.union(row[i] / 2, row[i + 1] / 2);
  7.         return N - unionFind.getCount();
  8.     }
  9.  
  10.     private class UnionFind {
  11.         private int[] parent;
  12.  
  13.         private int count;
  14.  
  15.         public int getCount() {
  16.             return count;
  17.         }
  18.  
  19.         public UnionFind(int n) {
  20.             this.count = n;
  21.             this.parent = new int[n];
  22.             for(int i = 0; i < n; ++i) parent[i] = i;
  23.         }
  24.  
  25.         public int find(int x) {
  26.             while(x != parent[x]) {
  27.                 parent[x] = parent[parent[x]];
  28.                 x = parent[x];
  29.             }
  30.             return x;
  31.         }
  32.         
  33.         public void union(int x, int y) {
  34.             int rootX = find(x);
  35.             int rootY = find(y);
  36.             if(rootX == rootY) return;
  37.             parent[rootX] = rootY;
  38.             count--;
  39.         }
  40.     }
  41. }

法二：反向索引

        遍历数组，i += 2，两个数一对，先看第一个数（固定它不动，寻找应该跟它配对的情侣的位置）。若它的情侣正好在 i+1 处，无需交换，直接看下一对；否则就交换，swap(i+1,情侣位置)。这种思路比较 nice，也易于小朋友们理解。

  1. class Solution {
  2.     public int minSwapsCouples(int[] row) {
  3.         int n = row.length;
  4.         int[] indexMap = new int[n]; //反向索引表，row[i] = num => index[num] = i
  5.         for(int i = 0; i < n; ++i) indexMap[row[i]] = i;
  6.         int count = 0;
  7.         for(int i = 0; i < n - 1; i += 2) {
  8.             int p1 = row[i];
  9.             int p2 = (p1 & 1) == 0 ? p1 + 1 : p1 - 1; //p1的情侣
  10.             if(row[i + 1] == p2) continue; //p1和p2正好挨着，无需交换
  11.             int index = indexMap[p2]; //p2的位置
  12.             swap(row, indexMap, i + 1, index);
  13.             count++;
  14.         }
  15.         return count;
  16.     }
  17.  
  18.     private static void swap(int[] row, int[] indexMap, int i, int j) {
  19.         int tmp = row[i];
  20.         row[i] = row[j];
  21.         row[j] = tmp;
  22.         indexMap[row[i]] = i;
  23.         indexMap[row[j]] = j;
  24.     }
  25. }

LeetCode768.最多能完成排序的块：

问题描述：

给你一个整数数组 arr 。

将 arr 分割成若干 块 ，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

返回能将数组分成的最多块数？

示例 1：

输入：arr = [2,1,3,4,4]
输出：4
解释：
可以把它分成两块，例如 [2, 1], [3, 4, 4]。 
然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。

提示：

  • 1 <= arr.length <= 2000
  • 0 <= arr[i] <= 10^8

代码分析：

法一：辅助栈

        想要划分最多的块，并且保证排序后结果与原数组排序后结果相同，则块中的元素必须保证：当前块中的最大值不大于右边所有元素，最小值不小于左边所有元素。

        因此，当遇到比块最大值大的元素，可以单独成块，遇到小的则需要融合，但融合也有讲究，是与当前块融合，还是使得当前块与上一个块融合到一起。

        根据栈的思想，在栈中维护每个块的最大值：

  • 若当前栈为空或者栈顶元素不大于当前元素，就直接入栈。
  • 若栈顶元素大于当前元素，则不能单独成块，需要融合到当前块或者上一个块，直到当前元素大于栈顶元素或者栈为空。
  1. class Solution {
  2.     public int maxChunksToSorted(int[] arr) {
  3.         Deque<Integer> stack = new LinkedList<>();
  4.         for(int num : arr) {
  5.             if(stack.isEmpty() || stack.peek() <= num) stack.push(num);
  6.             else {
  7.                 //融合块，保留当前块的最大元素
  8.                 //比如之前有块[3]、[4]，若 num = 1
  9.                 //则融合为[3,4,1]，因为经排序，1 会到 3 前面去，最大值还是 4
  10.                 int max = stack.pop();
  11.                 //如果持续地弹栈使得上一个块的最大值被弹出，此时已不满足块中的较小值不小于左边所有元素，那么当前栈和上一个栈应该合二为一
  12.                 while(!stack.isEmpty() && stack.peek() > num) stack.pop();
  13.                 stack.push(max);
  14.             }
  15.         }
  16.         //由于stack维护每个块的最大值，所以，最大值的数量反映了块的数量
  17.         return stack.size();
  18.     }
  19. }

        时空复杂度均为 O(n)。

法二：前缀与后缀

        上面我们提到了块中元素的保证，可以考虑维护一个前缀最大值数组和一个后缀最小值数组，只要满足 前缀的最大值 小于等于 后缀的最小值，即可划分。

  1. class Solution {
  2.     public int maxChunksToSorted(int[] arr) {
  3.         int n = arr.length;
  4.         int[] prefixMax = new int[n];
  5.         int[] suffixMin = new int[n];
  6.         prefixMax[0] = arr[0];
  7.         suffixMin[n - 1] = arr[n - 1];
  8.         for(int i = 1; i < n - 1; ++i) {
  9.             prefixMax[i] = Math.max(prefixMax[i - 1], arr[i]);
  10.         }
  11.         for(int i = n - 2; i >= 0; --i) {
  12.             suffixMin[i] = Math.min(suffixMin[i + 1], arr[i]);
  13.         }
  14.         int ans = 1;
  15.         for(int i = 0; i < n - 1; ++i) {
  16.             if(prefixMax[i] <= suffixMin[i + 1]) ans++;
  17.         }
  18.         return ans;
  19.     }
  20. }

        时空复杂度同上。

法三：排序+哈希

        记数组 arr 排完序后为 sortedArr。将原数组分为一块显然没问题，如何判断能否分为符合题意的两块呢？

        若能分两块，则一定能找到一个下标 k，分成 arr[0,...,k] 和 arr[k+1,...,n-1]，使得： arr[0,...,k] 和 sortedArr[0,...,k]、arr[k+1,...,n-1] 和 sortedArr[k+1,...,n-1] 的元素频次都分别相同。判断分为更多块同理。

        从左至右同时遍历 arr 和 sortedArr，并使用哈希表 cnt 来记录两个数组的频次之差。当 cnt 内所有键值均为 0 时，说明当前下标处应该划分新的块。

  1. class Solution {
  2. public:
  3.     int maxChunksToSorted(vector<int>& arr) {
  4.         unordered_map<int, int> cnt;
  5.         int res = 0;
  6.         vector<int> sortedArr = arr;
  7.         sort(sortedArr.begin(), sortedArr.end());
  8.         for(int i = 0; i < sortedArr.size(); ++i) {
  9.             int x = arr[i], y = sortedArr[i];
  10.             if(++cnt[x] == 0) cnt.erase(x);
  11.             if(--cnt[y] == 0) cnt.erase(y);
  12.             if(cnt.size() == 0) res++;
  13.         }
  14.         return res;
  15.     }
  16. };

LeetCode781.森林中的兔子：

问题描述：

森林中有未知数量的兔子。提问其中若干只兔子 "还有多少只兔子与你（指被提问的兔子）颜色相同?" ，将答案收集到一个整数数组 answers 中，其中 answers[i] 是第 i 只兔子的回答。

给你数组 answers ，返回森林中兔子的最少数量。

示例 1：

输入：answers = [1,1,2]
输出：5
解释：
两只回答了 "1" 的兔子可能有相同的颜色，设为红色。 
之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。 
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。 
因此森林中兔子的最少数量是 5 只：3 只回答的和 2 只没有回答的。

提示：

  • 1 <= answers.length <= 1000
  • 0 <= answers[i] < 1000

代码分析：

        本题属于脑筋急转弯题，标准思路也是严谨的数学或逻辑证明得来的，首次做想到属实不易。

        若一只兔子的回答是 x，则有 x 只兔子和回答的兔子颜色相同，该种颜色的兔子共有 x+1 只。有如下事实：

  • 若两只兔子颜色相同，则回答一定相同；若颜色不同，回答也可能相同。
  • 若两只兔子回答相同，则颜色可能相同；若回答不同，则颜色一定不同。

        有贪心结论：为了使兔子的数量最少，尽可能使得回答相同的兔子属于同一种颜色！（暂不证明）

        将所有回答 x 的兔子按照颜色分组（相同的 x），若有 y 只兔子的回答都是 x，则这 y 只可以分成 \left \lceil \frac{y}{x+1} \right \rceil 组（即颜色的种类），每组都有 x+1 只同颜色的兔子。则这 y 只兔子的回答可以确定这部分兔子的最少数量为 (x+1) * \left \lceil \frac{y}{x+1} \right \rceil。

        具体做法为：首先遍历数组 answers 并用哈希表记录每种回答的次数，然后遍历哈希表计算兔子数量。

  1. class Solution {
  2.     public int numRabbits(int[] answers) {
  3.         Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  4.         for(int answer : answers) map.put(answer, map.getOrDefault(answer, 0) + 1);
  5.         int rabbits = 0;
  6.         Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
  7.         for(Map.Entry<Integer, Integer> entry : entries) {
  8.             int answer = entry.getKey(), count = entry.getValue(); //(x,y)
  9.             int groupSize = answer + 1;
  10.             int groupsCount = (count - 1) / groupSize + 1;
  11.             rabbits += groupSize * groupsCount;
  12.         }
  13.         return rabbits;
  14.     }
  15. }

        时空复杂度均为 O(n)。       

LeetCode807.保持城市天际线：

问题描述：

给你一座由 n x n 个街区组成的城市，每个街区都包含一座立方体建筑。给你一个下标从 0 开始的 n x n 整数矩阵 grid ，其中 grid[r][c] 表示坐落于 r 行 c 列的建筑物的 高度 。

城市的 天际线 是从远处观察城市时，所有建筑物形成的外部轮廓。从东、南、西、北四个主要方向观测到的 天际线 可能不同。

我们被允许为 任意数量的建筑物 的高度增加 任意增量（不同建筑物的增量可能不同） 。 高度为 0 的建筑物的高度也可以增加。然而，增加的建筑物高度 不能影响 从任何主要方向观察城市得到的 天际线 。

在 不改变 从任何主要方向观测到的城市 天际线 的前提下，返回建筑物可以增加的 最大高度增量总和 。

示例 1：

输入：grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
输出：35
解释：建筑物的高度如上图中心所示。
用红色绘制从不同方向观看得到的天际线。
在不影响天际线的情况下，增加建筑物的高度：
gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

提示：

  • n == grid.length
  • n == grid[r].length
  • 2 <= n <= 50
  • 0 <= grid[r][c] <= 100

代码分析：

        从前和后来看（前和后可以视作一个角度），天际线只受每一列的最大值影响；从左和右来看（同理也可以视为一个角度），天际线只受每一行的最大值影响。换句话说，我们使得某建筑物高度增加后都不改变当前行、列的最大值即可！

  1. class Solution {
  2. public:
  3.     int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
  4.         int n = grid.size();
  5.         vector<int> rowMax(n);
  6.         vector<int> colMax(n);
  7.         for(int i = 0; i < n; ++i) {
  8.             for(int j = 0; j < n; ++j) {
  9.                 rowMax[i] = max(rowMax[i], grid[i][j]);
  10.                 colMax[j] = max(colMax[j], grid[i][j]);
  11.             }
  12.         }
  13.         int ans = 0;
  14.         for(int i = 0; i < n; ++i)
  15.             for(int j = 0; j < n; ++j)
  16.                 ans += min(rowMax[i], colMax[j]) - grid[i][j];
  17.         return ans;        
  18.     }
  19. };

LeetCode870.优势洗牌：

问题描述：

给定两个长度相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。

返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。

示例 1：

输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出：[24,32,8,12]

提示：

  • 1 <= nums1.length <= 10^5
  • nums2.length == nums1.length
  • 0 <= nums1[i], nums2[i] <= 10^9

代码分析：

        nums1 相当于田忌，nums2 相当于齐威王，短短几个字，就把这题的策略说明白了。

        现在来详细谈谈如何“以小博大”：

  • 若 nums1 中最小值 能比过 nums2 中最小值，直接拿下。
  • 若比不过，就用该值去消耗 nums2 中最大值，就去“恶心他打假赛”。

        去掉这两个使用过的元素，问题变成了一个规模更小（n - 1）的子问题，重复上述步骤，即得到了所有元素的对应关系。

        由于 nums2 不能排序，可以另辟下标数组 ids，对其排序（即 ids 为 nums2 从小到大排好序的模样），用双指针操作 ids，从而一一找到每个下标对应的 nums1 的排列。

        本题值得学习的地方是数组 ids 的巧妙作用和设置手法。

  1. class Solution {
  2. public:
  3.     vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
  4.         int n = nums1.size(), ids[n];
  5.         vector<int> ans(n);
  6.         sort(nums1.begin(), nums1.end());
  7.         iota(ids, ids + n, 0); //从头到尾进行初值为0、递增+1的赋值
  8.         sort(ids, ids + n, [&](int i, int j){
  9.             return nums2[i] < nums2[j];
  10.         });
  11.         int left = 0, right = n - 1;
  12.         for(int x : nums1) ans[x > nums2[ids[left]] ? ids[left++] : ids[right--]] = x;
  13.         return ans;
  14.     }
  15. };

        时间复杂度为 O(n * logn)。

LeetCode871.最低加油次数：

问题描述：

汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。

沿途有加油站，用数组 stations 表示。其中 stations[i] = [position_{i}, fuel_{i}] 表示第 i 个加油站位于出发位置东面 position_{i} 英里处，并且有 fuel_{i} 升汽油。

假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。

为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。

（注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。）

示例 1：

输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
输出：2
解释：
出发时有 10 升燃料。
开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。
然后，从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料），
并将汽油从 10 升加到 50 升。然后开车抵达目的地。
沿途在两个加油站停靠，所以返回 2 。

提示：

  • 1 <= target, startFuel <= 10^9
  • 0 <= stations.length <= 500
  • 1 <= position_{i} < position_{i} + 1 < target
  • 1 <= fueli < 10^9

代码分析：

        本题也是一道很好的考查动态规划或贪心的题目。

法一：动态规划

        二维动态规划，背包+贪心，到达每一站可以选择加或不加油，并更新 到达该站且加了某数量次油的最大可行里程。

  1. 版本一：
  2. class Solution {
  3.     public int minRefuelStops(int target, int startFuel, int[][] stations) {
  4.         long rightMost[][] = new long[stations.length + 1][stations.length + 1]; //表示对于[0, i - 1]范围内的车站，最多加 j 次油可以到达的最远位置
  5.         for(int i = 0; i <= stations.length; ++i) rightMost[i][0] = startFuel; //一次油也不加
  6.         for(int i = 1; i <= stations.length; ++i) {
  7.             if(rightMost[i - 1][i - 1] < stations[i - 1][0]) return -1; //到不了上一站
  8.             for(int j = 1; j <= i; ++j) {
  9.                 if(rightMost[i - 1][j - 1] >= stations[i - 1][0]) rightMost[i][j] = rightMost[i - 1][j - 1] + stations[i - 1][1]; //可以选择在上一站加油
  10.                 rightMost[i][j] = Math.max(rightMost[i][j], rightMost[i - 1][j]); //也可以选择在上一站不加油
  11.             }
  12.         }
  13.         for(int i = 0; i <= stations.length; ++i) 
  14.             if(target <= rightMost[stations.length][i])
  15.                 return i;
  16.         return -1;
  17.     }
  18. }
  19.  
  20. 版本二：记忆化搜索实现dp
  21. class Solution {
  22.     private int target;
  23.     private int startFuel;
  24.     private int[][] stations;
  25.     private Integer[][] memo;
  26.  
  27.     public int minRefuelStops(int target, int startFuel, int[][] stations) {
  28.         this.target = target;
  29.         this.startFuel = startFuel;
  30.         this.stations = stations;
  31.         memo = new Integer[stations.length + 1][stations.length + 1];
  32.         for(int i = 0; i <= stations.length; ++i)
  33.             if(helper(stations.length, i) >= target) 
  34.                 return i;
  35.         return -1;
  36.     }
  37.     
  38.     private int helper(int i, int j) {
  39.         if(j == 0) return startFuel;
  40.         if(i < j) return 0;
  41.         if(memo[i][j] != null) return memo[i][j];
  42.         //第 i-1 个加油站选择加油
  43.         int res = 0;
  44.         if(helper(i - 1, j - 1) >= stations[i - 1][0])
  45.             res = helper(i - 1, j - 1) + stations[i - 1][1];
  46.         //第 i-1 个加油站选择不加油
  47.         res = Math.max(res, helper(i - 1, j));
  48.         memo[i][j] = res;
  49.         return res;    
  50.     }
  51. }

法二：贪心

  1. class Solution {
  2.     public int minRefuelStops(int target, int startFuel, int[][] stations) {
  3.         if(startFuel >= target) return 0;
  4.         int n = stations.length, prev = 0;
  5.         int fuel = startFuel, ans = 0;
  6.         PriorityQueue<Integer> p = new PriorityQueue<>((a,b)->(b-a));
  7.         for(int i = 0; i < n; ++i) {
  8.             int cost = stations[i][0] - prev; //从上一位置走到当前位置需要的油量
  9.             fuel = fuel - cost;
  10.             //若油量不够，需加油以完成这段路
  11.             while(fuel < 0 && !p.isEmpty()) {
  12.                 fuel += p.poll();
  13.                 ans++;
  14.             }
  15.             if(fuel < 0) return -1; //加完后还是不够
  16.             //更新prev的值，将新的加油站的油放车上
  17.             p.offer(stations[i][1]);
  18.             prev = stations[i][0];
  19.         }
  20.         //单独计算最后一个加油站到达 target 的油用量
  21.         fuel = fuel - (target - prev);
  22.         while(fuel < 0 && !p.isEmpty()) {
  23.             fuel += p.poll();
  24.             ans++;
  25.         }
  26.         if(fuel < 0) return -1;
  27.         return ans;
  28.     }
  29. }

LeetCode881.救生艇：

持续更新......（60000字）

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号