class Solution {
public String addBinary(String a, String b) {
StringBuffer ans = new StringBuffer();
int n = Math.max(a.length(), b.length()), carry = 0;
//倒着加
for (int i = 0; i < n; ++i) {
carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
ans.append(carry % 2 );
carry /= 2;
}
if (carry > 0) {
ans.append('1');
}
ans.reverse();
return ans.toString();
}
}
解法2：
class Solution {
public String addBinary(String a, String b) {
return Integer.toBinaryString(
Integer.parseInt(a, 2) + Integer.parseInt(b, 2)
);
}
}
解法3：
计算当前 x 和 y 的无进位相加结果：answer = x ^ y 相同数字异或=0，0和任何数字异或=数字本身
计算当前 x 和 y 的进位：carry = (x & y) << 1
public class Solution {
public String addBinary(String a, String b) {
int x = Integer.parseInt(a, 2);
int y = Integer.parseInt(b, 2);
while (y != 0) {
int answer = x ^ y;
int carry = (x & y) << 1;
x = answer;
y = carry;
}
return Integer.toBinaryString(x);
}
}
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
int rev =0;
for(int i=0; i<32 && n!=0; i++){
rev |=(n&1)<<(31-i);
n >>>=1;
}
return rev;
}
}
解法2.位运算分治
public class Solution {
private static final int M1 = 0x55555555; // 01010101010101010101010101010101
private static final int M2 = 0x33333333; // 00110011001100110011001100110011
private static final int M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
private static final int M8 = 0x00ff00ff; // 00000000111111110000000011111111
public int reverseBits(int n) {
n = n >>> 1 & M1 | (n & M1) << 1;
n = n >>> 2 & M2 | (n & M2) << 2;
n = n >>> 4 & M4 | (n & M4) << 4;
n = n >>> 8 & M8 | (n & M8) << 8;
return n >>> 16 | n << 16;
}
}
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int cnt=0;
while(n!=0){
cnt += (n & 1);
n >>>= 1;
}
return cnt;
}
}
class Solution {
public int singleNumber(int[] nums) {
int ans=0;
Map<Integer, Integer> map = new HashMap<>();
for(int num : nums){
map.put(num, map.getOrDefault(num,0)+1);
if(map.get(num)==null || map.get(num)<=2){
ans ^=num;
}
}
return ans;
}
}
解法2.依次确定每一个二进制位
答案的第 i 个二进制位就是数组中所有元素的第 i 个二进制位之和除以 3 的余数。
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;
}
}
如何求出 x 呢？我们可以从字典树的根节点开始进行遍历，遍历的「参照对象」为 ai。在遍历的过程中，我们根据 ai的第 x个二进制位是 0 还是 1，确定我们应当走向哪个子节点以继续遍历。假设我们当前遍历到了第 k 个二进制位：
如果 ai 的第 k 个二进制位为 0，那么我们应当往表示 1 的子节点走，这样 0⊕1=1，可以使得 x 的第 k 个二进制位为 1。如果不存在表示 1 的子节点，那么我们只能往表示 0 的子节点走，x 的第 k个二进制位为 0；
如果 ai的第 k 个二进制位为 1，那么我们应当往表示 0 的子节点走，这样 1⊕0=1，可以使得 x 的第 k 个二进制位为 1。如果不存在表示 0 的子节点，那么我们只能往表示 1 的子节点走，x 的第 k 个二进制位为 0。
由于字典树中的每个节点最多只有两个子节点，分别表示 0 和 1，因此本题中的字典树是一棵二叉树。在设计字典树的数据结构时，我们可以令左子节点 left 表示 0，右子节点 right 表示 1。
class Solution {
// 字典树的根节点
Trie root = new Trie();
// 最高位的二进制位编号为 30
static final int HIGH_BIT = 30;
public int findMaximumXOR(int[] nums) {
int n = nums.length;
int x = 0;
//添加一个，check一个，为啥呢？因为i和j是有顺序的，j在i后面。
for (int i = 1; i < n; ++i) {
// 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中
add(nums[i - 1]);
// 将 nums[i] 看作 ai，找出最大的 x 更新答案
x = Math.max(x, check(nums[i]));
}
return x;
}
public void add(int num) {
Trie cur = root;
for (int k = HIGH_BIT; k >= 0; --k) {
int bit = (num >>> k) & 1;
if (bit == 0) {
if (cur.left == null) {
cur.left = new Trie();
}
cur = cur.left;
}
else {
if (cur.right == null) {
cur.right = new Trie();
}
cur = cur.right;
}
}
}
public int check(int num) {
Trie cur = root;
int x = 0;
for (int k = HIGH_BIT; k >= 0; --k) {
int bit = (num >>> k) & 1;
if (bit == 0) {
// a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走
if (cur.right != null) {
cur = cur.right;
x = x * 2 + 1;
} else {
cur = cur.left;
x = x * 2;
}
} else {
// a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走
if (cur.left != null) {
cur = cur.left;
x = x * 2 + 1;
} else {
cur = cur.right;
x = x * 2;
}
}
}
return x;
}
}
class Trie {
// 左子树指向表示 0 的子节点
Trie left = null;
// 右子树指向表示 1 的子节点
Trie right = null;
}
class Solution {
// 最高位的二进制位编号为 30
static final int HIGH_BIT = 30;
public int findMaximumXOR(int[] nums) {
int x = 0;
for (int k = HIGH_BIT; k >= 0; --k) {
Set<Integer> seen = new HashSet<Integer>();
// 将所有的 pre^k(a_j) 放入哈希表中
for (int num : nums) {
// 如果只想保留从最高位开始到第 k 个二进制位为止的部分
// 只需将其右移 k 位
seen.add(num >> k);
}
// 目前 x 包含从最高位开始到第 k+1 个二进制位为止的部分
// 我们将 x 的第 k 个二进制位置为 1，即为 x = x*2+1
int xNext = x * 2 + 1;
boolean found = false;
// 枚举 i
for (int num : nums) {
//判断是否能够异或得到xNext
if (seen.contains(xNext ^ (num >> k))) {
found = true;
break;
}
}
if (found) {
x = xNext;
} else {
// 如果没有找到满足等式的 a_i 和 a_j，那么 x 的第 k 个二进制位只能为 0
// 即为 x = x*2
x = xNext - 1;
}
}
return x;
}
}
DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。
例如，"ACGAATTCCG" 是一个 DNA序列 。
在研究 DNA 时，识别 DNA 中的重复序列非常有用。
给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。
class Solution {
static final int L = 10;
public List<String> findRepeatedDnaSequences(String s) {
List<String> ans = new ArrayList<String>();
Map<String, Integer> cnt = new HashMap<String, Integer>();
int n = s.length();
for (int i = 0; i <= n - L; ++i) {
String sub = s.substring(i, i + L);
cnt.put(sub, cnt.getOrDefault(sub, 0) + 1);
if (cnt.get(sub) == 2) {
ans.add(sub);
}
}
return ans;
}
}
318.最大单词长度乘积
给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
解法：如果可以将判断两个单词是否有公共字母的时间复杂度降低到 O(1)？
由于单词只包含小写字母，共有 26个小写字母，因此可以使用位掩码的最低 26 位分别表示每个字母是否在这个单词中出现。将 a 到 z 分别记为第 0 个字母到第 25 个字母，则位掩码的从低到高的第 i 位是 1 当且仅当第 i 个字母在这个单词中，其中 0≤i≤25 。