231. Power of Two

https://leetcode.com/problems/power-of-two/description/
Solution 1.
    bool isPowerOfTwo(int n) {
        if(n<=0) return false;
        int p = 0;
        while(n){
            p += (n & 1);
            n >>= 1;
        }
        if(p == 1) return true;
        return false;
    }
Solution 2.
    bool isPowerOfTwo(int n) {
        if(n<=0) return false;
        return !(n&(n-1));
    }

326. Power of Three

https://leetcode.com/problems/power-of-three/description/
Solution 0. A number is power of 3 if  it is a factor of the largest number of power of 3.
    bool isPowerOfThree(int n) {
        if (n<=0) return false;
        int t = pow(3,(int)(log(INT_MAX)/log(3)));
        return (t%n == 0);
    }
Solution 1. Use loop
    bool isPowerOfThree(int n) {
        if(n==0) return false;
        while(n%3 == 0) {
            n /= 3;
        }
        if(n==1) return true;
        return false;
    }

107. Binary Tree Level Order Traversal II

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/
Solution 1. Recursive level traversal. Need to add a {} to res to increase res.size() when starting a new level, otherwise res[level] causes index error.
    void levelOrder(TreeNode* node, vector<vector<int>>& res, int level) {
        if(!node) return;
        if(level == res.size()) res.push_back({});
        res[level].push_back(node->val);
        levelOrder(node->left, res, level+1);
        levelOrder(node->right, res, level+1);
    }
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        levelOrder(root, res, 0);
        reverse(res.begin(), res.end());
        return res;
    }
Solution 2. Push each level to a queue. Use nullptr as a separator between levels.
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        TreeNode* node;
        q.push(root);
        q.push(nullptr);
        while(!q.empty()) {
            vector<int> level;
            while(node = q.front()){
                q.pop();
                level.push_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            q.pop();
            q.push(nullptr);
            if(level.empty()) break;
            res.insert(res.begin(),level);
        }
        return res;
    }

645. Set Mismatch

https://leetcode.com/problems/set-mismatch/description/
Solution 0. Use XOR and count numbers
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int> cnt(nums.size(),0);
        vector<int> res = {0, 0};
        for(int i=0; i<nums.size(); i++) {
            if(++cnt[nums[i]-1] == 2)
                res[0] = nums[i];
            res[1] ^= (i+1)^nums[i];
        }
        res[1] ^= res[0];
        return res;
    }
Solution 1.  Sort by putting nums[i] at index nums[i]-1
   vector<int> findErrorNums(vector<int>& nums) {
        for(int i=0; i<nums.size(); i++) {
            while(nums[i] != nums[nums[i]-1]) swap(nums[i], nums[nums[i]-1]);
        }
        for(int i=0; i<nums.size(); i++) {
            if(nums[i] != i+1) return {nums[i], i+1};
        }
    }

Solution 2. Use bitset
    vector<int> findErrorNums(vector<int>& nums) {
        bitset<10000> bits(0);
        vector<int> res;
        for(auto n: nums) {
            if(bits.test(n-1)) res.push_back(n);
            else bits.set(n-1);
        }
        for(int i=0; i<bits.size(); i++) {
            if(!bits[i]) {
                res.push_back(i+1);
                break;
            }
        }
        return res;
    }

572. Subtree of Another Tree

https://leetcode.com/problems/subtree-of-another-tree/description/
Solution 1. Compare s to t, if they are not identical, then compare subtrees of s to t.
    bool isIdentical(TreeNode*s, TreeNode* t) {
        if(!s && !t) return true;
        if(!s || !t) return false;
        if(s->val != t->val) return false;
        return isIdentical(s->left, t->left) && isIdentical(s->right, t->right);
    }
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!t) return true;
        if(!s) return false;
        if(isIdentical(s, t)) return true;
        return isSubtree(s->left, t) || isSubtree(s->right, t);
    }
