LEETCODE 第171场周赛

又是dp不会😭😭😭，得好好练练啊。

Contents

1 第一题：将整数转换为两个无零整数的和
2 第二题：或运算的最小翻转次数
3 第三题：连通网络的操作次数
4 第四题：二指输入的的最小距离

第一题：将整数转换为两个无零整数的和

　　「无零整数」是十进制表示中不含任何 0 的正整数。
　　
　　给你一个整数 n，请你返回一个由两个整数组成的列表 [A, B]，满足：
　　
　　A 和 B 都是无零整数
　　A + B = n
　　题目数据保证至少有一个有效的解决方案。
　　
　　如果存在多个有效解决方案，你可以返回其中任意一个。
　　
　　示例 1：
　　输入：n = 2
　　输出：[1,1]
　　解释：A = 1, B = 1. A + B = n 并且 A 和 B 的十进制表示形式都不包含任何 0 。　　
　　示例 2：
　　
　　输入：n = 11
　　输出：[2,9]
　　
　　示例 3：
　　输入：n = 10000
　　输出：[1,9999]
　　
　　示例 4：
　　输入：n = 69
　　输出：[1,68]
　　
　　示例 5：
　　输入：n = 1010
　　输出：[11,999]

　　思路：用python就完了！

class Solution:
    def getNoZeroIntegers(self, n: int) -> List[int]:
        for i in range(1, n):
            j = n - i
            if '0' not in str(i) and '0' not in str(j):
                return [i, j]

class Solution:

def getNoZeroIntegers(self, n: int) -> List[int]:

for i in range(1, n):

j = n - i

if '0' not in str(i) and '0' not in str(j):

return [i, j]

第二题：或运算的最小翻转次数

　　给你三个正整数 a、b 和 c。
　　
　　你可以对 a 和 b 的二进制表示进行位翻转操作，返回能够使按位或运算 a OR b == c 成立的最小翻转次数。
　　
　　「位翻转操作」是指将一个数的二进制表示任何单个位上的 1 变成 0 或者 0 变成 1 。
　　
　　示例 1：
　　输入：a = 2, b = 6, c = 5
　　输出：3
　　解释：翻转后 a = 1 , b = 4 , c = 5 使得 a OR b == c
　　
　　示例 2：
　　输入：a = 4, b = 2, c = 7
　　输出：1
　　
　　示例 3：
　　输入：a = 1, b = 2, c = 3
　　输出：0

　　思路：如示例1，a=010, b=110, c=101，或操作的特性是，只要a和b中有1，a|b=1。
　　按每一位分情况讨论，如果c为1，a和b中没有1，那么翻转次数+1，否则不需要翻转；如果c为0，必须满足a=b=0才行，翻转次数=a和b中的1数。

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        # 转成二进制并在前面padding成一样长的
        a = bin(a)[2:]
        b = bin(b)[2:]
        c = bin(c)[2:]
        l = max(len(a), len(b), len(c))
        a = (l-len(a)) * '0' + a
        b = (l-len(b)) * '0' + b
        c = (l-len(c)) * '0' + c
        ans = 0
        for i in range(l):
            if c[i] == '1':
                if a[i] == '1' or b[i] == '1':
                    pass
                else:
                    ans += 1
            elif c[i] == '0':
                if a[i] == '1':
                    ans += 1
                if b[i] == '1':
                    ans += 1

        # print(a,b,c)
        return ans

class Solution:

def minFlips(self, a: int, b: int, c: int) -> int:

# 转成二进制并在前面padding成一样长的

a = bin(a)[2:]

b = bin(b)[2:]

c = bin(c)[2:]

l = max(len(a), len(b), len(c))

a = (l-len(a)) * '0' + a

b = (l-len(b)) * '0' + b

c = (l-len(c)) * '0' + c

ans = 0

for i in range(l):

if c[i] == '1':

if a[i] == '1' or b[i] == '1':

pass

else:

ans += 1

elif c[i] == '0':

if a[i] == '1':

ans += 1

if b[i] == '1':

ans += 1

# print(a,b,c)

return ans

