此题广为流传,所以不再复述题目,可以查看 LeetCode 188. 买卖股票的最佳时机 IV

写此文的目的是防止学了忘、忘了学,仅记录大概的题解思路,更加详细的思路解析可以查看(均为公众号):

此题依交易次数的不同,可以分为 一次无限次、和 k 次三种题目

以下思路、代码均根据 LeetCode 对应题目写出

一次交易

限制一次交易的情况比较简单,因为只能交易一次,所以需要寻找谷值和峰值,两者相减即最大收益

但同时也要注意时间不能倒流,需要顺序遍历数组

C# 代码

public class Solution {
    public int MaxProfit(int[] prices) {
        if(prices.Length == 0) return 0;
        int max = 0, n = prices.Length;
        int min = prices[0];
        for(int i = 1; i< n; i ++) {
            min = min > prices[i] ? prices[i] : min;
            max = prices[i] - min > max ? prices[i] - min : max;
        }

        return max;
    }
}

无限次交易

无限次交易也比较简单,遵循一个规则:股价逢涨必卖:

  • 如果股价连续几天一直上涨,那么每天都卖峰值一并卖出所获得的收益是相等的
  • 如果股价连续几天一直下跌,那么不卖,没有收益
  • 如果股价振荡,那么可以把每一天看作一次连续上涨或者连续下跌,按照前两个规则买卖

最后得出结论:逢涨必卖

C# 代码

public class Solution {
    public int MaxProfit(int[] prices) {
            if (prices.Length == 0) return 0;
            int maxProfit = 0;

            for (int i = 1; i < prices.Length; i++)
                if (prices[i] > prices[i - 1])
                    maxProfit += prices[i] - prices[i - 1];

            return maxProfit;
    }
}

k 次交易

2 次交易也可以并作 k 次交易

k 次交易事情开始变得复杂了,可以有动态规划贪心这两种理解方式,但产出的代码没有很大的差异

动态规划

动态规划的篇幅较长,可以直接参考 漫画:寻找股票买入卖出的最佳时机(整合版),递推式的推理过程非常清晰

贪心

每次交易有两种操作:买 和 卖,因此就有 2 * k 次收益的变化(建立 2 * k 大小的数组),将这些变化记录下来,每次交易操作时都获取最大值,卖出最后一笔就得到了最大收益

每过一天都模拟在当天价格下进行 k 次交易(遍历一次数据),用 Max 函数记录最大值:

  • 买入:之前的收益 – 当前股价
  • 卖出:之前的收益 + 当前股价

C# 代码

public class Solution {
    public int MaxProfit(int k, int[] prices) {
            if (prices.Length == 1 || prices.Length == 0 || k == 0) return 0;

            int recordCount = 2 * k; // k 次交易,2k 次买卖操作
            int[] profitRecord = new int[recordCount]; //收益记录数组

            for (int i = 0; i < recordCount; i += 2) //将 k 次的买入全部设为第一天股价
                profitRecord[i] = -prices[0]; //以第一天的股价买入

            for (int i = 1; i < prices.Length; i++) {
                for (int j = 0; j < recordCount ; j++) {
                    if (j == 0) profitRecord[j] = Math.Max(profitRecord[j], -prices[i]); //第一天作特殊处理
                    else if (Convert.ToBoolean(j & 1)) profitRecord[j] = Math.Max(profitRecord[j], profitRecord[j - 1] + prices[i]); //卖出操作,现收益 + 当天股价
                    else profitRecord[j] = Math.Max(profitRecord[j], profitRecord[j - 1] - prices[i]); //买入操作,现收益 - 当天股价
                }
            }

            return profitRecord[recordCount - 1]; //记录数组最后的元素
    }
}

题目

题意

给出一串字符,找出其中没有重复字符的最长子串

例如:

给出 abcabcbb,其无重复字符的最长子串为 abc,所以输出为 3

给出 abba,其无重复字符的最长子串为 ab 或 ba,所以输出为 2

解决方法

以下将 无重复字符的最长子串 简称为 最长子串

首先想到的解法就是暴力遍历整个字符串,查找最长子串, 伪代码:

n 为字符串长度,ans 为最长子串的长度

for i = 0; i < n; i++ //子串的起始索引

for j = i + 1; j < n; j++ //子串的尾部索引

for k = i; k < j; k++ //在长度为 [i, j) 的子串内检查

if unique ans = max(ans, j – i) //如果没有重复,更新ans

可见暴力算法的时间复杂度为 O(n^3),很容易就超时,因此需要优化算法。

暴力法中,需要不断的重复检查索引在 [i, j) 的子串内是否存在重复字符,而实际上如果在 [i, j-1) 索引内的子串没有出现重复字符,我们只需要检查 j 处的字符是否存在于之前的子串(即 [i, j-1) 子串)内就可以了。

检查一个元素是否存在于一组元素内,我们可以利用集合的性质——集合中的每个元素只能出现一次,使用 Set 来实现,即 Set.isContain(element),从而使时间复杂度降为 O(1)。

此处的集合即本题所涉及到的 “滑动窗口”,我们要维护这个窗口,使其内部没有重复字符。

在这个维护的过程中得到的所有无重复子串中最长的,就是本题的答案,因此,集合内的元素只要加入了新元素,我们就需要与当前的结果 ans 比较大小,取最大值。

伪代码:

S 为字符串,set 为子串字符集合,n 为字符串长度,ans 为最长子串的长度

i = j = 0

while i 和 j < n

if !set.contains(S[j])

set.add(S[j]), j++, ans = max(ans, j – i) //将新元素加入集合,尾部索引 j 向后移,更新 ans

else //集合中有重复元素

set.delete(S[i]), i++ //如果出现了重复字符,则将起始索引 i 一步步向前移,直到重复元素被删除

上述解法还有优化的空间,可以看到如果集合中出现了重复元素后,起始索引是一个一个向前移动的,我们还可以将起始索引 i 一步到位,直接跳到 j-1 的位置,即跳过一个字符窗口,而不是一个字符。

也就是说,如果在 [i, j) 内发现了重复字符(设重复字符的索引为 j‘),我们不需要一步步增加 i,而是跳过 [i, j’) 这个区间,将 i 的值变为 j’ + 1。

我们可以通过映射字符和索引来存储出现过的字符及其索引。

最终代码 (C#):

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        int i = 0, ans = 0, n = s.Length;
            int[] dic = new int[128];
            for (int j = 0; j < n; j++) {
                i = Math.Max(i, dic[s[j]]);
                ans = Math.Max(ans, j - i + 1);
                dic[s[j]] = j + 1;
            }
            return ans;
    }
}

在更新 i (起始索引)的值时,取最大值的意义在于防止起始索引 i 退回到重复的字符索引之前,例如:

如果 i = dic[s[j]] 而不是 i = Max(i, dic[s[j]])。

对于字符串 abba,j = 2 时(第二个 b 处),i = 2 (dic[b] = j + 1 = 1 +1 = 2,),到 j = 3 时,i 的值会回退到 1( i = dic[a],此时的 dic[a] = 1),导致 ans = Max(2, j – i + 1 = 3 – 1 + 1 = 3)。

因为本题的输入只包括字符,所以使用了 128 长度的数组作为映射——字母的ASCII码决定了其在数组中的位置,数组的值为索引,在 C# 中可以使用 Dictionary<char, int>,Python 中可以使用字典 dic = dict({}),C++中可以使用Map<char, int>。