1247. 交换字符使得字符串相同（中等）

有两个长度相同的字符串 s1 和 s2，且它们其中 只含有 字符 "x" 和 "y"，你需要通过「交换字符」的方式使这两个字符串相同。

每次「交换字符」的时候，你都可以在两个字符串中各选一个字符进行交换。

交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。也就是说，我们可以交换 s1[i] 和 s2[j]，但不能交换 s1[i] 和 s1[j]。

最后，请你返回使 s1 和 s2 相同的最小交换次数，如果没有方法能够使得这两个字符串相同，则返回 -1 。

示例 1：

输入：s1 = "xx", s2 = "yy"

输出：1

解释：

交换 s1[0] 和 s2[1]，得到 s1 = "yx"，s2 = "yx"。

示例 2：

输入：s1 = "xy", s2 = "yx"

输出：2

解释：

交换 s1[0] 和 s2[0]，得到 s1 = "yy"，s2 = "xx" 。

交换 s1[0] 和 s2[1]，得到 s1 = "xy"，s2 = "xy" 。

注意，你不能交换 s1[0] 和 s1[1] 使得 s1 变成 "yx"，因为我们只能交换属于两个不同字符串的字符。

示例 3：

输入：s1 = "xx", s2 = "xy"

输出：-1

示例 4：

输入：s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"

输出：4

提示：

1 <= s1.length, s2.length <= 1000

s1, s2 只包含 'x' 或 'y'。

解题思路

拿到这个题第一念头是把字符串扫一遍，把差异项识别出来；稍微纸上画画就不难发现下面的规律：

（1）'xx'与'yy'、'yy'与'xx'，他们之间仅需要1步即可完成满足题面的交换

（2）'xy'与'yx'、'yx'与'xy'，他们之间需要2步即可完成满足题面的交换

假设我们把1中两种情况分开记录，当遇到s1[i] = 'x'，s2[i] = 'y'，我们记录到xyCnt中；当遇到s1[i] = 'y'，s2[i] = 'x'，我们记录到yxCnt中，那么我们只需要统计xyCnt和yxCnt的个数即可完成计算。

具体计算的规则：

(1)如果xyCnt+yxCnt是个奇数，那肯定是要返回-1的，因为肯定最右有两个字符是无法通过对调匹配的；

(2排除上面的条件后，xyCnt+yxCnt肯定是个偶数，那么又分两种情况，即“奇数+奇数”和“偶数+偶数”；

基于上面的分析，可以发现每2个xyCnt或yxCnt对应一次移动，1个xyCnt与1个yxCnt对应两次移动。

class Solution:

    def minimumSwap(self, s1: str, s2: str) -> int:

        change1 = [s1[i] for i in range(len(s1)) if s1[i]!=s2[i]]

        if len(change1) % 2 == 1:

            return -1

        dic = collections.Counter(change1) 

        return len(change1)//2 if dic['x'] % 2 == 0 else (len(change1)-2)//2+2

45. 跳跃游戏 II（困难）

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]

输出: 2

解释: 跳到最后一个位置的最小跳跃数是 2。

     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:

假设你总是可以到达数组的最后一个位置。

方法：正向查找可到达的最大位置

如果我们「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。

例如，对于数组 [2,3,1,2,4,2,3]，初始位置是下标 0，从下标 0 出发，最远可到达下标 2。下标 0 可到达的位置中，下标 1 的值是 3，从下标 1 出发可以达到更远的位置，因此第一步到达下标 1。

从下标 1 出发，最远可到达下标 4。下标 1 可到达的位置中，下标 4 的值是 4 ，从下标 4 出发可以达到更远的位置，因此第二步到达下标 4。

在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。

在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素

class Solution:

    def jump(self, nums: List[int]) -> int:

        n = len(nums)

        step, end, max_bound = 0, 0, 0

        for i in range(n-1):

            max_bound = max(max_bound, i+nums[i])

            if i == end:

                step += 1

                end = max_bound

        return step 

621. 任务调度器（中等）

给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。

然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的最短时间。

示例 ：

输入：tasks = ["A","A","A","B","B","B"], n = 2

输出：8

解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.

     在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。

提示：

1. 任务的总个数为 [1, 10000]。
2. n 的取值范围为 [0, 100]。

解题思路：

完成所有任务的最短时间取决于出现次数最多的任务数量。

看下题目给出的例子

输入: tasks = ["A","A","A","B","B","B"], n = 2

输出: 8

执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.

