【LeetCode】剑指 Offer Ⅱ 第1章：整数（5道题） -- Java Version

题库链接：https://leetcode.cn/problem-list/e8X3pBZi/

1. 剑指 Offer II 001. 整数除法 – P1

相似题目：
[1] 程序员面试金典(第6版) 08.05. 递归乘法【不使用 * 运算符， 实现两个正整数的相乘，快速乘】

[2] 剑指 Offer 65. 不用加减乘除做加法 【位运算】

[3] AcWing 875. 快速幂 【模板题】

[4] AcWing 876. 快速幂求逆元 【若 p 为质数，则 a 的逆元，即为 a^p-2】

1.1 整活版：a/b

时间复杂度 $O(1)$，空间复杂度 $O(1)$

class Solution {
    public int divide(int a, int b) {
        if(a == -2147483648 &&b == -1) return 2147483647;
        else return a/b;
    }
}

1.2 快速除（⭐）

时间复杂度 $O(logn)$，空间复杂度 $O(n)$

类似于快速幂的思想，将被除数拆成除数的倍次形式，例如 a=15, b=2 就可以被拆为：15 = 2³ + 2² + 2¹ + 2⁰ = 8 + 4 + 2 + 1 = 24 + 22 + 2*1 + 1 = 商7，余1

class Solution {
    
    public int divide(int a, int b) {
        // 溢出处理
        if (a == Integer.MIN_VALUE && b == -1) return Integer.MAX_VALUE;
        // 正负号处理
        int flag = 2;
        if (a > 0) {
            flag--;
            a = -a;
        }
        if (b > 0) {
            flag--;
            b = -b;
        }
        // 除法变减法
        int ans = process(a, b);
        // 返回结果
        return flag == 1 ? -ans : ans;
    }
    
    public int process(int a, int b) {
        int res = 0; 
        while (a <= b) {
            int val = b;  // 每次要减去的值（b的某次幂）
            int quot = 1;  // 商
            while (val >= Integer.MIN_VALUE/2 && a <= val + val) {  // 防止 2*val 会越界
                quot += quot;
                val += val;
            }
            res += quot;
            a -= val;
        }
        return res;
    }
}

其它优秀写法：
[1] 位运算(快速相减法)

PS : 补充知识1 – 【快速乘 & 快速幂】

快速幂和快速乘法都是利用了二进制的思想，是时间复杂度为O(logN)级别的算法。
该算法由两大优点：1. 便于取模操作（避免溢出）；2. 时间复杂度较低

① 快速幂

快速幂经常被用来求解下列式子：
$$a^{b}modc$$

例如：a¹⁵⁶, 而 156(10) = 1001 1100(2)
那么

我们就按照这个公式来求解 a¹⁵⁶，原来要进行 156-1=155 次乘法运算，现在的差不多运算次数就是他 二进制的长度二进制中1的个数=84=24次.

快速幂的原理就是需要我们先不断的降低a，b的规模，然后再进行计算：

• 降低a的规模：只要让 a变成a*a
• 降低b的规模：如果b是偶数，那么每次a=a*a之后，b=b/2;
  如果b是奇数，那么我们就先把这个多出来的数先挑出来，然后再用偶数的处理方法.

快速幂模板：

// C形式
long long quickpow(long long base,long long power){
   long long ret=1;
   while(power){
     if(power & 1) ret = ret * base;
     base = base * base;
     power>>1;
   }
   return ret;
} 

// Java形式
// step1：循环判断当前指数是否已经移位到0;
// step2：如果当前指数的二进制第0位是1，说明此时可以累乘;
// step3：更新底数;
// step4：右移指数;
// 循环结束后，即可返回结果.

// a 是底数, b 是指数, mod 是模
long ksm(long a, long b, long c) {
	int res = 0;
	while (b > 0)  // 
	{
		if ((b & 1) == 1) res = res * a % c;
		a = a * a;
		b >> 1;
	}
	return res % c;
}

② 快速乘

快速乘法相比快速幂使用频率小很多，因为语言本身就有乘法这个运算符。因此最大的用途便是取模时避免溢出（还有一个好处是：加法运算要比乘法运算快）。

例如：在计算 $M\ast N\%P$ 时，为了避免溢出，我们常常采用的方法是利用分配律将式子转换为：$(M\%P)\ast (N\%P)\%P$，因为一个值模P后其范围为0到P-1，只要P*P不超过数据上限即可。但是如果P的值在 10¹⁸ 这个级别，那显然这种做法还是会爆数据上限。

而用快速乘法可以避免这个烦恼，就像快速幂本质上是乘法，并利用二进制思想减少运算次数。快速乘法本质上是加法，并利用了二进制思想来减少运算次数。因为本质是在做加法运算，所以只要P+P不超过数据上限即可。

实际例子：

以 $13\ast 27$ 为例：
乘法的本质是加法，13*27可以转化为27个13相加（或13个27相加）

将27转化为二进制：

式子即可转化为：

