目前刷了一遍代码随想录，跟着剑指再总结一下之前做过的题，参考代码随想录、剑指Offer、力扣，如有侵权，联系删除
整数&位运算
理论基础
整数
- JAVA有4中不同的整数类型，每种类型的范围不同（有符号整数）
| 类型 | 位数 | 范围 |
| byte | 4 | -23~23-1 |
| short | 8 | -27~27-1 |
| int | 16 | -215~215-1 |
| long | 32 | -231~231-1 |
- 溢出现象：计算结果超出了整数范围，出现意料之外的结果
。（-231）/（-1）
。-（-231）
二进制
- 二进制运算
。非（~）
。与（&）
。或（|）
。异或（^）
。左移（m<<n）：将m左移n位，最左边的n位将被丢弃，同时在最右边补上n个0
00001010 << 2 = 00101000
。右移（m>>n）：将m右移n位，最右边的n位将被丢弃，同时在最左边补上n个0（无符号数）or补上n个符号位（有符号数）
// 以8为有符号数值为例 byte 00001010 >> 2 = 00000010 10001010 >> 3 = 11110001
。Java中新增的无符号右移位操作符 >>>：最左边均进行补零
00001010 >>> 2 = 00000010 10001010 >>> 3 = 00010001
位运算
- i & (i-1)
将整数i的最右边的1变成0
- i>>1
将i右移1位，相当于计算i/2
- i & 1
将i的最低位和1进行与运算，相当于i%2
- 位运算比除法和求余运算更高效
- 异或
任何一个数字异或它自己的结果都是0
- num = num >>> 1
获取num所有未的值
- n = num & 1
获取二进制num的最低位（最右位）
- (num >> (31-i)) & 1
获取二进制num从左数其第i个数位
- 实现反转字符串
- 状态压缩
。状态压缩：一个维度能表示所有物品的状态情况
。n件物品，每个物品有2个状态（状态1和状态2），那么可以用n位2进制表示物品的状态
- 第k位为1时，表示第k件物品的状态为状态1
- 第k位为0时，表示第k件物品的状态为状态2
。比如
- LC864中可用一个int类型二进制代表当前收集到钥匙的情况
- 背包问题中每件物品放或不放的情况
。状态检测：(state >> k) & 1
- 返回1说明第k位为1
- 返回0说明第k位为0
。状态更新：state |= 1 << k
- 将 state 的第 k位设置为 1
1.两数相除【LC29】
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/divide-two-integers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2022/10/11
注意：将负数转换为整数，可能会发生溢出！！！
题解
- 使用变量isPos记录商的正负号
- 将被除数和除数转化为负数
- 当被除数小于除数时，不断减去除数，res++
- 最后调整正负号
- 代码
class Solution { public int divide(int dividend, int divisor) { // 特殊情况 if (dividend == 0){ return 0; } if (divisor == 1){ return dividend; } // 处理溢出情况 if (dividend == Integer.MIN_VALUE && divisor == -1){ return Integer.MAX_VALUE; } int res = 0; boolean isPos = false; if ( ( dividend < 0 && divisor < 0 ) || (dividend > 0 && divisor > 0)){ isPos = true; } if (dividend > 0){ dividend = -dividend; } if (divisor > 0){ divisor = -divisor; } while (dividend <= divisor ){ res++; dividend -= divisor; } return isPos ? res : -res; } }
。复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(1)
- 优化：减除数的两倍、四倍……，结果res+2，+4
防止溢出，d需要大于最小值的一半，0x8000000为最小的int型整数（-231），0xc000000为-230，-1e9=10003≈1024≈-230
class Solution { public int divide(int dividend, int divisor) { // 特殊情况 if (dividend == 0){ return 0; } if (divisor == 1){ return dividend; } // 处理溢出情况 if (dividend == Integer.MIN_VALUE && divisor == -1){ return Integer.MAX_VALUE; } int res = 0; boolean isPos = false; if ( ( dividend < 0 && divisor < 0 ) || (dividend > 0 && divisor > 0)){ isPos = true; } if (dividend > 0){ dividend = -dividend; } if (divisor > 0){ divisor = -divisor; } while(dividend <= divisor) { int x = 1; int d = divisor; while(d > -1e9 && dividend <= d + d) { x += x; d += d; } res += x; dividend -= d; } return isPos ? res : -res; } }
。复杂度
- 时间复杂度：O(logn)
- 空间复杂度：O(1)
2.二进制求和【LC67】
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
模拟
2022/10/12
1.首先将字符串a和b的位数扩充至相同，在长度较小者开头补0
2.然后从低位模拟二进制加法，使用sb记录最终结果，使用cnt记录进位，使用res记录每一位的结果
。res=3时，在sb的开头添加1，进位cnt=1
。res=2时，在sb的开头添加0，进位cnt=1
。res=1、0时，在sb的开头添加1或0，进位cnt=0
3.最后如果仍有进位，添加至res中
第二补可优化为,cnt = res / 2; res = res % 2;
- 代码
class Solution { public String addBinary(String a, String b) { int aLen = a.length(); int bLen = b.length(); if (aLen > bLen){ b = add0(b,aLen-bLen); }else if (aLen < bLen){ a = add0(a,bLen-aLen); } int len = a.length(); StringBuilder sb = new StringBuilder(); int cnt = 0; for (int i = len - 1; i >= 0; i--){ int na = a.charAt(i) - '0'; int nb = b.charAt(i) - '0'; int res = na + nb + cnt; sb.insert(0,res%2); cnt = res / 2; // if (res == 3){ // sb.insert(0,'1'); // cnt = 1; // }else if (res == 2){ // sb.insert(0,'0'); // cnt = 1; // }else{ // sb.insert(0,res); // cnt = 0; // } } if (cnt != 0){ sb.insert(0,String.valueOf(cnt)); } return new String(sb); } public String add0 (String a, int n){ StringBuilder sb = new StringBuilder(a); while (n > 0){ sb.insert(0,'0'); n--; } return new String(sb); } }
- 复杂度
。时间复杂度：O(n)，n为字符串的最长长度
。空间复杂度：O(n)
- 优化：
。第二补可优化为，使用cnt计算结果，sb.insert(0,(char)(cnt % 2 + ‘0’));cnt = res / 2;
。不额外构造字符串补0，根据坐标进行补0，i为位数
- 当i小于数组长度时，取len-1-i处的字符
- 当i大于数组长度时，取0
。代码
class Solution { public String addBinary(String a, String b) { int aLen = a.length(); int bLen = b.length(); int len = Math.max(aLen,bLen); StringBuilder sb = new StringBuilder(); int cnt = 0; for (int i = 0; i < len; i++){ cnt += i < a.length() ? (a.charAt(aLen - 1 - i) - '0') : 0; cnt += i < b.length() ? (b.charAt(bLen - 1 - i) - '0') : 0; sb.insert(0,(char)(cnt % 2 + '0')); cnt = cnt / 2; } if (cnt != 0){ sb.insert(0,String.valueOf(cnt)); } return new String(sb); } }
3.比特位计数【LC338】
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
动态规划
2022/10/14
1.确定dp数组（dp table）以及下标的含义
res[i]:表示i的二进制中1的个数
2.确定递推公式
需要使用变量a记录小于i的最大的2的幂
。当i为2的次方时，i的二进制中1的个数为1
。当a<i<a*2时，i的二进制中1的个数等于i-a的二进制个数+1
res[i] = res[i-a] + 1;
3.dp数组如何初始化
。a=1,res[0]=0，res[1]=1
。当n=0或者n=1时，返回res
4.确定遍历顺序
从i=2正向遍历n
- 代码
class Solution { public int[] countBits(int n) { int[] res = new int[n+1]; res[0] = 0; if (n == 0){ return res; } res[1] = 1; int a = 1; for (int i = 2; i <= n; i++){ if (i == a * 2){ res[i] = 1; a *= 2; }else{ res[i] = res[i-a] + 1; } } return res; } }
- 复杂度
。时间复杂度：O(n)
。空间复杂度：O(1)
简单计算i中一比特数
使用i & (i-1)，将整数i的最右边的1变成0。对i进行重复操作，直到i变为0，那么操作次数即为i的一比特数
class Solution { public int[] countBits(int n) { int[] bits = new int[n + 1]; for (int i = 0; i <= n; i++) { bits[i] = countOnes(i); } return bits; } public int countOnes(int x) { int ones = 0; while (x > 0) { x &= (x - 1); ones++; } return ones; } } 作者：力扣官方题解 链接：https://leetcode.cn/problems/counting-bits/solutions/627418/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 复杂度
。时间复杂度：O(n log n)
。空间复杂度：O(1)
i & (i-1)
根据**i & (i-1)**能够将整数i的最右边的1变成0。
那么i的一比特数比**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; } return res; } }
- 复杂度
。时间复杂度：O(n)
。空间复杂度：O(1)
i/2
- 偶数i的一比特数 = i/2的一比特数
。如果正整数i是一个偶数，那么i相当于将i/2左移一位的结果
- 偶数i的一比特数 = i/2的一比特数 + 1
。如果正整数i是一个奇数，那么i相当于将i/2左移一位再江最右边设为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 >> 1] + (i & 1); } return res; } }
- 复杂度
。时间复杂度：O(n)
。空间复杂度：O(1)
4.只出现一次的数字【LC136】
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
2022/10/15
map
使用map统计每个数字出现的次数，最后返回只出现一次的元素
- 代码
class Solution { public int singleNumber(int[] nums) { Map<Integer,Integer> map = new HashMap<>(); for (int i = 0; i < nums.length;i++){ map.put(nums[i],map.getOrDefault(nums[i],0)+1); } Set<Map.Entry<Integer,Integer>> set = map.entrySet(); for (Map.Entry<Integer,Integer> node : set){ if (node.getValue() == 1){ return node.getKey(); } } return -1; } }
- 复杂度
。时间复杂度：O(n)
。空间复杂度：O(n)
排序
将数组从小到大排序，返回与下一个元素不相等的元素
class Solution { public int singleNumber(int[] nums) { Arrays.sort(nums); int i = 0; while ( i < nums.length - 1 ){ if (nums[i] == nums[i+1]){ i = i + 2; }else{ return nums[i]; } } return nums[i]; } }
- 复杂度
。时间复杂度：O(nlogn)
。空间复杂度：O(1)
*异或
任何一个数字异或它自己的结果都是0。如果将数组中的所有数字进行异或运算，那么最终的结果就是那个只出现一次的数字
- 代码
class Solution { public int singleNumber(int[] nums) { int res = 0; for (int i = 0; i < nums.length; i++){ res = res ^ nums[i]; } return res; } }
- 复杂度
。时间复杂度：O(n)
。空间复杂度：O(1)
5.只出现一次的数字Ⅱ【LC137】
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且不使用额外空间来解决此问题。
2022/10/15
排序
将数组从小到大排序，返回与下下一个元素不相等的元素
- 代码
class Solution { public int singleNumber(int[] nums) { Arrays.sort(nums); int i = 0; while ( i < nums.length - 1 ){ if (nums[i] == nums[i+2]){ i = i + 3; }else{ return nums[i]; } } return nums[i]; } }
- 复杂度
。时间复杂度：O(nlogn)
。空间复杂度：O(1)
位运算
考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 3 的倍数。 因此，统计所有数字的各二进制位中 1的出现次数，并对 3求余，结果则为只出现一次的数字。
作者：Krahets
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
遍历统计
- 代码
class Solution { public int singleNumber(int[] nums) { int[] counts = new int[32]; for(int num : nums) { for(int j = 0; j < 32; j++) { counts[j] += num & 1; // 更新第 j 位 num >>>= 1; // 第 j 位 --> 第 j + 1 位 } } int res = 0, m = 3; for(int i = 0; i < 32; i++) { res <<= 1;// 左移 1 位 res |= counts[31 - i] % m;// 恢复第 i 位的值到 res } return res; } } 作者：Krahets 链接：https://leetcode.cn/problems/single-number-ii/solutions/8944/single-number-ii-mo-ni-san-jin-zhi-fa-by-jin407891/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 复杂度
。时间复杂度：O(n)
。空间复杂度：O(1)
有限状态机
举一反三
- 题目：输入一个整数数组，数组中只有一个数宇出现m次，其他数字都出现n次。请找出那个唯一出现m次的数宇。假设m不能被 n整除。
- 分析：如果数组中所有数字的第i个数位相加之和能被n整除，那么出现m 次的数宇的第个数位一定是0；否则出现m次的数字的第i个数位一定是1
6.最大单词长度乘积【LC318】
给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
2022/10/17
位运算
1.将每个单词转化为整数（二进制形式），用最低位代表a，第二低位代表b……最高位（第二十六位）代表z，例如单词“ab”可表示为11，十进制为3
2.将某个单词的二进制形式与其他单词进行与运算，如果结果为0，那么代表这两个单词不含有公共字母，判断是否需要更新结果
- 代码
class Solution { public int maxProduct(String[] words) { int len = words.length; int[] binary = new int[len]; // a:1 b:2 c:4 …… for (int i = 0; i < len; i++){ String str = words[i]; boolean[] map = new boolean[26]; for (int j = 0; j < str.length(); j++){ int n = str.charAt(j)-'a'; if (!map[n]){ binary[i] += Math.pow(2,n); map[n] = true; } } } int res = 0; for (int i = 0; i < len; i++){ for (int j = i + 1; j < len; j++){ if ((binary[i] & binary[j]) == 0){ res = Math.max(res,words[i].length()*words[j].length()); } } } return res; } }
- 复杂度
。时间复杂度：O(n2+nk)，n为字符串的个数，k为每个字符串的平均长度
。空间复杂度：O(n)
- 优化
将每个字符串转化为二进制的代码可优化为
for (int i = 0; i < len; i++){ String str = words[i]; for (char ch: words[i].toCharArray()){ binary[i] |= 1 << (ch - 'a'); } }
哈希表
使用哈希表记录出现在该字符串的所有字符
- 代码
class Solution { public int maxProduct(String[] words) { int len = words.length; boolean[][] flags = new boolean[len][26]; for (int i = 0; i < len; i++){ String str = words[i]; for (char ch: words[i].toCharArray()){ flags[i][ch-'a'] = true; } } int res = 0; for (int i = 0; i < len; i++){ for (int j = i + 1; j < len; j++){ int k = 0; for (; k < 26; k++){ if (flags[i][k] && flags[j][k]){ break; } } if (k == 26){ res = Math.max(res,words[i].length()*words[j].length()); } } } return res; } }
- 复杂度
。时间复杂度：O(n2+nk)，n为字符串的个数，k为每个字符串的平均长度
。空间复杂度：O(n)
7.反转字符串【LC344】
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
位运算
class Solution { public void reverseString(char[] s) { int l = 0; int r = s.length - 1; while (l < r) { s[l] ^= s[r]; //构造 a ^ b 的结果，并放在 a 中 s[r] ^= s[l]; //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b s[l] ^= s[r]; //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换 l++; r--; } } }
- 复杂度
。时间复杂度：O(n)
。空间复杂度：O(1)
双指针
//2021/11/9 class Solution { public void reverseString(char[] s) { int len = s.length; for (int l=0;l<len/2;l++){ char temp = s[l]; s[l] = s[len-l-1]; s[len-1-l] = temp; } } }
- 复杂度分析
。时间复杂度：O(n)，其中 n为字符数组的长度。一共执行了 n/2次的交换。
。空间复杂度：O(1)。只使用了常数空间来存放若干变量
