力扣周赛 198 - python 解答

目录

1. 5464 换酒问题
2. 5465 子树中标签相同的节点数
3. 5466 最多的不重叠子字符串
4. 5467 找到最接近目标值的函数值

做出了四道题目，但后两道做的很勉强，也错了几次。刚看第三道题，虽然写着 medium，但是没思路，打开第四道看到反而已经有人过了，于是先做了第四道，才回来做第一道。

最后一道是纯暴力枚举加了几个条件：

1. 去除相邻重复值
2. 是函数输出为 0 时停止枚举，因为 0 按位与任何数都依然是 0.
3. 因为在不断按位与的过程中函数输出是单调减的，所以，但差值大于当前最小差值也可以停止遍历

但是我感觉应该还有更好的解法

第三题用的模拟方法，依次寻找只含一个字母，两个字母 … 的串

5464 换酒问题

https://leetcode-cn.com/contest/weekly-contest-198/problems/water-bottles/

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        c = numBottles
        cc = numBottles
        kp = numBottles
        while kp >= numExchange:
            cc = kp // numExchange
            kp = kp % numExchange + cc
            c += cc
        return c

5465 子树中标签相同的节点数

https://leetcode-cn.com/contest/weekly-contest-198/problems/number-of-nodes-in-the-sub-tree-with-the-same-label/

class Solution:
    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
        ed = {}
        for s, e in edges:
            if s not in ed:
                ed[s] = []
            if e not in ed:
                ed[e] = []
            ed[s].append(e)
            ed[e].append(s)
        ans = [0] * n
        vised = [False] * n
        def vis(i):    
            vised[i] = True
            c = {}
            c[labels[i]] = 1
            if i in ed:
                for ch in ed[i]:
                    if not vised[ch]:
                        cc = vis(ch)
                        for k in cc:
                            if k not in c:
                                c[k] = 0
                            c[k] += cc[k]
            ans[i] = c[labels[i]]
            return c
        vis(0)
        return ans

5466 最多的不重叠子字符串

https://leetcode-cn.com/contest/weekly-contest-198/problems/maximum-number-of-non-overlapping-substrings/

代码有点长，但是思路还是清晰的。

贪心策略就是：

1. 尽可能选择出现字母数少的子串

2. 在 1 的前提下尽可能选择长度短的

对于出现字母数为 1 的子串，可以特别处理，因为他们一定不会干扰别人，所以可以直接挑出所有仅含一个字母的子串。

第一个循环用于统计每个字母第一次出现位置和最后一次出现位置，顺便还得出了这个字母是否都是连续出现的（如果除了第一次以外，如果有一个该字母前面是其他字母就不是连续出现了）。对每个字母得到三个值 [第一次出现的下标，最后一次出现的下标，是否是连续出现的]

然后定义 used 字典（其实用集合就行）保存有那些字母已经用过了。

ans 就是要返回结果。

nd 是去除了仅含一个字母的子串后的结果，后面会对这个 nd 排序。

循环二，挑出仅含一个字母的子串，这种仅含一个字母的子串自然就是循环一中标记为 True 的子串。

循环三，挑出每个字母构成的子串，并检验是否合法，对每个字母得到： [出现字母数, 长度, 字母, 出现的字母列表]

然后对上面得到的结果降序排序，在一次检验，合法的加入 ans 并在 used 记录。

class Solution:
    def maxNumOfSubstrings(self, s: str) -> List[str]:
        d = {}
        for i, ch in enumerate(s): # 循环一，得到每个字母的起点和终点
            if ch not in d:
                d[ch] = [i, i, True]
            else:
                if d[ch][1] != i - 1:
                    d[ch][2] = False
                d[ch][1] = i
        #print(d)
        used = {}
        ans = []
        nd = []
        for ch in d:  # 循环二，挑出仅含一个字母的子串
            if d[ch][2]:
                used[ch] = True
                ans.append(s[d[ch][0]:d[ch][1]+1])
        for ch in d:  # 循环三，挑出每个字母构成的子串，并检验是否合法
            if not d[ch][2]:
                cc = 0
                ccx = set()
                f = True
                
                mini = d[ch][0]
                maxi = d[ch][1]
                change = True
                while change:
                    change = False
                    i = d[ch][0]
                    while i <= maxi:
                        if s[i] in used:
                            f = False
                            break
                        else:
                            if maxi < d[s[i]][1]:
                                change = True
                                maxi = d[s[i]][1]
                            if mini > d[s[i]][0]:
                                mini = d[s[i]][0]
                                change = True
                            ccx.add(s[i])
                        i += 1
                    i = d[ch][0]
                    while i >= mini:
                        if s[i] in used:
                            f = False
                            break
                        else:
                            if maxi < d[s[i]][1]:
                                change = True
                                maxi = d[s[i]][1]
                            if mini > d[s[i]][0]:
                                mini = d[s[i]][0]
                                change = True
                            ccx.add(s[i])
                        i -= 1
                d[ch][1] = maxi
                d[ch][0] = mini
                if f:
                    nd.append([len(ccx), maxi-d[ch][0], ch, list(ccx)])
        #print(d)
        nd.sort()
        for n in nd:
            f = True
            for cc in n[3]:
                if cc in used:
                    f = False
                    break
            if f:
                for cc in n[3]:
                    used[cc] = True
                ch = n[2]
                ans.append(s[d[ch][0]:d[ch][1]+1])
        return ans

5467 找到最接近目标值的函数值

https://leetcode-cn.com/contest/weekly-contest-198/problems/find-a-value-of-a-mysterious-function-closest-to-target/

方法并不太好，但是写起来简单。

两层循环，外层遍历 l 的取值（0 ~ len(arr)），内层遍历 r 的取值（当前 l ~ len(arr)）

内层循环是一个不断按位与的过程，所以值一定是不断变小或者不变的，可以利用这个条件提前终止内层循环。

1. 先去除重复的相邻元素

2. 函数输出（ans）为 0 或这最小差（r） 为 0 则退出当前内层循环

3. 最小差为 0 则退出外层循环

4. 如果 target - 当前输出 大于已经得到的最小差，退出内层循环。

class Solution:
    def closestToTarget(self, arr: List[int], target: int) -> int:
        arr2 = []
        l = arr[0] -1
        for v in arr:
            if v != l:
                arr2.append(v)
                l = v
        #print(len(arr), len(arr2))
        arr = arr2
        r = abs(-1000000000 - target)
        for i in range(len(arr)):
            ans = arr[i]
            r = min(r, abs(ans - target))
            for j in range(i+1, len(arr)):
                ans = ans & arr[j]
                r = min(r, abs(ans - target))
                if ans == 0 or r == 0:
                    break
                if target > ans and target - ans >= r:
                    break
            if r == 0:
                break
        return r