Solution 1.1. Only compare t to the subtrees of s that have same depth as t.
class Solution {
    vector<TreeNode*> vd;
public:
    int getDepth(TreeNode* s, int d){
        if(!s) return 0;
        int depth = 1 + max(getDepth(s->left, d), getDepth(s->right, d));
        if(depth == d) {
            vd.push_back(s);
        }
        return depth;
    }
    bool isIdentical(TreeNode*s, TreeNode* t) {
        if(!s && !t) return true;
        if(!s || !t || s->val != t->val) return false;
        return isIdentical(s->left, t->left) && isIdentical(s->right, t->right);
    }
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!t) return true;
        if(!s) return false;
        getDepth(s, getDepth(t, -1));
        for(TreeNode* n: vd){
            if(isIdentical(n, t)) return true;
        }
        return false;
    }

};
Solution 2. Convert tree to string and compare
    void traversal(TreeNode* node, vector<string>& s) {
        if(!node) {
            s.push_back("#"); return;
        }
        s.push_back(to_string(node->val));
        traversal(node->left, s);
        traversal(node->right, s);
    }
    bool isSub(vector<string>& s, vector<string>& t) {
        if(s.size()<t.size()) return false;
        for(int i=0; i<s.size();i++){
            if(s[i]!=t[0]) continue;
            for(int ii=i, j=0; ii<s.size() && j<t.size(); ii++, j++) {
                if(s[ii]!=t[j]) break;
                if(j==t.size()-1) return true;
            }
        }
        return false;
    }
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!t) return true;
        if(!s) return false;
        vector<string> ss, ts;
        traversal(s, ss);
        traversal(t, ts);
        return isSub(ss, ts);
    }

594. Longest Harmonious Subsequence

https://leetcode.com/problems/longest-harmonious-subsequence/description/
Solution 1. Use a map
    int findLHS(vector<int>& nums) {
        if(nums.size()==0) return 0;
        map<int,int> cnt;
        for(int n : nums)
            cnt[n]++;
        int prevNum = 0, prevCnt = 0;
        int res = 0, tmp = 0;
        for(pair<int,int> p: cnt) {
            if(prevCnt && p.first == prevNum+1) {
                tmp = p.second + prevCnt;
                res = res>tmp? res:tmp;
            }
            prevNum = p.first;
            prevCnt = p.second;
        }
        return res;
    }
Solution 2. Fast but tedious (beat 97%)
    int findLHS(vector<int>& nums) {
        if(nums.size() < 2) return 0;
        sort(nums.begin(), nums.end());
        int cur = nums[0], prevNum = nums[0], prevCnt = 0, cnt = 0;
        int res = 0;
        for(int n: nums) {
            if(n == cur) {
                cnt++;
                continue;
            }
            if(prevNum + 1 == cur)
                res = res>(prevCnt+cnt)? res: (prevCnt+cnt);
            prevCnt = cnt;
            prevNum = cur;
            cur = n;
            cnt = 1;
        }
        if(prevNum + 1 == cur)
            res = res>(prevCnt+cnt)? res: (prevCnt+cnt);
        return res;
    }
Or simplify the code by adding an additional number at the end.
    int findLHS(vector<int>& nums) {
        if(nums.size() < 2) return 0;
        sort(nums.begin(), nums.end());
        nums.push_back(nums.back()+1);
        int cur = nums[0], prevNum = nums[0], prevCnt = 0, cnt = 0, res = 0;
        for(int n: nums) {
            if(n == cur) {
                cnt++;
                continue;
            }
            if(prevNum + 1 == cur)
                res = res>(prevCnt+cnt)? res: (prevCnt+cnt);
            prevCnt = cnt;
            prevNum = cur;
            cur = n;
            cnt = 1;
        }
        return res;
    }

202. Happy Number

https://leetcode.com/problems/happy-number/description/
Solution 1. Chasing
    inline int squareSum(int n) {
        int n2=0;
        while(n){
            n2 += pow(n%10, 2);
            n /= 10;
        }
        return n2;
    }
    bool isHappy(int n) {
        int slow, fast;
        slow = fast = n;
        do {
            slow = squareSum(slow);
            fast = squareSum(fast);
            fast = squareSum(fast);
        } while(slow != fast);
        if (slow == 1) return 1;
        else return 0;
    }