快速乘模板：
和快速幂大同小异，只需要修改符号即可，将乘法换为加法

// C形式
long long quickmul(long long a,long long b){
  long long ret=0;
  while(b){
    if(b%2) ret=ret+a;
    a=a+a;
    b/=2;
  }
  return ret;
}

③ 快速乘与快速幂结合

在计算快速幂时需要用到乘法，在取模对象P很大时乘法就会爆数据上限，所以需要同时使用快速幂和快速乘法：

long long quickmul(long long a,long long b){
  long long ret=0;
  while(b){
     if(b%2) ret=(ret+a)%p;
     a=(a+a)%p;
     b/=2;
  }
  return ret;
}
// key：将快速幂中的乘法运算用快速幂来替代
long long quickpow(long long base,long long power){
    long long ret=1;
    while(power){
       if(power%2) ret=quickmul(ret,base)%p;
       base=quickmul(base,base)%p;
       power/=2;
    }
    return ret;
}

PS : 补充知识2 – 【Java运算符优先级】

赋值运算符包括： =、+=、-=、*=、/=、%=、|=、^=、~=、<<=、>>=、>>>=

更多细节可参考：Java语言中运算符号优先级

PS : 相似题目

① 程序员面试金典(第6版) 08.05. 递归乘法 【快速乘】

Ⅰ. 快速乘循环实现：时间复杂度 $O(logn)$，空间复杂度 $O(1)$ ⭐

class Solution {
    public int multiply(int A, int B) {
        // 正负号处理
        int sign = 2;
        if (A < 0) {
            sign--;
            A = -A;
        }
        if (B < 0) {
            sign --;
            B = -B;
        }
        int res = ksc(A,B);

        return sign == 1 ? -res : res;
    }

    // 快速乘算法
    public int ksc(int a, int b) {
        int ans = 0;
        while (b > 0) {
            if ((b & 1) == 1) ans += a;  // == 的优先级比 & 高
            a += a;
            b >>= 1;
        }
        return ans;
    }
}

Ⅱ. 暴力递归写法：时间复杂度 $O(n)$，空间复杂度 $O(1)$

class Solution {
    // 递归写法：相当于一共进行了 n-1 次的加A操作，仅适用于正整数
    public int multiply(int A, int B) {
        if (A == 0 || B == 0){
            return 0;
        }
        if (B == 1){
            return A;
        }
        if (A == 1){
            return B;
        }
        return multiply(A,B-1)+A;
    }
}

Ⅲ. 类快速乘递归：时间复杂度 $O(logn)$，空间复杂度 $O(1)$

根据乘法的性质可知：$A\ast B=A\ast (B/2)\ast 2=A\ast (B/2)+A\ast (B/2)$，则

• 当B为偶数：$A\ast B=A\ast (B/2)+A\ast (B/2)$
• 当B为奇数：$A\ast B=A\ast (B/2)+A\ast (B/2)+A$

class Solution {
    // 类快速乘递归
    public int multiply(int A, int B) {
        if (B == 0) return 0;
        if (B == 1) return A;
        return (multiply(A, B >> 1) << 1) + ((B & 1) == 0 ? 0 : A);
    }
}

② 剑指 Offer 65. 不用加减乘除做加法 【位运算】

Ⅰ. 位运算：两数之和 = 无进位和 + 进位 （⭐）

// 递归写法
class Solution {
    // s = a + b = n + c;
    public int add(int a, int b) {
        return b == 0 ? a : add(a ^ b, (a & b) << 1);
    }
}

// 循环写法：通过不断循环迭代进位与非进位和，直到进位为0，就得到了最终的两数加和
// 进位 carry = (a & b) << 1;
// 非进位和 non-carry = a ^ b;
// a + b = carry + non-carry;
class Solution {
    public int add(int a, int b) {
        while(b != 0) { // 直到进位为0，循环才会结束
            int c = (a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;
    }
}

Ⅱ. 库函数：Integer.sum()

严格意义上讲，使用库函数属于作弊行为，Integer.sum()底层使用的还是加法运算符：

class Solution {
    public int add(int a, int b) {
        return Integer.sum(a,b);
    }
}

2. 剑指 Offer II 002. 二进制加法 – P5

相似题目：
[1] AcWing 791. 高精度加法【大整数类加法 A.add(B)】
[2] AcWing 792. 高精度减法【大整数类减法 A.subtract(B)】
[3] AcWing 793. 高精度乘法【大整数类乘法 A.multiply(b)】
[4] AcWing 794. 高精度除法【大整数类除法 A.divide(b) / 大整数类取余 A.mod(b)】

2.1 朴素做法：库函数（BigInteger）

时间复杂度 $O(n+m)$，空间复杂度 $O(1)$

import java.math.*;  // 需要额外引入 math 工具类
class Solution {
    public String addBinary(String a, String b) {
        BigInteger x = new BigInteger(a, 2);
        BigInteger y = new BigInteger(b, 2);
        BigInteger sum = x.add(y);
        String res = sum.toString(2);
        return res;
    }
}

2.2 字符串模拟（StringBuilder）⭐

时间复杂度 $O(n)$，空间复杂度 $O(1)$

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int alen = a.length() - 1;
        int blen = b.length() - 1;

        int carry = 0;  // 初始进位为0
        while (alen >= 0 || blen >= 0) {
            int ai = alen >= 0 ? a.charAt(alen--) - '0' : 0;  // 从最右边出发
            int bi = blen >= 0 ? b.charAt(blen--) - '0' : 0;
            int sum = ai + bi + carry;
            carry = sum >= 2 ? 1 : 0;  // 逢二进一，根据当前位的加和判断进位
            sum = sum >= 2 ? sum-2 : sum;
            sb.append(sum);  // 把当前位的结果记录到 sb 中
        }
        if (carry == 1) sb.append(carry);  // 检查最后一次操作是否产生了进位，如果有则加入
        return sb.reverse().toString();  // 返回反转结果
    }
}

