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

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

image.png

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

共 11 个回复

题解

5307. 将整数转换为两个无零整数的和

Brute Force 暴力
显然对于任何 2n1042 \leq n \leq 10^4 ,都至少存在一组解。直接构造或许是一种可行的方式,但由于数据范围非常小,不妨暴力枚举后检查是否合法。

  • 封装一个函数用来检查这个数是否包含数位 00
  • 11 开始枚举到 n1n-1 , 检查 iinin-i 是否都满足条件

或可采用类似的字符串处理办法

class Solution {
    bool check(int x){
        while (x){
            if (x%10==0) return false;
            x/=10;
        }
        return true;
    }
public:
    vector<int> getNoZeroIntegers(int n) {
        for (int i=1;i<n;++i){
            if (check(i)&&check(n-i)){
                return {i,n-i};
            }
        }
        return {};
    }
};

5308. 或运算的最小翻转次数

Greedy 贪心
由于位运算是各位独立的运算,位于位之间不会有相互干扰(如进位)。我们按位考虑这个问题,把每个数位对答案的贡献计算清楚,然后累加即可。

  • a=0,b=0,c=0 ans+=0
  • a=0,b=0,c=1 ans+=1
  • a=0,b=1,c=0 ans+=1
  • a=0,b=1,c=1 ans+=0
  • a=1,b=0,c=0 ans+=1
  • a=1,b=0,c=1 ans+=1
  • a=1,b=1,c=0 ans+=2
  • a=1,b=1,c=1 ans+=0

此外还需要最基本的位运算知识:

  • 一个数 xx 的二进制表示中第 ii 位为 00 当且仅当 x&(2^i)==0 (&为按位与)
  • 一个数 xx 的二进制表示中第 ii 位为 11 当且仅当 x&(2^i)!=0 (&为按位与)

或采用相关数字转二进制字符串后填充前导零处理也可以通过。

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int ans=0;
        for (int i=0;i<31;++i){
            if (c&(1<<i)){
                if (!(a&(1<<i))&&!(b&(1<<i))) ++ans; 
            }
            else{
                if (a&(1<<i)) ++ans;
                if (b&(1<<i)) ++ans;
            }
        }
        return ans;
    }
};

5309. 连通网络的操作次数

union-find sets 并查集DFS 深度优先搜索

对于一个 nn 个节点的无向图,要求连通至少需要 n1n-1 条边(即生成树)
所以当 connections.length<n1connections.length < n-1 时无解,返回 1-1

否则,一定有解。统计现有的边将图分割成了几个连通分量。则每个连通分量内部的点都是相互可达的,而不同分量的点都是相互不可达的。我们将每个连通分量连通起来,整个图就连通了。 现考虑有 uu 个连通分量,则答案为 u1u-1。(为什么?还是因为生成树)

进阶思考:如果要求给出任意一种可行的修改方案,怎么做?

class Solution {
    int fa[100100];
    int ra[100100];

    void init(int n){
        for (int i=0;i<n;++i){
            fa[i]=i;
            ra[i]=0;
        }
    }

    int findfa(int x){
        if (fa[x]==x) return x;
        return fa[x]=findfa(fa[x]);
    }

    void unite(int x,int y){
        x=findfa(x);y=findfa(y);
        if (x==y) return;
        if (ra[x]<ra[y]) fa[x]=y;
        else{
            fa[y]=x;
            if (ra[x]==ra[y]) ++ra[x];
        }
    }

public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        if (connections.size()<n-1) return -1;
        init(n);
        for (auto &e:connections){
            unite(e[0],e[1]);
        }
        int cnt=0;
        for (int i=0;i<n;++i){
            if (findfa(i)==i) ++cnt;
        }
        return cnt-1;
    }
};

5310. 二指输入的的最小距离

Dynamic Programming动态规划
dp[i][lx][ly][rx][ry]dp[i][lx][ly][rx][ry] 表示打到第 ii 个字符时左手在 [lx,ly][lx,ly] ,右手在 [rx,ry][rx,ry] 位置最少移动步数,然后按题意转移即可。初始化dp[0]的所有元素为0,最终答案为dp[n]中最小的值

一些技巧:

  • 由于想偷懒,直接将字母对应位置存到静态数组里了
  • 封装一个计算距离的函数

一些细节:

  • 左手和右手其实是等价的,应该时刻保证 dp[i][lx][ly][rx][ry]=dp[i][rx][ry][lx][ly]dp[i][lx][ly][rx][ry]=dp[i][rx][ry][lx][ly]
  • 当然,也可以规定存储优先级(始终保证左手在字母序号更小的位置),以做到等价数据只存储一份

根据数据范围,不带剪枝的暴力可能会超时。记忆化搜索本质类似,应该能够通过。

static int pos[26][2]={
    {0,0},{0,1},{0,2},{0,3},{0,4},{0,5},
    {1,0},{1,1},{1,2},{1,3},{1,4},{1,5},
    {2,0},{2,1},{2,2},{2,3},{2,4},{2,5},
    {3,0},{3,1},{3,2},{3,3},{3,4},{3,5},
    {4,0},{4,1}
};

class Solution {
    int dp[310][5][6][5][6];

