LeetCode笔记：Weekly Contest 296

• LeetCode笔记：Weekly Contest 296
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四
    • 1. 解题思路
    • 2. 代码实现

• 比赛链接：https://leetcode.com/contest/weekly-contest-296/

1. 题目一

给出题目一的试题链接如下：

• 2293. Min Max Game

1. 解题思路

这一题的解题思路暂时没想到啥奇技淫巧，就先按照题意进行一下迭代求解了，毕竟按照题意的话思路还是很直接的。

2. 代码实现

给出python代码实现如下：

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        tmp = []
        for i in range(n // 2):
            if i % 2 == 0:
                tmp.append(min(nums[2*i: 2*i+2]))
            else:
                tmp.append(max(nums[2*i: 2*i+2]))
        return self.minMaxGame(tmp)

提交代码评测得到：耗时74ms，占用内存14.1MB。

2. 题目二

给出题目二的试题链接如下：

• 2294. Partition Array Such That Maximum Difference Is K

1. 解题思路

这一题用贪婪算法即可求解。

我们首先对数组进行一下排序，然后在每一个集合当中依次加入元素直至最大元素与最小元素的差大于k，然后新建一个子集。

最后统计所有的子集个数。

2. 代码实现

给出python代码实现如下：

class Solution:
    def partitionArray(self, nums: List[int], k: int) -> int:
        nums = sorted(nums)
        _min = nums[0]
        n = len(nums)
        res = 1
        for i in range(1, n):
            if nums[i] - _min > k:
                res += 1
                _min = nums[i]
        return res

提交代码评测得到：耗时1561ms，占用内存28.8MB。

3. 题目三

给出题目三的试题链接如下：

• 2295. Replace Elements in an Array

1. 解题思路

这一题我属于审题不清，把题目做烦了，题目中限制了每个元素之可能出现一次，但是我没注意到，所以用了一个数组来记录每一个元素的位置，属于有点浪费了，但是anyway，也可以求解。

这道题感觉应该有更好的解法，但是这里我们就是借用了python当中字典的内置函数，然后就能直接求解了，所以就不多说了，算是投机取巧了吧……

2. 代码实现

给出python代码实现如下：

class Solution:
    def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:
        rec = {
    }
        for i, x in enumerate(nums):
            if x in rec:
                rec[x].append(i)
            else:
                rec[x] = [i]
        
        for u, v in operations:
            rec[v] = rec[u]
            rec.pop(u)
        
        res = [0 for _ in nums]
        for k, v in rec.items():
            for i in v:
                res[i] = k
        return res

提交代码评测得到：耗时2498ms，占用内存70.4MB。

4. 题目四

给出题目四的试题链接如下：

• 2296. Design a Text Editor

1. 解题思路

这一题思路上感觉没啥，按照题意去做就行了，算是一种暴力求解的思路，不过anyway能过测试样例……

2. 代码实现

给出python代码实现如下：

class TextEditor:

    def __init__(self):
        self.text = ""
        self.cursor = 0
        

    def addText(self, text: str) -> None:
        n = len(text)
        self.text = self.text[:self.cursor] + text + self.text[self.cursor:]
        self.cursor += n
        return

    def deleteText(self, k: int) -> int:
        cursor = max(0, self.cursor - k)
        rm = self.cursor - cursor
        self.text = self.text[:cursor] + self.text[self.cursor:]
        self.cursor = cursor
        return rm

    def cursorLeft(self, k: int) -> str:
        self.cursor = max(0, self.cursor - k)
        return self.text[max(0, self.cursor-10):self.cursor]
        
    def cursorRight(self, k: int) -> str:
        self.cursor = min(len(self.text), self.cursor + k)
        return self.text[max(0, self.cursor-10):self.cursor]

提交代码评测得到：耗时6010ms，占用内存29.6MB。