417. Pacific Atlantic Water Flow

We should start from the boundary of the matrix to see if they can reach the other ocean. So it is a typical DSF problem. For DSF problem, we need to have a visited matrix. The trick here is right on the visited matrix. The value in visited matrix is no long bool now. It should use bit to represent the ocean. We can have 0b01 to be pacific and 0b10 to be atlantic. So only when visited becomes 0b11, we know the element is able to reach both oceans.

1:  class Solution {  
2:  private:  
3:    int rows, cols;  
4:    vector<pair<int,int>> res;  
5:    vector<vector<int>> visited;  
6:    vector<pair<int,int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  
7:  public:  
8:    vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {  
9:      if (matrix.empty()) return res;  
10:      rows = matrix.size(), cols = matrix[0].size();  
11:      visited = vector<vector<int>>(rows, vector<int>(cols, 0));  
12:      for (int i = 0; i < rows; i++) {  
13:        dfs(matrix, i, 0, INT_MIN, 1); // 1 is pacific  
14:        dfs(matrix, i, cols-1, INT_MIN, 2); // 2 is atlatic  
15:      }  
16:      for (int j = 0; j < cols; j++) {  
17:        dfs(matrix, 0, j, INT_MIN, 1);  
18:        dfs(matrix, rows-1, j, INT_MIN, 2);  
19:      }  
20:      return res;  
21:    }  
22:    void dfs(vector<vector<int>> &matrix, int i, int j, int prev, int ocean) {  
23:      if (i<0||j<0||i==rows||j==cols||matrix[i][j]<prev||(visited[i][j]&ocean)==ocean) return;  
24:      visited[i][j] |= ocean;  
25:      if (visited[i][j] == 3) res.push_back(make_pair(i, j));  
26:      for (int d = 0; d < dir.size(); d++) {  
27:        int ii = i + dir[d].first;  
28:        int jj = j + dir[d].second;  
29:        dfs(matrix, ii, jj, matrix[i][j], visited[i][j]);  
30:      }  
31:    }  
32:  };  

389. Find the Difference

The naive way is to sort the two strings and find the different character. The code is very straightforward.

1:  class Solution {  
2:  public:  
3:    char findTheDifference(string s, string t) {  
4:      sort(s.begin(), s.end());  
5:      sort(t.begin(), t.end());  
6:      int i = 0;  
7:      for (; i < s.size(); i++) {  
8:        if (s[i] != t[i]) break;  
9:      }  
10:      return t[i];  
11:    }  
12:  };  

However, this problem is actually equivalent to the problem of "136. Single Number".

1:  class Solution {  
2:  public:  
3:    char findTheDifference(string s, string t) {  
4:      char res = 0;  
5:      for (c : s) res ^= c;  
6:      for (c : t) res ^= c;  
7:      return res;  
8:    }  
9:  };  

401. Binary Watch

The idea behind is to enumerate all possible combinations and count the bit of 1. If the bits number matches the input, then output the time.

1:  class Solution {  
2:  public:  
3:    vector<string> readBinaryWatch(int num) {  
4:      vector<string> res;  
5:      for (int h = 0; h < 12; h++) {  
6:        for (int m = 0; m < 60; m++) {  
7:          if (countBits((h << 6) | m) == num) {  
8:            res.push_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m));  
9:          }  
10:        }  
11:      }  
12:      return res;  
13:    }  
14:    int countBits(int n) {  
15:      int count = 0;  
16:      while (n) {  
17:        n &= n-1;  
18:        count++;  
19:      }  
20:      return count;  
21:    }  
22:  };  

393. UTF-8 Validation

The idea is count bytes first and validate the following bytes.

1:  class Solution {  
2:  public:  
3:    bool validUtf8(vector<int>& data) {  
4:      int c = 0;  
5:      for (int d : data) {  
6:        if (c == 0) {  
7:          if ((d >> 7) == 0) c = 0;  
8:          else if ((d >> 5) == 0b110) c = 1;  
9:          else if ((d >> 4) == 0b1110) c = 2;  
10:          else if ((d >> 3) == 0b11110) c = 3;  
11:          else return false;  
12:        } else {  
13:          if ((d >> 6) != 0b10) return false;  
14:          c--;  
15:        }  
16:      }  
17:      return c == 0;  
18:    }  
19:  };  

201. Bitwise AND of Numbers Range

I brute force the problem in first place but I got TLE. Then I had to look at the problem closely. Look at 7,8,9,10,11,12,13,14 which have binary representation 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110. You'll find that the smallest number cancels the largest number's more significant bits.  And also, the adjacent number cancels the least significant bits which means, as long as a number is larger than the other, the least significant bit will get cancelled. So we can keep moving the least significant bits out and recall the function itself recursively until the two numbers are equal. The rest bits that the two equal number shares will be the result.

1:  class Solution {  
2:  public:  
3:    int rangeBitwiseAnd(int m, int n) {  
4:      return n > m ? (rangeBitwiseAnd(m>>1, n>>1)<<1) : m;  
5:    }  
6:  };  

137. Single Number II

The comment in the code explains the solution clearly.

1:  class Solution {  
2:  public:  
3:    int singleNumber(vector<int>& nums) {  
4:      int one = 0, two = 0, three = 0;  
5:      for (int i = 0; i < nums.size(); i++) {  
6:        two |= one & nums[i]; // get the bits that appears twice  
7:        one ^= nums[i]; // cancel the bits that appears twice  
8:        three = one & two; // get the bits that appears three times  
9:        one ^= three; // cancel the bits that appears three times  
10:        two ^= three; // cancel the bits that appears three times  
11:      }  
12:      return one;  
13:    }  
14:  };  

