Java教程

2021-6

本文主要是介绍2021-6,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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中,那么我们只需要统计xyCntyxCnt的个数即可完成计算。

具体计算的规则:

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

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

基于上面的分析,可以发现每2xyCntyxCnt对应一次移动,1xyCnt1yxCnt对应两次移动。

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)

这篇关于2021-6的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!