1. 将整数转化为两个无零整数的和

「无零整数」是十进制表示中 不含任何 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]

提示

  • 2 <= n <= 10^4

代码

viv丑陋版

直接暴力。

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

zz美丽版

一样,不过get了用{}表示vector的方法。

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

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

给你三个正整数 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 <= 10^9
  • 1 <= b <= 10^9
  • 1 <= c <= 10^9

代码

viv丑陋版

这么简单的题我也能磕磕绊绊这么久。哭哭。
按位处理,分类讨论。
直接看代码吧。

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int ans = 0;
        for(int i=0; i<50; i++) {
            int aa = a % 2; a >>= 1;
            int bb = b % 2; b >>= 1;
            int cc = c % 2; c >>= 1;
            if(aa==0 && bb==0 && cc==1) ans += 1;
            if(aa==1 && bb==1 && cc==0) ans += 2;
            else if(aa|bb==1 && cc==0) ans += 1;
        }
        return ans;
    }
};

zz美丽版

大同小异,有几个注意点。
首先,i只需要到30即可。$2^10=1024$,$1024^3>10^9$。
其次,或运算一定要加括号。

if((aa | bb) == cc) // 先或再判断相等
if(aa | bb == cc) // 先判断相等再或

代码如下。

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int ans = 0;
        for(int i=0; i<=30; i++) {
            int aa = (a >> i) & 1;
            int bb = (b >> i) & 1;
            int cc = (c >> i) & 1;
            if((aa | bb) == cc) continue;
            if(cc == 1) ans++;
            else ans += aa + bb;
        }
        return ans;
    }
};

3. 连通网络的操作次数

用以太网线缆将 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 <= connectionsi, connectionsi < n
  • connectionsi != connectionsi
  • 没有重复的连接。
  • 两台计算机不会通过多条线缆连接。

代码

viv丑陋版

想到了并查集。
首先对于给定的connections中的元素进行并查集,如果当前两台主机已经在同一个网络中,那么这条网线就是多余的,记录下来。
然后考察没有被连入网络中主机的数量即为答案,如果大于网线数则返回-1。
遇到了几个问题,首先是查找指定元素的父亲应该是调用find函数而不是直接使用数组fa,其次merge时要注意顺序,两个元素顺序不同是会有不同结果的,在题目中merge(rt, i)是必须的。

const int MAXN = 1e5 + 5;
int fa[MAXN];

int find(int x) {
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if(fx != fy) fa[fy] = fx;
}
class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        int len = connections.size();
        int line = 0, rt = 0;
        for(int i=0; i<n; i++) fa[i] = i;
        for(int i=0; i<len; i++) {
            int x = connections[i][0], y = connections[i][9];
            if(find(x) == find(y)) line++;
            else {
                merge(x, y);
                rt = find(x);
            }
        }
        int ans = 0;
        for(int i=0; i<n; i++) {
            if(find(i) != rt) {
                merge(rt, i);
                ans++;
            }
        }
        if(ans > line) return -1;
        return ans;
    }
};

zz美丽版

思路一致。
不同点,一是zz写的是按秩合并,效率高点。二是zz的想法比我简洁许多。
首先判断如果给定边不足n-1,那么一定返回-1。否则,一定可以成功连接。
一定可以连接的情况下,只需要返回连通块个数-1即可。

const int MAXN = 1e5 + 5;
int fa[MAXN];

int find(int x) {
    return fa[x] = (fa[x] == x ? x : find(fa[x]));
}
bool merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if(fx == fy) return false;
    if(fx > fy) swap(fx, fy);
    fa[fx] = fy;
    return true;
}
class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        int len = connections.size();
        if(len < n - 1) return -1;

        int ans = 0;
        for(int i=0; i<n; i++) fa[i] = i;

        int cnt = n;
        for(auto edge: connections) {
            int x = edge[0], y = edge[1];
            if(merge(x, y)) --cnt;
        }
        return cnt - 1;
    }
};

4.

4. 二指输入的最小距离

二指输入法定制键盘在 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] 都是一个大写英文字母。

代码

viv丑陋版

无。

zz美丽版

dpi[k]表示输入完前i个字母,手指落在j和k字母上所移动的最小距离。
考虑到直接按下手指停留的位置不需要代价,用j和k为26来表示这种状态。

class Solution {
public:
    int getX(char ch) {
        int num = ch - 'A';
        return num / 6;
    }
    int getY(char ch) {
        int num = ch - 'A';
        return num % 6;
    }
    int minimumDistance(string word) {
        int dp[305][30][30];
        memset(dp, -1, sizeof(dp)); 
        dp[0][26][26] = 0;

        int len = word.size();
        for(int i=1; i<=len; i++) {
            char ch = word[i-1];
            int x = getX(ch), y = getY(ch);
            for(int a=0; a<=26; a++) {
                for(int b=0; b<=26; b++) {
                    if(dp[i-1][a][b] == -1) continue;

                    int cost = 0;
                    
                    if(a == 26) cost = 0;
                    else cost = abs(x-getX('A'+a)) + abs(y-getY('A'+a));
                    if(dp[i][ch-'A'][b] == -1 || dp[i][ch-'A'][b] > dp[i-1][a][b] + cost)
                        dp[i][ch-'A'][b] = dp[i-1][a][b] + cost;

                    if(b == 26) cost = 0;
                    else cost = abs(x-getX('A'+b)) + abs(y-getY('A'+b));
                    if(dp[i][a][ch-'A'] == -1 || dp[i][a][ch-'A'] > dp[i-1][a][b] + cost)
                        dp[i][a][ch-'A'] = dp[i-1][a][b] + cost;
                }
            }
        }
        int ans = 0x3f3f3f3f;
        for(int a=0; a<26; a++) {
            for(int b=0; b<26; b++) {
                if(dp[len][a][b] != -1) ans = min(ans, dp[len][a][b]);
            }
        }
        return ans;
        
    }
};
最后修改:2020 年 06 月 06 日 11 : 08 AM
如果觉得我的文章对你有用,请随意赞赏