PS : 补充知识1 – 【二进制字符串与整型】

在 Java 语言中，基本的整型数据类型有 byte、short、int、long 四种类型，用于需要不同存储空间的数据使用。（Java中的整型全都是有符号整型，即区分正负号）

• byte：一个 byte 类型整数在内存里占8位，数据范围：-2⁷ ~ 2⁷ -1
• short：一个 short 类型整数在内存里占16位，数据范围：-2¹⁵ ~ 2¹⁵ -1
• int：一个 int 类型整数在内存里占32位，数据范围：-2³¹ ~ 2³¹ -1
• long：一个long类型整数在内存里占64位，数据范围：-2⁶³ ~ 2⁶³ -1

整型与二进制字符串之间的转换方式：

💡 需要注意的是：

• 诸如 valueOf(String,int radix)、parseInt(String,int radix) 、new BigInteger(String, 2) 之类的方法是无法解释二进制的二进制补码(radix = 2)的，如果你想让它解释一个负数，那么就需要加该数的原码前加上一个‘-’号.
• 例如：
  Integer.parseInt(“1011”,2); // 11
  Integer.parseInt(“-1011”,2); // -11

String a = "11010010";
// int
int x = Integer.parseInt(a, 2);  // 将二进制字符串 a 转为 int 型数据
String res = Integer.toBinaryString(x);  // 将 int 型数据转为二进制字符串

// long
long x = Long.parseLong(a, 2);  // 将二进制字符串 a 转为 long 型数据
String res = Long.toBinaryString(x);  // 将 long 型数据转为二进制字符串

// BigInteger
BigInteger x = new BigInteger(a, 2);  // 将将二进制字符串 a 转为BigInteger类对象
String res = x.toString(2);  // 将BigInteger类对象 x 转为二进制字符串
// BigInteger的四则运算
BigInteger num1 = new BigInteger("12345678901234567890");
BigInteger num2 = new BigInteger("98765432109876543210");
BigInteger sum = num1.add(num2);  // 加
BigInteger difference = num1.subtract(num2);  // 减
BigInteger product = num1.multiply(num2);  // 乘
BigInteger quotient = num1.divide(num2);  // 除
BigInteger remainder = num1.mod(num2);  // 取余

实际例子：

// Integer：如果字符串超过 33 位，则不能转化为 Integer
int x = Integer.parseInt(a, 2);
int y = Integer.parseInt(b, 2);
String res = Integer.toBinaryString(x + y);

// Long：如果字符串超过 65 位，则不能转化为 Long
long x = Long.parseLong(a, 2);
long y = Long.parseLong(b, 2);
String res = Long.toBinaryString(x + y);

// BigInteger：如果字符串超过 500000001 位，则不能转化为 BigInteger
BigInteger x = new BigInteger(a, 2);
BigInteger y = new BigInteger(b, 2);
BigInteger sum = x.add(y);
String res = sum.toString(2);

PS : 补充知识2 – 【StringBuilder与StringBuffer的区别】

补充资料：
[1] String、StringBuilder、StringBuffer的区别，优缺点
[2] String、StringBuffer和StringBuilder类的区别

Ⅰ. String 与 StringBuffer 和 StringBuilder

💡 String 与 StringBuffer 和 StringBuilder之间最大的区别在于 底层是否是 final 修饰的 char 数组.

• String：字符串常量，是不可变字符串对象（底层是固定的char数组），这就导致每次对String的操作都会生成新的String对象，这样不仅效率低下，而且大量浪费有限的内存空间。
• StringBuffer 和 StringBuilder 都是字符串变量，其底层也都是char数组，其与String的区别就在于没有被 final 修饰，因此StringBuffer 和 StringBuilder 类的对象能够被多次的修改，并且不产生新的未使用对象。

Ⅱ. StringBuffer 与 StringBuilder的区别

💡 StringBuffer 与 StringBuilder之间最大的区别在于 StringBuffer 对几乎所有的成员方法都使用了 synchronized 关键字 来实现同步，而 StringBuilder 没有实现同步.

