位运算 算法

2019-01-17  本文已影响0人  YOLO哈哈哈

位运算 算法

-1.与: &
或: |
非: !
异或 : ^ 相同为 0， 不同为 1
int 32 位 -> int 的范围 -2^（31）to 2^ 31 - 1
long 64 位 -> long 的范围 -2^(63) to 2^ 63 -1
=========================================
-2.补码：
-x + 1 是 x 的 补码
2 + 1111111111111111111111111111110 = 0000....0
=========================================
-3. 1 << n = 2 ^ n
n >> x = n/ (2 ^ x )
=========================================
-4. 把array of char 转换成 String -> String.valueOf( arr)
-> new String(arr)
把 array of char 里的一个字符转换Case -> Character.toUpperCase( arr[i] )
-> Character.toLowerCase( arr[i] )
=================================================
-5. "<<" : 左移运算符，num << 1,相当于num乘以2
">>": 右移运算符，num >> 1,相当于num除以2 （如果是负数补位是“1”， 正数补位是“0”）。
">>>": 无符号右移，忽略符号位，空位都以0补齐
=================================================
-6. 二进制状态压缩
操作：                  运算：
取出整数 n 在二进制下的第 k 位 ----> (n >> k) & 1
取出整数 n 在二进制表示下的第 0 ~ k - 1 位（后k位）---> n &（(1 << k) -1）
把整数 n 在二进制表示下的第 k 位取反 ---> n ^( 1 << k)
把整数 n 在二进制表示下的第 k 位赋值1 ---> n | ( 1<< k)
把整数 n 在二进制表示下的第 k 位赋值0 ---> n &( ~( 1 << k ))

题目类型总结：

1.直接问二进制数的相关操作（翻转， 补码，加法， 计算1bit 的总数）
2.字符串的a到z， 或者 A到Z 的matching（前缀树，字符串共同字符）
3.要操作的数字都是2的倍数（判断指数是2或3或4， 二进制表（时间），快速幂算法)
4.寻找二进制数的规律（判断alerting bits, ）

1· 二进制中1 的个数（15 剑指offer ）
public static int NumberOf1(int n) {
    int count = 0;
    while( n ) {
        count ++;
        n = (n- 1) & n;
    }
    return count;
}
2· 数值的整数次方（16 剑指offer ）
public static double PowerWithExp(double base, int exponent){
    if(exponent == 1)
          return base;
    if(exponent == 0)
          return 1;
    double  result = PowerWithExp( base, exponent >> 1 );
    result * = result;
    if((exponent & 0x1)== 1)
          result *= base;
    return result; 
}

public static int int PowerExp(int base, int exponent) {
      int res = 1, tmp = base;
      while(exponent != 0) {
            if( ( exponent & 0x1) == 1) 
                res = res * tmp;
            tmp *= tmp;
            exponent  >>= 1;    
      }
      return res;        
}
3· 算法进阶 a^b % p

3 ^ 1000000
3 ^ 1 = 3
3 ^ 2 = 9
3 ^ 4 = 81
3 ^ 8
3^( 2 ^ 19)=
2^k 次 3 的相乘

import java.util.*;
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int a = in.nextInt() , b = in.nextInt(), c = in.nextInt();
    long res = 1 % p;
    long tmp = a;
    for(; b!= 0; b >> = 1) {
          if( (b & 1 ) == 1) {
              /* (  (a * b) % p = a % p * b % p ) % p */
              res = res * tmp % p ;
          }
          tmp = tmp * tmp % p ;
    }
    System.out.println( res);
}
4· 算法进阶 a * b % p
import java.util.*;

public static void main(String [] args) {
    Scanner in= new Scanner (System.in);
    long a = in.nextInt(), b = in.nextInt(), c = in.nextInt();
    long tmp = a;
    long res = 0 % p;
    while( b != 0) {
        if( ( b & 1) == 1)
            res = (res + tmp ) % p;
        tmp = (tmp + tmp) % p;
        b >> = 1;   
    }
    return res;
}
5· Sum of two Integer(371 leetcode)
public static int getSum(int a, int b) {
    return b == 0 ? a : getSum( a^b, (a & b )<< 1);
}
6·Single Number II (137 leetcode)
class Solution {
      public static int singleNumber(int[] nums) {
        int[] res = new int[32];
        for(int i=0; i<nums.length; i++){
            int tmp = nums[i];
            for(int j=res.length -1 ; j >=0 ;j--){
                res[j] += tmp & 0x1;
                tmp >>= 1; 
            }
        }
        for(int i =0; i<res.length; i++){
            res[i] = res[i] % 3;
        }
        int a = 0;
        for(int i=0  ; i< res.length ; i++){
            a <<= 1;
            a += res[i]; 
        }
        return a;
    }
}

