目录
以下均为接触的力扣原题，作一个总结，以便日后复习。
设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。
示例:
输入: a = 1, b = 1
输出: 2
提示：
1）a, b 均可能是负数或 0
2）结果不会溢出 32 位整数
关键点：
代码实现：
class Solution {
public int add(int a, int b) {
while(b!=0){
int res = (a^b);
int num = (a&b)<<1;
a = res;
b = num;
}
return a;
}
}给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
示例 1:
输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16
解释: 这两个单词为 "abcw", "xtfn"。
示例 2:
输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4
解释: 这两个单词为 "ab", "cd"。
示例 3:
输入: ["a","aa","aaa","aaaa"]
输出: 0
解释: 不存在这样的两个单词。
算法思路：
用二进制的一位表示某一个字母是否出现过，0表示没出现，1表示出现。"abcd"二进制表示00000000 00000000 00000000 00001111、"bc"二进制表示00000000 00000000 00000000 00000110。当两个字符串没有相同的字母时，二进制数与的结果为0。
代码实现：
class Solution {
public int maxProduct(String[] words) {
int wlength = words.length;
int[] arr = new int[wlength];
for(int i = 0; i < wlength; ++i){
int length = words[i].length();
for(int j = 0; j < length; ++j){
arr[i] |= 1 << (words[i].charAt(j) - 'a');
}
}
int ans = 0;
for(int i = 0; i < wlength; ++i){
for(int j = i + 1; j < wlength; ++j){
if((arr[i] & arr[j]) == 0){
int k = words[i].length() * words[j].length();
ans = ans < k ? k : ans;
}
}
}
return ans;
}
}给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]
示例 2:
输入: 5
输出: [0,1,1,2,1,2]
代码实现：
// class Solution {
// public int[] countBits(int num) {
// int[] res = new int[num+1];
// res[0] = 0;
// for(int i=1;i<num+1;i++){
// int n = i;
// int count = 0;
// while(n>0){
// if((n & 1)!=0){
// count++;
// }
// n = n>>1;
// }
// res[i] = count;
// }
// return res;
// }
// }
/**找规律，归纳出递归表达式
观察x和 x′=x/2的关系：
x=(1001011101)2=(605)10
x′=(100101110)2=(302)10
可以发现 x′与 x只有一位不同，这是因为x′可以看做 x移除最低有效位的结果。
这样，我们就有了下面的状态转移函数：
P(x)=P(x/2)+(xmod 2)
*/
class Solution{
public int[] countBits(int num){
int[] res = new int[num+1];
res[0] = 0;
for(int i=1;i<num+1;i++){
res[i] = res[i>>1]+(i&1);// x / 2 is x >> 1 and x % 2 is x & 1
}
return res;
}
}给定一个正整数 n，你可以做如下操作：
1. 如果 n 是偶数，则用 n / 2替换 n。
2. 如果 n 是奇数，则可以用 n + 1或n - 1替换 n。
n 变为 1 所需的最小替换次数是多少？
示例 1:
输入:
8
输出:
3
解释:
8 -> 4 -> 2 -> 1
示例 2:
输入:
7
输出:
4
解释:
7 -> 8 -> 4 -> 2 -> 1
或
7 -> 6 -> 3 -> 2 -> 1
代码实现：
// 1、偶数没有任何疑问，无符号右移即可。
// 2、奇数时的两个选择，其实有迹可循：
// 例子：101111 - - > (110000 or 101110)?
// 首先明白，使用n + 1或n - 1 替代 n 都会计一步，可以理解为“转化1代价”，那么最舒适的情况当然是1越少越好(1000000[注：为偶数])，一路右移通畅无阻。如例子中所示，此时选择 n + 1 一次可以处理掉 (4 - 1 = )3 个 1，而选择n - 1稍后仍然要在其他的3 个 1 上消耗时间。显而易见前者是更高效的。
// 但这里要注意两个特殊的情况：
// 3的特殊性：按照上面偶数的处理方式 n + 1 和 n - 1都会消耗掉一个 1 ，但 n + 1 方式下路线为：3 - > 4 - > 2 - > 1，n - 1 方式下路线为3 - > 2 - > 1;所以将此时的累计值直接加二处理掉即可。
// Integer.MAX_VALUE(2147483647)溢出兼容
// Integer.MAX_VALUE会被算法使用奇数处理逻辑 +1 导致溢出为Integer.MIN_VALUE(0x80000000),此时做31次无符号右移即可得到1，这也是选用无符号右移的原因。
class Solution {
public int integerReplacement(int n) {
int count = 0;
while (n!=1){
//与运算判断最后一位来区分奇偶
if((n & 1) == 0){
//偶数直接无符号右移，
//2147483647 会被奇数处理算法加一溢出为负数，
//若选用带符号右移将无法回到1.
n >>>=1;
count++;
}
else {
//识别奇数的上一位是否为1，即 以 10 结尾(xxxx01)还是以11结尾(xxxx11)
if((n & 2) == 0){
//01结尾最优则应当 用 n -1 取代 n
n -= 1;
count++;
}else {
//11结尾除3这个特殊情况外，其余选用 n + 1取代 n，原因如上
if(n == 3){
//3的特殊性处理，原因如上
count+=2;break;
}else {
n += 1;
}
count++;
}
}
}
return count;
}
}给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。
示例 1：
输入：s = "eleetminicoworoep"
输出：13
解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。
示例 2：
输入：s = "leetcodeisgreat"
输出：5
解释：最长子字符串是 "leetc" ，其中包含 2 个 e 。
示例 3：
输入：s = "bcbcbc"
输出：6
解释：这个示例中，字符串 "bcbcbc" 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。
原题链接：https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/
代码实现：
class Solution {
public int findTheLongestSubstring(String s) {
int res = 0;
char[] c = s.toCharArray();
// Key为前i项的前缀和，value为i
HashMap<Integer,Integer> map = new HashMap<>();
int[] dp = new int[c.length+1];
dp[0] = 0;
for(int i = 0; i < c.length; i++) {
// 当遇到元音时进行异或运算，两个相同字母异或运算为0
if( c[i] == 'a' ||
c[i] == 'e' ||
c[i] == 'i' ||
c[i] == 'o' ||
c[i] == 'u')
dp[i+1] = dp[i] ^ c[i];
// 如果遇到非元音字母则保持前项结果
else
dp[i+1] = dp[i];
// 如果前项和为0，则说明此字串为满足题意要求的子串
if (dp[i+1] == 0) {
res = i + 1;
continue;
}
//dp[i+1]!=0时执行以下操作
// 如果当前map中存在当前的前缀和，则当前前缀和与前部前缀和异或运算也为0
if(map.containsKey(dp[i+1])) {//map中key存放的是前缀和，而不是具体的字母
res = Math.max(res,i - map.get(dp[i+1]));
}
// 若不含当前字串前缀和，将其前缀和作为key，i作为value加入map中
else
map.put(dp[i+1],i);
}
return res;
}
}
绘制直线。有个单色屏幕存储在一个一维数组中，使得32个连续像素可以存放在一个 int 里。屏幕宽度为w，且w可被32整除（即一个 int 不会分布在两行上），屏幕高度可由数组长度及屏幕宽度推算得出。请实现一个函数，绘制从点(x1, y)到点(x2, y)的水平线。
给出数组的长度 length，宽度 w（以比特为单位）、直线开始位置 x1（比特为单位）、直线结束位置 x2（比特为单位）、直线所在行数 y。返回绘制过后的数组。
示例1:
输入：length = 1, w = 32, x1 = 30, x2 = 31, y = 0
输出：[3]
说明：在第0行的第30位到第31为画一条直线，屏幕表示为[0b000000000000000000000000000000011]
示例2:
输入：length = 3, w = 96, x1 = 0, x2 = 95, y = 0
输出：[-1, -1, -1]
审题：
解题思路：
代码实现：
//https://leetcode-cn.com/problems/draw-line-lcci/solution/javawei-yun-suan-by-loser-11/
class Solution {
public int[] drawLine(int length, int w, int x1, int x2, int y) {
int[] ret = new int[length];
// 注意根据所在行数计算偏移量
int offset = y * w / 32;
// 首位数字下标
int head = x1 / 32 + offset;
// 末位数字下标
int rear = x2 / 32 + offset;
// 把涉及到的数全部置 -1 也就是 0b11111111111111111111111111111111
for (int i = head; i <= rear; i++)
ret[i] = -1;
// 调整首位数字,先求余再移位运算再求与
ret[head] = ret[head] & -1 >>> x1 % 32;
// 调整末位数字，Integer.MIN_VALUE==1000..00(31个0)，有符号右移，是负数所以添1
ret[rear] = ret[rear] & Integer.MIN_VALUE >> x2 % 32;
return ret;
}
}（力扣260）给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例 :
注意：
题解思路：如果我们把原数组分成两组，只出现过一次的两个数字分别在两组里边，那么问题就转换成之前的老问题了，只需要这两组里的数字各自异或，答案就出来了。
那么通过什么把数组分成两组呢？
放眼到二进制，我们要找的这两个数字是不同的，所以它俩至少有一位是不同的，所以我们可以根据这一位，把数组分成这一位都是 1 的一类和这一位都是 0 的一类，这样就把这两个数分到两组里了。
那么怎么知道那两个数字哪一位不同呢？
回到我们异或的结果，如果把数组中的所有数字异或，最后异或的结果，其实就是我们要找的两个数字的异或。而异或结果如果某一位是 1，也就意味着当前位两个数字一个是 1 ，一个是 0，也就找到了不同的一位。
思路就是上边的了，然后再考虑代码怎么写。
怎么把数字分类？
我们构造一个数，把我们要找的那两个数字二进制不同的那一位写成 1，其它位都写 0，也就是 0...0100...000 的形式。
然后把构造出来的数和数组中的数字相与，如果结果是 0，那就意味着这个数属于当前位为 0 的一类。否则的话，就意味着这个数属于当前位为 1 的一类。
代码实现：
class Solution {
public int[] singleNumber(int[] nums) {
int[] res = new int[2];
int count = 0;
int len = nums.length;
for(int i=0;i<len;i++){
count ^= nums[i];
}
int sum = 0;
while(count!=0){
if((count&1)==1){
break;
}
sum++;
count >>= 1;
}
List<Integer> list1 = new ArrayList();
List<Integer> list2 = new ArrayList();
for(int i=0;i<len;i++){
if(((nums[i] >> sum) &1) == 0){
list1.add(nums[i]);
}else{
list2.add(nums[i]);
}
}
int r = 0;
for(int i:list1){
r ^= i;
}
res[0] = r;
r = 0;
for(int i:list2){
r ^= i;
}
res[1] = r;
return res;
}
}颠倒给定的 32 位无符号整数的二进制位。
示例 1：
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596， 因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
示例 2：
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。
代码实现：
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
int ans = 0;
for(int size=31;n!=0;n=n>>>1,size--){
ans += (n&1) << size;
}
return ans;
}
}给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:
解释: 7/-3 = truncate(-2.33333..) = -2
代码实现：
class Solution {
public int divide(int dividend, int divisor) {
if (dividend == 0) {
return 0;
}
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
boolean negative;
negative = (dividend ^ divisor) <0;//用异或来计算是否符号相异
long t = Math.abs((long) dividend);
long d= Math.abs((long) divisor);
int result = 0;
for (int i=31; i>=0;i--) {
if ((t>>i)>=d) {//找出足够大的数2^n*divisor
result+=1<<i;//将结果加上2^n
t-=d<<i;//将被除数减去2^n*divisor
}
}
return negative ? -result : result;//符号相异取反
}
}