algBitMap

发表于 | 更新于: | 分类于

CF558C Amr and Chemistry

每个元素可以乘2 除2 变成相同元素的最少操作数
思路：相当于可以左移1，右移1
记录每个数字到变成每个数字的最小步数，而且变成的这个数一定是<=最大的数的

输入：
3
3 5 6
输出：
5


内存超

318 ！Maximum Product of Word Lengths 字符串数组中不共享字符的字符串长度的乘积

find the maximum value of length(word[i]) * length(word[j])
输入: [“abcw”,”baz”,”foo”,”bar”,”xtfn”,”abcdef”]
输出: 16
解释: 这两个单词为 “abcw”, “xtfn”。

不会
思路：每个字符串表示成一个【26位的int】，如果这两个int & 是0，表示没有重合的位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int maxProduct(String[] words) {
    int n = words.length;
    int[] map = new int[n];
    for(int i =0;i<n;i++){
        for(char c : words[i].toCharArray()){
            map[i] |= (1<<(c-'a'));
        }
    }
    int max = 0;      
    for(int i =0;i<n-1;i++){
        for(int j = i+1;j < n;j++){
            if((map[i] & map[j]) == 0){
                max = Math.max(max,words[i].length() * words[j].length());
            }
        }
    }
    return max;
}

868 Binary Gap 二进制1的间距

输入：22
输出：2
解释：
22 的二进制是 0b10110 。
在 22 的二进制表示中，有三个 1，组成两对连续的 1 。
第一对连续的 1 中，两个 1 之间的距离为 2 。
第二对连续的 1 中，两个 1 之间的距离为 1 。
答案取两个距离之中最大的，也就是 2 。

260 Single Number III 两个数字只出现一次，其它出现2次

Input: [1,2,1,3,2,5]
Output: [3,5]

137 Single Number II 所有数字都出现3次，只有一个出现1次

Input: [0,1,0,1,0,1,99]
Output: 99

三进制不进位加法
不会

1
2
3
4
5
6
7
8
public int singleNumber(int[] A) {
    int ones = 0, twos = 0;
    for(int i = 0; i < A.length; i++){
        ones = (ones ^ A[i]) & ~twos;
        twos = (twos ^ A[i]) & ~ones;
    }
    return ones;
}

190 Reverse Bits 逆序二进制位

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000

不熟练

1
2
3
4
5
6
7
8
public int reverseBits(int n) {
  int rst = 0;
  for(int i = 0;i<32;i++){
        rst <<= 1;
        rst  += (n>>>i)&1;  
    }
    return rst;
}

191 Number of 1 Bits 十进制数int有几个二进制1

Input: 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three ‘1’ bits.

熟练

1
2
3
4
5
6
7
8
9
public int hammingWeight(int n) {
    int cnt =0;
    while(n!=0){
        n = n&(n-1);
        n>>>=1;
        cnt++;
    }
    return cnt;
}

1
2
3
4
5
6
7
8
9
10
11
12
int bitcount(unsigned int n)
{
unsigned int tmp;

tmp = n
    - ((n >> 1) & 033333333333)
    - ((n >> 2) & 011111111111);

tmp = (tmp + (tmp >> 3)) & 030707070707

return (tmp%63);
}

268 Missing Number 0-n个数字放进长度n-1的数组，少了哪个

Input: [3,0,1]
Output: 2

熟练 位运算

1
2
3
4
5
6
7
8
public int missingNumber(int[] nums) {
    int n = nums.length;
    int rst = n;
    for(int i =0;i<n;i++){
        rst ^= i^nums[i];
    }
    return rst;
}

89 !Gray Code 格雷编码

两个连续的数值仅有一个位数的差异。

Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

不会
G(i) = i^ (i/2)

1
2
3
4
5
6
7
public List<Integer> grayCode(int n) {
   List<Integer> rst = new ArrayList<>();
    for(int i =0;i<(1<<n);i++){
        rst.add(i^(i>>>1));
    }
    return rst;
}

回溯？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int num = 0;
public List<Integer> grayCodeBack(int n) {
    List<Integer> rst = new ArrayList<>();
    backtrack(rst, n );
    return rst;
}

