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:  };  

187. Repeated DNA Sequences

My intuition of this problem is pattern match. However, after reading the problem more carefully, I realized it can be done by assistance of hash table. What I do is to keep a 10 letters window and then move the window to right.

1:  class Solution {  
2:  public:  
3:    vector<string> findRepeatedDnaSequences(string s) {  
4:      unordered_map<string, int> map;  
5:      vector<string> res;  
6:      if (s.size() < 10) return res;  
7:      for (int i = 0; i <= s.size()-10; i++) {  
8:        string ss = s.substr(i, 10);  
9:        if (map.find(ss) == map.end()) map[ss] = 1;  
10:        else if (map[ss] == 1) {  
11:          res.push_back(ss);  
12:          map[ss]++;  
13:        };  
14:      }  
15:      return res;  
16:    }  
17:  };  

This can pass but the performance is not very good (beat 31.4%).  Let's look at the hex number of ASCII code for 'A' (0x41), 'C' (0x43), 'G' (0x47) and 'T' (0x54). It's easy to see the last 3 bits for these four letters are different (subtract letters by multiple of 16), where A is 001, C is 010, G is 111 and T is 110. Considering the string length is only 10 letters long, so the hash key can be represented by an integer which has 32 bits in total.

1:  class Solution {  
2:  public:  
3:    vector<string> findRepeatedDnaSequences(string s) {  
4:      unordered_map<int, int> map;  
5:      vector<string> res;  
6:      if (s.size() < 10) return res;  
7:      int key = 0, i = 0;  
8:      while (i < 9) {  
9:        key = key << 3 | s[i++] & 0x7;  
10:      }  
11:      while (i < s.size()) {  
12:        key = key << 3 & 0x3FFFFFFF | s[i++] & 0x7;  
13:        if (map[key]++ == 1) {  
14:          res.push_back(s.substr(i-10, 10));  
15:        }  
16:      }  
17:      return res;  
18:    }  
19:  };  

289. Game of Life

My naive way is to create a new matrix to compute the updated board. And then dump the values from the new matrix to the board.

1:  class Solution {  
2:  public:  
3:    void gameOfLife(vector<vector<int>>& board) {  
4:      int rows = board.size();  
5:      int cols = board[0].size();  
6:      vector<vector<int>> res(rows, vector<int>(cols, 0));  
7:      for (int i = 0; i < rows; i++) {  
8:        for (int j = 0; j < cols; j++) {  
9:          int lives = 0;  
10:          for (int ii = max(0, i-1); ii <= min(rows-1, i+1); ii++) {  
11:            for (int jj = max(0, j-1); jj <= min(cols-1, j+1); jj++) {  
12:              if ((ii != i || jj != j) && board[ii][jj] == 1) lives++;  
13:            }  
14:          }  
15:          if (lives < 2 || lives > 3) res[i][j] = 0;  
16:          else if (lives == 3) res[i][j] = 1;  
17:          else res[i][j] = board[i][j];  
18:        }  
19:      }  
20:      for (int i = 0; i < rows; i++) {  
21:        for (int j = 0; j < cols; j++) {  
22:          board[i][j] = res[i][j];  
23:        }  
24:      }  
25:    }  
26:  };  

The top voted solution updates the board in position. Since the life in the board is actually just one bit. We can use the second bit for the update state and make a one right shift to get the updated board.

1:  class Solution {  
2:  public:  
3:    void gameOfLife(vector<vector<int>>& board) {  
4:      int row = board.size();  
5:      if (row == 0) return;  
6:      int col = board[0].size();  
7:      if (col == 0) return;  
8:      vector<pair<int,int>> dir = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};  
9:      for (int i = 0; i < row; i++) {  
10:        for (int j = 0; j < col; j++) {  
11:          int lives = 0;  
12:          for (int d = 0; d < dir.size(); d++) {  
13:            int ii = i + dir[d].first;  
14:            int jj = j + dir[d].second;  
15:            if (ii < 0 || ii == row || jj < 0 || jj == col) continue;  
16:            if ((board[ii][jj] & 0x1) == 1) lives++;  
17:          }  
18:          if ((board[i][j] & 0x1)== 0 && lives == 3) {  
19:            board[i][j] |= 0x2;  
20:          } else if (lives == 2 || lives == 3) {  
21:            board[i][j] |= board[i][j] << 1;  
22:          }  
23:        }  
24:      }  
25:      for (int i = 0; i < row; i++) {  
26:        for (int j = 0; j < col; j++) {  
27:          board[i][j] >>= 1;  
28:        }  
29:      }  
30:    }  
31:  };  

318. Maximum Product of Word Lengths

I used bucket to hash the letters in first place but I got the TLE.

1:  class Solution {  
2:  public:  
3:    int maxProduct(vector<string>& words) {  
4:      unordered_map<string, vector<int>> mp;  
5:      for (int i = 0; i < words.size(); i++) {  
6:        vector<int> bucket(26, 0);  
7:        for (int j = 0; j < words[i].size(); j++) {  
8:          bucket[words[i][j]-'a'] = 1;  
9:        }  
10:        mp[words[i]] = bucket;  
11:      }  
12:      int res = 0;  
13:      for (int i = 0; i < words.size(); i++) {  
14:        for (int j = i+1; j < words.size(); j++) {  
15:          int k = 0;  
16:          for (; k < 26; k++) {  
17:            if (mp[words[i]][k] && mp[words[j]][k]) break;  
18:          }  
19:          if (k == 26) res = max(res, (int)words[i].size() * (int)words[j].size());  
20:        }  
21:      }  
22:      return res;  
23:    }  
24:  };  

A trick here is the problem explicitly says that all letters in the words will be low case. Since there are 26 letters, we can use integer which has 32bits as a letter mask for each word.

1:  class Solution {  
2:  public:  
3:    int maxProduct(vector<string>& words) {  
4:      vector<int> masks(words.size(), 0);  
5:      for (int i = 0; i < words.size(); i++) {  
6:        for (int j = 0; j < words[i].size(); j++) {  
7:          masks[i] |= 1 << (words[i][j]-'a');  
8:        }  
9:      }  
10:      int res = 0;  
11:      for (int i = 0; i < words.size(); i++) {  
12:        for (int j = 0; j < i; j++) {  
13:          if (!(masks[i] & masks[j])) {  
14:            res = max(res, (int)(words[i].size()*words[j].size()));  
15:          }  
16:        }  
17:      }  
18:      return res;  
19:    }  
20:  };