第三题：连通网络的操作次数

　　用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。
　　
　　网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。
　　
　　给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。
　　
　　示例 1：
　　输入：n = 4, connections = [[0,1],[0,2],[1,2]]
　　输出：1
　　解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。

　　示例 2：
　　输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
　　输出：2
　　
　　示例 3：
　　输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
　　输出：-1
　　解释：线缆数量不足。
　　
　　示例 4：
　　输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
　　输出：0

　　思路：如果len(connections) < n-1，则线缆数量不足，返回-1。否则返回连通子图个数减1。

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n-1:
            return -1

        connections_dict = {i: [] for i in range(n)}
        for c in connections:
            i, j = c
            connections_dict[i].append(j)
            connections_dict[j].append(i)

        ans = 0
        vis = [0 for i in range(n)]

        def dfs(node):  # dfs几遍ans就加几
            if vis[node]:
                return
            vis[node] = 1
            for neibour in connections_dict[node]:
                dfs(neibour)

        for v in range(n):
            if vis[v]:
                continue
            dfs(v)
            ans += 1

        return ans-1

class Solution:

def makeConnected(self, n: int, connections: List[List[int]]) -> int:

if len(connections) < n-1:

return -1

connections_dict = {i: [] for i in range(n)}

for c in connections:

i, j = c

connections_dict[i].append(j)

connections_dict[j].append(i)

ans = 0

vis = [0 for i in range(n)]

def dfs(node): # dfs几遍ans就加几

if vis[node]:

return

vis[node] = 1

for neibour in connections_dict[node]:

dfs(neibour)

for v in range(n):

if vis[v]:

continue

dfs(v)

ans += 1

return ans-1

第四题：二指输入的的最小距离

　　二指输入法定制键盘在 XY 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处，例如字母 A 位于坐标 (0,0)，字母 B 位于坐标 (0,1)，字母 P 位于坐标 (2,3) 且字母 Z 位于坐标 (4,1)。
　　
　　给你一个待输入字符串 word，请你计算并返回在仅使用两根手指的情况下，键入该字符串需要的最小移动总距离。坐标 (x1,y1) 和 (x2,y2) 之间的距离是 |x1 – x2| + |y1 – y2|。
　　
　　注意，两根手指的起始位置是零代价的，不计入移动总距离。你的两根手指的起始位置也不必从首字母或者前两个字母开始。
　　
　　示例 1：
　　
　　输入：word = “CAKE”
　　输出：3
　　解释：
　　使用两根手指输入 “CAKE” 的最佳方案之一是：
　　手指 1 在字母 ‘C’ 上 -> 移动距离 = 0
　　手指 1 在字母 ‘A’ 上 -> 移动距离 = 从字母 ‘C’ 到字母 ‘A’ 的距离 = 2
　　手指 2 在字母 ‘K’ 上 -> 移动距离 = 0
　　手指 2 在字母 ‘E’ 上 -> 移动距离 = 从字母 ‘K’ 到字母 ‘E’ 的距离 = 1
　　总距离 = 3
　　示例 2：
　　
　　输入：word = “HAPPY”
　　输出：6
　　解释：
　　使用两根手指输入 “HAPPY” 的最佳方案之一是：
　　手指 1 在字母 ‘H’ 上 -> 移动距离 = 0
　　手指 1 在字母 ‘A’ 上 -> 移动距离 = 从字母 ‘H’ 到字母 ‘A’ 的距离 = 2
　　手指 2 在字母 ‘P’ 上 -> 移动距离 = 0
　　手指 2 在字母 ‘P’ 上 -> 移动距离 = 从字母 ‘P’ 到字母 ‘P’ 的距离 = 0
　　手指 1 在字母 ‘Y’ 上 -> 移动距离 = 从字母 ‘A’ 到字母 ‘Y’ 的距离 = 4
　　总距离 = 6
　　
　　示例 3：
　　输入：word = “NEW”
　　输出：3
　　
　　示例 4：
　　输入：word = “YEAR”
　　输出：7

　　思路：这题看了题解。

