409. Longest Palindrome

Very straightforward solution. Count the frequency for characters in the input string. If a character appears even times, it must be a part of palindrome. On the other hand, if a character appears odd times, then we want to add (odd times - 1). In the end, if there is odd time character, the return value should be added one.

1:  class Solution {  
2:  public:  
3:    int longestPalindrome(string s) {  
4:      unordered_map<char, int> mp;  
5:      for (c : s) mp[c]++;  
6:      int res = 0, odd = 0;  
7:      for (auto it : mp) {  
8:        if (it.second & 1) { res += it.second - 1, odd = 1; }  
9:        else res += it.second;  
10:      }  
11:      return res + odd;  
12:    }  
13:  };  

408. Valid Word Abbreviation

No trick. Pretty straightforward solution. Note when return, we need to check if we've reached both ends of word and it abbreviation.

1:  class Solution {  
2:  public:  
3:    bool validWordAbbreviation(string word, string abbr) {  
4:      int i = 0, j = 0;  
5:      while (i < word.size() && j < abbr.size()) {  
6:        if (!isNum(abbr[j])) {  
7:          if (word[i++] != abbr[j++]) return false;  
8:        } else {  
9:          if (abbr[j] == '0') return false;  
10:          int l = 0;  
11:          while (j < abbr.size() && isNum(abbr[j])) {  
12:            l = l * 10 + abbr[j++] - '0';  
13:          }  
14:          i += l;  
15:        }  
16:      }  
17:      return i == word.size() && j == abbr.size();  
18:    }  
19:    bool isNum(char c) {  
20:      return c >= '0' && c <= '9';  
21:    }  
22:  };  

399. Evaluate Division

I don't have clue to solve the problem. I followed one of the top rated solutions.
The idea is that each equation is a link of graph with value as weight on the link. Note the graph should be directed because given a/b=x it's easy to get b/a=1/x. Therefore, for a query a/c, it is to find a valid path that connects node a and c.

For example, a / b = 3.0, b / c = 2.0, the graph looks like:
a <==> b <==> c. So for query, a/c, the path exists and the value is 3.0 * 2.0 = 6.0. On the other hand, for query c/a, the path also exists and the value is 1 / 3* 1 / 2 = 1 / 6.

The path can be find by DFS. Note, to avoid loop, i.e. a / b * b / a = 1, we need to have a set to cache the visited node.

1:  class Solution {  
2:  public:  
3:    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {  
4:      unordered_map<string, unordered_map<string, double>> mp;  
5:      for (int i = 0; i < equations.size(); i++) {  
6:        mp[equations[i].first].insert(make_pair(equations[i].second, values[i]));  
7:        mp[equations[i].second].insert(make_pair(equations[i].first, 1 / values[i]));  
8:      }  
9:      vector<double> res;  
10:      for (auto q : queries) {  
11:        unordered_set<string> s;  
12:        double tmp = check(mp, q.first, q.second, s);  
13:        if (tmp) res.push_back(tmp);  
14:        else res.push_back(-1);  
15:      }  
16:      return res;  
17:    }  
18:    double check(unordered_map<string, unordered_map<string, double>> &mp, string up, string down, unordered_set<string> &s) {  
19:      if (mp[up].find(down) != mp[up].end()) return mp[up][down];  
20:      for (auto it : mp[up]) {  
21:        if (s.find(it.first) == s.end()) {  
22:          s.insert(it.first);  
23:          double tmp = check(mp, it.first, down, s);  
24:          if (tmp) return it.second * tmp;  
25:        }  
26:      }  
27:      return 0;  
28:    }  
29:  };  

400. Nth Digit

The solution consists of three steps:
- find the length of number that the Nth digit comes from
- find the number that contains Nth digit
- find the Nth digit

Note the variable "count" must be long because "count *= 10" could make it overflow.

1:  class Solution {  
2:  public:  
3:    int findNthDigit(int n) {  
4:      int len = 1;  
5:      long count = 9;  
6:      int start = 1;  
7:      while (n > len * count) {  
8:        n -= len * count;  
9:        len++;  
10:        count *= 10;  
11:        start *= 10;  
12:      }  
13:      start += (n - 1) / len;  
14:      string s = to_string(start);  
15:      return s[(n-1) % len] - '0';  
16:    }  
17:  };  

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

406. Queue Reconstruction by Height

I don't have clue to solve the problem in first place. I followed the top rated solution.
- sort the array by the height in descending order and if heights are the same then sort by the k number in ascending order.
- create an empty array and insert into kth position the sorted people one by one.

1:  class Solution {  
2:  public:  
3:    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {  
4:      auto comp = [](pair<int, int> &p1, pair<int, int> &p2) {  
5:        return (p1.first > p2.first) || (p1.first == p2.first && p1.second < p2.second);  
6:      };  
7:      sort(people.begin(), people.end(), comp);  
8:      vector<pair<int, int>> res;  
9:      for (auto p : people) {  
10:        res.insert(res.begin() + p.second, p);  
11:      }  
12:      return res;  
13:    }  
14:  };