小O的数位翻转
小O的数位翻转
https://www.nowcoder.com/practice/80a2e1aa90a24841bb153d14f13aa24a
小O的数位翻转
[题目链接](https://www.nowcoder.com/practice/80a2e1aa90a24841bb153d14f13aa24a)
思路
对数组中的每个数字，将其二进制表示翻转（去除前导零），如果翻转后的值严格大于原值，则计入答案。
二进制翻转
对于一个正整数 ，将其二进制从低位到高位逐位取出，依次拼到结果
的低位。具体做法：每次取
的最低位追加到
，然后
右移一位，直到
为 0。这样自然去除了前导零。
例如 ，翻转后得
，计入答案。
，翻转后得
，不计入。
判断条件
翻转后值严格大于原值，等价于二进制的最低位为 1（否则翻转后位数变少，不可能更大）且翻转后确实更大。直接比较即可，无需额外优化。
时间复杂度 ，其中
为数值上界。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
int ans = 0;
for (int i = 0; i < n; i++) {
long long x;
scanf("%lld", &x);
long long rev = 0, tmp = x;
while (tmp > 0) {
rev = (rev << 1) | (tmp & 1);
tmp >>= 1;
}
if (rev > x) ans++;
}
printf("%d\n", ans);
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int ans = 0;
for (int i = 0; i < n; i++) {
long x = sc.nextLong();
long rev = 0, tmp = x;
while (tmp > 0) {
rev = (rev << 1) | (tmp & 1);
tmp >>= 1;
}
if (rev > x) ans++;
}
System.out.println(ans);
}
}
查看8道真题和解析