LeetCode 周赛407 - 三题题解

这次是手速场掉大分，还不知道会不会unrate。PS：怎么这次周赛刚结束5min脑子就和开了光一样

T1:100372. 使两个整数相等的位更改次数

看到题的时候没想太多，按着常规的处理方法写，没睡醒写错了一个地方还WR了一发

常规遍历思路：二进制，补齐，遍历

class Solution:
    def minChanges(self, n: int, k: int) -> int:
        if n == k:return 0
        n = bin(n)[2:]
        k = bin(k)[2:]
        if len(k)>len(n) or k.count("1")>n.count("1") :return -1
        while len(k) < len(n):
            k = "0"+k
        ans = 0
        print(n,k)
        for i in range(len(k)):
            if k[i] == "0" and n[i] == "1": ans += 1
            elif k[i] == "1" and n[i] == "0": return -1
        
        return ans

比赛结束后整理代码的时候突然就想到能不能用异或同或这些试试发现：如果出现了n的位置为0而k的位置为1的话，进行或运算之后res > n，返回-1。除此之外n-k的二进制1的个数即为答案

class Solution:
    def minChanges(self, n: int, k: int) -> int:
        if n|k > n: return -1
        return bin(n-k)[2:].count("1")

T2:100335. 字符串元音游戏

说实话这道题是最让我无语的，先入为主认为A选元音B选辅音，然后就在想是不是要用dp还是贪心，于是先做第三题。写了半小时发现通过率有点高，重新审题，只要有元音，A就赢，绝了！

class Solution:
    def doesAliceWin(self, s: str) -> bool:
        for ch in ["a","e","i","o","u"]:
            if ch in s: return True
        return False
    

T3:100360. 将 1 移动到末尾的最大操作次数

这个题其实一看就知道要用前缀，就是怎么用的问题。例子：100100110101，这个ans=12考虑一下移动的本质，由于他是直接把100变成001，连续的0意义不大，也就是说等价于1010110101，这个时候要把0往前移，答案即为0前面1的个数的前缀和pre = [1 2 4 5] ans = sum(pre)

因为去0感觉挺麻烦的，所以我就用了个数组做标记

class Solution:
    def maxOperations(self, s: str) -> int:
        cnt = 0
        n = len(s)
        pre = [0]
        tar = [0 for _ in range(n)]
        for idx in range(n):
            if s[idx] == "1":
                cnt += 1
            else:
                if idx>0 and s[idx-1]!="0":
                    tar[idx] = 1
            pre.append(cnt)
        ans = 0
        for i in range(n):
            ans += pre[i+1]*tar[i]
        return ans