public int singleNumber(int[] nums) {
        int one = 0, two = 0;
        for(int i : nums) {
            one = (one ^ i) & ~two;
            two = (two ^ i) & ~one;
        }
        return one;
    }
7 · Power of Two(231 leetcode)
class Solution {
    public boolean isPowerOfTwo(int n) {
        return n >0 && ( (n &( n-1) )== 0);
        
    }
}
8 · Power of Four(342 leetcode)
  public boolean isPowerOfFour(int num) {
      return num > 0 && (num &(num -1) == 0 ) && ((num & 0x55555555) == num );  
  }
9 · Power of Three (326 leetcode)
public static boolean isPowerOfThree(int n) {
    if(n <= 0)
      return false;
   while( n % 3 == 0) {
        n /= 3;
   }
   return n == 1;
10 · Bitwise AND of Numbers Range (201 leetcode)
public int rangeBitwiseAnd(int m, int n) {
    if( m  == 0)
        return 0;
    int moveFactor = 0 ;
    while( m != n) {
        m >>= 1;
        n >>= 
    }
}
11 · Maximum XOR of Two Numbers in an Array (421 leetcode)

我们可以总结出以下几点：

1.因为整型的位数是固定的，排除第一位符号位，Trie树的高度是常数的，即最高32层（包括root）。
2. 由于只有0 和 1 两个子节点，所以为了节省空间，可以使用 二叉树 的方式（或者数组或 HashMap 均可）
3. 由于是异或，前缀为如果相同，异或值都是0，所以可以先找到第一个 两个字节都不为空的节点当做root。

class Solution{
    class TrieNode{
        int val;
        TrieNode zero, one;
        boolean isEnd;
    }
    class TrieTree{
        TrieNode root;
        public TrieTree() {
            root = new TrieNode();
        }
        public void insert(int num){
            TrieNode cur = root;
            int j = 1 << 30;
            for(int i=0; i<31; i++){
                 /*根据 num 在 j 位置的数目判断应该向 0 还是向 1 */
                  int b = num & j == 0 ? 0 : 1 ;
                  TrieNode node = new TrieNode();
                  if( b == 1  && cur.one == null )
                      cur.one = new TrieNode();
                  if( b == 0 &&  cur.zero == null )
                      cur.zero = new TrieNode();
                  cur = b == 0 ? cur.zero : cur.one;
                  j >> 1;         
            } /* for loop */
            cur.isEnd = true;
            cur.val = num;
        }

        public int findMaximumXOR(int[] nums) {
            if( nums == null || nums.length <= 1)
                return 0;
            TrieTree tree = new TrieTree();
            for(int val : nums){
                  tree.insert(val);  
            }     
            /* 获取真正需要开始判断的root */
             TrieNode cur = tree.root;
            while( cur.one == null || cur.zero == null) {
                 cur = cur.zero == null ? cur.one : cur.zero;
             }
            return maxHelper( cur.zero , cur.one )
        }
/*  分治法， 原则就是使两个分支的高位不同
1. 当1分支的下一位只有1时，找 0 分支的0， 若没有就找1；
2. 当1分支的下一位只有0 时，找 0 分支的1， 若没有就找0；
3. 当1分支的下一位有0  和 1时， 看0 分支， 如果0 分支只有 1 ，则1分支走1，反之走0.
4. 当0，1两个分支均有两个下一位时，尝试【1分支走1，0分支走0】和【1分支走0，0分支走1】两条路线并取最大值
*/
      public int maxHelper(TrieNode zero , TrieNode one) {
          if(zero.isEnd && one.isEnd)
              return zero.val ^ one.val;
           if( one.zero == null)
               return maxHelper( one.one, zero.zero != null ? zero.zero : zero.one  );
            else if(one.one == null)
              return maxHelper( one.zero , zero.one != null ? zero.one : zero.zero);
            else if(zero.zero == null)
                return maxHelper( one.zero, zero.one);
            else if (zero.one == null)
                return maxHelper( one.one, zero.zero);
            else
                return Math.max( maxHelper( zero.one , one.zero ), maxHelper( zero.zero, one.one ));
      }
    }
}
12 · Number Complement (476 leetcode)
 public int findComplement(int num) {
      if(num == 0)
          return 1;
      int mask = 1;
      int ret = 0;
      while( num != 0) {
          if( num & 1 == 0 )
              ret |= mask;
          mask <<= 1;
          num >>= 1;
      }
      return ret;
}
13 · Missing Number (268 leetcode)
public int  missingNumber(int[] nums) {
    if(nums == null)
        return 0;
    int sum = (nums.length + 1)*nums.length/2;
    for(int val : nums) 
        sum -= val;
    return sum;
}
14 · Maximum Product of Word Lengths(318. leetcode)
public int maxProduct(String[] words) {
    if(words == null)
        return 0;
    int[] value = new int[words.length];
    for(int i =0; i< words.length ; i++) {
        for(int j = 0; i < words[i].length; j++) {
            value[i]  |= 1 << (words[i].charAt(j) - 'a');
        }
    }
    int max = 0 ;
    int tmp = 0 ; 
    for(int i =0 ; i<value.length; i++) {
        for(int j = i+1 ; j < value.length; j++) {
            if( (value[i]  & value[j]) == 0) {
                  tmp = words[i].length() * words[j].length();
                  max = max > tmp ? max : tmp;
            }
        }
    }
    return max;
}
15 · Reverse Bits(190. leetcode)
  public int reverseBits(int n) {
      int ret = 0;
      for(int i=0; i<32; i++) {
          ret |= n & 1;
          n  >>= 1; 
          if (i < 31)
              ret <<= 1;
      }
      return ret;
  }
16 · Binary Watch (401. leetcode)

这道题不是很明显的 bit manipulation 的类型问题

public List<String> readBinaryWatch(int num) {
  List res = new ArrayList<String>();
  if(num == null)
    return res;
  generate(num, res, 0,0,0,0);
  return res;
}

public void generate(int n, List<String> res, int hour, int minutes, int i, int j) {
 if(hour > 11 || minutes > 59) return;
 if(n == 0)
  res.add( hour+":" + minutes>10? "": "0" + minutes);
else{
  while(j < 6){
      generate( n-1, res, hour, minutes+ 1 << j, i, j+1);
      j++;
  }
   while(i < 4){
     generate( n-1, res, hour + 1<< i , minutes, i+1, j);
      i++;
    }     
  }  /*else */
}
16 · Integer Replacement(397. leetcode)
 public int integerReplacement(int n) {
   if( n == Integer.MAX_VALUE)
      return 32;
   int ret = 0 ;
    while( n != 1) {
        if( ( n & 1) == 0)
            n >>= 1;
        else {
            if( n == 3 || (n -1 ) % 4 == 0) n--;
            else {
                 n++;
            } 
        }
      ret ++;
    }
    return ret;  
}
17·Binary Number with Alternating Bits (693.leetcode)
  public boolean hasAlternatingBits(int n) {
      int d = n & 1;
      while( (n & 1) == d) {
          d ^= 1;
          n >>= 1;
      }
      return  n == 0;
  }

public boolean hasAlternatingBits(int n) {
    int a = ( n ^ ( n >> 1) );
    return ( a & ( a + 1)) == 0;
}
18· IP to CIDR (751.leetcode)
 public List<String> ipToCIDR(String ip, int range) {
     long x = 0; 
      List<String > list = new ArrayList<String>();
     String[]  ips = ip.split(".");
    /* 把32位的二进制放到 long 里面 */
      for(int i = 0; i < ips.length; i++) {
          x = Integer.parseInt( ips[i]) + ( x << 8);
      } 
      while( range > 0) {
       long step = x & -x;
       while(step > range) step >>= 1；
       list.add( ipToString(x, (int) step) );
       x += step;
      range -= step;
      }
      return list;
 }

public String ipToString( long x, int step) {
    int[] ans = new int[4];
    for(int i=0; i< ans.length; i++) {
      ans[i] = x & 255;
      x >>= 8;
    }
    int len = 32;
    while(step > 1) {
      step >>= 1;
      len --;
    }
  return ans[3] +"."+ ans[2] +"."+ ans[1] +"."+ ans[0] +"\"+len; 
 }
19. Letter Case Permutation (784.leetcode)
public List<String> letterCasePermutation(String S) {
    if(S == null) return new LinkedList<String>();
    Queue<String> queue = new LinkedList<String>();
    queue.offer(S);
    for(int i=0; i< S.length(); i++) {
        if( Character.isDigit(S.charAt(i))); continue;
        int size = queue.size();
        for(int j =0; j<size;j++) {
         String cur = queue.poll();
          int[] curArr = cur.tocharArray();
          curArr[i] = Character.toUpperCase(curArr[i]);
          queue.add(String.valueOf(curArr));
          curArr[i] = Character.toLowerCase(currArr[i]);
          queue.add(String.valueOf(curArr));
        }
    }
    return new LinkedList<>(queue);
}

public List<String> letterCasePermutation(String S)  {
if(S == null ) return null;
List<String> res = new ArrayList<String>();
char[] cur = S.toCharArray();
helper(res, S, 0 );
return res;
}

public void helper(List<String> res , char[] cur, int pos ) {
    if(pos == S.length) {
         res.add( new String(cur));
         return;
    }
    if( Character.isDigit( cur[pos] )) {
        helper( res, cur, pos + 1);
        return;
     }
        cur[pos] = Character.isLowerCase(cur[pos]);
        helper(res, cur, pos +1 );
         
       cur[pos] = Character.isUpperCase(cur[pos]);
       helper(res, cur, pos + 1);
}
20. Bitwise ORs of Subarrays (898.leetcode)
  public int subarrayBitwiseORs(int[] A) {
      Set<Integer> ans = new HashSet();
      Set<Integer> cur = new HashSet();
      cur.add(0);
     for(int x : A) {
          Set<Integer>  cur2 = new HashSet();
         for(int  y : cur) { 
              cur2.add( x | y);
         }  
        cur2.add(x);
        cur = cur2;
        ans.addAll( cur);
     }
    return res;
  }
21. Prime Number of Set Bits in Binary Representation (762.leetcode)

-解题思路：因为所有的数字都是用32个bits 表示，通过计算有几个数的bits 个数是prime number。 所以bits 个数会在[0, 32] 区间内。[0,32] 的区间内 2,3,5,7,9,11,13,17,19,23,29 是prime number。所以可以把这个映射在bits的位置上 0010100010100010101100 -> 665772 (十进制)
2nd,3rd,5th,7th,11th,13th,17th,19th,23rd and 29th bits are 1。
-注意的细节
-1.>> 的优先级 高于 &
-2.L++ 是先算L，然后再++
-3.查看一个小于32 的数字是否存在，可以用一下方法

public int countPrimeSetBits(int L, int R) {
     int res = 0;
      while(L <= R) {
          res += 665772 >> Integer.bitCount(L++) &1;
      }    
      return res;
}
22.Convert a Number to Hexadecimal (405.leetcode)

-主要解决问题：
-1. 把32 位的bits， 拆分到array 里面
-2. 把 array of char 用正确的顺序放到string里面
-3. 把 [10, 15] 隐射到[a,f]
-4.这里最好用 >>> 而不是 >>, 因为当 num 是负数的时候，>> 的补位永远是“1”， 所以while loop 永远不会结束。

public String toHex(int num) {
    char [] map = {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
    String str = "";
    while(num >0) {
        int index = num & 15;
        str = map[index] + str;
        num >>>= 4;
    }
    return str;
}
23.Total Hamming Distance(477.leetcode)

-解题思路：
-这道题提别的做法是，一共是 1 到32 位，,首先 遍历n 个 元素， 之后记录每位有多少个1。这就意味着， 在每一位上有k个1 bit，就说明有 （n-k）个 是在这一位是不一样的， 所以在每一位上就有 k *( n - k) 个 hamming distance 。

public int totalHammingDistance(int[] nums)  {
     int total = 0;
     int mask = 1;
     int bitCount = 0;
      for(int i = 0; i<30;i++) {
          mask <<= i;
          for(int val : nums)
                if((val & mask) == 1) bitCount++;
          total += bitCount * ( nums.length - bitCount);     
          bitCount =0;
      }
      return total;
}
24. Valid Word Abbreviation（408.leetcode）这一题和之后的2题是follow up

-.在比较两个string 的pattern的时候，例如和数字之间的pattern， 可以用O（n）解决。 一个是 detail string ， 还有一个是 abbrev string
-解题思路： 直接 遍历其中的abbev string ， 然后一一对照word string 检查。

public boolean  validWordAbbreviation(String word, String abbr) {
    int n = word.length(), index =0, num=0;
    for(int i=0; i<abbr.length(); i++) {
        char ch = abbr.charAt(i);
        if( Character.isDigit(ch)) {
            if( ch == '0' && (i ==0 ||  !Character.isDigit(abbr.charAt(i-1))))
                return false;
            num = num * 10 + (ch - '0');
        }
        else{
            index += num;
            num =0;
            if(index >= word.length() || word.charAt(index) != ch)
                return false;
           index ++;
        }
      index += num;
     return index == n;
    }    
}
25. Generalized Abbreviation（ 320.leetcode）这一题是medium 难度[ 这题还是不太明白]
class Solution {
    public List<String> generateAbbreviations(String word){
        List<String> ret = new ArrayList<String>();
        backtrack(ret, word, 0, "", 0);

        return ret;
    }

    private void backtrack(List<String> ret, String word, int pos, String cur, int count){
        if(pos==word.length()){
            if(count > 0) cur += count;
            ret.add(cur);
        }
        else{
           
            backtrack(ret, word, pos + 1, cur, count + 1); 
            
           
            backtrack(ret, word, pos+1, cur + (count>0 ? count : "") + word.charAt(pos), 0);
        }
    }
}
26. Minimum Unique Word Abbreviation（411.leetcode）这一题是hard 难度[ 这题还是不太明白]
上一篇 下一篇

猜你喜欢

热点阅读