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