• StringBuilder：是为了解决大量拼接字符串时产生很多中间对象问题而提供的一个类. StringBuilder类不是线程安全的，但其在单线程中的性能比StringBuffer高.
• StringBuffer：具备 StringBuilder 的所有特性，唯一加强的是它用于多线程编程时能够保证线程的安全性 【 StringBuffer进行了加锁处理（用synchronized修饰）】.
  

PS : 补充知识3 – 【synchronized 关键字是什】

补充资料：
[1] synchronized关键字详解 - 夏屿 - CSDN博客
[2] synchronized 关键字 - zq231 - 博客园
[3] JMM（Java内存模型）详解 - 渣娃-小晴晴 - CSDN博客 【补充资料2中描述的synchronized 关键字的三个作用正好是 JMM 的三大特性（原子性、可见性、有序性）】
[4] Java关键字synchronized - 哔哩哔哩【图片比较形象】

Ⅰ. synchronized关键字有什么用？

💡synchronized关键字解决的是多线程访问资源的同步性问题。synchronized可以保证被它修饰的方法或者代码块在任意时刻只能有一个线程执行。一旦一个线程尝试获取给定对象的Synchronized锁，则其他线程就不能访问被保护的代码。

当一个方法被 synchronized 关键字修饰时，代表这个方法加锁,相当于不管哪一个线程，运行到这个方法时，都要检查有没有其它线程正在使用这个方法(或者该类的其他同步方法)，如果有的话则需要等待正在使用 synchronized 方法的线程运行完这个方法后再运行该线程，而如果没有的话，则在锁定调用者之后直接运行。

3. 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数 – P6

相似题目：
[1] AcWing 801. 二进制中1的个数【使用的 return x & -x 的方法，每次返回的是 x 中从右数第1个为1的数】

举个例子：x = 5(10) = 0101(2)，那么 -x = 1011(2)，x & -x = 0001(2) = 1(10)

💡 关于 x & -x 可参考：如何理解x&(-x)和x&(x-1) - 一只小阿狗 - 博客园

3.1 朴素做法：库函数（Integer.bitCount()）

时间复杂度 $O(n)$，空间复杂度 $O(1)$

class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n+1];
        for (int i = 0; i <= n; i++) {  // 顺序遍历 0 ~ n
            res[i] = Integer.bitCount(i);  // 返回 i 的二进制形式中1的个数
        }
        return res;
    }
}

Integer.bitCount(i) 底层源码：

运行结果：

3.2 朴素做法：手写位运算

时间复杂度 $O(32\ast n)$，空间复杂度 $O(1)$

// 纯朴素写法，遍历完所有的 32 bit
class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n+1];
        res[0] = 0;  // 0 就是 0，这一步可以不写，因为默认值为0
        for (int i = 1; i <= n; i++) {  // 顺序遍历 1 ~ n
            int cnt = 0;  // 用于记录二进制形式中 1 的个数
            int t = i;
            while (t > 0) {
                if ((t & 1) == 1) cnt++;  // 遇 1 则加1
                t >>= 1;  // 右移 t
            }
            res[i] = cnt;
        }
        return res;
    }
}

// i & (i - 1) 优化：i & (i - 1) 会将i的二进制形式中最右边的1变成0
// 因为时间复杂度从 32 * n 优化成了 i 中1的个数 * n
class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n+1];
        for (int i = 0; i <= n; i++) {
        	int t = i;
        	while (t != 0) {
        		res[i]++;
        		t = t & (t-1);
        	}
        }
        return res;
    }
}

3.3 动规思想：res[i] = res[i & (i-1)] + 1 (⭐)

时间复杂度 $O(n)$，空间复杂度 $O(1)$

根据 i & (i - 1)每次会把当前数的二进制形式最右边的1变为0的规律，我们可以得到如下递推公式：

$$dp\left[i\right]=dp[i\&(i-1\left)\right]+1$$

// 1. i & (i-1)方法，递推公式：
// res[i] = res[i & (i-1)] + 1 
class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n+1];
        for (int i = 1; i <= n; i++) {
            res[i] = res[i & (i-1)] + 1;  // dp 递推公式
        }
        return res;
    }
}

// 2. i /2 方法，递推公式：
// 偶数：res[i] = res[(i/2)]
// 奇数：res[i] = res[(i/2)]+1
// 类似于题目1中相似题目①程序员面试金典(第6版) 08.05. 递归乘法的Ⅲ类快速乘递归解法
class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n+1];
        for (int i = 1; i <= n; i++) {
            res[i] = res[i >> 1] + (i & 1);  // i & 1 == i % 2，用来判断奇偶数
        }
        return res;
    }
}

4. 剑指 Offer II 004. 只出现一次的数字 – P8

补充资料：
[1] 只出现一次的数字（共四种）- 2021dragon的博客 - CSDN博客

