Easy

题目描述

给你一个正整数 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^9

提示：

  • 生成二进制字符串的反转，并使用双指针从两端确定需要翻转的位置。

解题思路

解题思路

这个问题的核心是比较二进制字符串与其反转后的差异。

基本思路：

  1. 将整数 n 转换为二进制字符串
  2. 生成该字符串的反转
  3. 使用双指针从两端向中心比较，统计不同的位数

关键观察：

  • 对于长度为 len 的二进制字符串，我们只需要比较前 len/2 对位置
  • 如果位置 i 和位置 len-1-i 的字符不同，就需要翻转
  • 由于我们要使原字符串等于反转字符串，每对不匹配的位置都需要恰好一次翻转

优化思路： 可以直接通过位运算来比较对应位置，避免显式构造反转字符串：

  • 获取第 i 位：(n >> i) & 1
  • 获取第 len-1-i 位：(n >> (len-1-i)) & 1

这种方法时间复杂度为 O(log n)，空间复杂度为 O(1)，比字符串方法更高效。

代码实现

class Solution {
public:
    int minimumFlips(int n) {
        string s = "";
        int temp = n;
        while (temp > 0) {
            s = (temp % 2 == 1 ? "1" : "0") + s;
            temp /= 2;
        }
        
        int flips = 0;
        int len = s.length();
        
        for (int i = 0; i < len / 2; i++) {
            if (s[i] != s[len - 1 - i]) {
                flips++;
            }
        }
        
        return flips;
    }
};

class Solution:
    def minimumFlips(self, n: int) -> int:
        s = bin(n)[2:]  # 去掉 '0b' 前缀
        
        flips = 0
        length = len(s)
        
        for i in range(length // 2):
            if s[i] != s[length - 1 - i]:
                flips += 1
        
        return flips

public class Solution {
    public int MinimumFlips(int n) {
        string s = Convert.ToString(n, 2);
        
        int flips = 0;
        int len = s.Length;
        
        for (int i = 0; i < len / 2; i++) {
            if (s[i] != s[len - 1 - i]) {
                flips++;
            }
        }
        
        return flips;
    }
}

var minimumFlips = function(n) {
    const s = n.toString(2);
    
    let flips = 0;
    const len = s.length;
    
    for (let i = 0; i < Math.floor(len / 2); i++) {
        if (s[i] !== s[len - 1 - i]) {
            flips++;
        }
    }
    
    return flips;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log n)需要遍历二进制字符串的一半长度，字符串长度为 log n
空间复杂度O(log n)需要存储二进制字符串，长度为 log n