本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
位运算专题
计算机中的数在内存中都是以二进制形式进行存储的，用位运算就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。
首先来看下位运算的基本操作：
n&(n-1)
这个运算的作用是消除
n的二进制表达式的最后一个
1。看下面的例子：
10 & (10 - 1)
10 1 0 1 0
9 1 0 0 1
----------------
1 0 0 0
从上可知，最后一位1已经置0
这个表达式也可以引申下，
n & (n - 1) = 0，可以用来判断
n是否为
2的次方，即是否满足表达式
n = 2 ^ i。
8 & (8 - 1) = 0
8 1 0 0 0
7 0 1 1 1
0 0 0 0
异或运算交换两数
常规交换两个数，采用以下方式：
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
以上方式，需要一个额外的空间，我们也可以采用异或运算来实现：
public void swap(int[] nums, int i, int j) {
nums[i] ^= nums[j];
num[j] ^= nums[i];
nums[i] ^= nums[j];
}
(~n)+1：绝对值
这个运算可以用来求绝对值。
~(-1) + 1 = 1;
~(-2) + 1 = 2;
需要注意的是，
Integer.MIN_VALUE取反后的值为
Integer.MAX_VALUE，再加
1会溢出，结果仍为
Integer.MIN_VALUE。
136. 只出现一次的数字
本题来自 LeetCode：136. 只出现一次的数字[1]
题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
题目分析
由于数组中，除了一个元素只出现一次，其它元素均出现两次。可以利用异或运算
a^a=0的特性，对数组中的元素依次进行异或操作，将出现两次的元素排除掉，剩下的就是只出现一次的元素。
题目解答
class Solution {
public int singleNumber(int[] nums) {
int single = 0;
for(int i = 0; i nums.length; i ++) {
single = single ^ nums[i];
}
return single;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
137. 只出现一次的数字 II
本题来自 LeetCode：137. 只出现一次的数字 II[2]
题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99
题目分析
由于数组中，只有一个元素只出现一次，其他元素均出现三次。因此不能采用
136. 只出现一次的数字的异或运算来解答。
但可以注意到，数组中所有整数的相同位上的
1的个数为
i * 3 + （0 或 1）。
0表示该单数该位为
0，
1表示该单数该位为
1。因此只需要统计出所有位上
1的个数，然后对
3求余数即可。此解法也适应于第
136题。
题目解答
解法一
class Solution {
public int singleNumber(int[] nums) {
// 统计每位上1的个数
int[] count = new int[32];
for(int i = 0; i nums.length; i ++) {
int num = nums[i];
for(int j = 31; j = 0 && num !=0; j --) {
count[j] += (num & 1);
num = 1;
}
}
// 组装单数
int single = 0;
for(int i = 0; i 32; i ++) {
single = 1;
// 某位是否为1
single |= count[i] % 3;
}
return single;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
解法二
解法一使用了额外空间，如果不使用额外空间，需要将内外循环体交换一下。
class Solution {
public int singleNumber(int[] nums) {
int single = 0;
for(int i = 0; i 32; i ++) {
// 统计位置i上1的个数
int count = 0;
for(int j = 0; j nums.length; j ++) {
if(((nums[j] i) & 1) == 1) {
count ++;
}
}
// 唯一的那个元素在位i上是否为1
if(count % 3 == 1) {
single |= (1 i);
}
}
return single;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
260. 只出现一次的数字 III
本题来自 LeetCode：260. 只出现一次的数字 III[3]
题目描述
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。
示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]
注意：
结果输出的顺序并不重要，对于上面的例子，
[5, 3]也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
题目分析
由于存在两个只出现一次的元素
[x1,x2]，故不能采用
136. 只出现一次的数字的解法来解答。但是我们可以通过异或操作得到两个单数的异或结果
xor = x1 ^ x2。由于
x1 != x2，故
xor != 0，那么至少存在某位上
x1和
x2的是不同的，我们可以通过这个位置，将数组分成两部分，一部分这个位置上为
0，一部分这个位置上为
1。这两部分分别包含一个单数，这样就可以采用
136的解法了。
题目解答
class Solution {
public int[] singleNumber(int[] nums) {
// x1, x2 分别为只出现一次的元素
// 1. 计算出xor = x1 ^ x2
int xor = 0;
for(int i = 0; i nums.length; i ++) {
xor ^= nums[i];
}
// 2. 获取x1和x2不同的位
int mask = 1;
while(true) {
if((xor & 1) == 1) {
break;
}
xor = 1;
mask = 1;
}
// 3. 根据mask将数组分成两部分进行异或操作
int[] result = {0, 0};
for(int i = 0; i nums.length; i ++) {
if((nums[i] & mask) != 0) {
result[0] ^= nums[i];
} else {
result[1] ^= nums[i];
}
}
return result;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
78. 子集
本题来自 LeetCode：78. 子集[4]
题目描述
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
题目分析
在中，对子集采用的是回溯法，对于回溯法，空间复杂度为
O(n)，主要是调用栈的深度。时间复杂为
O(2^n)，因为每个元素有两种选择：
选中和未选中。
当然本题也可以用
位元算来解答。可以采用
n位来表示这
n个数的选中情况：
0表示未选中，
1表示选中。采用题目给出的示例如下：
num 1 2 3
0 0 0 0 []
1 1 0 0 [1]
2 0 1 0 [2]
3 1 1 0 [1, 2]
4 0 0 1 [3]
5 1 0 1 [1, 3]
6 0 1 1 [2, 3]
7 1 1 1 [1, 2, 3]
题目解答
解法一
可以采用一个长度为
n的数组
int[]来模拟，将其当成一个
n位的整数，枚举
0...2^n这个
2^n个数的位表达式情况。
class Solution {
public ListListInteger subsets(int[] nums) {
ListListInteger subSets = new LinkedList();
int n = nums.length;
// 采用一个长度为n的数组来标记每个数字是否选中
int[] selected = new int[nums.length];
while(true) {
ListInteger subSet = new LinkedList();
for(int i = 0; i n; i ++) {
if(selected[i] == 1) {
subSet.add(nums[i]);
}
}
subSets.add(subSet);
// 表示已经全部选中了
if(subSet.size() == n) {
break;
}
increment(selected);
}
return subSets;
}
// 模拟自增进位
public void increment(int[] selected) {
int carry = 1;
for(int i = 0; i selected.length && carry != 0; i ++) {
carry += selected[i];
selected[i] = carry % 2;
carry = 1;
}
}
}
复杂度分析：
时间复杂度：
O(n * (2 ^ n))
空间复杂度：
O(n)，使用了额外数组。
解法二
也可以采用一个长度为
n的数组
boolean[]来模拟。
class Solution {
public ListListInteger subsets(int[] nums) {
ListListInteger subSets = new LinkedList();
int n = nums.length;
// 采用一个长度为n的数组来标记每个数字是否选中
boolean[] selected = new boolean[nums.length];
while(true) {
ListInteger subSet = new LinkedList();
for(int i = 0; i n; i ++) {
if(selected[i]) {
subSet.add(nums[i]);
}
}
subSets.add(subSet);
// 表示已经全部选中了
if(subSet.size() == n) {
break;
}
increment(selected);
}
return subSets;
}
// 模拟进位
public void increment(boolean[] selected) {
boolean carry = true;
for(int i = 0; i selected.length && carry; i ++) {
boolean temp = selected[i];
selected[i] ^= carry;
carry &= temp;
}
}
}
解法三
以上解法都需要额外的空间，若
n不超过
32，这可以不使用额外的空间。
class Solution {
public ListListInteger subsets(int[] nums) {
ListListInteger subSets = new LinkedList();
if(nums == null || nums.length == 0) {
return subSets;
}
int n = nums.length;
// 子集个数：2^n
int total = 2 (n - 1);
for(int i = 0; i total; i ++) {
// 以i各位上是否为1，来判断对应位置上的数是否被选中
int bytes = i;
ListInteger subSet = new LinkedList();
for(int j = 0; bytes != 0; j ++) {
if((bytes & 1) == 1) {
subSet.add(nums[j]);
}
bytes = 1;
}
subSets.add(subSet);
}
return subSets;
}
}
复杂度分析：
时间复杂度：
O(n * (2 ^ n))
空间复杂度：
O(1)
784. 字母大小写全排列
本题来自 LeetCode：784. 字母大小写全排列[5]
题目描述
给定一个字符串 S，通过将字符串 S 中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
示例:
输入: S = "a1b2"
输出: ["a1b2", "a1B2", "A1b2", "A1B2"]
输入: S = "3z4"
输出: ["3z4", "3Z4"]
输入: S = "12345"
输出: ["12345"]
注意：
S 的长度不超过 12。
S 仅由数字和字母组成。
题目分析
本题和
78. 子集类似，由于 S 的长度不超过 12，可以用 int 的二进制表达式，来表示字母是否需要需要进行大小写转换。
字母个数为2，全排列个数为4，下面枚举每种排列的情况。
i 二进制 排列
0 0 0
a b a1b2
1 0 1
a B a1B2
2 1 0
A b A1b2
3 1 1
A B A1B2
当然本题也可以采用
DFS/BFS来解答，本文在此不做解答了。
题目解答
class Solution {
public ListString letterCasePermutation(String S) {
ListString lists = new ArrayList();
if(S == null || S.length() == 0) {
return lists;
}
// 转换成小写字母方便处理
S = S.toLowerCase();
// 字母个数
int letterCount = 0;
for(int i = 0; i S.length(); i ++) {
if(Character.isLowerCase(S.charAt(i))) {
letterCount ++;
}
}
// 采用字母掩码将对应位上的字母转换为大小写
// 全排列子集个数为 2 ^ letterCount
for(int i = 0; i (1 letterCount); i ++) {
lists.add(convert(i, letterCount, S));
}
return lists;
}
// mask的二进制表达式表示字符串的相应位上的字母是否需要转换为大写（0 表示小写，1表示大写）
public String convert(int mask, int letterCount, String s) {
StringBuilder sb = new StringBuilder();
// 表示第idx位字母
int idx = 0;
for(int i = 0; i s.length(); i ++) {
char c = s.charAt(i);
if(Character.isLowerCase(c)) {
// 表示需要将字符串第i位字母转换为大写
if((mask & (1 (letterCount - idx - 1))) != 0) {
c = Character.toUpperCase(c);
}
idx ++;
}
sb.append(c);
}
return sb.toString();
}
}
复杂度分析：
时间复杂度：
O(n * 2 ^ letterCount),其中
n表示字母长度，
letterCount表示字母个数。
空间复杂度：
O(1)
318. 最大单词长度乘积
本题来自 LeetCode：318. 最大单词长度乘积[6]
题目描述
给定一个字符串数组
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
解释: 不存在这样的两个单词。
题目分析
由于两个单词不含有公共字母，故每次都需要去比较两个单词是否含有相同字母。那么如何快速地判断两个单词是否有相同的字母呢？
注意到单词中只有小写字母，且小写字母只有
26个，那么可以用
int的位表达（
32位）来表示某个单词各字母的占用情况。
题目解答
class Solution {
public int maxProduct(String[] words) {
int[] masks = new int[words.length];
// 包含全部小写字母的掩码
int allMask = (1 26) - 1;
// 计算出每个单词的字母掩码
for(int i = 0; i words.length; i ++) {
String word = words[i];
// 计算出单词的字母掩码
for(int j = 0; j word.length(); j ++) {
masks[i] |= (1 (word.charAt(j) - 'a'));
// 已经包含全部字母
if(masks[i] == allMask) {
break;
}
}
}
int max = 0;
// 找到最大单词长度乘积
for(int i = 0; i words.length; i ++) {
for(int j = i + 1; j words.length; j ++) {
// 表示两个单词不包含公共字母
if((masks[i] & masks[j]) == 0) {
max = Math.max(max, words[i].length() * words[j].length());
}
}
}
return max;
}
}
复杂度分析：
时间复杂度：
O(n * max(n, max(length(word))), 其中
max(length(word)) 表示单词的最大长度
空间复杂度：
O(n)
191. 位 1 的个数
本题来自 LeetCode：191. 位 1 的个数[7]
题目描述
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
进阶:
如果多次调用这个函数，你将如何优化你的算法？
题目分析
利用上面提到的
n & (n - 1)运算来不断消除最右边一个位的
1。
题目解答
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
while(n != 0) {
count ++;
n &= (n -1);
}
return count;
}
}
复杂度分析：
时间复杂度：
O(length(n))，
length(n)表示最高位
1的位置下标。
空间复杂度：
O(1)
338. 比特位计数
本题来自 LeetCode：338. 比特位计数[8]
题目描述
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]
示例 2:
输入: 5
输出: [0,1,1,2,1,2]
进阶: 给出时间复杂度为
O(n*sizeof(integer))的解答非常容易。但你可以在线性时间
O(n)内用一趟扫描做到吗？
要求算法的空间复杂度为
O(n)。
题目分析
本题之前解答过，采用动态规划，请查看。
本文对此解法的细节稍作修改。
题目解答
class Solution {
public int[] countBits(int num) {
int[] bits = new int[num + 1];
if(num == 0) {
return bits;
}
bits[1] = 1;
int pow2 = 1; // 记录2的n次方
for(int i = 2; i = num; i ++) {
// 若i是2的次方，直接设置为1
if((i & (i - 1)) == 0) {
pow2 = 1;
bits[i] = 1;
} else {
bits[i] = bits[pow2] + bits[i^pow2];
}
}
return bits;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
477. 汉明距离总和
本题来自 LeetCode：477. 汉明距离总和[9]
题目描述
两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。
计算一个数组中，任意两个数之间汉明距离的总和。
示例:
输入: 4, 14, 2
输出: 6
解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。（这样表示是为了体现后四位之间关系）
所以答案为：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
注意:
数组中元素的范围为从
0到
10^9。
数组的长度不超过
10^4。
解法一（超时未通过）
题目分析
两个数的汉明距离，通过通过求其异或的结果，然后通过
n&(n-1)来计算
1的个数。
本题可以两两求其汉明距离，类加即可。但是由于时间复杂度为
O(n^2)，超时未通过。
题目解答
class Solution {
public int totalHammingDistance(int[] nums) {
int totalCount = 0;
for(int i = 0; i nums.length - 1; i ++) {
for(int j = i + 1; j nums.length; j ++) {
totalCount += hammingDistance(nums[i], nums[j]);
}
}
return totalCount;
}
public int hammingDistance(int num1, int num2) {
int xor = num1 ^ num2;
int count = 0;
while(xor != 0) {
count ++;
xor &= (xor - 1);
}
return count;
}
}
复杂度分析：
时间复杂度：
O(n^2)
空间复杂度：
O(1)
解法二
题目分析
汉明距离等于两个数二进制表示中对应位置不同的数量。假设数组中的每个数都表示为 k 位的二进制数（高位补 0），那么我们可以发现，要计算数组中任意两个数的汉明距离的总和，可以先算出数组中任意两个数二进制第 i 位的汉明距离的总和，在将所有的 k 位之和相加。也就是说，二进制中的每一位都是可以独立计算的。
因此，我们考虑数组中每个数二进制的第 i 位，假设一共有
countOne个
1和
n - countOne个
0，那么显然在第
i位的汉明距离的总和为
countOne * (n - countOne)。
由于所有的数都在
[0, 10^9]的范围内，因此
k最大为
31。我们只要计算出每一位上的汉明距离的总和，再相加即可。
题目解答
class Solution {
public int totalHammingDistance(int[] nums) {
int n = nums.length;
int totalCount = 0;
for(int i = 0; i 32; i ++) {
// 记录数组中第i位上的1的个数
int countOne = 0;
for(int j = 0; j n; j ++) {
countOne += ((nums[j] i) & 1);
}
totalCount += countOne * (n - countOne);
}
return totalCount;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
231. 2 的幂
本题来自 LeetCode：231. 2 的幂[10]
题目描述
给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
示例 1:
输入: 1
输出: true
解释: 20 = 1
示例 2:
输入: 16
输出: true
解释: 24 = 16
示例 3:
输入: 218
输出: false
题目分析
n & (n - 1) = 0，可以用来判断
n是否为
2的次方，即是否满足表达式
n = 2 ^ i。
8 & (8 - 1) = 0
8 1 0 0 0
7 0 1 1 1
0 0 0 0
题目解答
class Solution {
public boolean isPowerOfTwo(int n) {
if(n == 0) {
return false;
}
return n 0 && (n & (n - 1)) == 0;
}
}
复杂度分析：
时间复杂度：
O(1)
空间复杂度：
O(1)
326. 3 的幂
本题来自 LeetCode：326. 3 的幂[11]
题目描述
给定一个整数，写一个函数来判断它是否是
3的幂次方。
示例 1:
输入: 27
输出: true
示例 2:
输入: 0
输出: false
示例 3:
输入: 9
输出: true
示例 4:
输入: 45
输出: false
进阶：
你能不使用循环或者递归来完成本题吗？
解法一
题目分析
常规解法，通过判断取模运算
n % 3 == 0是否满足这个条件。
题目解答
class Solution {
public boolean isPowerOfThree(int n) {
if(n = 0) {
return false;
}
while(n != 0) {
if(n == 1) {
return true;
}
if(n % 3 != 0) {
return false;
}
n /= 3;
}
return false;
}
}
复杂度分析：
时间复杂度：
O(log3(n))
空间复杂度：
O(1)
解法二
题目分析
我们也可以找到
32位
Integer所表示的最大值
MAX_POW_3_VALUE。然后通过
MAX_POW_3_VALUE % n == 0来判断
n是否为
3的幂。
题目解答
class Solution {
// Integer 所表示的3最大指数的值
public static final int MAX_POW_3_VALUE = (int) Math.pow(3, (int)(Math.log(Integer.MAX_VALUE) / Math.log(3)));
public boolean isPowerOfThree(int n) {
return n 0 && MAX_POW_3_VALUE % n == 0;
}
}
复杂度分析：
时间复杂度：
O(1)
空间复杂度：
O(1)
342. 4 的幂
本题来自 LeetCode：342. 4 的幂[12]
题目描述
给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是
4的幂次方。
示例 1:
输入: 16
输出: true
示例 2:
输入: 5
输出: false
进阶：
你能不使用循环或者递归来完成本题吗？
解法一
题目分析
常规解法，和
326. 3的幂一样，通过判断取模运算
n % 4 == 0是否满足这个条件。
题目解答
class Solution {
public boolean isPowerOfFour(int num) {
if(num = 0) {
return false;
}
while(num != 0) {
if(num == 1) {
return true;
}
if(num % 4 != 0) {
return false;
}
num /= 4;
}
return false;
}
}
复杂度分析：
时间复杂度：
O(log4(n))
空间复杂度：
O(1)
解法二
题目分析
若一个整数是
4的幂，那么也一定是
2的幂。它的二进制表达式，一定存在着某个偶数位为
1。通过掩码
n & 0x55555555 != 0能保证某个偶数位的值为
1。
0x55555555=01010101010101010101010101010101
题目解答
class Solution {
public boolean isPowerOfFour(int num) {
return num 0 && (num & (num - 1)) == 0 && (num & 0x55555555) != 0;
}
}
复杂度分析：
时间复杂度：
O(log4(n))
空间复杂度：
O(1)
201. 数字范围按位与
本题来自 LeetCode：201. 数字范围按位与[13]
题目描述
给定范围
[m, n]，其中
0 = m = n = 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。示例 1:
输入: [5,7]
输出: 4
示例 2:
输入: [0,1]
输出: 0
解法一
题目分析
本题比较简单，需要注意几个
case，因为我没有考虑，本题第三次才解答正确。
题目解答
class Solution {
public int rangeBitwiseAnd(int m, int n) {
int result = Integer.MAX_VALUE;
for(int i = m; ; i ++) {
result &= i;
// 提前中止，防止无效运算，因为 0 & i = 0
if(result == 0) {
return 0;
}
// 防止n=Integer.MAX_VALUE时，越界
if(i == n) {
break;
}
}
return result;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
解法二
题目分析
=
n & (n - 1)可以用来消除二进制表达式的最右边的
1。
题目解答
class Solution {
public int rangeBitwiseAnd(int m, int n) {
while(n m) {
n = n & (n - 1);
}
return n;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
169. 多数元素
本题来自 LeetCode：169. 多数元素[14]
题目描述
给定一个大小为
n的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于
⌊ n/2 ⌋的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
题目分析
由于多数元素在数组上出现的次数大于
⌊n/2⌋，那么可以知道多数元素在，数组中某位上
1的个数也是大于
⌊n/2⌋的。故可以统计数组中所有元素所有位的
1的个数。使用示例 1 的例子如下：
元素 3 ：0 1 1
元素 2 ：0 1 0
元素 3 ：0 1 1
count[i] 0 3 2
n/2
多数元素 0 1 1 = 3
题目解答
class Solution {
public int majorityElement(int[] nums) {
int n = nums.length;
// 统计每位上1的个数
int[] count = new int[32];
for(int i = 0; i n; i ++) {
int num = nums[i];
for(int j = 31; num !=0; j --) {
count[j] += (num & 1);
num = 1;
}
}
// 组装多数元素
int single = 0;
for(int i = 0; i = 31; i ++) {
if(count[i] * 2 n) {
single |= (1 (31 - i));
}
}
return single;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
405. 数字转换为十六进制数
本题来自 LeetCode：405. 数字转换为十六进制数[15]
题目描述
给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。
注意:
十六进制中所有字母(a-f)都必须是小写。
十六进制字符串中不能包含多余的前导零。如果要转化的数为 0，那么以单个字符’0’来表示；对于其他情况，十六进制字符串中的第一个字符将不会是 0 字符。
给定的数确保在 32 位有符号整数范围内。
不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。
示例 1：
输入:
26
输出:
"1a"
示例 2：
输入:
-1
输出:
"ffffffff"
题目分析
本题主要注意点为处理好补码，原码求补码的计算规则如下：
题目解答
class Solution {
public String toHex(int num) {
// 0...9
if(num = 0 && num = 9) {
return String.valueOf(num);
}
// a...f
if(num 9 && num = 15) {
return String.valueOf((char) (num + 'a' - 10));
}
// 负数取补码
if(num 0) {
num = (-num ^ 0xffffffff) + 1;
}
// 转换为16进制
String hex = "";
while(num != 0) {
hex = toHex(num & 15) + hex;
num = 4;
}
return hex;
}
}
复杂度分析：
时间复杂度：
O(log(n))
空间复杂度：
O(1)
参考资料
只出现一次的数字 II: https://leetcode-cn.com/problems/single-number-ii
只出现一次的数字 III: https://leetcode-cn.com/problems/single-number-iii
字母大小写全排列: https://leetcode-cn.com/problems/letter-case-permutation
最大单词长度乘积: https://leetcode-cn.com/problems/maximum-product-of-word-lengths
汉明距离总和: https://leetcode-cn.com/problems/total-hamming-distance
数字范围按位与: https://leetcode-cn.com/problems/bitwise-and-of-numbers-range/
数字转换为十六进制数: https://leetcode-cn.com/problems/convert-a-number-to-hexadecimal
原文始发于微信公众号（xiaogan的技术博客）：
