讨论/题目交流/🏆 第 171 场力扣周赛/
🏆 第 171 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 将整数转换为两个无零整数的和
4 分 - 或运算的最小翻转次数
5 分 - 连通网络的操作次数
7 分 - 二指输入的的最小距离

展开讨论
力扣 (LeetCode)发起于 2020-01-12

题解

第一题
A、B的范围很小,直接暴力搜索即可(而且约束其实很弱,解很多)

class Solution(object):
    def getNoZeroIntegers(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        
        for i in range(1, n):
            if self.check(i) and self.check(n-i):
                return [i, n-i]
        
    def check(self, x):
        while (x > 0):
            if x % 10 == 0:
                return False
            x = x // 10
        return True

第二题
用不到位运算,就是二进制分解的知识
根据c的当前位,分两种情况讨论

  1. 当前位位1,则a和b至少一个为1,如果两个都为0则修改任一个即可,修改位+1
  2. 当前位为0,则a和b都必须为0,任一不为0修改位+1
    按位统计直到所有数都为0
class Solution(object):
    def minFlips(self, a, b, c):
        """
        :type a: int
        :type b: int
        :type c: int
        :rtype: int
        """
        
        Ans = 0
        while (a > 0 or b > 0 or c > 0):
            if (c & 1 == 1):
                if (a & 1 == 0) and (b & 1 == 0):
                    Ans = Ans + 1
            if (c & 1 == 0):
                if (a & 1 == 1):
                    Ans = Ans + 1
                if (b & 1 == 1):
                    Ans = Ans + 1
            a = a // 2
            b = b // 2
            c = c // 2
        
        return Ans

第三题
图联通问题,用并查集直接解

  1. 边数不够,返回-1
  2. 边数够时,只需要求出来有几个联通块,然后将多余的边改成连接这些块的边,问题就转变为统计联通块数
    思考用并查集联通的过程,初始为n-1个块,每连接成功一次,则块数-1
    则块数=n-合并成功次数
    还需要修改的边=块数-1
    Ans=n-1-合并成功次数
class Solution(object):
    def makeConnected(self, n, connections):
        """
        :type n: int
        :type connections: List[List[int]]
        :rtype: int
        """
        
        if (len(connections) < n-1):
            return -1
        
        self.Fa = list([0] * n)
        
        for i in range(n):
            self.Fa[i] = i
        
        Ans = n-1
        
        for p, q in connections:
            fp = self.Father(p)
            fq = self.Father(q)
            if fp != fq:
                self.Fa[fp] = fq
                Ans -= 1
        
        return Ans
    
    def Father(self, x):
        if x != self.Fa[x]:
            self.Fa[x] = self.Father(self.Fa[x])
        return self.Fa[x]

第四题
动态规划,由于只有两根手指,定义f[i][j]为一根手指用来画单词中第i个字母,另一根手指用来画单词中第j个字母(严格保证i>j)
由于python下标从0开始,为了方便定义f[0][0]=0,单词中第一个字母下标为1
那么,考虑转移方程
当画第i个字母时,有两种情况:

  1. 使用画第i-1个字母的那根手指来画,则f[i][j] = f[i-1][j] + dist(word[i], word[j])
  2. 不使用画第i-1个字母的那根手指来画,则f[i][i-1] = f[i-1][k] + dist(word[i], word[k])

注意一些特殊情况:
如当前只用了一根手指,另一根手指第一次用(可以通过设计dist函数来解决该问题,也可以特判)

class Solution(object):
    def minimumDistance(self, word):
        """
        :type word: str
        :rtype: int
        """
        Dict = dict()
        
        for i in range(26):
            Dict[chr(i+ord('A'))] = [i // 6, i % 6]
        
        inf = 12 * 300
        
        # 设置初始值inf,方便后面使用min函数
        Dist = [[inf] * 310 for i in range(310)]
        
        Dist[0][0] = 0
        
        N = len(word)
        
        for i in range(1, N+1):
            if i == 1:
                Dist[i][i-1] = Dist[i-1][0]
            else:
                for j in range(i-1):
                    if (j == 0):
                        Dist[i][i-1] = min(Dist[i][i-1], Dist[i-1][j])
                    else:
                        Dist[i][i-1] = min(Dist[i][i-1], Dist[i-1][j] + self.distance(Dict[word[i-1]],Dict[word[j-1]]))
                for j in range(i-1):
                    Dist[i][j] = min(Dist[i][j], Dist[i-1][j]+self.distance(Dict[word[i-1]],Dict[word[i-2]]))
        
        Ans = inf
        for i in range(N):
            Ans = min(Ans, Dist[N][i])
        
        return Ans
    
    # 字符距离函数
    def distance(self, l1, l2):
        return abs(l1[0]-l2[0])+abs(l1[1]-l2[1])

(第一题心急错了两次,罚了10min,掉出前20了/(ㄒoㄒ)/~~)

5
展开全部 11 讨论