相似题目：
[1] LeetCode 136. 只出现一次的数字 – （除一个数字之外，其他数字都出现了两次）【位运算：异或 res ^= num】

[2] LeetCode 260. 只出现一次的数字 III – （除两个数字之外，其他数字都出现了两次）【位运算：分治异或 + lowbit】

[3] LeetCode 540. 排序数组中只出现一次的数字 – （有序数组，除一个数字之外，其他数字都出现了两次，要求$O(logn)$的时间复杂度和$O(1)$的空间复杂度）【奇偶二分：mid 与 mid ^ 1】

[4] 自拟 只出现一次的数字 Ⅳ – （除一个数字之外，其他数字都恰好出现了 k 次）【位运算：按位取模再相加】

[5] 剑指 Offer 03. 数组中重复的数字 – （数组中某些数字是重复的，但不知道有几个数字重复，找出任意一个重复数字）【离散化：原地交换】

4.1 位运算：按位取模（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(1)$

class Solution {
    // 按位取模
    public int singleNumber(int[] nums) {
        // int型数据总共 32 bit
        int[] bitSum = new int[32];  
        
        // 将数组中的所有数字按位相加，记录每一位的个数
        for (int num : nums) {  
            for (int i = 0; i < 32; i++) {
                bitSum[i] += (num >> i) & 1;   
            }
        }
        
        int res = 0;
          // 因为除某个元素外，其它元素都出现了3次，因此只需对位模3，剩下的余数移位相加后就是我们要找的数了
        for (int i = 31; i >= 0; i--) {
            res += (bitSum[i] % 3) << i;
        }
        return res;
    }
}

4.2 哈希表：找value为1的数

时间复杂度 $O(n)$，空间复杂度 $O(n)$

class Solution {
    // 哈希表
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
		// getOrDefault(key, default)
		// 如果存在key, 则返回其对应的value, 否则返回给定的默认值 default
        for (int num : nums) {
            map.put(num, map.getOrDefault(num,0)+1);
        }

        // 遍历哈希
        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            int key = entry.getKey();
            int val = entry.getValue();
            if (val == 1) return key;    
        }
        return -1;
    }
}

PS : 补充知识1 – 【HashMap底层原理】

更多内容可参考：
[1] HashMap（底层实现原理）、红黑树（平衡二叉树）_entry数组和node数组【通俗易懂】

[2] 深入理解JDK8 HashMap-腾讯云开发者社区-腾讯云 【源码解读】

[3] HashMap解读_hashmap bucket - CSDN博客【源码解读】

[4] HashMap初步面试题 - 51CTO博客 【快速背诵】

Ⅰ. HashMap 中的 Bucket（桶）是个什么东西？

💡 如下图所示，bucket 指的是 HashMap 底层数组中的每个元素（这个元素在 1.8 中可能是一个 LinkedList 或者是一个 TreeMap）；在 1.7 中是 Entry 数组，在 1.8 中则是 Node 数组。

因此，这篇博客《还不了解HashMap底层实现原理？看着一篇就够了》中所说的：HashMap使用 key 的 hashcode 确定 bucket 位置，其实指的是确定底层数组的索引位置（也可以称为数组下标）。

Ⅱ. HashMap 中 Entry数组 与 Node数组的区别？

💡 HashMap里面底层数据结构实现是：Entry 数组、Node 数组、链表/红黑树，其中，Node 和 Entry 都是 HashMap 中的内部类，用于表示键值对，两者都含有 key、value、hash、以及 next 属性，底层上 Node<K,V> 和 Entry<K,V> 类都实现了 Map.Entry<K,V> 接口，两者在实现上的区别并不大，仅仅是名称和一些细节上的变化。

Ⅲ. HashMap 的内部数据结构 ⭐

💡 HashMap的内部存储结构其实就是数组与链表的结合（1.8后引入了红黑树，由 $O(n)$ 的时间开销变为了 $O(logn)$）。当对 HashMap 进行实例化操作时（即，new 一个 HashMap），系统会创建一个长度为 Capacity 的 Entry 数组，在这个数组中用来存放元素的位置就被称之为 “桶”，每个桶都有自己的索引，系统可以根据索引快速的查找桶中的元素。每个桶中都存储着一个元素，即一个 Entry 对象，但每一个 Entry 对象都带有一个引用变量，用于指向下一个元素。因此，在一个桶中，就有可能生成一个 Entry 链。所以说 Entry 是 HashMap 的基本组成单元（Entry 是 HashMap 中的一个静态内部类），每一个 Entry 都包含一个 key-value 键值对。

🎈 问题引申1：什么是静态内部类？

• 在一个类中创建另外一个类，叫做成员内部类，这个成员内部类可以静态的（利用static关键字修饰），也可以是非静态的。【总结：静态内部类其实就是被 static 关键字修饰的成员内部类】

……
🎈 问题引申2：静态内部类的使用目的？

