LeetCode笔记：Weekly Contest 319

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

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

1. 题目一

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

• 2469. Convert the Temperature

1. 解题思路

这一题思路就很直接，直接做一下摄氏度到开氏和华氏的温度转换即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def convertTemperature(self, celsius: float) -> List[float]:
        return [celsius + 273.15, celsius*1.8 + 32]
1
2
3

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

2. 题目二

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

• 2470. Number of Subarrays With LCM Equal to K

1. 解题思路

这一题我的思路还是非常暴力的，因为从条件看到时间复杂度要求不高，因此就直接用了一个二重循环来对这一问题进行了求解。

2. 代码实现

给出python代码实现如下：

class Solution:
    def subarrayLCM(self, nums: List[int], k: int) -> int:
        n = len(nums)
        res = 0
        s = 1
        for i in range(n):
            s = 1
            for j in range(i, n):
                if k % nums[j] != 0:
                    break
                s = math.lcm(s, nums[j])
                if s == k:
                    res += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

3. 题目三

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

• 2471. Minimum Number of Operations to Sort a Binary Tree by Level

1. 解题思路

这一题思路上也很直接，就是分两步进行实现：

1. 用一个先序遍历获取每一层中的元素；
2. 考察对每一层中元素进行排序所需的最小交换次数。

不过比较惭愧的是，其中，关于第二步的实现，我们给出了一种简单地实现：

• 首先排序获取每一个元素的正确位置，然后从小到大依次考虑，每次找到对应对应元素的原始位置，然后进行一次交换，重复上述步骤直至完成完整的排序。

这个方法简单，且感觉上应该是交换次数最少的排序，但是暂时想不到严格的数学说明，不过万幸而言通过了全部测试样例，只能说感觉应该是对的了……

2. 代码实现

给出python代码实现如下：

class Solution:
    def minimumOperations(self, root: Optional[TreeNode]) -> int:
        nodes = []
        
        def dfs(root, depth):
            nonlocal nodes
            if root is None:
                return
            if len(nodes) <= depth:
                nodes.append([root.val])
            else:
                nodes[depth].append(root.val)
            dfs(root.left, depth+1)
            dfs(root.right, depth+1)
            return
        
        dfs(root, 0)
        
        def get_min_swap(arr):
            index = {}
            for i, x in enumerate(arr):
                index[x] = i
            s = sorted(arr)
            cnt = 0
            for i, x in enumerate(s):
                if index[x] == i:
                    continue
                j = index[x]
                y = arr[i]
                arr[i], arr[j] = x, y
                index[y] = j
                index[x] = i
                cnt += 1
            return cnt
        
        return sum(get_min_swap(arr) for arr in nodes)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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

4. 题目四

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

• 2472. Maximum Number of Non-overlapping Palindrome Substrings

1. 解题思路

这一题我的思路基本就是找到每一个字符开始所能够构成的回文以及对应的终点，然后就可以使用动态规划进行求解了。

不过思路虽然是这么个思路，但是我的实现方法有点暴力了，导致超时了好几次，最后也是勉强通过了全部测试样例。

2. 代码实现

给出python代码实现如下：

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        n = len(s)
        if k == 1:
            return n
        
        palindromes = defaultdict(list)
        for i in range(n-k+1):
            j = i
            while True:
                j = s.find(s[i], j+1)
                if j == -1:
                    break
                elif j+1-i < k:
                    continue
                elif s[i:j+1] == s[i:j+1][::-1]:
                    palindromes[i].append(j+1)
                    
        @lru_cache(None)
        def dp(idx):
            if idx >= n:
                return 0
            res = dp(idx+1)
            for j in palindromes[idx]:
                res = max(res, 1+dp(j))
            return res
        
        return dp(0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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

3. 算法优化

这一题看了其他大佬们的解答之后，发现大佬的思路和我的思路基本一致，也是先找到每一个字符对应的回文字符串，然后再用动态规划找到最优解。

但是，他的实现比我要优雅太多了。

首先，我是通过从头遍历的方式寻找回文，这会导致大量的冗余计算，而大佬采用的方式是从回文的中部开始检索，从而就可以从中直接剪枝，因此可以节省极大的计算量。

而另一方面，在第二步的动态规划当中，我是找寻了所有可能的情况，但是事实上，对于每一个位置的回文，只要找寻以之作为终点的最短回文即可。

从而又可以进一步优化检索效率。

这里，我们摘录大佬的解答如下：

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        n = len(s)
        pals = [-1] * n
        
        for m in range(n):
            # odd
            l, r = m, m
            while 0 <= l and r < n and s[l] == s[r]:
                if r - l + 1 >= k:
                    pals[r] = max(pals[r], l)
                    break
                l -= 1
                r += 1

            # even
            l, r = m - 1, m
            while 0 <= l and r < n and s[l] == s[r]:
                if r - l + 1 >= k:
                    pals[r] = max(pals[r], l)
                    break
                l -= 1
                r += 1

        dp = [0] * (n + 1)
        for r in range(n):
            if pals[r] == -1:
                dp[r + 1] = dp[r]
            else:
                dp[r + 1] = max(dp[r], dp[pals[r]] + 1)
        return dp[n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31