北京网站建设软件,石家庄哪家公司做网络推广好,汉服设计制作培训,做网站的实施过程题库链接#xff1a;https://leetcode.cn/problem-list/e8X3pBZi/ 题目解决方案剑指 Offer II 001. 整数除法快速除 ⭐剑指 Offer II 002. 二进制加法模拟#xff1a;StringBuilder ⭐剑指 Offer II 003. 前 n 个数字二进制中 1 的个数动规#xff1a;res[i] res[i (…题库链接https://leetcode.cn/problem-list/e8X3pBZi/ 题目解决方案剑指 Offer II 001. 整数除法快速除 ⭐剑指 Offer II 002. 二进制加法模拟StringBuilder ⭐剑指 Offer II 003. 前 n 个数字二进制中 1 的个数动规res[i] res[i (i-1)] 1 ⭐剑指 Offer II 004. 只出现一次的数字位运算按位取模 ⭐剑指 Offer II 005. 单词长度的最大乘积位运算 模拟 ⭐ 1. 剑指 Offer II 001. 整数除法 – P1 相似题目 [1] 程序员面试金典(第6版) 08.05. 递归乘法【不使用 * 运算符 实现两个正整数的相乘快速乘】
[2] 剑指 Offer 65. 不用加减乘除做加法 【位运算】
[3] AcWing 875. 快速幂 【模板题】
[4] AcWing 876. 快速幂求逆元 【若 p 为质数则 a 的逆元即为 ap-2】
1.1 整活版a/b
时间复杂度 O ( 1 ) O(1) O(1)空间复杂度 O ( 1 ) 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 ( l o g n ) O(logn) O(logn)空间复杂度 O ( n ) O(n) O(n)
类似于快速幂的思想将被除数拆成除数的倍次形式例如 a15, b2 就可以被拆为15 23 22 21 20 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 m o d c a^{b} \ \ mod \ \ c ab mod c
例如a156, 而 156(10) 1001 1100(2) 那么
我们就按照这个公式来求解 a156原来要进行 156-1155 次乘法运算现在的差不多运算次数就是他 二进制的长度二进制中1的个数8424次.
快速幂的原理就是需要我们先不断的降低ab的规模然后再进行计算
降低a的规模只要让 a变成a*a降低b的规模如果b是偶数那么每次aa*a之后bb/2; 如果b是奇数那么我们就先把这个多出来的数先挑出来然后再用偶数的处理方法.
快速幂模板
// C形式
long long quickpow(long long base,long long power){long long ret1;while(power){if(power 1) ret ret * base;base base * base;power1;}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 ∗ N % P M*N \ \% \ P M∗N % P 时为了避免溢出我们常常采用的方法是利用分配律将式子转换为 ( M % P ) ∗ ( N % P ) % P (M\%P)∗(N\%P)\%P (M%P)∗(N%P)%P因为一个值模P后其范围为0到P-1只要P*P不超过数据上限即可。但是如果P的值在 1018 这个级别那显然这种做法还是会爆数据上限。
而用快速乘法可以避免这个烦恼就像快速幂本质上是乘法并利用二进制思想减少运算次数。快速乘法本质上是加法并利用了二进制思想来减少运算次数。因为本质是在做加法运算所以只要PP不超过数据上限即可。
实际例子
以 13 ∗ 27 13*27 13∗27 为例 乘法的本质是加法13*27可以转化为27个13相加或13个27相加
将27转化为二进制 式子即可转化为 快速乘模板 和快速幂大同小异只需要修改符号即可将乘法换为加法
// C形式
long long quickmul(long long a,long long b){long long ret0;while(b){if(b%2) retreta;aaa;b/2;}return ret;
}③ 快速乘与快速幂结合
在计算快速幂时需要用到乘法在取模对象P很大时乘法就会爆数据上限所以需要同时使用快速幂和快速乘法
long long quickmul(long long a,long long b){long long ret0;while(b){if(b%2) ret(reta)%p;a(aa)%p;b/2;}return ret;
}
// key将快速幂中的乘法运算用快速幂来替代
long long quickpow(long long base,long long power){long long ret1;while(power){if(power%2) retquickmul(ret,base)%p;basequickmul(base,base)%p;power/2;}return ret;
}PS : 补充知识2 – 【Java运算符优先级】 赋值运算符包括 、、-、*、/、%、|、^、~、、、 更多细节可参考Java语言中运算符号优先级
PS : 相似题目
① 程序员面试金典(第6版) 08.05. 递归乘法 【快速乘】
Ⅰ. 快速乘循环实现时间复杂度 O ( l o g n ) O(logn) O(logn)空间复杂度 O ( 1 ) O(1) 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(n) O(n)空间复杂度 O ( 1 ) O(1) 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 ( l o g n ) O(logn) O(logn)空间复杂度 O ( 1 ) O(1) O(1)
根据乘法的性质可知 A ∗ B A ∗ ( B / 2 ) ∗ 2 A ∗ ( B / 2 ) A ∗ ( B / 2 ) A * B A * (B/2) * 2 A * (B/2) A * (B/2) A∗BA∗(B/2)∗2A∗(B/2)A∗(B/2)则
当B为偶数 A ∗ B A ∗ ( B / 2 ) A ∗ ( B / 2 ) A * B A * (B/2) A * (B/2) A∗BA∗(B/2)A∗(B/2)当B为奇数 A ∗ B A ∗ ( B / 2 ) A ∗ ( B / 2 ) A A * B A * (B/2) A * (B/2) A A∗BA∗(B/2)A∗(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(nm) O(nm)空间复杂度 O ( 1 ) O(1) 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(n) O(n)空间复杂度 O ( 1 ) O(1) 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; // 初始进位为0while (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位数据范围-27 ~ 27 -1short一个 short 类型整数在内存里占16位数据范围-215 ~ 215 -1int一个 int 类型整数在内存里占32位数据范围-231 ~ 231 -1long一个long类型整数在内存里占64位数据范围-263 ~ 263 -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] JMMJava内存模型详解 - 渣娃-小晴晴 - 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(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
class Solution {public int[] countBits(int n) {int[] res new int[n1];for (int i 0; i n; i) { // 顺序遍历 0 ~ nres[i] Integer.bitCount(i); // 返回 i 的二进制形式中1的个数}return res;}
}Integer.bitCount(i) 底层源码
运行结果
3.2 朴素做法手写位运算
时间复杂度 O ( 32 ∗ n ) O(32*n) O(32∗n)空间复杂度 O ( 1 ) O(1) O(1)
// 纯朴素写法遍历完所有的 32 bit
class Solution {public int[] countBits(int n) {int[] res new int[n1];res[0] 0; // 0 就是 0这一步可以不写因为默认值为0for (int i 1; i n; i) { // 顺序遍历 1 ~ nint cnt 0; // 用于记录二进制形式中 1 的个数int t i;while (t 0) {if ((t 1) 1) cnt; // 遇 1 则加1t 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[n1];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(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
根据 i (i - 1)每次会把当前数的二进制形式最右边的1变为0的规律我们可以得到如下递推公式 d p [ i ] d p [ i ( i − 1 ) ] 1 dp\big[i \big] dp\big[ i \ \big( i-1\big)\big]1 dp[i]dp[i(i−1)]1
// 1. i (i-1)方法递推公式
// res[i] res[i (i-1)] 1
class Solution {public int[] countBits(int n) {int[] res new int[n1];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[n1];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 ( l o g n ) O(logn) O(logn)的时间复杂度和 O ( 1 ) O(1) O(1)的空间复杂度【奇偶二分mid 与 mid ^ 1】
[4] 自拟 只出现一次的数字 Ⅳ – 除一个数字之外其他数字都恰好出现了 k 次【位运算按位取模再相加】
[5] 剑指 Offer 03. 数组中重复的数字 – 数组中某些数字是重复的但不知道有几个数字重复找出任意一个重复数字【离散化原地交换】
4.1 位运算按位取模⭐
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
class Solution {// 按位取模public int singleNumber(int[] nums) {// int型数据总共 32 bitint[] 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) O(n)空间复杂度 O ( n ) O(n) O(n)
class Solution {// 哈希表public int singleNumber(int[] nums) {MapInteger, Integer map new HashMap();// getOrDefault(key, default)// 如果存在key, 则返回其对应的value, 否则返回给定的默认值 defaultfor (int num : nums) {map.put(num, map.getOrDefault(num,0)1);}// 遍历哈希for (Map.EntryInteger,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 属性底层上 NodeK,V 和 EntryK,V 类都实现了 Map.EntryK,V 接口两者在实现上的区别并不大仅仅是名称和一些细节上的变化。 Ⅲ. HashMap 的内部数据结构 ⭐ HashMap的内部存储结构其实就是数组与链表的结合1.8后引入了红黑树由 O ( n ) O(n) O(n) 的时间开销变为了 O ( l o g n ) O(logn) 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种
遍历 Map.entrySet()它的每一个元素都是 Map.Entry 对象这个对象中放着的就是 Map 中的某一对key-value遍历Map.keySet()它是 Map 中 key 值的集合我们可以通过遍历这个集合来读取 Map 中的元素遍历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 支持 CurrencyLevelSegment 数组数量级别的线程并发。每当一个线程持有锁访问一个 Segment 时不会影响到其它的 Segment。1.8版本中的 ConcurrentHashMap 是通过 synchronized 和 CAS 操作来保证并发的安全性采用的是 Node数组 链表/红黑树的形式采用红黑树之后可以保证查询效率 O ( l o g n ) O(logn) O(logn)另外它还取消了 1.7 中的 ReentrantLock改为了 synchronized进行加锁。 问题引申1volatile 和 synchronized 的区别 volatile 关键字是线程同步的轻量级实现所以 volatile 的性能要比 synchronized 的好一些 作用的位置不同volatile 是修饰变量而synchronized 则是修饰方法和代码块作用不同 synchronized可以保证变量修改的可见性和原子性但可能会造成线程的阻塞synchronized在锁释放的时候会将数据写入主存以此保证可见性而 volatile 仅能实现变量修改的可见性无法保证原子性但其不会造成线程的阻塞volatile修饰变量后每次读取都是去主存进行读取以此保证可见性 …… 【总结因此volatile 关键字解决的是变量在多线程之间的可见性而 synchronized 关键字解决的是多线程之间访问公共资源的同步性】 …… 问题引申2synchronized锁的到底是什么八锁问题及扩展 当 synchronized 修饰普通方法时锁的是方法的调用者也就是对象当 synchronized 修饰静态方法时锁的是当前类的 class 对象当 synchronized 修饰代码块时可以设置为锁对象或者锁引用类型的变量或常量. …… 补充资料 所谓的JUC的“八锁”问题synchronized的灵活使用 - 知乎经典8锁问题–助你彻底搞懂锁的概念 - 叁有三分之一 - 博客园【八锁代码示例】 …… 问题引申3并发编程三大特性原子性、可见性、有序性 原子性一个或多个操作要么全部执行要么全部不执行执行的过程中是不会被任何因素打断的可见性只要有一个线程对共享变量的值进行了修改其他线程都将马上收到通知并立即获得最新值。有序性程序执行代码指令的顺序应当保证按照程序指定的顺序执行即便是编译优化指令重排也应当保证程序源语一致。 …… 补充资料 浅谈JMM和并发三大特性(volatile、MESI、内存屏障) - 掘金【三大特性解释】并发编程深入理解JMM并发三大特性 - 余明星 - 博客园【JMM 内存交互的八大操作】 PS : 相似题目
① LeetCode 260. 只出现一次的数字 III 【位运算】 只有两个数字出现过一次其他数字都出现了两次 该题解法和 只出现一次的数字Ⅱ 基本一致都是 哈希表 和 位运算 的方法.
Ⅰ. 哈希表找value为1的数
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n)
class Solution {// 哈希表同只出现一次数字Ⅱpublic int[] singleNumber(int[] nums) {MapInteger, Integer map new HashMap();for (int num : nums) {map.put(num, map.getOrDefault(num,0)1);}ListInteger list new ArrayList();for (Map.EntryInteger,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(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
class Solution {// 位运算分治异或 lowbitpublic 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 ( l o g n ) O(logn) O(logn)空间复杂度 O ( 1 ) O(1) O(1) 因为是排序数组所以如上图所示数组中相同的元素一定相邻如果排序数组中所有的元素都是两两对应的那么奇数索引的元素一定与索引减1的元素相等同理偶数索引的元素也一定与其索引加1的元素相等. …… 因此我们就可以通过二分查找来根据 mid 的奇偶性决定和左边或右边的相邻元素比较 如果 mid 是奇数比较 mid 和 mid - 1 是否相同如果 mid 是偶数比较 mid 和 mid 1 是否相同 …… 值得一提的是利用按位异或的性质可得 当 m i d 是奇数时 m i d − 1 m i d ⊕ 1 当 \ mid \ 是奇数时 mid -1 mid ⊕ 1 当 mid 是奇数时mid−1mid⊕1 当 m i d 是偶数时 m i d 1 m i d ⊕ 1 当 \ mid \ 是偶数时 mid 1 mid ⊕ 1 当 mid 是偶数时mid1mid⊕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[mid1]) 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(n) O(n)空间复杂度 O ( 1 ) O(1) 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(n) O(n)空间复杂度 O ( 1 ) O(1) 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[i1]) return nums[i];}return -1;}
}Ⅱ. 离散化原地交换 (⭐)
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) 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 ( n k 26 n 2 ) O(nk 26n^2) O(nk26n2)空间复杂度 O ( 26 n ) O(26n) 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 ( n k 26 n 2 ) O(nk 26n^2) O(nk26n2)空间复杂度 O ( n ) O(n) 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]) 0for (int i 0; i n; i) {for (int j i1; 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) {MapInteger, 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
文章转载自： http://www.morning.bfgbz.cn.gov.cn.bfgbz.cn http://www.morning.ffhlh.cn.gov.cn.ffhlh.cn http://www.morning.zpqbh.cn.gov.cn.zpqbh.cn http://www.morning.mhmsn.cn.gov.cn.mhmsn.cn http://www.morning.lgmty.cn.gov.cn.lgmty.cn http://www.morning.zpnfc.cn.gov.cn.zpnfc.cn http://www.morning.nrcbx.cn.gov.cn.nrcbx.cn http://www.morning.gqfks.cn.gov.cn.gqfks.cn http://www.morning.tfpbm.cn.gov.cn.tfpbm.cn http://www.morning.xnkb.cn.gov.cn.xnkb.cn http://www.morning.rbknf.cn.gov.cn.rbknf.cn http://www.morning.dswtz.cn.gov.cn.dswtz.cn http://www.morning.smcfk.cn.gov.cn.smcfk.cn http://www.morning.gnlyq.cn.gov.cn.gnlyq.cn http://www.morning.stmkm.cn.gov.cn.stmkm.cn http://www.morning.hbhnh.cn.gov.cn.hbhnh.cn http://www.morning.ckdgj.cn.gov.cn.ckdgj.cn http://www.morning.tcsdlbt.cn.gov.cn.tcsdlbt.cn http://www.morning.bnpcq.cn.gov.cn.bnpcq.cn http://www.morning.bxczt.cn.gov.cn.bxczt.cn http://www.morning.btpll.cn.gov.cn.btpll.cn http://www.morning.rppf.cn.gov.cn.rppf.cn http://www.morning.xgjhy.cn.gov.cn.xgjhy.cn http://www.morning.thbkc.cn.gov.cn.thbkc.cn http://www.morning.tfbpz.cn.gov.cn.tfbpz.cn http://www.morning.ktmpw.cn.gov.cn.ktmpw.cn http://www.morning.bdypl.cn.gov.cn.bdypl.cn http://www.morning.fywqr.cn.gov.cn.fywqr.cn http://www.morning.tdzxy.cn.gov.cn.tdzxy.cn http://www.morning.hqpyt.cn.gov.cn.hqpyt.cn http://www.morning.qgjgsds.com.cn.gov.cn.qgjgsds.com.cn http://www.morning.mpxbl.cn.gov.cn.mpxbl.cn http://www.morning.wlggr.cn.gov.cn.wlggr.cn http://www.morning.kyytt.cn.gov.cn.kyytt.cn http://www.morning.wnkbf.cn.gov.cn.wnkbf.cn http://www.morning.eviap.com.gov.cn.eviap.com http://www.morning.xnqjs.cn.gov.cn.xnqjs.cn http://www.morning.sogou66.cn.gov.cn.sogou66.cn http://www.morning.kpygy.cn.gov.cn.kpygy.cn http://www.morning.fjtnh.cn.gov.cn.fjtnh.cn http://www.morning.ccsdx.cn.gov.cn.ccsdx.cn http://www.morning.hqgkx.cn.gov.cn.hqgkx.cn http://www.morning.fxwkl.cn.gov.cn.fxwkl.cn http://www.morning.hrpbq.cn.gov.cn.hrpbq.cn http://www.morning.lqpzb.cn.gov.cn.lqpzb.cn http://www.morning.nmtyx.cn.gov.cn.nmtyx.cn http://www.morning.dtnjr.cn.gov.cn.dtnjr.cn http://www.morning.hxxzp.cn.gov.cn.hxxzp.cn http://www.morning.mpwgs.cn.gov.cn.mpwgs.cn http://www.morning.xnqwk.cn.gov.cn.xnqwk.cn http://www.morning.lwnwl.cn.gov.cn.lwnwl.cn http://www.morning.jncxr.cn.gov.cn.jncxr.cn http://www.morning.htrzp.cn.gov.cn.htrzp.cn http://www.morning.gjlml.cn.gov.cn.gjlml.cn http://www.morning.qsmmq.cn.gov.cn.qsmmq.cn http://www.morning.wrdlf.cn.gov.cn.wrdlf.cn http://www.morning.lxwjx.cn.gov.cn.lxwjx.cn http://www.morning.cpkcq.cn.gov.cn.cpkcq.cn http://www.morning.fglth.cn.gov.cn.fglth.cn http://www.morning.nlglm.cn.gov.cn.nlglm.cn http://www.morning.dwhnb.cn.gov.cn.dwhnb.cn http://www.morning.wtcd.cn.gov.cn.wtcd.cn http://www.morning.gybnk.cn.gov.cn.gybnk.cn http://www.morning.xphls.cn.gov.cn.xphls.cn http://www.morning.jlgjn.cn.gov.cn.jlgjn.cn http://www.morning.ppzgr.cn.gov.cn.ppzgr.cn http://www.morning.mghgl.cn.gov.cn.mghgl.cn http://www.morning.qsxxl.cn.gov.cn.qsxxl.cn http://www.morning.pkmcr.cn.gov.cn.pkmcr.cn http://www.morning.rwpjq.cn.gov.cn.rwpjq.cn http://www.morning.znlhc.cn.gov.cn.znlhc.cn http://www.morning.rwlsr.cn.gov.cn.rwlsr.cn http://www.morning.zhnpj.cn.gov.cn.zhnpj.cn http://www.morning.zcxjg.cn.gov.cn.zcxjg.cn http://www.morning.hgwsj.cn.gov.cn.hgwsj.cn http://www.morning.zhqfn.cn.gov.cn.zhqfn.cn http://www.morning.yrwqz.cn.gov.cn.yrwqz.cn http://www.morning.drjll.cn.gov.cn.drjll.cn http://www.morning.xllrf.cn.gov.cn.xllrf.cn http://www.morning.gbhsz.cn.gov.cn.gbhsz.cn