因为相同任务必须要有时间片为 n 的间隔，所以我们先把出现次数最多的任务 A 安排上（当然你也可以选择任务 B）。例子中 n = 2，那么任意两个任务 A 之间都必须间隔 2 个单位的时间：

A -> (单位时间) -> (单位时间) -> A -> (单位时间) -> (单位时间) -> A

中间间隔的单位时间可以用来安排别的任务，也可以处于“待命”状态。当然，为了使总任务时间最短，我们要尽可能地把单位时间分配给其他任务。现在把任务 B 安排上：

A -> B -> (单位时间) -> A -> B -> (单位时间) -> A -> B

很容易观察到，前面两个 A 任务一定会固定跟着 2 个单位时间的间隔。最后一个 A 之后是否还有任务跟随取决于是否存在与任务 A 出现次数相同的任务。

该例子的计算过程为：

(任务 A 出现的次数 - 1) * (n + 1) + (出现次数为 3 的任务个数)，即：

(3 - 1) * (2 + 1) + 2 = 8

所以整体的解题步骤如下：

（1）计算每个任务出现的次数

（2）找出出现次数最多的任务，假设出现次数为 x

（3）计算至少需要的时间 (x - 1) * (n + 1)，记为 min_time

（4）计算出现次数为 x 的任务总数 count，计算最终结果为 min_time + count

（5）特殊情况

然而存在一种特殊情况，例如：

输入: tasks = ["A","A","A","B","B","B","C","C","D","D"], n = 2

输出: 10

执行顺序: A -> B -> C -> A -> B -> D -> A -> B -> C -> D

此时如果按照上述方法计算将得到结果为 8，比数组总长度 10 要小，应返回数组长度。

from typing import List

from collections import Counter

class Solution:

    def leastInterval(self, tasks: List[str], n: int) -> int:

        m = len(tasks)

        if m <= 1:

            return m

        task_map = Counter(tasks)

        task_sort = sorted(task_map.items(), key=lambda x: x[1], reverse=True)

        max_task_count = task_sort[0][1]

        res = (max_task_count-1)*(n+1)

        for item in task_sort:

            if item[1] == max_task_count:

                res += 1

        return m if res < m else res

***********************************************

class Solution:

    def leastInterval(self, tasks: List[str], n: int) -> int:

        m = len(tasks)

        if m <= 1:

            return m

        task_map = dict()

        for task in tasks:

            task_map[task] = task_map.get(task, 0)+1

        # 按任务出现的次数从大到小排序

        task_sort = sorted(task_map.items(), key=lambda x:x[1], reverse=True)

        # 出现最多次任务的次数

        max_task_count = task_sort[0][1]

        # 至少需要的最短时间

        res = (max_task_count-1)*(n+1)

        for sort in task_sort:

            if sort[1] == max_task_count:

                res += 1

        # 如果结果比任务数量少，则返回总任务数

        return m if res < m else res

376. 摆动序列（中等）

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

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

示例 1:

输入: [1,7,4,9,2,5]

输出: 6

解释: 整个序列均为摆动序列。

示例 2:

输入: [1,17,5,10,13,15,10,5,16,8]

输出: 7

解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。

示例 3:

输入: [1,2,3,4,5,6,7,8,9]

输出: 2

进阶:
你能否用 O(n) 时间复杂度完成此题?

方法：DP

每当我们选择一个元素作为摆动序列的一部分时，这个元素要么是上升的，要么是下降的，这取决于前一个元素的大小。

up[i] 存的是目前为止最长的以第 i个元素结尾的上升摆动序列的长度。

类似的， down[i]记录的是目前为止最长的以第 i个元素结尾的下降摆动序列的长度。

数组中的任何元素都对应下面三种可能状态中的一种：

（1）上升的位置，意味着 nums[i] > nums[i - 1]

（2）下降的位置，意味着 nums[i] < nums[i - 1]

（3）相同的位置，意味着 nums[i] == nums[i - 1]

更新的过程如下：

（1）如果 nums[i] > nums[i-1]，意味着这里在摆动上升，前一个数字肯定处于下降的位置。所以 up[i] = down[i-1] + 1， down[i]与down[i-1]保持相同。

（2）如果 nums[i] < nums[i-1]，意味着这里在摆动下降，前一个数字肯定处于上升的位置。所以 down[i] = up[i-1] + 1， up[i]与up[i-1]保持不变。

（3）如果 nums[i] == nums[i-1]，意味着这个元素不会改变任何东西因为它没有摆动。所以 down[i]和 up[i] 与 down[i-1]和 up[i-1]都分别保持不变。

