3750. 最少反转次数得到翻转二进制字符串

题目描述

给你一个正整数 n。

令 s 为 n 的 二进制表示（不含前导零）。

二进制字符串 s 的反转是指将 s 中的字符按相反顺序排列得到的字符串。

你可以翻转 s 中的任意一位（将 0 → 1 或 1 → 0）。每次翻转仅影响一位。

请返回使 s 等于其原始形式的反转所需的最少翻转次数。

示例 1：

输入： n = 7

输出： 0

解释：

7 的二进制表示为 "111"。其反转也是 "111"，两者相同。因此，不需要翻转。

示例 2：

输入： n = 10

输出： 4

解释：

10 的二进制表示为 "1010"。其反转为 "0101"。必须翻转所有四位才能使它们相等。因此，所需的最少翻转次数为 4。

提示：

1 <= n <= 10⁹

解法

方法一：模拟

我们首先将整数 \(n\) 转换成二进制字符串 \(s\)，然后我们使用双指针分别从字符串的两端向中间遍历，统计对应位置字符不同的个数 \(cnt\)。由于每次翻转只能影响一位，因此总的翻转次数为 \(cnt \times 2\)。

时间复杂度 \(O(\log n)\)，空间复杂度 \(O(\log n)\)，其中 \(n\) 是输入的整数。

Python3JavaC++GoTypeScript

class Solution:
    def minimumFlips(self, n: int) -> int:
        s = bin(n)[2:]
        m = len(s)
        return sum(s[i] != s[m - i - 1] for i in range(m // 2)) * 2

class Solution {
    public int minimumFlips(int n) {
        String s = Integer.toBinaryString(n);
        int m = s.length();
        int cnt = 0;
        for (int i = 0; i < m / 2; i++) {
            if (s.charAt(i) != s.charAt(m - i - 1)) {
                cnt++;
            }
        }
        return cnt * 2;
    }
}

class Solution {
public:
    int minimumFlips(int n) {
        vector<int> s;
        while (n > 0) {
            s.push_back(n & 1);
            n >>= 1;
        }

        int m = s.size();
        int cnt = 0;
        for (int i = 0; i < m / 2; i++) {
            if (s[i] != s[m - i - 1]) {
                cnt++;
            }
        }
        return cnt * 2;
    }
};

func minimumFlips(n int) int {
    s := strconv.FormatInt(int64(n), 2)
    m := len(s)
    cnt := 0
    for i := 0; i < m/2; i++ {
        if s[i] != s[m-i-1] {
            cnt++
        }
    }
    return cnt * 2
}

function minimumFlips(n: number): number {
    const s = n.toString(2);
    const m = s.length;
    let cnt = 0;
    for (let i = 0; i < m / 2; i++) {
        if (s[i] !== s[m - i - 1]) {
            cnt++;
        }
    }
    return cnt * 2;
}

3750. 最少反转次数得到翻转二进制字符串

题目描述

解法

方法一：模拟

评论