Solution 2. Use a map to store the square sums. If a sum is already in the map, return false.
    bool happy(int n, unordered_map<int,int> &mp){
        if(n==1) return true;
        if(mp[n]) return false;
        mp[n]++;
        int n2=0;
        while(n){
            n2 += pow(n%10, 2);
            n /= 10;
        }
        return happy(n2, mp);
    }
    bool isHappy(int n) {
        unordered_map<int,int> mp;
        return happy(n, mp);
    }

405. Convert a Number to Hexadecimal

https://leetcode.com/problems/convert-a-number-to-hexadecimal/description/

Solution 2.
    string toHex(int num) {
        if(num==0) return "0";
        vector<char> dict {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
        string res;
        for(int i=0;i<8 && num;i++){
            res = dict[num & 15] + res;
            num >>= 4;
        }
        return res;
    }

121. Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/
Solution
    int maxProfit(vector<int>& prices) {
        if(prices.size()<2) return 0;
        int b = prices[0], p = 0;
        for(int i=1; i<prices.size();i++) {
            p = max(prices[i] - b, p);
            if(prices[i]<b) b = prices[i];
        }
        return p;
    }

415. Add Strings

https://leetcode.com/problems/add-strings/description/
Solution 1. Use the input string to store the result.
    string addStrings(string num1, string num2) {
        if(num1.size() < num2.size()) return addStrings(num2, num1);
        int i = num1.size()-1, j = num2.size()-1, c = 0, t = 0;
        for(; i>=0 && (j>=0 || c); j--, i--) {
            t = num1[i] - '0' + (j>=0 ? num2[j] -'0' : 0) + c;
            num1[i] = t%10 + '0';
            c = t/10;
        }
        return (c? "1":"") + num1;
    }
Solution 2.
    string addStrings(string num1, string num2) {
        if(num1.size() < num2.size()) return addStrings(num2, num1);
        string res;
        int i, j, c = 0, t=0;
        for(j=num2.size()-1, i=num1.size()-1; j>=0; j--, i--) {
            t = num2[j] - '0' + num1[i] -'0' + c;
            res = to_string(t%10) + res;
            c = t/10;
        }
        while(i>=0) {
            t = num1[i] - '0' + c;
            res = to_string(t%10) + res;
            c = t/10;
            i--;
        }
        if(c)
            res = to_string(c) + res;
        return res;
    }

108. Convert Sorted Array to Binary Search Tree

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/
Solution 1. (19 ms)
    TreeNode* array2bst(vector<int>& nums, int i, int j) {
        if(i>j) return nullptr;
        int m = (i+j)/2;
        TreeNode* node = new TreeNode(nums[m]);
        node->left = array2bst(nums, i, m-1);
        node->right = array2bst(nums, m+1, j);
        return node;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return array2bst(nums, 0, nums.size()-1);
    }
Solution 2. (19 ms)
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size()==0) return nullptr;
        int m = nums.size()/2;
        TreeNode* node = new TreeNode(nums[m]);
        vector<int> nl(nums.begin(), nums.begin()+m);
        vector<int> nr(nums.begin()+m+1,nums.end());
        node->left = sortedArrayToBST(nl);
        node->right = sortedArrayToBST(nr);
        return node;

    }

543. Diameter of Binary Tree

https://leetcode.com/problems/diameter-of-binary-tree/description/
Solution 1. (9 ms)
    int maxDepth(TreeNode* node, int &mxDia) {
        if(!node) return 0;
        int dl = 0;
        if(node->left) {
            dl = maxDepth(node->left, mxDia) + 1;
        }
        int dr = 0;
        if(node->right) {
            dr = maxDepth(node->right, mxDia) + 1;
        }
        mxDia = max(dl + dr, mxDia);
        return max(dl, dr);
    }
    int diameterOfBinaryTree(TreeNode* root) {
        int mxDia = 0;
        maxDepth(root, mxDia);
        return mxDia;
    }
Solution 2. Similar to 1 (12 ms)
    int maxDepth(TreeNode* node, int &mxDia) {
        if(!node) return 0;
        int dl = maxDepth(node->left, mxDia);
        int dr = maxDepth(node->right, mxDia);
        mxDia = max(dl + dr, mxDia);
        return max(dl, dr) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        int mxDia = 0;
        maxDepth(root, mxDia);
        return mxDia;
    }