（4）最后，我们可以将 up[length-1]和 down[length-1]中的较大值作为问题的答案，其中 length 是给定数组中的元素数目。

class Solution:

    def wiggleMaxLength(self, nums: List[int]) -> int:

        if not nums:

            return 0

        n = len(nums)

        if n <= 1:

            return n

        up = down = 1

        for i in range(1, n):

            if nums[i] > nums[i-1]:

                up = down + 1

            elif nums[i] < nums[i-1]:

                down = up + 1

        return max(up, down)

方法2：贪心

只统计出现波峰或波谷数量

class Solution:

    def wiggleMaxLength(self, nums: List[int]) -> int:

        if not nums:

            return 0

        n = len(nums)

        if n < 2:

            return n

        prediff = nums[1] - nums[0]

        count = 2 if prediff else 1

        for i in range(2, n):

            diff = nums[i] - nums[i-1]

            if (diff < 0 and prediff >= 0) or (diff > 0 and prediff <= 0):

                count += 1

                prediff = diff

        return count            

135. 分发糖果（困难）

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

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

• 每个孩子至少分配到 1 个糖果。
• 相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1:

输入: [1,0,2]

输出: 5

解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

输入: [1,2,2]

输出: 4

解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。

     第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

方法：贪心

两次遍历

将「相邻的孩子中，评分高的孩子必须获得更多的糖果」这句话拆分为两个规则，分别处理：

（1）左规则：当 ratings[i - 1] < ratings[i] 时，i 号学生的糖果数量将比 i - 1号孩子的糖果数量多。

（2）右规则：当 ratings[i]>ratings[i+1] 时，i号学生的糖果数量将比 i + 1 号孩子的糖果数量多。

遍历该数组两次，处理出每一个学生分别满足左规则或右规则时，最少需要被分得的糖果数量，每个人最终分得的糖果数量即为这两个数量的最大值。

时间复杂度：O(n)，其中n是孩子的数量。

空间复杂度：O(n)，其中n是孩子的数量。

class Solution:

    def candy(self, ratings: List[int]) -> int:

        n = len(ratings)

        left = [0] * n

        for i in range(n):

            if i > 0 and ratings[i] > ratings[i-1]:

                left[i] = left[i-1] + 1

            else:

                left[i] = 1

        right = res = 0

        for i in range(n-1, -1, -1):

            if i < n - 1 and ratings[i] > ratings[i+1]:

                right += 1

            else:

                right = 1

            res += max(left[i], right)

        return res

字典树

820

648

208

820. 单词的压缩编码（中等）

给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。

例如，如果这个列表是 ["time", "me", "bell"]，我们就可以将其表示为 S = "time#bell#" 和 indexes = [0, 2, 5]。

对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 "#" 结束，来恢复我们之前的单词列表。

那么成功对给定单词列表进行编码的最小字符串长度是多少呢？

示例：

输入: words = ["time", "me", "bell"]

输出: 10

说明: S = "time#bell#" ， indexes = [0, 2, 5] 。

提示：

1. 1 <= words.length <= 2000
2. 1 <= words[i].length <= 7
3. 每个单词都是小写字母 。

方法1：存储后缀

如果单词 X 是 Y 的后缀，那么单词 X 就不需要考虑了，因为编码 Y 的时候就同时将 X 编码了。例如，如果 words 中同时有 "me" 和 "time"，我们就可以在不改变答案的情况下不考虑 "me"。

如果单词 Y 不在任何别的单词 X 的后缀中出现，那么 Y 一定是编码字符串的一部分。

因此，目标就是保留所有不是其他单词后缀的单词，对于每个后缀，如果其存在 words 列表中，我们就将其从列表中删除。最后的结果就是这些单词长度加一的总和，因为每个单词编码后后面还需要跟一个 # 符号。

class Solution:

    def minimumLengthEncoding(self, words: List[str]) -> int:

        hash = set(words)

        for word in words:

            for k in range(1, len(word)):

                hash.discard(word[k:])

        return sum(len(word)+1 for word in hash)

方法2：字典树

目标就是保留所有不是其他单词后缀的单词。

算法

去找到是否不同的单词具有相同的后缀，我们可以将其反序之后插入字典树中。例如，我们有 "time" 和 "me"，可以将 "emit" 和 "em" 插入字典树中。

然后，字典树的叶子节点（没有孩子的节点）就代表没有后缀的单词，统计叶子节点代表的单词长度加一的和即为我们要的答案。

