套路
- 涉及到二进制、不用单目运算符做加法运算，其中某一位的问题（两数不同，至少有一位不同）
- 求解运算符选择受限时可以考虑利用逻辑与&&逻辑或||的短路特性
- 二进制数1的个数： n = n & n - 1
- a ^ b 不进位加法，(a & b) << 1 进位加法
- 仅利用位去存储少量（小于32）的数字
注意点
- 暂无
目录
- 二进制中1的个数
- 求1+2+3+...+n
- 数组中只出现一次的数字
- 不用加减乘除做加法
- 扑克牌顺子
二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
- 解法一：将数字转二进制字符串，再处理每一个字符
public int NumberOf1(int n) {
int ans = 0;
char[] arr = Integer.toBinaryString(n).toCharArray();
for (char ch : arr) {
if (ch == '1') ans++;
}
return ans;
}
- 解法二： 将数字转成二进制字符串，再将其中的0用""代替，返回结果字符串的长度即可
public int NumberOf1(int n) {
return Integer.toBinaryString(n).replaceAll("0", "").length();
}
- 最优解：位运算，n = n & n - 1 计算一次，1的个数减一
public int NumberOf1(int n) {
int count = 0;
while (n != 0) {
n &= n - 1;
count++;
}
return count;
}
求1+2+3+...+n
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
- 递归调用的出口不能用if语句，可用 n == 0 时 && (逻辑与)的短路特性来终止递归调用
public int Sum_Solution(int n) {
boolean b = (n > 0) && ((n += Sum_Solution(n - 1)) > 0);
return n;
}
数组中只出现一次的数字
题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
- 数组中只有出现了一次和出现了两次的数，所以可以用异或解题。出现了两次的数异或结果为0，整个数组异或完就是两个只出现一次的数异或的结果。
- 这两个数字不同，其中必然有一位一个是1，一个是0，从刚才异或的结果中找到这一位的位置。两数组按这一位为0和为1分成两部分，其中相同的数那一位必然都为0或都为1，一定会被分在一组，而两个只出现一次的数因为那一位不同，必然会被分在不同的组。两组各自分别再进行一遍异或，即可得到两个数。
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
// ans 保存两个只出现一次的数异或的结果
// index 保存ans中不同的那一位从右往左方向的索引位置
int ans = 0, index = 0;
for (int i = 0; i < array.length; i++) {
ans ^= array[i];
}
// == 比 & 优先级高！
while ((ans & 1) == 0) {
ans >>= 1;
index++;
}
for (int i = 0; i < array.length; i++) {
// == 比 & 优先级高！
(array[i] >> index & 1) == 0 ? num1[0] ^= array[i] : num2[0] ^= array[i];
}
}
不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
- a ^ b 不进位加法，(a & b) << 1 进位加法,两者之和为不进位加法结果加进位加法相加的结果，然而不能用+号得到。我们不断的循环调用这一过程，当进位加法为0时，不进位加法的结果即为两数之和。
public int Add(int num1,int num2) {
do {
int temp = num1 ^ num2;
num2 = (num1 & num2) << 1;
num1 = temp;
} while (num2 != 0);
return num1;
}
扑克牌顺子
LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张_)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何。为了方便起见,你可以认为大小王是0。
- 最优解：不使用任何额外空间（一两个变量不算啊，空间在这里指数据结构），时间复杂度 O(n)，只要满足以下两条即可： 1. 除0以外没有重复的数；2. 除0以外其它数的差小于5。因为数字最大值只有13，所以可以用以下这种方式保存数字，数字1左移num位保存在bitFlag里，标记出现过的数字用来判重。
public boolean isContinuous(int [] numbers) {
if (numbers == null || numbers.length != 5) {
return false;
}
int min = 14, max = -1, bitFlag = 0;
for (int i = 0; i < 5; i++) {
int num = numbers[i];
if (num < 0 || num > 13) return false;
if (num == 0) continue;
if ((bitFlag >> num & 1) == 1) return false;
bitFlag |= 1 << num;
if (num < min) min = num;
if (num > max) max = num;
if (max - min >= 5) return false;
}
return true;
}
