剑指 Offer 64. 求 1+2+…+n、剑指 Offer 56 - II. 数组中数字出现的次数 II、剑指 Offer 56 - I. 数组中数字出现的次数

剑指 Offer 64. 求 1+2+…+n

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句（A?B:C）。
示例 1：

输入: n = 3
输出: 6

示例 2：

输入: n = 9
输出: 45

限制：

• 1 <= n <= 10000

思路

递归

使用 js 隐式转换，判断 n 是否大于 0，Boolean(0)为 false，&&断路，终止递归。

幂运算、位移动

根据等差数列求和公式，首项加尾项乘以项数除以 2，可以得到为(1+n)n/2 = (n^2+n) /2，题目要求不出现乘除法，可以使用幂运算及位移动来代替。n^2=n**2，/2=>>2，所以 (n^2+n) /2 = (n ** 2 + n) >> 1

reduce

本质其实还是循环，循环加数组下标，其实加的是 0-9，所以起始值要设为 n。

解答

递归

/**
 * @param {number} n
 * @return {number}
 */
var sumNums = function (n) {
  return n && sumNums(n - 1) + n;
};

幂运算、位移动

/**
 * @param {number} n
 * @return {number}
 */
var sumNums = function (n) {
  return (n ** 2 + n) >> 1;
};

reduce

/**
 * @param {number} n
 * @return {number}
 */
var sumNums = function (n) {
  return Array(n)
    .fill(0)
    .reduce((a, b, index) => a + index, n);
};

剑指 Offer 56 - II. 数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：

输入：nums = [3,4,3,3]
输出：4

示例 2：

输入：nums = [9,1,7,9,7,9,7]
输出：1

限制：

• 1 <= nums.length <= 10000
• 1 <= nums[i] < 2^31

思路

MAP

存储每个数计数，等于 3 时删除，最后 map 中只剩下结果，返回即可。

数学

假设对于 a、b、c、d 来说，d 出现了 1 次，其他数字出现 3 次。那么求 d 的值的表达式是：2 _ d = 3_(a + b + c + d) - (3a + 3b + 3c + d)
为了计算(a + b + c + d)，可以将数组去重后，再求和。去重借助的是集合（Set）。

位运算

最符合题目要求的解决方法就是：位运算。能在不开辟额外空间的情况下，完成要求。
按照位数（最高 32 位）去考虑，这种方法的关键就是找到对于只出现一次的数字，它的哪些二进制位是 1。
整体算法流程如下：
从第 1 位开始
创建掩码（当前位为 1，其他为 0），count 设置为 0
将每个数字和掩码进行&运算，如果结果不为 0，count 加 1
如果 count 整除 3，说明出现一次的数字这一位不是 1；否则，说明出现一次的数字这一位是 1
继续检查第 2 位，一直到 32 位，结束

状态机

暂时不学

解答

MAP

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  const map = new Map();
  for (const num of nums) {
    if (map.get(num) === 2) {
      map.delete(num);
    } else {
      map.set(num, map.get(num) ? map.get(num) + 1 : 1);
    }
  }
  return [...map.keys()][0];
};

数学

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  //a+b+c+d的和
  const sum1 = [...new Set(nums)].reduce((a, b) => a + b);
  //3a+3b+3c+d的和
  const sum2 = nums.reduce((a, b) => a + b);
  return (3 * sum1 - sum2) / 2;
};

位运算

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let res = 0;
  for (let bit = 0; bit < 32; ++bit) {
    // 构造第i位为1的mask
    let mask = 1 << bit;
    let count = 0;
    // 统计所有数字当前位为1的个数
    for (let num of nums) {
      if (num & mask) ++count;
    }
    // 如果当前位1的和不能整除3，说明混入了目标数字的1，这里3可以换成任意奇数
    if (count % 3) {
      res = res | mask;
    }
  }
  return res;
};

剑指 Offer 56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O(n)，空间复杂度是 O(1)**。
**示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：

• 2 <= nums.length <= 10000

思路

两个相同数异或得到的值为 0，因此可以知道，对 nums 进行累计异或得到的 s 一定是两个不同的数 a、b 的异或值
创建一个数组记录结果
对每一个数进行与运算，可以将数分为 1、0 两个组，其中 a、b 两个只出现一次的数必定出现在不同的组
进行异或运算，其他出现过两次的数一定会为 0，最后只剩下只出现一次的一个数

解答

var singleNumbers = function (nums) {
  // 两个相同数异或得到的值为0，因此可以知道，对nums进行累计异或得到的s一定是两个不同的数a、b的异或值
  let s = nums.reduce((a, b) => a ^ b);
  // 这里令 k= s & (-s)是求出不相同二进制串中的第一个1。进行与运算时，使用补码进行计算，求-s的补码过程如下。
  // 例如s=6   原码0000 0000 0000 0000 0000 0000 0000 0110
  //    s=6   补码0000 0000 0000 0000 0000 0000 0000 0110
  // 例如s=-6  原码1000 0000 0000 0000 0000 0000 0000 0110
  //    s=-6  反码1111 1111 1111 1111 1111 1111 1111 1001
  //    s=-6  补码1111 1111 1111 1111 1111 1111 1111 1010
  //    s=6   补码0000 0000 0000 0000 0000 0000 0000 0110
  //          结果0000 0000 0000 0000 0000 0000 0000 0010
  let k = s & -s;
  // 创建一个数组记录结果
  let res = Array(2);

  for (const num of nums) {
    // 对每一个数进行与运算，可以将数分为1、0两个组，其中a、b两个只出现一次的数必定出现在不同的组
    if (num & k) {
      // 进行异或运算，其他出现过两次的数一定会为0，最后只剩下只出现一次的一个数
      res[0] ^= num;
    } else {
      res[1] ^= num;
    }
  }
  return res;
};