刷题记录

Problem: According to the  Wikipedia's article : "The  Game of Life , also known simply as  Life , is a cellular automaton devised by the British mathematician John Horton Conway in 1970." Given a  board  with  m  by  n  cells, each cell has an initial state  live  (1) or  dead  (0). Each cell interacts with its  eight neighbors  (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article): Any live cell with fewer than two live neighbors dies, as if caused by under-population. Any live cell with two or three live neighbors lives on to the next generation. Any live cell with more than three live neighbors dies, as if by over-population.. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction. Write a function to compute the next state (after one update) of the board given its current state.  The next state is created ...

Problem: Reverse bits of a given 32 bits unsigned integer. Example: Input: 43261596 Output: 964176192 Explanation: 43261596 represented in binary as 00000010100101000001111010011100 ,   return 964176192 represented in binary as 00111001011110000010100101000000 . Analysis: skip Solution: public class Solution { // you need treat n as an unsigned value public int reverseBits ( int n) { int res = 0 ; for ( int i = 0 ; i < 32 ; i ++ ) { if ((n & 1 ) == 1 ) { res = (res << 1 ) + 1 ; } else { res = res << 1 ; } n = n >> 1 ; } return res; } }

Problem: Given an integer, write a function to determine if it is a power of two. Analysis: Base 2 representation of 2 is 10, 4 is 100, 8 is 1000.    100 &011 --------   000 If a number is power of 2, it qualifies the property that n & (n - 1) == 0 Solution:    class Solution { public boolean isPowerOfTwo ( int n) { return n > 0 && (n & (n - 1 )) == 0 ; } }

Problem: Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. For example, given the range [5, 7], you should return 4. Analysis: 8 4 2 1 --------------- 5 | 0 1 0 1 6 | 0 1 1 0 7 | 0 1 1 1 m has the fewest 1 prefix, n has the most 1 prefix. Need to find the common 1 prefix. So clear n's last 1 one by one until n <= m; Solution: class Solution { public int rangeBitwiseAnd ( int m, int n) { while (n > m) { n = n & (n - 1 ); } return m & n; } }

Set bit: n |= 1 << i Clear bit: n &= ~(1<<i) Test bit: (n>>i) & 1 Clear last 1: n & (n - 1)

Problem: The  Hamming distance  between two integers is the number of positions at which the corresponding bits are different. Now your job is to find the total Hamming distance between all pairs of the given numbers. Example: Input: 4, 14, 2 Output: 6 Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). So the answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6. Note: Elements of the given array are in the range of  0  to  10^9 Length of the array will not exceed  10^4 Analysis: 4:     0 1 0 0 14:   1 1 1 0 2:     0 0 1 0 1:     0 0 0 1 Count bit by bit. Take look at the first bit. There is one 1. The hamming distance for first bit is 3. one 1 to three 0. Second bit has two 1, hamming distance is 4. one 1 to two 0 twice. We can conclude that the hamming di...

Problem: The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer  n  representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. For example, given  n  = 2, return  [0,1,3,2] . Its gray code sequence is: 00 - 0 01 - 1 11 - 3 10 - 2 Note: For a given  n , a gray code sequence is not uniquely defined. For example,  [0,2,3,1]  is also a valid gray code sequence according to the above definition. For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that. Analysis: We can conclude from the above image that, n can get from  n - 1. n == 1, code is 0, 1. Add 0 to front we have 00, 01. Then add 1 to front and reverse the code, we get 11, 10. Thus we have n == 2's code: 00, 01, 11, 10. Solution: class Solution { public List< Integer > grayCode ( i...

Problem: Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the  Hamming weight ). For example, the 32-bit integer ’11' has binary representation  00000000000000000000000000001011 , so the function should return 3. Analysis: To determine ith bit in n is 1: 1 & (n >> i) Solution: public class Solution { // you need to treat n as an unsigned value public int hammingWeight ( int n) { int count = 0 ; for ( int i = 0 ; i < 32 ; i ++ ) { count += ( 1 & (n >> i)); } return count; } }