• 静态内部类的的创建不依赖于外部类，创建内部类的实例不需要像普通内部类一样先创建外部类实例之后，才能创建自己的实例；但同时静态内部类它也不能像普通内部类一样无限制的访问外部类的方法和成员变量，只能访问静态成员变量和静态方法。
• 因此，静态内部类的使用场景是：当外部类需要使用内部类，而内部类无需外部类资源，并且内部类可以单独创建的时候会考虑采用静态内部类的设计，例如：用于程序的代码测试（主方法：public static void main(String[] args)）。
• Note：在 Java 中，如果一个类要被声明为 static 的，只有一种情况，就是静态内部类。如果在外部类声明为 static，程序则会编译不通过。

……
参考：
[1] Java内部类——静态内部类 - 哔哩哔哩
[2] Java静态类 - Facilitate - 博客园

PS : 补充知识2 – 【Map集合中的遍历方式】

Map的遍历大体有3种：

1. 遍历 Map.entrySet()：它的每一个元素都是 Map.Entry 对象，这个对象中，放着的就是 Map 中的某一对key-value；
2. 遍历Map.keySet()：它是 Map 中 key 值的集合，我们可以通过遍历这个集合来读取 Map 中的元素；
3. 遍历Map.values()：它是 Map 中 value 的集合，我们可以直接通过这个集合遍历 Map 中的值，却不能读取 key。

PS : 补充知识3 – 【ConcurrentHashMap 实现原理】

补充资料：
[1] ConcurrentHashMap实现原理
[2] ConcurrentHashMap原理详解
[3] ConcurrentHashMap的实现原理
[4] 深入浅出ConcurrentHashMap详解
[5] Java中synchronized和volatile有什么区别？

Ⅰ. ConcurrentHashMap和HashMap以及Hashtable的区别

• HashMap是非线程安全的，因为在HashMap中的操作都没有加锁，因此在多线程环境下容易导致数据覆盖之类的问题（比如经典的扩容并发问题，在put操作时，易出现死循环，即：链表会形成环形 (next元素指向前一个元素) )；
• 而HashTable与ConcurrentHashMap都属于是线程安全的，区别在于HashTable只是单纯的在成员方法上添加了synchronized关键字，这样做的话，虽然安全，但是效率低下；
• ConcurrentHashMap做的就并非锁住整个方法，而是通过原子操作和局部加锁的方法保证了多线程的线程安全，且尽可能减少了性能损耗.

Ⅱ. ConcurrentHashMap的原理 ⭐

• 1.7版本中的 ConcurrentHashMap 采用的是分段锁的技术实现的高效的并发操作，它是由一个Segment数组和多个HashEntry数组组成的（Segment数组的意义就是将一个大的table分成很多小table来进行加锁，每一个Segment元素存储的是HashEntry数组+链表）。它不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel（Segment 数组数量）级别的线程并发。每当一个线程持有锁访问一个 Segment 时，不会影响到其它的 Segment。
• 1.8版本中的 ConcurrentHashMap 是通过 synchronized 和 CAS 操作来保证并发的安全性，采用的是 Node数组 + 链表/红黑树的形式，采用红黑树之后可以保证查询效率 $O(logn)$，另外它还取消了 1.7 中的 ReentrantLock，改为了 synchronized进行加锁。

🎈 问题引申1：volatile 和 synchronized 的区别？

• volatile 关键字是线程同步的轻量级实现，所以 volatile 的性能要比 synchronized 的好一些；

1. 作用的位置不同：volatile 是修饰变量，而synchronized 则是修饰方法和代码块；
2. 作用不同：

• synchronized，可以保证变量修改的可见性和原子性，但可能会造成线程的阻塞；（synchronized在锁释放的时候会将数据写入主存，以此保证可见性）
• 而 volatile 仅能实现变量修改的可见性，无法保证原子性，但其不会造成线程的阻塞；（volatile修饰变量后，每次读取都是去主存进行读取，以此保证可见性）
  ……

【总结：因此，volatile 关键字解决的是变量在多线程之间的可见性；而 synchronized 关键字解决的是多线程之间访问公共资源的同步性】

……
🎈 问题引申2：synchronized锁的到底是什么？（八锁问题及扩展）

1. 当 synchronized 修饰普通方法时，锁的是方法的调用者，也就是对象；
2. 当 synchronized 修饰静态方法时，锁的是当前类的 class 对象；
3. 当 synchronized 修饰代码块时，可以设置为锁对象，或者锁引用类型的变量或常量.

……
补充资料：

• 所谓的JUC的“八锁”问题（synchronized的灵活使用） - 知乎
• 经典8锁问题–助你彻底搞懂锁的概念 - 叁有三分之一 - 博客园【八锁代码示例】

……
🎈 问题引申3：并发编程三大特性（原子性、可见性、有序性）

1. 原子性：一个或多个操作，要么全部执行，要么全部不执行（执行的过程中是不会被任何因素打断的）；
2. 可见性：只要有一个线程对共享变量的值进行了修改，其他线程都将马上收到通知，并立即获得最新值。
3. 有序性：程序执行代码指令的顺序应当保证按照程序指定的顺序执行，即便是编译优化（指令重排），也应当保证程序源语一致。