268. Missing Number

This idea comes from the problem of "136. Single Number", i.e. xor cancels the same number. So we can xor all the numbers from 0 to n first. And then xor the numbers in the input array. The remaining number must be the missing number.

1:  class Solution {  
2:  public:  
3:    int missingNumber(vector<int>& nums) {  
4:      int n = nums.size();  
5:      int res = 0;  
6:      for (int i = 0; i <= n; i++) {  
7:        res ^= i;  
8:      }  
9:      for (int i = 0; i < nums.size(); i++) {  
10:        res ^= nums[i];  
11:      }  
12:      return res;  
13:    }  
14:  };  

260. Single Number III

The idea is to get a mixed one first by xor all numbers. Then get the first bit 1 from the right to left in the mixed number which means that single1 differs single2 in that bit. And then scan the array again using this bit to differentiate single1 and single2.

1:  class Solution {  
2:  public:  
3:    vector<int> singleNumber(vector<int>& nums) {  
4:      int mixed = 0, single1 = 0, single2 = 0;  
5:      for (int i = 0; i < nums.size(); i++) {  
6:        mixed ^= nums[i];  
7:      }  
8:      int j = 1;  
9:      while ((mixed & j) == 0) j <<= 1;  
10:      for (int i = 0; i < nums.size(); i++) {  
11:        if (nums[i] & j) single1 ^= nums[i];  
12:      }  
13:      single2 = mixed ^ single1;  
14:      return vector<int>{single1, single2};  
15:    }  
16:  };  

136. Single Number

1 xor 1 = 0, 1 xor 0 = 1. So XOR operator will cancel a number if it appears twice. So this problem can be solve by xor all the numbers and the one left will be the one that appears once.

1:  class Solution {  
2:  public:  
3:    int singleNumber(vector<int>& nums) {  
4:      int single = 0;  
5:      for (int n : nums) {  
6:        single ^= n;  
7:      }  
8:      return single;  
9:    }  
10:  };  

338. Counting Bits

My intuition is to count bits for each number. So the total run time is O(32*n). However, if we look at binary representation closely,  "0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111", we'll see that once we reach a multiple of 2 say 2^n, its right bits just repeat all the numbers from 0 to 2^n-1. So we can program dynamically.

1:  class Solution {  
2:  public:  
3:    vector<int> countBits(int num) {  
4:      int shift = 0;  
5:      vector<int> res(num+1, 0);  
6:      int i = 1, j = 0;  
7:      while (i <= num) {  
8:        for (int j = 0; i <= num && j <(1<<shift); i++,j++) {  
9:          res[i] = res[j]+1;  
10:        }  
11:        shift++;  
12:      }  
13:      return res;  
14:    }  
15:  };  

266. Palindrome Permutation

I was thinking to traverse the buckets twice. First round is to count the number of each character. The second round is to count the number of odds. If odds is less than 2, return true. Otherwise, return false.
The top rated solution combine the two rounds into one round but actually the same running time.

1:  class Solution {  
2:  public:  
3:    bool canPermutePalindrome(string s) {  
4:      vector<int> chars(256, 0);  
5:      int odd = 0;  
6:      for (char c : s) {  
7:        odd += ++chars[c] & 1 ? 1 : -1;  
8:      }  
9:      return odd < 2;  
10:    }  
11:  };  

231. Power of Two

Look at binary of an integer. If an integer is a power of two, it must contains only one "1" in its binary. Also, all the negative integers and zero are not power of two.

1:  class Solution {  
2:  public:  
3:    bool isPowerOfTwo(int n) {  
4:      if (n <= 0) return false;  
5:      while (!(n & 1)) {  
6:        n >>= 1;  
7:      }  
8:      return !(n >> 1) ? true : false;  
9:    }  
10:  };  

The following solution is inspired by counting number of ones in a integer.

1:  class Solution {  
2:  public:  
3:    bool isPowerOfTwo(int n) {  
4:      return n > 0 && (n & (n - 1)) == 0;  
5:    }  
6:  };  

29. Divide Two Integers

Let's see what we should do if we want 3 to divide 18 where 18 is dividend and 3 is divisor.
(1) We subtract 3 from 18 and we get 15. 15 is larger than 3, so we shift 3 to the left by 1 bit and we get 6 which means we have 2 of 3s.
(2) We subtract 6 from 18 again and we get 12. 12 is larger than 6, so we shift 6 to the left by 1 bit again and we get 12 which means we have 4 of 3s.
(3) We subtract 12 from 18 and we get 6. Now 6 is less than 12, so we stop here and add the 4 to the result and subtract 12 from 18 as new dividend and start from 3 again as divisor. Now we go back to step (1) again. At the end, we'll get 2 so the final result is 4+2 = 6.

When implementing, we should be careful about overflow. Since -INT_MIN will be overflowed, so we can't simply flip the sign for dividend or divisor if they are negative, for example at line 6 and 7.
We should either assign dvd by casted long long dividend or do labs(dividend).

1:  class Solution {  
2:  public:  
3:    int divide(int dividend, int divisor) {  
4:      if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX;  
5:      int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;  
6:      long long dvd = labs(dividend);  
7:      long long dvs = labs(divisor);  
8:      int res = 0;  
9:      while (dvd >= dvs) {  
10:        long long multiple = 1;  
11:        long long temp = dvs;  
12:        while (dvd >= (temp << 1)) {  
13:          multiple <<= 1;  
14:          temp <<= 1;  
15:        }  
16:        dvd -= temp;  
17:        res += multiple;  
18:      }  
19:      return sign == -1 ? -res : res;  
20:    }  
21:  };