方法一：逐一计算
时间复杂度 O(n log n)
class Solution {
public int[] countBits(int n) {
int[] ans = new int[n + 1];
for (int i = 0; i <= n; i++) {
int a = i;
int b = 0;
int count = 0;//计数器
while (a != 0){//计算二进制中1的个数
b = a & 1;//b为二进制中的最后一个数字
if (b == 1)count++;
a = a >> 1;
}
ans[i] = count;
}
return ans;
}
}
方法二：方法一的另一种写法
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);// x & (x - 1)用来抹除x二进制中最后的一个1
ones++;
}
return ones;
}
}
方法三：使用内置函数
class Solution {
public int[] countBits(int n) {
int[] ans = new int[n + 1];
for (int i = 0; i <= n; i++) {
//使用内置函数计算 i 的二进制表示中1的位数
ans[i] = Integer.bitCount(i);
}
return ans;
}
}
方法四：动态规划 最高有效位
class Solution {
public int[] countBits(int n) {
int[] ans = new int[n + 1];
int height = 0;
for (int i = 1; i <= n; i++) {
if ((i & (i - 1)) == 0) {
height = i;
}
ans[i] = ans[i - height] + 1;
}
return ans;
}
}
方法五：动态规划 最低有效位
class Solution {
public int[] countBits(int n) {
int[] ans = new int[n + 1];
for (int i = 0; i <= n; i++) {
ans[i] = ans[i >> 1] + (i & 1);
}
return ans;
}
}
方法六：动态规划 最低设置位
与方法五对照着思考
class Solution {
public int[] countBits(int n) {
int[] bits = new int[n + 1];
for (int i = 1; i <= n; i++) {
bits[i] = bits[i & (i - 1)] + 1;
}
return bits;
}
}
2.位 1 的个数（ LeetCode 191 ）
方法一：循环检查二进制位
public class Solution {
public int hammingWeight(int n) {
int ret = 0;
for (int i = 0; i < 32; i++) {
if ((n & (1 << i)) != 0) {
ret++;
}
}
return ret;
}
}
方法二：位运算优化
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int ans = 0;
while (n != 0){
n = n & (n - 1);
ans++;
}
return ans;
}
}
错误解法
public int hammingWeight(int n) {
int ans = 0;
while (n != 0){
int x = n & 1;
if (x == 1)ans++;
//正数与负数右移规则不同，此处不适用
n = n >> 1;
}
return ans;
}
3.只出现一次的数字 II（ LeetCode 137 ）
方法一：排序 暴力解法
class Solution {
public int singleNumber(int[] nums) {
Arrays.sort(nums);
int num = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]){
num++;
}else {
if (num == 1)
return nums[i - 1];
num = 1;
}
}
return nums[nums.length - 1];
}
}
方法二：hash
class Solution {
public int singleNumber(int[] nums) {
Map freq = new HashMap();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
int ans = 0;
for (Map.Entry entry : freq.entrySet()) {
int num = entry.getKey(), occ = entry.getValue();
if (occ == 1) {
ans = num;
break;
}
}
return ans;
}
}
方法三：依次确定每一个二进制位
class Solution {
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < 32; ++i) {
int total = 0;
for (int num: nums) {
total += ((num >> i) & 1);
}
//余数就是出现一次的那个数的该位的二进制
if (total % 3 != 0) {
ans |= (1 << i);
}
}
return ans;
}
}
4.只出现一次的数字 III（ LeetCode 260 ）
方法一：hash
class Solution {
public int[] singleNumber(int[] nums) {
int[] ans = new int[2];
int k = 0;
Map map = new HashMap<>();
for (int x:nums
) {
map.put(x,map.getOrDefault(x,0) + 1);
}
for (Map.Entry x:map.entrySet()
) {
Integer key = x.getKey();
Integer value = x.getValue();
if (value == 1){
ans[k++] = key;
}
}
return ans;
}
}
方法二：
位运算
class Solution {
public int[] singleNumber(int[] nums) {
int xorsum = 0;
for (int num : nums) {
xorsum ^= num;
}
//Integer.MIN_VALUE = 10000000000000000000000000000000
// 防止溢出
int lsb = (xorsum == Integer.MIN_VALUE ? xorsum : xorsum & (-xorsum));
int type1 = 0, type2 = 0;
for (int num : nums) {
if ((num & lsb) != 0) {
type1 ^= num;
} else {
type2 ^= num;
}
}
return new int[]{type1, type2};
}
}
5.最大单词长度乘积（ LeetCode 318 ）
方法一：暴力解法 超时
时间复杂度 O(n3)
class Solution {
public int maxProduct(String[] words) {
int max = 0;
for (int i = 0; i < words.length - 1; i++) {
for (int j = i + 1; j < words.length; j++) {
max = Math.max(max,mulStr(words[i],words[j]));
}
}
return max;
}
public int mulStr(String s,String s2){
Set set = new HashSet<>();
for (char x:s.toCharArray()
) {
set.add(x);
}
for (char x:s2.toCharArray()
) {
if (set.contains(x))return 0;
}
return s.length() * s2.length();
}
}
方法二：位运算
方法一的基础上进行优化
降低比较a，b是否包含相同字符的时间复杂度
class Solution {
public int maxProduct(String[] words) {
int[] temp = new int[words.length];
for (int i = 0; i < words.length; i++) {
int x = 0;
//遍历words[i]
//x的二进制表示中
//第0位为1表示word[i]中存在a
//第1位为1表示word[i]中存在b
//...
for (int j = 0; j < words[i].length(); j++) {
x = x | (1 << (words[i].charAt(j) - 'a'));
}
temp[i] = x;
}
int ans = 0;
for (int i = 0; i < words.length - 1; i++) {
for (int j = i + 1; j < words.length; j++) {
if ((temp[i] & temp[j]) == 0){
ans = Math.max(ans,words[i].length() * words[j].length());
}
}
}
return ans;
}
}
方法三：对方法二进行优化
class Solution {
public int maxProduct(String[] words) {
Map map = new HashMap();
int length = words.length;
for (int i = 0; i < length; i++) {
int mask = 0;
String word = words[i];
int wordLength = word.length();
for (int j = 0; j < wordLength; j++) {
mask |= 1 << (word.charAt(j) - 'a');
}
if (wordLength > map.getOrDefault(mask, 0)) {
map.put(mask, wordLength);
}
}
int maxProd = 0;
Set maskSet = map.keySet();
for (int mask1 : maskSet) {
int wordLength1 = map.get(mask1);
for (int mask2 : maskSet) {
if ((mask1 & mask2) == 0) {
int wordLength2 = map.get(mask2);
maxProd = Math.max(maxProd, wordLength1 * wordLength2);
}
}
}
return maxProd;
}
}