……
补充资料：

• 浅谈JMM和并发三大特性(volatile、MESI、内存屏障) - 掘金【三大特性解释】
• 并发编程深入理解JMM&并发三大特性 - 余明星 - 博客园【JMM 内存交互的八大操作】

PS : 相似题目

① LeetCode 260. 只出现一次的数字 III 【位运算】

只有两个数字出现过一次，其他数字都出现了两次

该题解法和 只出现一次的数字Ⅱ 基本一致，都是 哈希表 和 位运算 的方法.

Ⅰ. 哈希表：找value为1的数

时间复杂度 $O(n)$，空间复杂度 $O(n)$

class Solution {
    // 哈希表：同只出现一次数字Ⅱ
    public int[] singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            map.put(num, map.getOrDefault(num,0)+1);
        }

        List<Integer> list = new ArrayList<>();
        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            int key = entry.getKey();
            int value = entry.getValue();

            if (value == 1) list.add(key);
        }
        
        // Java中没有直接将ArrayList转成int数组的库函数，但是我们可以通过Stream流来简化操作
        // 要不然就是手写循环
        return list.stream().mapToInt(Integer::intValue).toArray();  
    }
}

Ⅱ. 位运算：分治异或 + lowbit （⭐）

时间复杂度 $O(n)$，空间复杂度 $O(1)$

class Solution {
    // 位运算：分治异或 + lowbit
    public int[] singleNumber(int[] nums) {
        int x = 0;
        for (int num : nums) {
            x ^= num;
        }
        // 使用lowbit，找出二进制位最右边1的数作为标记值
        int mark = x & -x;
        // 根据 mark 将数组分成两组，然后分别再进行异或即可
        int[] res = new int[2];
        for (int num : nums) {
            if ((num & mark) == 0) {
                res[0] ^= num;
            } else res[1] ^= num;
        }
        return res;
    }
}

② LeetCode 540. 排序数组中只出现一次的数字【2022.05.18 字节一面】

Ⅰ. 二分：全数组二分 （⭐）

时间复杂度 $O(logn)$，空间复杂度 $O(1)$

因为是排序数组，所以如上图所示，数组中相同的元素一定相邻（如果排序数组中所有的元素都是两两对应的，那么奇数索引的元素一定与索引减1的元素相等；同理，偶数索引的元素也一定与其索引加1的元素相等）.
……
因此，我们就可以通过二分查找来根据 mid 的奇偶性决定和左边或右边的相邻元素比较：

• 如果 mid 是奇数，比较 mid 和 mid - 1 是否相同；
• 如果 mid 是偶数，比较 mid 和 mid + 1 是否相同；

……
值得一提的是：利用按位异或的性质，可得

• $当mid是奇数时，mid-1=mid\oplus 1$
• $当mid是偶数时，mid+1=mid\oplus 1$

因此，对于 mid 的奇偶索引比较，就通过比较 nums[mid] 和 nums[mid^1] 来简化代码.

class Solution {
    // 1. 全数组的二分查找：排序后的奇偶规律
    public int singleNonDuplicate(int[] nums) {
        int l = 0, r = nums.length-1;

        while (l < r) {
            int mid = l + r >> 1;
            // 奇偶处理
            System.out.println(mid);
            if (nums[mid] != nums[mid ^ 1]) r = mid;
            else l = mid + 1;
        }
        return nums[l];
    }
}

// 2. 偶数下标的二分查找
// 优化方式：由于只出现一次的元素所在下标 x 的左边有偶数个元素，
// 因此下标 x 一定是偶数，所以我们可以把二分查找范围缩小到偶数下标范围内.
class Solution {
    // 偶数下标的二分查找
    public int singleNonDuplicate(int[] nums) {
        int l = 0, r = nums.length-1;
        while (l < r) {
            int mid = l + r >> 1;
            mid -= mid & 1;  // 判断 mid 的奇偶，如果是奇数，则减1，变成偶数
            if (nums[mid] != nums[mid+1]) r = mid;
            else l = mid + 2;
        }
        return nums[l];
    }
}

③ 自拟 只出现一次的数字 Ⅳ【位运算】

已知 array 中只有 1 个数出现一次，其他的数都出现 k 次，请返回只出现了 1 次的数。
……
同时，题目还可以这样出：已知数组中只有一个数字出现了 m 次，其他数字都出现 n 次，请找出那个唯一出现 m 次的数字，假设 m 不能被 n 整除。

• m 不能被 n 整除：意为 m % n 依旧等于 m；基于此，不管这个唯一的数字是出现了 1 次，还是 m 次，都没有关系，只要 m ≠ n 即可，解题方法都是一样的（按位取模后相加）

Ⅰ. 位运算：不开数组版按位取模再相加（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(1)$