Solution 3. (19 ms)
    int depth(TreeNode* node) {
        if(!node) return 0;
        return max(depth(node->left), depth(node->right)) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        int dia = depth(root->left) + depth(root->right);
        return max(dia, max(diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right)));
    }

541. Reverse String II

https://leetcode.com/problems/reverse-string-ii/description/
Solution 1.
    string reverseStr(string s, int k) {
        for(int i=0; i<s.size(); i += 2*k) {
            reverse(s.begin()+i, min(s.begin()+i+k, s.end()));
        }
        return s;
    }
Solution 2.
    string reverseStr(string s, int k) {
        for(int i=0; i<s.size(); i += 2*k) {
            for(int m=i, n=min(i+k-1, (int)s.size()-1);m<n;m++,n--) {
                swap(s[m], s[n]);
            }
        }
        return s;
    }

551. Student Attendance Record I

https://leetcode.com/problems/student-attendance-record-i/description/
Solution 1.
    bool checkRecord(string s) {
        int A = 0;
        int L = 0;
        for(int i=0; i<s.size(); i++) {
            if(s[i] == 'A') { A++; if(A==2) return false;}
            if(s[i] == 'L') {
                L++;
                if(L==3) return false;
                continue;
            }
            L = 0;
        }
        return true;
    }

268. Missing Number

https://leetcode.com/problems/missing-number/description/
Solution 1. 
    int missingNumber(vector<int>& nums) {
        int res = 0;
        for(int i=0; i<nums.size(); i++) {
            res ^= (i ^ nums[i]);
        }
        return res^nums.size();
    }
Solution 2.
    int missingNumber(vector<int>& nums) {
        vector<int> s(nums.size()+1, -1);
        for(int i=0; i<nums.size(); i++) {
            s[nums[i]] = 1;
        }
        for(int i=0; i<s.size(); i++) {
            if(s[i] == -1) return i;
        }
        return -1;
    }

504. Base 7

https://leetcode.com/problems/base-7/description/
Solution 1.
    string convertToBase7(int num) {
        if(num == 0) return "0";
        string res;
        int x = abs(num);
        while(x) {
            res = to_string(x % 7) + res;
            x /= 7;
        }
        return (num>0 ? "":"-")+res;
    }

350. Intersection of Two Arrays II

https://leetcode.com/problems/intersection-of-two-arrays-ii/description/
Solution 1. Use a map
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        unordered_map<int,int> cnt;
        for(int i=0; i<nums1.size(); i++) {
            cnt[nums1[i]]++;
        }
        for(int j=0; j<nums2.size(); j++) {
            if(cnt[nums2[j]]-- > 0) res.push_back(nums2[j]);
        }
        return res;
    }
Solution 2.
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        for(int i=0, j=0; i<nums1.size()&&j<nums2.size();) {
            if(nums1[i] == nums2[j]) {
                res.push_back(nums1[i]);
                i++;
                j++;
            }
            else if(nums1[i]<nums2[j]) i++;
            else j++;
        }
        return res;
    }

401. Binary Watch

https://leetcode.com/problems/binary-watch/description/
Solution 1. Loop through hour and minute, check the total bits
    vector<string> readBinaryWatch(int num) {
        vector<string> res;
        for(int h=0; h<12; h++) {
            for(int m=0; m<60; m++) {
                if(bitset<10> (h<<6 | m).count() == num)
                   res.push_back(to_string(h) + ":" + (m<10 ? "0":"") + to_string(m));
            }
        }
        return res;
    }
Solution 2. Get all possible numbers with num bits
    void combination(int n, int N, int s, vector<int>& c) {
        if(n>N || n==0) return;
        if(n==1) {
            for(int i=0;i<N;i++) {
                c.push_back(s + (1<<i));
            }
            return;
        }
        combination(n, N-1, s, c);
        combination(n-1, N-1, s + (1<<(N-1)), c);
    }
    vector<string> readBinaryWatch(int num) {
        if(num == 0) return vector<string> {"0:00"};
        vector<string> res;
        vector<int> c;
        combination(num, 10, 0, c);
        for(auto x : c) {
            int m = x & 15;
            int s = x >> 4;
            if(m<12 && s<60) res.push_back(to_string(m) + ":" + (s<10? "0":"") + to_string(s));
        }
        return res;
    }

