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

English Version

题目描述

给你一个 正 整数 n。

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

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

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

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

 

示例 1：

示例 2：

 

提示：

• 1 <= n <= 109

解法

方法一：模拟

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

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

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

TypeScript

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;
}