class Solution:

    def minimumLengthEncoding(self, words: List[str]) -> int:

        words = list(set(words))

        Trie = lambda: collections.defaultdict(Trie)

        trie = Trie()

        nodes = [reduce(dict.__getitem__, word[::-1], trie) for word in words]

        return sum(len(word)+1 for i, word in enumerate(words) if len(nodes[i])==0)

Trie树中最常见的两个能是键的插入和查找。

1. 向Trie树中插入键

通过搜索Trie树来插入一个键，从根开始搜索它对应于第一个键字符的链接。

（1）链接存在。沿着链接移动到树的下一个子层。算法继续搜索下一个键字符。

（2）链接不存在。创建一个新的节点，并将它与父节点的链接相连，该链接与当前的键字符相匹配。

重复以上步骤，直到到达键的最后一个字符，然后将当前节点标记为结束节点，算法完成。

def insert(self, word: str) -> None:

        """

        Inserts a word into the trie.

        """

        tree = self.lookup

        for a in word:

            if a not in tree:

                tree[a] = {}

            tree = tree[a]

        tree['#'] = '#' #单词结束标记

复杂度分析

（1）时间复杂度：O(m)，其中m为键长。在算法的每次迭代中，要么检查要么创建一个节点，直到到达键尾。只需要m次操作。

（2）空间复杂度：O(m)。最坏的情况下，新插入的键和Trie树中已有的键没有公共前缀。此时需要添加m个结点，使用O(m)空间。

2.在Trie树中查找键

每个键在trie中表示从根到内部节点或叶的路径。用第一个键字符从根开始，检查当前节点中与键字符对应的链接。有两种情况：

（1）存在链接。移动到该链接后面路径中的下一个节点，并继续搜索下一个键字符。

（2）不存在链接。若已无键字符，且当前节点标记为isEnd，则返回true。否则有两种可能，均返回false：

1）还有键字符剩余，但无法跟随Trie树的键路径，找不到键。

2）没有键字符剩余，但当前节点没有标记为isEnd。也就是说，待查找键只是Trie树中另一个键的前缀。

def search(self, word: str) -> bool:

        """

        Returns if the word is in the trie.

        """

        tree = self.lookup

        for a in word:

            if a not in tree:

                return False

            tree = tree[a]

        if '#' in tree:

            return True

        return False

复杂度分析

（1）时间复杂度：O(m)。算法的每一步均搜索下一个键字符。最坏的情况下需要m次操作。

（2）空间复杂度：O(1)

3.查找Trie树中的键前缀

该方法与在Trie树中搜索键时使用的方法非常相似。从根遍历Trie树，直到键前缀中没有字符，或者无法用当前的键字符继续Trie中的路径。与上面提到的“搜索键”算法唯一的区别是，到达键前缀的末尾时，总是返回true。不需要考虑当前Trie节点是否用“isend”标记，因为搜索的是键的前缀，而不是整个键。

def startsWith(self, prefix: str) -> bool:

        """

        Returns if there is any word in the trie that starts with the given prefix.

        """

        tree = self.lookup

        for a in prefix:

            if a not in tree:

                return False

            tree = tree[a]

        return True

复杂度分析

（1）时间复杂度：O(m)

（2）空间复杂度：O(1)

208. 实现 Trie (前缀树)

难度中等446

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");  
trie.search("app");     // 返回 true

说明:

• 你可以假设所有的输入都是由小写字母 a-z 构成的。
• 保证所有输入均为非空字符串。

class Trie:

    def __init__(self):

        """

        Initialize your data structure here.

        """

        self.lookup = {}

    def insert(self, word: str) -> None:

        """

        Inserts a word into the trie.

        """

        tree = self.lookup

        for a in word:

            if a not in tree:

                tree[a] = {}

            tree = tree[a]

        tree['#'] = '#' #单词结束标记

    def search(self, word: str) -> bool:

        """

        Returns if the word is in the trie.

        """

        tree = self.lookup

        for a in word:

            if a not in tree:

                return False

            tree = tree[a]

        if '#' in tree:

            return True

        return False

    def startsWith(self, prefix: str) -> bool:

        """

        Returns if there is any word in the trie that starts with the given prefix.

        """

        tree = self.lookup

        for a in prefix:

            if a not in tree:

                return False

            tree = tree[a]

        return True

# Your Trie object will be instantiated and called as such:

# obj = Trie()

# obj.insert(word)

# param_2 = obj.search(word)

# param_3 = obj.startsWith(prefix)