628. Maximum Product of Three Numbers

https://leetcode.com/problems/maximum-product-of-three-numbers/description/
Solution 1. O(n) version of Solution 2.
    int maximumProduct(vector<int>& nums) {
        int N = nums.size();
        int mx1 = INT_MIN, mx2 = INT_MIN, mx3 = INT_MIN, mi1 = INT_MAX, mi2 = INT_MAX;
        for(int n : nums) {
            if(n>mx1){
                mx3 = mx2;
                mx2 = mx1;
                mx1 = n;
            }
            else if(n>mx2) {
                mx3 = mx2;
                mx2 = n;
            }
            else if(n>mx3) {
                mx3 = n;
            }
            if(n<mi1) {
                mi2 = mi1;
                mi1 = n;
            }
            else if(n<mi2){
                mi2 = n;
            }
        }
        return max(mx1*mx2*mx3, mx1*mi1*mi2);
    }
Solution 2.
    int maximumProduct(vector<int>& nums) {
        int N = nums.size();
        sort(nums.begin(),nums.end());
        if(nums[0]>=0 || nums[N-1]<=0) return nums[N-1]*nums[N-2]*nums[N-3]; //could skip this
        // the maximum would be the bigger one of the two cases:
        return max(nums[0]*nums[1]*nums[N-1], nums[N-1]*nums[N-2]*nums[N-3]);
    }

447. Number of Boomerangs

https://leetcode.com/problems/number-of-boomerangs/description/
Solution 1. 
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int d, res = 0;
        for(auto &x : points) {
            unordered_map<int,int> vm(points.size());
            for(auto &y : points) {
                d = pow(x.first - y.first, 2) + pow(x.second - y.second, 2);
                res += 2 * vm[d]++;
            }
        }
        return res;
    }
Solution 2.
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int d, res = 0;
        for(int i=0; i<points.size(); i++) {
            unordered_map<int,int> vm(points.size());
            for(int j=0; j<points.size(); j++) {
                d = pow(points[i].first - points[j].first, 2) + pow(points[i].second - points[j].second, 2);
                vm[d]++;
            }
            for(auto &x: vm){
                res += x.second * (x.second - 1);
            }
        }
        return res;
    }

409. Longest Palindrome

https://leetcode.com/problems/longest-palindrome/description/
Solution 1.
    int longestPalindrome(string s) {
        int cnt['z'+1] = {0};
        int res = 0;
        for(int i=0; i<s.size(); i++) {
            cnt[s[i]]++;
        }
        for(int i=0; i<='z'; i++){
                res += (cnt[i]& ~1);
        }
        return res + (res < s.size()); // there is odd when (res < s.size())
    }

Solution 2. slower
    int longestPalindrome(string s) {
        int cnt['z'+1] = {0};
        int res = 0;
        int odd = 0;
        for(int i=0; i<s.size(); i++) {
            cnt[s[i]]++;
        }
        for(int i=0; i<='z'; i++){
            if(cnt[i]%2==0)
                res += cnt[i];
            else {
                res += cnt[i] - 1;
                odd = 1;
            }
        }
        return res + odd;
    }

661. Image Smoother

https://leetcode.com/problems/image-smoother/description/
Solution 0. Use the bits at the same address to store the sum and counts
    vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
        int L = M.size();
        int W = M[0].size();

        for(int i=0;i<L;i++){
            for(int j=0;j<W;j++){
                for(int m=i-1;m<=i+1;m++) {
                    for(int n=j-1;n<=j+1;n++) {
                        if(m>=0 && m<L && n>=0 && n<W) {
                            // bits 0~7: 255 = 11111111b
                            // original value = M[m][n] & 255
                            // bits 8~11: counts 
                            // 256 = 100000000b
                            // bits 12~ : sum
                            M[i][j] += 256 + ((M[m][n]&255) << 12);
                        }
                    }
                }
            }
        }
        for(int i=0;i<L;i++){
            for(int j=0;j<W;j++){
                // 15 = 1111b, use & to get the counts
                M[i][j] = (M[i][j]>>12)/((M[i][j]>>8) & 15);
            }
        }
        return M;
    }
