LeetCode笔记：Weekly Contest 251（补发）

1. 题目一

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

1. 解题思路

这一题没啥好说的，按照题目意思进行变换操作即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def getLucky(self, s: str, k: int) -> int:
        s = "".join([str(ord(c)-ord(a)+1) for c in s])
        for _ in range(k):
            s = str(sum(int(c) for c in s))
        return int(s)

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

2. 题目二

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

1. 解题思路

这题由于限制了substring必须是连续的，因此，我们就是找到第一个经过mapping之后会变大的字符，然后将以此为开头，然后所有的字符都满足变大关系的子串取出来进行变换即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def maximumNumber(self, num: str, change: List[int]) -> str:
        n = len(num)
        for i, c in enumerate(num):
            c = int(c)
            if change[c] <= c:
                continue
            j = i
            while j < n and change[int(num[j])] >= int(num[j]):
                j += 1
            return num[:i] + "".join([str(change[int(x)]) for x in num[i:j]]) + num[j:]
        return num

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

3. 题目三

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

1. 解题思路

这一题也还好，首先计算每一个学生和老师的匹配分数，然后仿照八皇后问题进行求解即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
        n = len(students)
        scores = [[sum([1-x^y for x, y in zip(students[i], mentors[j])]) for j in range(n)] for i in range(n)]
        
        @lru_cache(None)
        def dp(idx, status):
            if idx == n:
                return 0
            return max(scores[idx][i] + dp(idx+1, status^(1<<i)) for i in range(n) if status&(1<<i) == 0)
        
        return dp(0, 0)

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

4. 题目四

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

1. 解题思路

放弃again，给出官方解答如下，有兴趣的读者自行研究一下吧……

官方解答：