    inline int dis(int x1,int y1,int x2,int y2){
        return abs(x1-x2)+abs(y1-y2);
    }

public:
    int minimumDistance(string word) {
        int n=word.length();
        memset(dp,0x3f,sizeof(dp));
        memset(dp[0],0,sizeof(dp[0]));
        for (int i=1;i<=n;++i){
            char c=word[i-1];
            int x=pos[c-'A'][0],y=pos[c-'A'][1];
            for (int ii=0;ii<5;++ii){
                for (int jj=0;jj<6;++jj){
                    dp[i][x][y][ii][jj]=min(dp[i][x][y][ii][jj],dp[i][ii][jj][x][y]);
                    for (int px=0;px<5;++px){
                        for (int py=0;py<6;++py){
                            dp[i][x][y][ii][jj]=min(dp[i][x][y][ii][jj],dp[i-1][ii][jj][px][py]+dis(px,py,x,y));
                            dp[i][x][y][ii][jj]=min(dp[i][x][y][ii][jj],dp[i-1][px][py][ii][jj]+dis(px,py,x,y));
                        }
                    }
                    dp[i][x][y][ii][jj]=dp[i][ii][jj][x][y]=min(dp[i][x][y][ii][jj],dp[i][ii][jj][x][y]);
                }
            }
        }
        int ans=0x3f3f3f3f;
        for (int i=0;i<5;++i){
            for (int j=0;j<6;++j){
                for (int ii=0;ii<5;++ii){
                    for (int jj=0;jj<6;++jj){
                        ans=min(ans,dp[n][i][j][ii][jj]);
                    }
                }
            }
        }
        return ans;
    }
};

13

题解

第一题
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

T1:
暴力对比即可

T2:
根据 or 的性质来做。每一位不会影响到其他位。

初始ansans 置零。
从低位往高位扫。
如果该位正确, 则不管。
如果该位不正确。 则分两种情况
(1) c[i] = 1. 此时a[i] = b[i] = 0, 改1位即可。
(2) c[i] = 0. 此时需要把a[i]和b[i]都改为0, 改a[i] + b[i]位即可。

T3:
先看边够不够n1n - 1, 不够直接返回1-1.
够的话看连通分量有几个, 可以用并查集维护.
如果连通分量有xx个则答案为x1x-1. 原因是每个连通分量中必定有环, 将其环上的任意一条边改动可以联通另一个分量使得连通分量数量减少11. 总共需要x1x-1次操作才能连通全图。

T4:
简单dp.
dp(i,x1,y1,x2,y2)dp(i, x1, y1, x2, y2) 为输入前ii个字符时, 左手在(x1,y1)(x1, y1), 右手在(x2,y2)(x2, y2)处的最小距离。
类推很好类推。

1

好菜啊,简单dp又没搞出来

1

第4题,动态规划...

增加坐标的长度,用0坐标表示该手指尚未开始移动,则移动该手指的成本为0。


const int maxn = 305;
const int kInf = 0x3f3f3f3f;

int dp[maxn][27][27];
int dist[27][27];

class Solution {
public:
    int minimumDistance(string word) {
        memset(dp, 0x3f, sizeof(dp));
        dp[0][0][0] = 0;
        // 初始化距离表, 0到任意位置的成本为0
        for (int i = 0; i < 26; i++) {
            for (int j = i+1; j < 26; j++) {
                int y0 = i/6, x0 = i%6;
                int y1 = j/6, x1 = j%6;
                dist[i+1][j+1] = dist[j+1][i+1] = abs(y0-y1) + abs(x0-x1);
            }
        }

        int lw = (int)word.size();
        for (int i = 0; i < lw; i++) {
            int next = word[i] - 'A' + 1; // 映射到 1 ~ 26

            // 0位置表示手指尚未移动
            for (int a = 0; a < 27; a++) {
                for (int b = 0; b < 27; b++) { // 遍历两个手指的位置
                    if (dp[i][a][b] == kInf) continue;
                    int cost = dp[i][a][b];

                    // 移动第一根手指
                    dp[i+1][next][b] = min(dp[i+1][next][b], cost + dist[a][next]);
                    
                    // 移动第二根手指
                    dp[i+1][a][next] = min(dp[i+1][a][next], cost+dist[b][next]);
                }
            }
        }
        
        int ans = kInf;
        for (int i = 0; i < 27; i++) {
            for (int j = 0; j < 27; j++)
                if (dp[lw][i][j] != kInf)
                    ans = min(ans, dp[lw][i][j]);
        }
        return ans;
    }
};



1

或运算最小翻转次数那题第一个示例没有问题吗?把a变成3不是一次就行吗?

求大神给菜鸟讲解一下将整数转换为两个无零整数的和的思路

第一题算出答案了怎么返回啊,那个returnsize怎么使用??

第一题: 遍历1到n, 逐个检查 (1, n-1) (2, n-2).....
第二题:转为二进制, 先a|b, 然后和bin(c) 比较, 不同的是1: +1, 不同的是0, 加 2.
第三题:只要并查集, 然后检查环数 >= len(set(parents))-1 就可以咯. 只要检查边数和独立的网络数就可以了...想复杂了...
第四题:DP四种状态:

AB, 新来一个C
A->C, B
A, B->C
A-B, C
A-B-C

第三题连通网络的操作次数在线够的情况下为什么不是有没链接的电脑直接改一条连接线就行了?这时候肯定是有多余的连接线啊。