On the shoulders of giants.

weekly-contest-171

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

「无零整数」是十进制表示中 不含任何 0 的正整数。

给你一个整数 n,请你返回一个 由两个整数组成的列表 [A, B],满足:

  • AB 都是无零整数
  • 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]

提示:

  • 2 <= n <= 10^4
题解

枚举即可,返回第一个成立的。

时间复杂度: \(O(n)\)

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

或运算的最小翻转次数

给你三个正整数 abc

你可以对 ab 的二进制表示进行位翻转操作,返回能够使按位或运算   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 <= 10^9
  • 1 <= b <= 10^9
  • 1 <= c <= 10^9
题解

二进制下处理,模拟或运算分类讨论。

时间复杂度:\((\log n)\)

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int result = 0;
        while(a || b || c) {
            int x = a & 1, y = b & 1, z = c & 1;
            if(z) {
                result += ((x | y) == 0);
            } else {
                result += x + y;
            }
            a >>= 1, b >>= 1, c >>= 1;
        }
        return result;
    }
};

连通网络的操作次数

用以太网线缆将 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

提示:

  • 1 <= n <= 10^5
  • 1 <= connections.length <= min(n*(n-1)/2, 10^5)
  • connections[i].length == 2
  • 0 <= connections[i][0], connections[i][1] < n
  • connections[i][0] != connections[i][1]
  • 没有重复的连接。
  • 两台计算机不会通过多条线缆连接。
题解

把网络看成无向图,然后求出连通块,假如连通块数量为 n ,那么答案就是: n-1

如果边数都不够组成连通图 \((M<N-1)\) ,那么就是无解。

时间复杂度:\(O(n)\)

const int N = 1E5 + 50;
class Solution {
public:
    vector<int> edge[N];
    int vis[N], id;
    void dfs(int x) {
        vis[x] = id;
        for(auto y : edge[x]) {
            if(!vis[y]) dfs(y);
        }
    }
    int makeConnected(int n, vector<vector<int>>& connections) {
        if(connections.size() < n - 1) return -1;
        for(auto connection : connections) {
            edge[connection[0]].push_back(connection[1]);
            edge[connection[1]].push_back(connection[0]);  
        }
        for(int i = 0; i < n; i++) if(!vis[i]) {
            id++;
            dfs(i);
        }
        return id - 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

提示:

  • 2 <= word.length <= 300
  • 每个 word[i] 都是一个大写英文字母。
题解

动态规划:设 \(dp_{i,x,y}\) 为处理完第 i 为字符,左手在 x 号字符,右手在 y 号字符的最小移动距离。

动态转移方程:

边界: \(dp_{0,i,j} = 0\) ,表明还没输入时,两个手可以在任意位置。

\(dp_{i,x,z}=\min (dp_{i-1,x,y}+cost_{y,z})\)

\(dp_{i,z,y}=\min (dp_{i-1,x,y}+cost_{x,z})\)

其中 z 为第 i 位字符的编号,\(cost_{A,B}=|A.x-B.x|+|A.y-B.y|\)

答案 \(result=\min (dp[l][i][j])\) 。

时间复杂度:\(O(n26^2)\) ,n 为字符串长度。

class Solution {
public:
    static const int L = 3E2 + 10, N = 30, INF = 0x3f3f3f3f;
    int dp[L][N][N], tx[N], ty[N];
    Solution() {
        for(int i = 0; i < 26; i++) {
            tx[i] = i / 6, ty[i] = i % 6;
        }
        memset(dp, 0x3f, sizeof(dp));
    }
    int getValue(int a, int b) {
        return abs(tx[a] - tx[b]) + abs(ty[a] - ty[b]);
    }
    int minimumDistance(string word) {
        int l = word.length();
        memset(dp[0], 0, sizeof(dp[0]));
        for(int k = 1; k <= l; k++) {
            int id = word[k - 1] - 'A';
            for(int i = 0; i < 26; i++) {
                for(int j = 0; j < 26; j++) {
                    if(dp[k - 1][i][j] == INF) continue;
                    dp[k][i][id] = min(dp[k][i][id], dp[k - 1][i][j] + getValue(j, id));
                    dp[k][id][j] = min(dp[k][id][j], dp[k - 1][i][j] + getValue(i, id));
                }
            }
        }
        int result = INF;
        for(int i = 0; i < 26; i++) {
            for(int j = 0; j < 26; j++) {
                result = min(result, dp[l][i][j]);
            }
        }
        return result;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注