　　对于任意的输入字符串 word，在输入完毕时，必然有至少一根手指停留在字符串最后一个字符上（请思考一下为什么说是至少）。因此，对于两指输入的最小距离，可以转化为求所有以最后一个字符为终点的移动距离中的最小值。

　　接下来是如何得到这个值，我们可以使用 DP （或者同理如其他题解所说的从上而下的递归+记忆化方法）来解决问题。考虑一个 DP 数组 d[i][j]，其中 i≥j，表示以 word 第 i 和第 j 个字符为手指终点的最小移动距离。特别地，d[i][i] 表示仅使用一根手指移动的情况。

　　对于每一个 i ，和前一状态 i−1 之间存在四条转移方程：

将之前放在第 k 个字母上的手指移动到第 i 个字母上，此时新的双指位置为 i 和 i-1
- $d[i][i-1]=d[i-1][k]+d i s t(k, i)$
将之前放在第 i−1 个字母上的手指移动到第 i 个字母上，此时新的双指位置为 i 和 k
- $d[i][k]=d[i-1][k]+d i s t(i-1, i)$
之前仅使用一根手指的情况下，将第二根手指直接移动到第 i 个字母上
- $d[i][i-1]=d[i-1][i-1] + 0$
依然只使用一根手指
- $d[i][i]=d[i-1][i-1] + d i s t(i-1, i)$

转移顺序为从左到右，转移基态为

$d[0][0]=0$
$d[1][0]=0$
$d[1][1]=dist(0,1)$

代码如下：

class Solution:
    def minimumDistance(self, word: str) -> int:
        dis = {
            chr(ord(‘A’) + i): [0, i] for i in range(6)
        }
        dis.update({chr(ord(‘G’) + i): [1, i] for i in range(6)})
        dis.update({chr(ord(‘M’) + i): [2, i] for i in range(6)})
        dis.update({chr(ord(‘S’) + i): [3, i] for i in range(6)})
        dis.update({chr(ord(‘Y’) + i): [4, i] for i in range(2)})

        def get_dis(i,j):
            x, y = dis[word[i]]
            k, l = dis[word[j]]
            return abs(x - k) + abs(y - l)

        dp = [[9999999 for i in range(len(word))] for i in range(len(word))]
        dp[0][0] = 0
        dp[1][0] = 0

        for i in range(1, len(word)):
            for j in range(i-1):
                dp[i][i-1] = min(dp[i][i-1], dp[i-1][j] + get_dis(j, i))
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + get_dis(i-1, i))

            dp[i][i-1] = min(dp[i][i-1], dp[i-1][i-1] + 0)
            dp[i][i] = dp[i-1][i-1] + get_dis(i-1, i)

        ans = 99999999

        for i in range(len(word)):
            ans = min(ans, dp[len(word)-1][i])

        return ans

class Solution:

def minimumDistance(self, word: str) -> int:

dis = {

chr(ord(‘A’) + i): [0, i] for i in range(6)

}

dis.update({chr(ord(‘G’) + i): [1, i] for i in range(6)})

dis.update({chr(ord(‘M’) + i): [2, i] for i in range(6)})

dis.update({chr(ord(‘S’) + i): [3, i] for i in range(6)})

dis.update({chr(ord(‘Y’) + i): [4, i] for i in range(2)})

def get_dis(i,j):

x, y = dis[word[i]]

k, l = dis[word[j]]

return abs(x - k) + abs(y - l)

dp = [[9999999 for i in range(len(word))] for i in range(len(word))]

dp[0][0] = 0

dp[1][0] = 0

for i in range(1, len(word)):

for j in range(i-1):

dp[i][i-1] = min(dp[i][i-1], dp[i-1][j] + get_dis(j, i))

dp[i][j] = min(dp[i][j], dp[i - 1][j] + get_dis(i-1, i))

dp[i][i-1] = min(dp[i][i-1], dp[i-1][i-1] + 0)

dp[i][i] = dp[i-1][i-1] + get_dis(i-1, i)

ans = 99999999

for i in range(len(word)):

ans = min(ans, dp[len(word)-1][i])

return ans