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

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

image.png

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

展开讨论

题解

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
展开全部 11 讨论