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

真顶。

3.1 题目

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

输入: n = 3 输出: 6

示例 2：

输入: n = 9 输出: 45

3.2 思路

本题有2两种思路：

  1. 等差数列前n项和的求和公式，运算符只需要Math.pow、+、>>；
  2. 递归，递归有分为两种：
    1. 普通递归；
    2. 基于短路与的递归。

      3.3 代码

      等差数列前n项和： ```java class Solution { public int sumNums(int n) { return ((int) Math.pow(n, 2) + n) >> 1; } }
  1. 普通递归：
  2. ```java
  3. class Solution {
  4.     public int sumNums(int n) {
  5.         if (n == 1) {
  6.             return 1;
  7.         }
  8.         return n + sumNums(n - 1);
  9.     }
  10. }

基于短路与的递归：

  1. class Solution {
  2.     public int sumNums(int n) {
  3.         // 巧妙运用短路与的性质，如果n == 1，则 && 右边的运算都不会执行；如果n > 1，才会执行
  4.         // && 右边的运算。flag不参与实际运算，(n += sumNums(n - 1)) == 0 的 == 0完全是为了
  5.         // 凑一个boolean值
  6.         boolean flag = n > 1 && (n += sumNums(n - 1)) == 0;
  7.         return n;
  8.     }
  9. }

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

2.1 题目

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

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

示例 2：

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

2.2 思路

如果一个数字出现3次，它的二进制每一位也出现的3次。如果把所有的出现三次的数字的二进制表示的每一位都分别加起来，那么每一位都能被3整除。 我们把数组中所有的数字的二进制表示的每一位都加起来。如果某一位能被3整除，那么这一位对只出现一次的那个数的这一肯定为0。如果某一位不能被3整除，那么只出现一次的那个数字的该位置一定为1。

2.3 代码

  1. class Solution {
  2.     public int singleNumber(int[] nums) {
  3.         int[] arr = new int[32];
  4.         for (int num: nums) {
  5.             for (int i = 0; i < 32; ++i) {
  6.                 arr[i] += num & 1;
  7.                 num >>= 1;
  8.             }
  9.         }
  11.         int res = 0;
  12.         for (int i = 31; i >= 0; --i) {
  13.             res <<= 1;
  14.             if (arr[i] % 3 == 1) {
  15.                 res |= 1;
  16.             }
  17.         }
  18.         return res;
  19.     }
  20. }

3、剑指 Offer 15.二进制中1的个数

3.1 题目

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。

3.2 思路

注意是n无符号右移1位，再与1按位与。

3.3 代码

  1. public class Solution {
  2.     public int hammingWeight(int n) {
  3.         int cnt = 0;
  4.         while (n != 0) {
  5.             cnt += (n & 1);
  6.             n = n >>> 1;
  7.         }
  8.         return cnt;
  9.     }
  10. }

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

妙啊。

4.1 题目

一个整型数组 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]

4.2 思路

由于题目要求空间复杂度是O(1)，因此排除了用Map暴力破解法。

  1. 假设只出现一次的数字为x和y，遍历nums数组，每个元素异或操作，由于数组中其他元素均出现两次，因此异或结果是x^y；
  2. 确定x和y的二进制数哪一位不同，基于此将数组num中的元素分成两拨，x和y划分到不同的两波中，然后对每一个子数组每位元素异或，最后得到的结果就是x或者y；
  3. 如何分成两个子数组？由于第一步得到了x^y的结果，结果的二进制位数为1，则代表x和y的二进制在这一位上不同，进而可以划分两个子数组同时将x和y分别放到这两个子数组中。具体做法是：用一个二进制为1的标尺m与x^y的结果按位与，如果为0，则m << 1，直到不为0，则代表此时找到了x^y为1的位数。然后用这个标尺m将数组划分为两个子数组；
  4. 注意空间复杂度为1，因此不能new两个数组然后再分别异或，而是直接遍历nums数组，将num直接与x或者y按位异或。

注意最后划分两个子数组时，判断条件必须是(num & m) == 0，而不能是(num & m) == 1。

