基础&技巧
1.aab=b,依据此特性可以实现数据去重
2.a^b的是a+b不带进位的结果，依据此可通过位运算实现+法
3.a% N = value & (N - 1),N为2的指数倍
LeetCode136:只出现一次的数组
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
思路：利用异或的去重特征一次遍历循环异或即可
/**
* LeetCode-136：
* 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
*
* 思路:利用异或的去重特性一把过
*/
public int singleNumber(int[] nums) {
int xor = 0;
for (int i : nums) {
xor = xor ^ i;
}
return xor;
}
LeetCode-137：只出现一次的数组
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
思路:
1.由于元素出现了三次，所以不能利用异或做过滤处理了，考虑其他位运算的方案
2.题设的数组，各个bit位上相加，要么是3N,要么是3N+1, 3N则表示唯一元素对应的位是0，3N+1则表示对应位是1.
3.所以按位遍历计算各个bit位的和，对3取模即可得到唯一元素上对应的bit位，做位移累加即可。
public int singleNumber2(int[] nums) {
int res = 0;
int tmp = 0;
for (int i = 0; i < 32; i++) {
for (int j = 0; j < nums.length; j++) {
int mask = nums[j] & (1 << i);//过滤1
mask = mask == 0 ? 0 : 1;
tmp += mask;
}
if (tmp % 3 != 0) {
res += 1 << i;
}
tmp = 0;
}
return res;
}
LeetCode29:两数相除
给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。
整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。
思路:
1.先取绝对值和结果符号;
2.divisor左移直到大于被除数，记录位移数r，r = r-1就是对应bit位1;
3.被除数-pow(2, r),继续步骤2,直到结果小于0;
4.考虑边界:
1>Integer.MIN_VALUE/-1 = Integer.MAX_VALUE;
2>避免位移运算的时候无法退出，绝对值取long;
/**
* LeetCode29:两数相除
* 给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。
* <p>
* 整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。
* <p>
* 思路：
* 1.先取绝对值
* 2.divisor左移直到大于被除数，记录位移数r，r = r-1就是对应bit位1
* 3.被除数-pow(2, r),继续步骤2,直到结果小于0
* 4.考虑边界:
* 1>Integer.MIN_VALUE/-1 = Integer.MAX_VALUE
* 2>避免位移运算的时候无法退出，绝对值取long
* <p>
* 来源：力扣（LeetCode）
* 链接：https://leetcode.cn/problems/divide-two-integers
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public int divide(int dividend, int divisor) {
//Integer.MIN_VALUE/-1 = Integer.MAX_VALUE
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
int res = 0;
boolean isNeg = (dividend ^ divisor) < 0;//先定义符号
//取绝对值
long tmpDividend = Math.abs((long) dividend);
long tmpDivisor = Math.abs(divisor);
//小于直接返回0
if (tmpDividend < tmpDivisor) {
return 0;
}
while (tmpDividend > 0) {
int count = 0;
//除数左移,直到超过被除数,tmpDivisor和tmpDividend都未long,tmpDividend=Integer.MAX也不会无限循环
while ((tmpDivisor << count) <= tmpDividend) {
count++;
}
count--;
//累加结果
if (count >= 0) {
//更新被除数
tmpDividend -= (tmpDivisor << count);
res += 1 << count;
} else {//没有移位，表示tmpDivisor>tmpDividend，直接减
tmpDividend -= tmpDivisor;
}
}
return isNeg ? -res : res;
}
LeetCode67:二进制求和
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
思路:
双指针逆序遍历，按位计算，考虑进位即可
/**
* LeetCode67:二进制求和
* 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
*/
public String addBinary(String a, String b) {
StringBuilder stb = new StringBuilder();
int i = a.length() - 1;
int j = b.length() - 1;
int c = 0; // 进位
while(i >= 0 || j >= 0) {
if(i >= 0) c += a.charAt(i --) - '0';
if(j >= 0) c += b.charAt(j --) - '0';
stb.append(c % 2);
c >>= 1;
}
String res = stb.reverse().toString();
return c > 0 ? '1' + res : res;
}
LeetCode190:颠倒的二进制位
颠倒给定的 32 位无符号整数的二进制位。
思路：bit[i]->bit[31-i]的转换
/**
* LeetCode190:颠倒给定的 32 位无符号整数的二进制位。
* <p>
* 提示：
* <p>
* 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
* 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。
* <p>
* 来源：力扣（LeetCode）
* 链接：https://leetcode.cn/problems/reverse-bits
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*
* @param n
* @return
*/
public int reverseBits(int n) {
int res = 0;
for (int i = 0; i < 32; i++) {
int mask = 1 << I;
//bit[i]
if ((mask & n) != 0) {
//转换到bit[31-i]
res += 1 << (31 - i);
}
}
return res;
}
LeetCode268: 丢失的数字
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
思路:
1.求0-n的异或和
2.在遍历数组继续做异或做去重
/**
* LeetCode268: 丢失的数字
* 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
* 思路:
* 1.求0-n的异或和
* 2.在遍历数组继续做异或做去重
*
* @param nums
*/
public int missingNumber(int[] nums) {
int n = nums.length;
//异或和
int xor = 0;
for (int i = 0; i <= n; i++) {
xor = xor ^ i;
//去重
if (i < n) {
xor = xor ^ nums[i];
}
}
return xor;
}
网友评论