private void backtrack(List<Integer> rst,int n){
    if(n ==0){
        rst.add(num );
        return;
    }
   else{
        backtrack(rst, n-1);
        num ^= (1<< n-1);
        backtrack(rst, n-1);
    }
}

338 !Counting Bits 数1-num各数分别有几个1

Input: 2
Output: [0,1,1]

不会
0 1 1 2 2 3
0 1 2 3 4 5
如果偶数，f[n] = f[n/2] // 4：100 2：010
如果奇数f[n] = f[n/2]+1 // 1：001 3：011

1
2
3
4
5
6
7
public int[] countBits(int num) {
    int[] cnt = new int[num+1];
    for(int i = 0;i<num+1;i++){
        cnt[i] = cnt[i/2] + i%2;
    }
    return cnt;
}

371 !!Sum of Two Integers 不用加减求和

Input: a = 1, b = 2
Output: 3

不会x2

1
2
3
4
5
6
public int getSum(int a, int b) {
    int rst = a^b;
    int carry = (a&b)<<1;
    if(carry!=0)return getSum(rst,carry);
    return rst;
}

201 ！Bitwise AND of Numbers Range 闭区间所有数字的与

输入: [0,1] [m,n]
输出: 0

不会
公共左边的部分。去掉n最右边的1,直到n<=m

1
2
3
4
public int rangeBitwiseAnd(int m, int n) {
    while(m<n) n = n & (n-1);
    return n;
}

393. ！UTF-8 Validation

1
2
3
4
5
6
7
Char. number range  |        UTF-8 octet sequence
   (hexadecimal)    |              (binary)
--------------------+---------------------------------------------
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

data = [197, 130, 1], 表示 8 位的序列: 11000101 10000010 00000001.
返回 true 。
这是有效的 utf-8 编码，为一个2字节字符，跟着一个1字节字符。

不会
思路：先确定第一个int应该后面带几个10开头的，然后数后面能不能-到0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean validUtf8(int[] data) {
    int cnt = 0;
    for(int d :data){
        if(cnt == 0){
            if((d >> 5)==0b110)cnt = 1;
            else if((d >> 4) == 0b1110)cnt = 2;
            else if((d >> 3) == 0b11110) cnt = 3;
            else if((d >> 7) == 1)return false;
        }else {
            if((d >> 6)!=0b10)return false;
            cnt--;
        }
    }
    return cnt == 0;
}

136 Single Number 都出现2次，数组中只出现一次的数字

Input: [4,1,2,1,2]
Output: 4

方法2：数学：都出现2次 没想到
$$2(a+b+c)-(a+a+b+b+c)$$
2*sum(set(list))-sum(list)

方法1：异或 0^12=12,12^12=0 位运算比较熟练

1
2
3
4
5
6
7
public int singleNumber(int[] nums) {
    int rst = nums[0];
    for(int i = 1;i<nums.length;i++){
        rst ^= nums[i];           
    }
    return rst;
}

389 Find the Difference 两个字符串打乱后多余的字符

String t is generated by random shuffling string s and then add one more letter at a random position.
Input:
s = “abcd”
t = “abcde”
Output:
e

位运算：
‘b’异或两次同一个字符，会回到原来的。
异或自己变成0，再异或一个其它字符就是赋值。

1
2
3
4
5
6
7
8
9
public char findTheDifference(String s, String t) {
    int n = t.length();
    char c = t.charAt(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        c ^= s.charAt(i);
        c ^= t.charAt(i);
    }
    return c;
}

正常做法：熟练

展开代码
1
2
3
4
5
6
7
8
9
10
11
12
public char findTheDifference(String s, String t) {
    int[] cnt = new int[26];
    for(int i =0;i<t.length();i++){
        if(i < s.length())
        cnt[s.charAt(i)-'a']++;
        cnt[t.charAt(i)-'a']--;
    }
    for(int i =0;i<26;i++){
        if(cnt[i] < 0)return (char)(i+'a');
    }
    return ' ';
}