4.3 代码

  1. class Solution {
  2.     public int[] singleNumbers(int[] nums) {
  3.         int val = 0;
  4.         for (int num: nums) {
  5.             val ^= num;
  6.         }
  8.         int m = 1;
  9.         while ((val & m) == 0) {
  10.             m <<= 1;
  11.         }
  12.         int x = 0, y = 0;
  13.         for (int num: nums) {
  14.             if ((num & m) == 0) {
  15.                 x ^= num;
  16.             } else {
  17.                 y ^= num;
  18.             }
  19.         }
  20.         return new int[]{x, y};
  21.     }
  22. }

5、剑指 Offer 65.不用加减乘除做加法

5.1 题目

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:

输入: a = 1, b = 1 输出: 2

5.2 思路

image.png

5.3 代码

  1. class Solution {
  2.     public int add(int a, int b) {
  3.         int n, cin = 0;
  4.         while (b != 0) {
  5.             n = a ^ b;
  6.             cin = (a & b) << 1;
  7.             a = n;
  8.             b = cin;
  9.         }
  10.         return a;
  11.     }
  12. }

6、剑指 Offer 53 - II.0～n-1中缺失的数字

边界条件很容易出错…..

6.1 题目

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:

输入: [0,1,3] 输出: 2

示例 2:

输入: [0,1,2,3,4,5,6,7,9] 输出: 8

6.2 思路

排序数组中的搜索问题，首先想到二分法解决。
本题有两种思路：

  1. 数学法：0到数组中最后一个数字正常的前n项和 - 数组中所有元素之和，差就是缺失的数字。时间复杂度为O(n)；
  2. 二分查找，时间复杂度为O(lgn)。

二分查找虽然不好想，但时间复杂度优于数学法，因此面试时还是用二分查找。

  1. 根据题意，数组可以按照以下规则划分为两部分，其中i为数组下标：
    1. 左子数组： nums[i] =i ；
    2. 右子数组： nums[i] != i；
  2. 缺失的数字等于 “右子数组的首位元素” 对应的下标；因此考虑使用二分法查找 “右子数组的首位元素”。

image.png

while循环里的结束条件是left <= right，这个可以用以下两个例子带入来确定：[0,1,2,3,4,5,6,7,9]，[0,2,3,4,5]

6.3 代码

  1.  class Solution {
  2.     public int missingNumber(int[] nums) {
  3.         int left = 0, right = nums.length - 1;
  4.         // 跳出循环时，left 和 right 分别指向 “右子数组的首位元素” 和 “左子数组的末位元素” ，
  5.         // 因此返回 left 即可。
  6.         while (left <= right) {
  7.             int mid = (left + right) >> 1;
  8.             if (nums[mid] == mid) {
  9.                 left = mid + 1;
  10.             } else {
  11.                 right = mid - 1;
  12.             }
  13.         }
  14.         return left;
  15.     }
  16. }

7、461. 汉明距离

7.1 题目

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
示例 1：

输入：x = 1, y = 4 输出：2 解释： 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ 上面的箭头指出了对应二进制位不同的位置。

7.2 思路

  1. 先x、y按位异或，如果x，y对应的二进制位不同，得到的数val的二进制的对应位为1；
  2. 统计val的二进制中数为1的位数。

    7.3 代码

    1. class Solution {
    2.  public int hammingDistance(int x, int y) {
    3.      int cnt = 0;
    4.      int val = x ^ y;
    5.      while (val != 0) {
    6.          if ((val & 1) == 1) {
    7.              ++cnt;
    8.          }
    9.          val >>= 1;
    10.      }
    11.      return cnt;
    12.  }
    13. }

    8、338. 比特位计数

    8.1 题目

    给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
    示例 1：

    输入：n = 2 输出：[0,1,1] 解释： 0 —> 0 1 —> 1 2 —> 10

8.2 思路

本质就是求一个二进制数中1的个数。

8.3 代码

  1. class Solution {
  2.     public int[] countBits(int n) {
  3.         int[] res = new int[n + 1];
  4.         for (int i = 0; i <= n; ++i) {
  5.             res[i] = getOne(i);
  6.         }
  7.         return res;
  8.     }
  10.     private int getOne(int n) {
  11.         int cnt = 0;
  12.         while (n != 0) {
  13.             if ((n & 1) == 1) {
  14.                 ++cnt;
  15.             }
  16.             n >>= 1;
  17.         }
  18.         return cnt;
  19.     }
  20. }