Solution 1. A boring solution.

206. Reverse Linked List

Solution 1. Iterative method
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* node = head;
        while(node){
            head = node;
            node = node->next;
            head->next = prev;
            prev = head;
        }
        return head;

    }
Solution 2. Recursion
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* node = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return node;

    }
Solution 2. With the help of a stack
    ListNode* reverseList(ListNode* head) {
        stack<ListNode*> st;
        ListNode* node = head;
        while(node){
            st.push(node);
            node = node->next;
        }
        if(head) {
            head = st.top();
            node = head;
            st.pop();
        }
        while(!st.empty()) {
            node->next = st.top();
            st.pop();
            node = node->next;
        }
        if(node) node->next = nullptr;
        return head;
    }

13. Roman to Integer

https://leetcode.com/problems/roman-to-integer/description/
Solution 1. Use a map
    int romanToInt(string s) {
        unordered_map<char, int> R2I = {
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}
        };
        int res = 0;
        for(int i=0; i<s.size();i++) {
            if(i+1<s.size() && R2I[s[i]]<R2I[s[i+1]])
                res -= R2I[s[i]];
            else
                res += R2I[s[i]];
        }
        return res;
    }

Solution 2. Convert each char in s to the corresponding number first.
    int romanToInt(string s) {
        int res = 0;
        int nums[s.size()];
        for(int i=0; i<s.size();i++) {
            switch(s[i]){
                case 'I': nums[i] = 1; break;
                case 'V': nums[i] = 5; break;
                case 'X': nums[i] = 10; break;
                case 'L': nums[i] = 50; break;
                case 'C': nums[i] = 100; break;
                case 'D': nums[i] = 500; break;
                case 'M': nums[i] = 1000; break;
            }
        }
        for(int i=0; i<s.size();i++) {
            if(i+1<s.size() && nums[i]<nums[i+1])
                res -= nums[i];
            else
                res += nums[i];
        }
        return res;
    }

217. Contains Duplicate

https://leetcode.com/problems/contains-duplicate/description/
Solution 1. Use a map.
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int,int> m;
        for(int n: nums) {
            m[n]++;
            if(m[n]==2) return true;
        }
        return false;
    }

242. Valid Anagram

https://leetcode.com/problems/valid-anagram/description/
Solution 1. Use array as map.
    bool isAnagram(string s, string t) {
        if(s.size()!=t.size()) return false;
        int cnt[26] = {0};
        for(int i=0; i<s.size();i++){
           // do the counting in one loop
            cnt[s[i]-'a']++;
            cnt[t[i]-'a']--;
        }
        for(int i=0;i<26;i++){
            if(cnt[i] != 0) return false;
        }
        return true;
    }
Solution 2. Compare sorted string.
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return(s==t);
    }

100. Same Tree

https://leetcode.com/problems/same-tree/description/
Try to simplify the code.
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p || !q) return p == q;
        return 
            (p->val == q->val) &&
            isSameTree(p->left, q->left) && 
            isSameTree(p->right, q->right);
    }

C++ priority_queue

http://en.cppreference.com/w/cpp/container/priority_queue

A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.

A user-provided Compare can be supplied to change the ordering, e.g. using std::greater<T> would cause the smallest element to appear as the top().

Working with a priority_queue is similar to managing a heap in some random access container, with the benefit of not being able to accidentally invalidate the heap.

506. Relative Ranks

https://leetcode.com/problems/relative-ranks/description/
Solution 1. Lambda expression.
    vector<string> findRelativeRanks(vector<int>& nums) {
        int N = nums.size();
        if(N==0) return vector<string> {};
        vector<int> rank2idx(N);
        vector<string> res(N);

        for(int i=0; i < N; i++) rank2idx[i] = i;
        sort(rank2idx.begin(), rank2idx.end(), [&](int i, int j){return nums[i]>nums[j];});
        for(int i=3; i < N; i++) {
            res[rank2idx[i]] = to_string(i+1);
        }
        if(N>0) res[rank2idx[0]] = "Gold Medal";
        if(N>1) res[rank2idx[1]] = "Silver Medal";
        if(N>2) res[rank2idx[2]] = "Bronze Medal";
        return res;
    }