Problem: Given an array containing  n  distinct numbers taken from  0, 1, 2, ..., n , find the one that is missing from the array. Example 1 Input: [3,0,1] Output: 2 Example 2 Input: [9,6,4,2,3,5,7,0,1] Output: 8 Analysis: Similar to single number. If we have [0,1,3], then XOR with the complete set [0,1,2,3], we can get 2. Solution: class Solution { public int missingNumber ( int [] nums) { int res = nums . length; for ( int i = 0 ; i < nums . length; i ++ ) { res ^ = i ^ nums[i]; } return res; } }

The  Hamming distance  between two integers is the number of positions at which the corresponding bits are different. Given two integers  x  and  y , calculate the Hamming distance. Note: 0 ≤  x ,  y  < 2 31 . Example: Input: x = 1, y = 4 Output: 2 Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ The above arrows point to positions where the corresponding bits are different. Analysis: XOR x and y, can set the diff digit to be 1. Then count 1s in xor. Solution: class Solution { public int hammingDistance ( int x, int y) { int count = 0 , xor = x ^ y; for ( int i = 0 ; i < 32 ; i ++ ) { count += ( 1 & (xor >> i) ); } return count; } }

Problem: Given a string array  words , find the maximum value of  length(word[i]) * length(word[j])  where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0. Example 1: Given  ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"] Return  16 The two words can be  "abcw", "xtfn" . Example 2: Given  ["a", "ab", "abc", "d", "cd", "bcd", "abcd"] Return  4 The two words can be  "ab", "cd" . Example 3: Given  ["a", "aa", "aaa", "aaaa"] Return  0 No such pair of words. Analysis: Convert string to bit, just record the occurrence of char. abc should be 00111, ab should be 00011. If there is a char in string, the char - 'a' th bit in mask integer should be 1.  If t...

Problem: Given two strings  s  and  t  which consist of only lowercase letters. String  t  is generated by random shuffling string  s  and then add one more letter at a random position. Find the letter that was added in  t . Example: Input: s = "abcd" t = "abcde" Output: e Explanation: 'e' is the letter that was added. Analysis: solution 1: use int[256] map, count s, subtract in t. 字符串的对比首先就要想到int[256] map. solution 2: similar to single number, the added char appears only once, others twice. class Solution { 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; } }

Problem: Given an array of integers, every element appears  twice  except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Analysis: Use XOR, because any number XOR itself is 0. We can set result's initial value to 0, 0 XOR any number is that number.  Solution: class Solution { public int singleNumber ( int [] nums) { int res = 0 ; for ( int n : nums) { res ^ = n; } return res; } }

3/20/2018 update: 这道题另外一种解法真是太难了。看不懂，性价比超低。 Analysis: Use array [14,14,14,9] as an example. Translate every number to binary, we can get: 1110 1110 1110 1001 ------- 4331 and sum up each position, we can get the result binary from %3 on each position. Solution: class Solution { public int singleNumber(int[] nums) { int[] A = new int[32]; int result = 0; for(int i = 0; i < 32; i++) { int count = 0; for(int j = 0; j < nums.length; j++) { // count nums[j] at position A[i] if(((nums[j] >> i) & 1) == 1) { count++; } } if(count > 0) { result |= (count%3) << i; } } return result; } }

Problem: Calculate the sum of two integers  a  and  b , but you are  not allowed  to use the operator  +  and  - . Example: Given  a  = 1 and  b  = 2, return 3. 3/22/2017 update: See example below: Use XOR, we can get the bits without carry, use & we can get carry before shift left by 1.  class Solution { public int getSum ( int a, int b) { while (b != 0 ) { int carry = a & b; a = a ^ b; b = carry << 1 ; } return a; } } Analysis : Shift a&b to left by 1 bit makes carry of a+b. a^b means a+b without considering carry. Solution: class Solution { public int getSum(int a, int b) { while (b!=0) { int _a = a ^ b; int _b = (a & b) << 1; a = _a; b = _b; } return a; } }