class Solution {
    public int singleNumber(int[] nums) {
        int k = 3, res = 0;  // k 代表其余元素出现了 k 次
        for (int i = 0; i < 32; i++) {
            int bit = 0;
            for (int num : nums) {
                bit += num >> i & 1;
            }
            res += (bit % k) << i;
        }
        return res;
    }
}

④ 剑指 Offer 03. 数组中重复的数字【离散化】

Ⅰ. 快排：顺序查找（也可以用哈希表来判重）

时间复杂度 $O(n)$，空间复杂度 $O(1)$

class Solution {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);  // 库函数排序 O(nlogn)
        for (int i = 0; i < nums.length-1; i++) {  // O(n)
            if (nums[i] == nums[i+1]) return nums[i];
        }
        return -1;
    }
}

Ⅱ. 离散化：原地交换 (⭐)

时间复杂度 $O(n)$，空间复杂度 $O(1)$

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            if(nums[i] == i) {  // 值与下标索引对应后，移动到下一位置
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i]) return nums[i];  // 发现重复数字
            // swap 交换过程：交换nums[i] 与 nums[num[i]]，直到与下标索引一致
            int tmp = nums[i];  
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }
        return -1;
    }
}

5. 剑指 Offer II 005. 单词长度的最大乘积 – P10

5.1 哈希表：数组模拟

时间复杂度 $O(nk+26n^2)$，空间复杂度 $O(26n)$

class Solution {
    // 找出数组中的两个不同的字符串
    // 1. 哈希表：二维数组
    public int maxProduct(String[] words) {
        int n = words.length, res = 0;
        boolean[][] flags = new boolean[n][26];

        // 初始化二维数组 O(nk)
        for (int i = 0; i < n; i++) {
            for (char c : words[i].toCharArray()) {
                flags[i][c-'a'] = true;
            }
        } 
        // 开始比较数组中各字符串是否含有相同字符 O(26n^2)
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int k = 0;
                // 按位比较是否相同
                while (k < 26) {
                    if (flags[i][k] && flags[j][k]) break;
                    k++;
                }
                // 循环结束，没有相同，说明找到了两个完全不同的字符串
                if (k == 26) {
                    int prod = words[i].length() * words[j].length();
                    res = Math.max(res, prod);  // 特别注意：返回乘积的最大值
                }
            }
        }
        return res;
    }
} 

5.2 位运算：一维数组（⭐）

时间复杂度 $O(nk+26n^2)$，空间复杂度 $O(n)$

该题解相当于是对 5.1 题解的进一步升级，将 boolean 类型的二维数组 改成了 int 类型的 一维数组（这是因为boolean类型其实也是只有两个状态，true 和 false，这就很像二进制的形式，恰好英文小写字母的数量是26个，而一个 int 型的数字是 32 位，所以说我们用一个 int 类型的数字就可以表示一个字符串了），具体形式可见题目开头的展示图片.

class Solution {
    // 找出数组中的两个不同的字符串
    // 2. 位运算：一维数组
    public int maxProduct(String[] words) {
        int n = words.length, res = 0;
        int[] flags = new int[n];

        // 初始化一维数组，数组中每个元素存储的是对应下标的字符串按序转成的2进制形式（去重）
        for (int i = 0; i < n; i++) {
            for (char c : words[i].toCharArray()) {
                flags[i] |= 1 << (c - 'a');  // 我们只需要确定某个字符是否存在即可，不需要考虑重复的问题，因此用的是 |
            }
        }
        // 找出完全不同的两个字符串：(flags[i] & flags[j]) == 0
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if ((flags[i] & flags[j]) == 0) res = Math.max(res, words[i].length() * words[j].length());
            }
        }
        return res;
    }
} 

// 使用哈希表进行代码优化：用「哈希表」代替 flags 数组
// 但是实际上的执行速度没有纯位运算的要快
class Solution {
    public int maxProduct(String[] words) {
        Map<Integer, Integer> map = new HashMap<>();
        for (String w : words) {
            int t = 0, m = w.length();
            for (int i = 0; i < m; i++) {
                int u = w.charAt(i) - 'a';
                t |= (1 << u);
            }
            if (!map.containsKey(t) || map.get(t) < m) map.put(t, m);
        }
        // 最后哈希表中剩下的就全都是不同的字符串
        int ans = 0;
        for (int a : map.keySet()) {  
            for (int b : map.keySet()) {
                if ((a & b) == 0) ans = Math.max(ans, map.get(a) * map.get(b));
            }
        }
        return ans;
    }
}

6. 继续提升：加练题目

可参考：
[1] 【宫水三叶】简单位运算模拟题
[2] 模拟 · SharingSource/LogicStack-LeetCode Wiki
[3] 位运算 · SharingSource/LogicStack-LeetCode Wiki文章来源地址https://www.toymoban.com/news/detail-618080.html

到了这里，关于【LeetCode】剑指 Offer Ⅱ 第1章：整数（5道题） -- Java Version的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！