Solution 2.  Using a map.
    vector<string> findRelativeRanks(vector<int>& nums) {
        map<int, int, greater<int>> score2idx;
        vector<string> res(nums.size());
        for(int i=0;i<nums.size();i++){
            score2idx[nums[i]] = i;
        }
        int i=1;
        for(auto &x: score2idx) {
            if(i==1) res[x.second] = "Gold Medal";
            else if(i==2) res[x.second] = "Silver Medal";
            else if(i==3) res[x.second] = "Bronze Medal";
            else res[x.second] = to_string(i);
            i++;
        }
        return res;
    }
Solution 3. Use a priority_queue
    vector<string> findRelativeRanks(vector<int>& nums) {
        priority_queue<pair<int,int>> q;
        vector<string> res(nums.size());
        for(int i=0;i<nums.size();i++){
            q.push(make_pair(nums[i],i));
        }
       
        for(int i=0; i<nums.size();i++) {
            auto x = q.top();
            if(i==0) res[x.second] = "Gold Medal";
            else if(i==1) res[x.second] = "Silver Medal";
            else if(i==2) res[x.second] = "Bronze Medal";
            else res[x.second] = to_string(i+1);
            q.pop();
        }
        return res;
    }

compare

map<int, int, greater<int>>

sort(nums.begin(),nums.end(), greater<int>());

387. First Unique Character in a String

https://leetcode.com/problems/first-unique-character-in-a-string/description/
Solution 1. Use int array as hash table.
    int firstUniqChar(string s) {
        int m[26+'a'] = {0};
        for(auto c : s){
            m[c]++;
        }
        for(int i=0; i<s.size();i++){
            if(m[s[i]]==1) return i;
        }
        return -1;
    }
Solution 2. Use hash table.
    int firstUniqChar(string s) {
        unordered_map<char,int> m;
        for(int i=0;i<s.size();i++){
            m[s[i]]++;
        }
        for(int i=0;i<s.size();i++){
            if(m[s[i]]==1) return i;
        }
        return -1;
    }

169. Majority Element

https://leetcode.com/problems/majority-element/description/
Solution 1. Use Boyer–Moore majority vote algorithm.
http://shxi.blogspot.com/2017/11/boyermoore-majority-vote-algorithm.html
Make use of the fact that the majority element appears more than n/2 times. Keep track of the element value and count when looping the array. Increase the count each time when get the same value and decrease the count when get a different value. When the count is 0, change the value to the new element. Because the majority element appears more than n/2 times, the value kept after looping is always the majority element with count larger than 0.
    int majorityElement(vector<int>& nums) {
        int res = nums[0], cnt = 1;
        for(int i=1; i<nums.size(); i++){
            if(cnt == 0){
                res = nums[i];
                cnt = 1;
            }
            else if(nums[i] == res)
                cnt++;
            else
                cnt--;
        }
        return res;
    }

Solution 2. Use map to count for each element
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> m;
        int mx = 0, res = 0;
        for(int n: nums)
            m[n]++;
        for(auto const& x: m) {
            if(mx < x.second) {
                mx = x.second;
                res = x.first;
            }
        }
        return res;
    }

Loop through map

https://stackoverflow.com/questions/26281979/c-loop-through-map
Loop through a map:

map<string, int>::iterator it; for ( it = symbolTable.begin(); it != symbolTable.end(); it++ ) { std::cout << it->first // string (key) << ':' << it->second // string's value << std::endl ; } With C++11 ( and onwards ), for (auto const& x : symbolTable) { std::cout << x.first // string (key) << ':' << x.second // string's value << std::endl ; } With C++17 ( and onwards ), for( auto const& [key, val] : symbolTable ) { std::cout << key // string (key) << ':' << val // string's value << std::endl ; }