Medium
题目描述
给定一个整数数组 nums。
对于每个元素 nums[i]，你可以执行以下操作任意次数（包括零次）：
- 将
nums[i]增加 1，或 - 将
nums[i]减少 1。
如果一个数的二进制表示（不含前导零）正着读和倒着读是相同的，则称该数为二进制回文数。
你的任务是返回一个整数数组 ans，其中 ans[i] 表示将 nums[i] 转换为二进制回文数所需的最少操作次数。
示例 1：
输入：nums = [1,2,4]
输出：[0,1,1]
解释：
1的二进制是1，已经是回文，需要 0 次操作2的二进制是10，最近的回文是3（二进制11），需要增加 1 次4的二进制是100，最近的回文是3（二进制11），需要减少 1 次
示例 2：
输入：nums = [6,7,12]
输出：[1,0,3]
解释：
6的二进制是110，最近的回文是5（二进制101），需要减少 1 次7的二进制是111，已经是回文，需要 0 次操作12的二进制是1100，最近的回文是15（二进制1111），需要增加 3 次
约束条件：
1 <= nums.length <= 50001 <= nums[i] <= 5000
提示：
- 预处理二进制回文数
- 对于每个
nums[i]，从预处理的值中找到最近的二进制回文数
解题思路
解题思路
这道题的核心是找到每个数字对应的最近二进制回文数。我们可以采用预处理的方法：
预处理所有二进制回文数：由于数值范围在 1-5000，我们可以预先生成所有可能的二进制回文数。考虑到操作后的数字可能超出原始范围，我们需要扩大预处理范围。
生成二进制回文数的方法：
- 对于奇数长度的二进制串：取前半部分，中间保留一位，后半部分为前半部分的镜像
- 对于偶数长度的二进制串：取前半部分，后半部分为前半部分的镜像
查找最近回文数：对于每个输入数字，在预处理的回文数集合中找到距离最近的一个（可能有多个，取任意一个即可）。
优化查找：由于回文数是有序的，我们可以使用二分查找来快速定位最近的回文数。
算法步骤：
- 预处理：生成所有长度在合理范围内的二进制回文数
- 对每个输入数字，使用二分查找找到最近的回文数
- 计算操作次数（绝对值差）
时间复杂度主要在预处理阶段，查询阶段非常高效。
代码实现
class Solution {
public:
vector<int> minOperations(vector<int>& nums) {
// 预处理所有可能的二进制回文数
set<int> palindromes;
// 生成所有长度的二进制回文数
for (int len = 1; len <= 20; len++) {
// 奇数长度
if (len % 2 == 1) {
int half_len = len / 2;
for (int i = 0; i < (1 << half_len); i++) {
int palindrome = i;
int temp = i >> 1;
while (temp > 0) {
palindrome = (palindrome << 1) | (temp & 1);
temp >>= 1;
}
if (palindrome > 0) palindromes.insert(palindrome);
}
} else {
// 偶数长度
int half_len = len / 2;
for (int i = 1; i < (1 << half_len); i++) {
int palindrome = i;
int temp = i;
while (temp > 0) {
palindrome = (palindrome << 1) | (temp & 1);
temp >>= 1;
}
palindromes.insert(palindrome);
}
}
}
vector<int> palindrome_list(palindromes.begin(), palindromes.end());
vector<int> result;
for (int num : nums) {
int min_ops = INT_MAX;
// 二分查找最近的回文数
auto it = lower_bound(palindrome_list.begin(), palindrome_list.end(), num);
// 检查当前位置及前一个位置
if (it != palindrome_list.end()) {
min_ops = min(min_ops, abs(*it - num));
}
if (it != palindrome_list.begin()) {
--it;
min_ops = min(min_ops, abs(*it - num));
}
result.push_back(min_ops);
}
return result;
}
};
class Solution:
def minOperations(self, nums: List[int]) -> List[int]:
# 预处理所有可能的二进制回文数
palindromes = set()
# 生成所有长度的二进制回文数
for length in range(1, 21):
if length % 2 == 1:
# 奇数长度
half_len = length // 2
for i in range(1 << half_len):
palindrome = i
temp = i >> 1
while temp > 0:
palindrome = (palindrome << 1) | (temp & 1)
temp >>= 1
if palindrome > 0:
palindromes.add(palindrome)
else:
# 偶数长度
half_len = length // 2
for i in range(1, 1 << half_len):
palindrome = i
temp = i
while temp > 0:
palindrome = (palindrome << 1) | (temp & 1)
temp >>= 1
palindromes.add(palindrome)
palindrome_list = sorted(list(palindromes))
result = []
for num in nums:
# 使用二分查找找到最近的回文数
import bisect
pos = bisect.bisect_left(palindrome_list, num)
min_ops = float('inf')
# 检查当前位置及前一个位置
if pos < len(palindrome_list):
min_ops = min(min_ops, abs(palindrome_list[pos] - num))
if pos > 0:
min_ops = min(min_ops, abs(palindrome_list[pos - 1] - num))
result.append(min_ops)
return result
public class Solution {
public int[] MinOperations(int[] nums) {
// 预处理所有可能的二进制回文数
HashSet<int> palindromes = new HashSet<int>();
// 生成所有长度的二进制回文数
for (int len = 1; len <= 20; len++) {
if (len % 2 == 1) {
// 奇数长度
int halfLen = len / 2;
for (int i = 0; i < (1 << halfLen); i++) {
int palindrome = i;
int temp = i >> 1;
while (temp > 0) {
palindrome = (palindrome << 1) | (temp & 1);
temp >>= 1;
}
if (palindrome > 0) palindromes.Add(palindrome);
}
} else {
// 偶数长度
int halfLen = len / 2;
for (int i = 1; i < (1 << halfLen); i++) {
int palindrome = i;
int temp = i;
while (temp > 0) {
palindrome = (palindrome << 1) | (temp & 1);
temp >>= 1;
}
palindromes.Add(palindrome);
}
}
}
var palindromeList = palindromes.ToArray();
Array.Sort(palindromeList);
int[] result = new int[nums.Length];
for (int i = 0; i < nums.Length; i++) {
int num = nums[i];
int pos = Array.BinarySearch(palindromeList, num);
int minOps = int.MaxValue;
if (pos >= 0) {
minOps = 0;
} else {
pos = ~pos;
// 检查当前位置及前一个位置
if (pos < palindromeList.Length) {
minOps = Math.Min(minOps, Math.Abs(palindromeList[pos] - num));
}
if (pos > 0) {
minOps = Math.Min(minOps, Math.Abs(palindromeList[pos - 1] - num));
}
}
result[i] = minOps;
}
return result;
}
}
var minOperations = function(nums) {
function isBinaryPalindrome(n) {
const binary = n.toString(2);
return binary === binary.split('').reverse().join('');
}
function findMinOps(num) {
if (isBinaryPalindrome(num)) return 0;
let ops = 1;
while (true) {
if (num - ops >= 1 && isBinaryPalindrome(num - ops)) {
return ops;
}
if (isBinaryPalindrome(num + ops)) {
return ops;
}
ops++;
}
}
return nums.map(findMinOps);
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(P + n log P)，其中 P 是预处理生成的回文数个数（约2^10 = 1024个），n 是输入数组长度，每次查询需要 O(log P) 的二分查找时间 |
| 空间复杂度 | O(P)，用于存储预处理的回文数集合 |