129 lines
5.5 KiB
JavaScript
129 lines
5.5 KiB
JavaScript
/**
|
||
* 异或运算是一种位运算，相同为0，不同为1，比如110 ^ 001结果为111，也可看成无进位加法这点非常有用
|
||
*/
|
||
|
||
/**
|
||
* 使用疑惑交换两个变量的值
|
||
*/
|
||
function swap() {
|
||
let a = 1;
|
||
let b = 2;
|
||
a = a ^ b;
|
||
b = a ^ b;
|
||
a = a ^ b;
|
||
console.log(a);
|
||
console.log(b);
|
||
}
|
||
|
||
/**
|
||
* 比较两个数，返回其中较大的那个
|
||
*/
|
||
function getMax(a, b) {
|
||
let flag = (a - b) >>> 31; // 如果b大的话，结果就是个负数，负数的符号位为1
|
||
return a * (flag ^ 1) + b * flag;
|
||
/* 解释：比较两个数的大小最直观的方式就是作差，然后判断差是否大于零，如果大于零则说明
|
||
被减数大，如果小雨零则说明减数大，我们只要拿到最高位，如果是1，我们就返回减数b，否则
|
||
返回减数a，这个时候我们需要找到某种运算在falg为1的时候它要为0，flag为0的时候它要为1
|
||
所以我们把flag^1,并分别把(flag^1)和flag分别作为a,b的乘数，相加的结果就是我们要求
|
||
的最大数。这里面之所以没有用到判断是因为，位本身就表示一种状态。
|
||
*/
|
||
}
|
||
|
||
/**
|
||
* https://leetcode.cn/problems/missing-number/
|
||
* 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
|
||
* @param {number[]} nums - 如果把缺失的数补上，排序后下标和值是一一对应的
|
||
*/
|
||
function missingNumber(nums) {
|
||
let eorAll = 0,
|
||
eorHas = 0;
|
||
for (let i = 0; i < nums.length; i++) {
|
||
eorAll ^= i;
|
||
eorHas ^= nums[i];
|
||
}
|
||
eorAll ^= nums.length;
|
||
return eorAll ^ eorHas;
|
||
}
|
||
/*
|
||
分析：按照题目要求，如果没有缺少那个数的话，0-n应该是n+1个数，而且和下标一一对应，因为
|
||
它们是连续的，只有那个多出的数是没有下表与其对应的（这里的对应表示它们的值相等），根据异或
|
||
的运算特点，两个相同的数做异或运算的结果为0，任何数和0做运算为本身，我们只需把所有下标异或的结果
|
||
和所有值异或的结果做一次异或运算就可以得到多出来的那个数，如果之间缺少一个数的话数组中最后一个值
|
||
对应的是数组下标，所以也要把数组下标异或上。
|
||
*/
|
||
|
||
/**
|
||
* https://leetcode.cn/problems/single-number/
|
||
* 数组中1种数出现了奇数次，其他的数都出现了偶数次,返回出现了奇数次的数。
|
||
* @param {number[]} nums - 这个数组里面有某个数只出现了奇数次
|
||
*/
|
||
function singleNumber(nums) {
|
||
let eor = 0;
|
||
for (let num of nums) {
|
||
eor ^= num;
|
||
}
|
||
return eor;
|
||
}
|
||
/**
|
||
* 原理：这个很简单，两个相同的数异或结果为0，任何数和0异或结果为本身，如果数组中所有
|
||
* 的除了一中出现奇数次，其余数属出现偶数次，那么异或的结果必定是这个出现奇数次的数，因为
|
||
* 所有偶数次的数异或结果为0，0在和这个出现奇数次的数异或，结果为这个奇数次的数。
|
||
*/
|
||
|
||
/**
|
||
* 给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
|
||
* @param {number[]} nums
|
||
* @return {number[]}
|
||
*/
|
||
function DoubleNumber(nums) {
|
||
let eor1 = 0;
|
||
for (let num of nums) {
|
||
// 把所有的数值都异或一遍，最后留下的结果就是两个奇数次数异或的结果
|
||
eor1 ^= num;
|
||
}
|
||
// 由于异或的性质，两个数异或的结果如果某位上是1则说明这两个数原本这位上一位为1，一位为0，只需
|
||
let rightOne = eor1 & -eor1; // 重要技巧，与eor1 &（~eor1 + 1）等价，效果为取出最右侧的1
|
||
let eor2 = 0;
|
||
for (let num of nums) {
|
||
if ((num & rightOne) === 0) {
|
||
// 数组中的所有数要么这位是0，要么是1,刚好分开了a和b
|
||
eor2 ^= num;
|
||
}
|
||
}
|
||
return [eor2, eor1 ^ eor2];
|
||
}
|
||
/**
|
||
* 思路：把所有数都异或起来，最后留下的数就是a和b异或的结果，a和b在某位上肯定是不相等的，假设a在某位上是1
|
||
* b在某位上是0，那么这位上异或的结果就是1，而这个一刚好就是异或结果最右侧的1，再来看整个数组的数，由于是
|
||
* 二进制，那么所有的数在这位上要么是1要么是0，其中a,和b也分别在这两组数中，现在我们只需要求出a，或者求出b
|
||
* 那么eor1 ^ a 的结果就是b,eor1 ^ b的结果就是a
|
||
*/
|
||
|
||
/**
|
||
* https://leetcode.cn/problems/single-number-ii/
|
||
* 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
|
||
* @param {number[]} nums
|
||
* @return {number}
|
||
*/
|
||
var singleNumberOne = function (nums) {
|
||
let ans = 0;
|
||
for (let i = 0; i < 32; i++) {
|
||
let total = 0; // 统计每一位上的和
|
||
for (let num of nums) {
|
||
total += (num >> i) & 1;
|
||
}
|
||
// 判断total是否能被三除净，如果除不尽，这个位置就是1
|
||
if (total % 3 !== 0) {
|
||
ans |= 1 << i;
|
||
}
|
||
}
|
||
return ans;
|
||
};
|
||
|
||
/**
|
||
* 思路：我们统计每个数每一位上的数值累加总和，首先我们不考虑只出现一次的那个数，其余出现
|
||
* 三次的数累加起来对3求模的结果一定是0，我们再把多出的那个数考虑进去，如果多出的那个数某
|
||
* 位上面是0，那么求模的结果还是0，如果是1，那么total求模的结果就是1，而这个1我们要把它放到
|
||
* 对应的位置上去，对nums的所有数的每一位都做处理后，所得的结果就是只出现一次的那个数。
|
||
*/
|