563. Binary Tree Tilt

https://leetcode.com/problems/binary-tree-tilt/description/
Solution 1. Recursive post order traversal.
    void tilt(TreeNode *node, int &s, int &st) {
        if(!node) return;
        int sl=0, sr=0;
        tilt(node->left, sl, st);
        tilt(node->right, sr, st);
        s = node->val + sl + sr;
        st += abs(sl-sr);
    }
    int findTilt(TreeNode* root) {
        int s = 0, st = 0;
        tilt(root, s, st);
        return st;
    }
or
    int tilt(TreeNode *node, int &st) {
        if(!node) return 0;
        int sl = tilt(node->left, st);
        int sr = tilt(node->right, st);
        st += abs(sl-sr);
        return node->val + sl + sr;
    }
    int findTilt(TreeNode* root) {
        int st = 0;
        tilt(root, st);
        return st;
    }
Solution 2. Iterative post order traversal. Using maps to save the sums and tilts of the sub-tree at a particular node. (much slow by using the maps)

599. Minimum Index Sum of Two Lists

https://leetcode.com/problems/minimum-index-sum-of-two-lists/description/
Solution 1. Hash table
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        unordered_map<string,int> m;
        vector<string> res;
        int least = INT_MAX, s;
        for(int i=0;i<list1.size();i++) {
            m[list1[i]] = i;
        }
        for(int i=0;i<list2.size();i++) {
            if(m.count(list2[i])) {
                s = i+m[list2[i]];
                if( s == least) {
                    res.push_back(list2[i]);
                }
                else if(s < least){
                    res.clear();
                    res.push_back(list2[i]);
                    least = s;
                }
            }
        }
        return res;
    }

657. Judge Route Circle

https://leetcode.com/problems/judge-route-circle/description/

    bool judgeCircle(string moves) {
        int h=0, v=0;
        for(int i=0;i<moves.size();i++) {
            switch (moves[i]) {
                case 'R': h++; break;
                case 'L': h--; break;
                case 'U': v++; break;
                case 'D': v--; break;
            }
        }
        return h==0 && v==0;
    }

404. Sum of Left Leaves

https://leetcode.com/problems/sum-of-left-leaves/description/
Solution 1. Recursive tree traversal, use a bool to indicate if the node is the left branch.
    void inOrder(TreeNode*node, int &s, bool left) {
        if(!node) return;
        if(node->left) inOrder(node->left, s, true);
        if(left && !node->left && !node->right) s += node->val;
        if(node->right) inOrder(node->right, s, false);
    }
    int sumOfLeftLeaves(TreeNode* root) {
        int s=0;
        inOrder(root, s, false);
        return s;
    }
Solution 2. Iterative tree traversal.
    int sumOfLeftLeaves(TreeNode* root) {
        if(!root) return 0;
        int s=0;
        bool isLeft = false;
        TreeNode* node = root;
        stack<TreeNode*> st;
        st.push(node);
        while(!st.empty()){
            node = st.top();
            st.pop();
            if(isLeft && !node->left && !node->right) {
                s += node->val;
                isLeft = false;
                continue;
            }
            if(node->right) {
                st.push(node->right);
                isLeft = false;
            }
            if(node->left) {
                st.push(node->left);
                isLeft = true;
            }
        }
        return s;
    }

122. Best Time to Buy and Sell Stock II

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

    }

167. Two Sum II - Input array is sorted

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
Solution 1. Use two pointers to search the array
   vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> res;
        for(int i=0,j=numbers.size()-1;i<j;) {
            if(numbers[i]+numbers[j] == target) {
                res={i+1,j+1};
                break;
            }
            else if(numbers[i]+numbers[j] < target) i++;
            else j--;
        }
        return res;
    }
Solution 2. Construct a map from value to its index
    vector<int> twoSum(vector<int>& numbers, int target) {
        unordered_map<int,int> m;
        for(int i=0; i<numbers.size();i++) {
            if(m.find(target-numbers[i])!=m.end())
                return vector<int> {m[target-numbers[i]]+1,i+1};
            m[numbers[i]] = i;
        }
    }

575. Distribute Candies

https://leetcode.com/problems/distribute-candies/description/
Solution 1. use int array for hash
    int distributeCandies(vector<int>& candies) {
        if(candies.empty()) return 0;
        int count = 0;
        int sz = candies.size();
        // when hash[i] = 1, candy type i in candies.
        int hash[200001] = {0};
        for(int i=0; i<sz; i++) {
            if(!hash[candies[i]+100000] ) {
                count++;
                hash[candies[i]+100000] = 1;
            }
        }
        return min(count,sz/2);
    }

Solution 2. use bitset for hash
    int distributeCandies(vector<int>& candies) {
        if(candies.empty()) return 0;
        int count = 0;
        int sz = candies.size();
        // when hash[i] = 1, candy type i in candies.
        bitset<200001> hash;
        for(int i: candies) {
            if(!hash.test(i+100000) ) {
                count++;
                hash.set(i+100000);
            }
        }
        return min(count, sz/2);
    }

455. Assign Cookies

https://leetcode.com/problems/assign-cookies/description/
Solution 1. sort and match
 int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int res = 0;
        for(int i=0,j=0;i<g.size()&&j<s.size();) {
            if(g[i]<=s[j]) {
                i++;j++;res++;
            }
            else
               j++;
        }
        return res;
    }

171. Excel Sheet Column Number

https://leetcode.com/problems/excel-sheet-column-number/description/

    int titleToNumber(string s) {
        int res = 0;
        int n = 1;
        for(int i=s.size()-1;i>=0;i--) {
            res += n*(s[i]-'A' + 1);
            n *= 26;
        }
        return res;
    }

383. Ransom Note

https://leetcode.com/problems/ransom-note/description/
Solution 1. construct a map:  char -> nums of appearance 
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> m(26);
        for(int i = 0; i < magazine.size(); i++) {
            ++m[magazine[i]];
        }
        for(int i = 0; i < ransomNote.size(); i++) {
            --m[ransomNote[i]];
            if(m[ransomNote[i]]<0) return false;
        }
        return true;
    }
Solution 2. use a vector for the map (fastest)
    bool canConstruct(string ransomNote, string magazine) {
        vector<int> m(26+'a',0);
        for(char c: magazine) {
            ++m[c];
        }
        for(char c: ransomNote) {
            if(--m[c]<0) return false;
        }
        return true;
    }

Solution 3. sort and compare (much slower).
    bool canConstruct(string ransomNote, string magazine) {
        int i, j;
        sort(ransomNote.begin(),ransomNote.end());
        sort(magazine.begin(),magazine.end());
        if(ransomNote.size()>magazine.size()) return false;
        for( i=0,j=0;i<ransomNote.size()&&j<magazine.size();) {
            if(ransomNote[i] == magazine[j]) {
                i++;
                j++;
            }
            else if(ransomNote[i]<magazine[j]) return false;
            else j++;
        }
        return i==ransomNote.size();
    }

530. Minimum Absolute Difference in BST

https://leetcode.com/problems/minimum-absolute-difference-in-bst/description/
Solution 1. Construct a vector by an in-order traversal and then run through the vector.
    void inOrder(TreeNode*node, vector<int>&a) {
        if(!node) return;
        if(node->left) inOrder(node->left, a);
        a.push_back(node->val);
        if(node->right) inOrder(node->right, a);
    }
    int getMinimumDifference(TreeNode* root) {
        vector<int> a;
        int dmin = INT_MAX;
        inOrder(root, a);
        for(int i=1; i<a.size(); i++) {
            dmin = min(dmin, a[i]-a[i-1]);
        }
        return dmin;
    }
Solution 2. Comparing when doing traversal (slower). Set initial prev = -1 and check for -1 before calculate dmin to avoid overflow.
    void inOrder(TreeNode*node, int&prev, int&dmin) {
        if(!node) return;
        if(node->left) inOrder(node->left, prev, dmin);
        if(prev!=-1) dmin = min(dmin, node->val - prev);
        prev = node->val;
        if(node->right) inOrder(node->right, prev, dmin);
    }
    int getMinimumDifference(TreeNode* root) {
        int dmin=INT_MAX, prev=-1;
        inOrder(root, prev, dmin);
        return dmin;
    }

349. Intersection of Two Arrays

https://leetcode.com/problems/intersection-of-two-arrays/description/
Sort the arrays, and compare. Pay attention to the duplicated numbers.
    vector<int> intersection(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]) { 
                if( res.empty() || nums1[i]!=res.back())
                    res.push_back(nums1[i]); 
                i++; 
                j++;
            }
            else if(nums1[i]<nums2[j]) i++;
            else j++;
        }
        return res;
    }

283. Move Zeroes

https://leetcode.com/problems/move-zeroes/description/
Solution 1, use iterators to erase 0s and add 0 to the end.
    void moveZeroes(vector<int>& nums) {
        vector<int>::iterator it=nums.begin();
        for(int i=0;i<nums.size();i++) {
            if(*it == 0) {
                nums.erase(it);
                nums.push_back(0);
            }
            else
                it++;
        }
    }
Solution 2, for i = 0 to nums.size()-1, copy nums[i] to an array starts from j=0. Since non-zeros is less than nums.size() and i>=j always, just use &nums[0] for the copied array.
    void moveZeroes(vector<int>& nums) {
        int j = 0;
        for(int i=0;i<nums.size();i++) {
            if(nums[i]!=0) {
                nums[j++] = nums[i];
            }
        }
        while(j<nums.size()) {
            nums[j] = 0; ->
            j++;
        }
    }

606. Construct String from Binary Tree

https://leetcode.com/problems/construct-string-from-binary-tree/description/
Use pre-order tree traversal. Note that the left (or right) branch and its sub-nodes are surrounded by "()". Add "(" and ")" accordingly.
    void preOrder(TreeNode *node, string &tStr){
        if(!node) return;
        tStr += to_string(node->val);
        if(node->left) {
            tStr += "(";
            preOrder(node->left, tStr);
            tStr += ")";
        }
        
        if(node->right) {
            if(!node->left)
                tStr += "()";
            tStr += "(";
            preOrder(node->right, tStr);
            tStr += ")";
        }
    }
    string tree2str(TreeNode* t) {
        string treeStr;
        preOrder(t, treeStr);
        return treeStr;
    }

258. Add Digits

https://leetcode.com/problems/add-digits/description/

Digital root : dr(n) = 1 + (n-1) % (b-1), where n is the base.
Solution O(1):
int addDigits(int num) { 

    return 1 + (num - 1) % 9; 

}
Solution using loop/recursion:
    int addDigits(int num) {
        if(num<10) return num;
        int s=0;
        while(num!=0){
            s+=num%10;
            num/=10;
        }
        return addDigits(s);
    }

371. Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
https://leetcode.com/problems/sum-of-two-integers/description/
    int getSum(int a, int b) {
        int s = a;
        while(b != 0) {
            s = a ^ b;
            b = (a & b) << 1;
            a = s;
        }
        return s;
    }

389. Find the Difference

Description https://leetcode.com/problems/find-the-difference/description/
Solution 1, use XOR
    char findTheDifference(string s, string t) {
        char c = 0;
        for(int i=0;i<s.size();i++)
            c ^= s[i];
        for(int i=0;i<t.size();i++)
            c ^= t[i];
        return c;
    }
Solution 2, sort the strings and compare.
    char findTheDifference(string s, string t) {
        sort(s.begin(),s.end());
        sort(t.begin(),t.end());
        for(int i=0; i<s.size();i++) {
            if(s[i]!=t[i]) return t[i];
        }
        return t.back();
    }

538. Convert BST to Greater Tree

Description https://leetcode.com/problems/convert-bst-to-greater-tree/description/
Solution:
Recursion. Use inverse in-order recursive traversal and use a variable to store the sum greater than the current node.
class Solution {
private:
    int gSum = 0;
public:
    void invInOrder(TreeNode* node){
        if(!node) return;
        if(node->right) invInOrder(node->right);
        gSum+=node->val;
        node->val = gSum;
        if(node->left) invInOrder(node->left);
    }
    TreeNode* convertBST(TreeNode* root) {
        invInOrder(root);
        return root;
    }
};

653. Two Sum IV - Input is a BST

Problem description: https://leetcode.com/problems/two-sum-iv-input-is-a-bst/description/
Solution 1: Conduct two in-order searches from left most and right most leaves. (fastest)
    bool findTarget(TreeNode* root, int k) {
        if(!root) return false;
        TreeNode* nl = root, * nh = root, *nle, *nhe;
        stack<TreeNode*> stl, sth;
        while(nl) {stl.push(nl); nl = nl->left; }
        while(nh) {sth.push(nh); nh = nh->right; }
        nle = stl.top();
        nhe = sth.top();
        int lo = nle->val, hi = nhe->val;
        while(nle != nhe) {
            if(lo + hi == k) return true;
            if(lo + hi < k) {
                while(nl) {stl.push(nl); nl = nl->left;}
                nle = stl.top();
                stl.pop();
                lo = nle->val;
                nl = nle->right;
            }
            else {
                while(nh) {sth.push(nh); nh = nh->right;}
                nhe = sth.top();
                sth.pop();
                hi = nhe->val;
                nh = nhe->left;
            }
        }
        return false;
    }
Solution 2:
Make an in-order traversal for the BST and get the values in an array in ascending order. Then do the two sum of O(n).
    void inOrder(TreeNode* node, vector<int>& vt){
        if(!node) return;
        if(node->left)
            inOrder(node->left, vt);
        vt.push_back(node->val);
        if(node->right)
            inOrder(node->right, vt);
    }
    bool findTarget(TreeNode* root, int k) {
        vector<int> vt;
        inOrder(root,vt);
        for(int i=0, j=vt.size()-1;i<j;){
            if(vt[i]+vt[j] == k) return true;
            else if(vt[i]+vt[j]>k) j--;
            else i++;
        }
        return false;
    }
Solution 3:
Construct iterator objects for the tree.
    class BSTiterator{
        private:
            stack<TreeNode*> s;
            TreeNode* node;
            bool inc;
        public:
            BSTiterator(TreeNode*root, bool increase):node(root),inc(increase){}
            int next(){
                while(!s.empty()||node) {
                    if(node) {
                        s.push(node);
                        node = inc ? node->left:node->right;
                    }
                    else {
                        node = s.top();
                        s.pop();
                        int nval = node->val;
                        node = inc ? node->right:node->left;
                        return nval;
                    }
                }
                return -1;
            }
    };
    bool findTarget(TreeNode* root, int k) {
        if(!root) return false;
        BSTiterator f(root,true);
        BSTiterator b(root,false);
        for(int i=f.next(), j=b.next();i<j;){
            if(i+j == k) return true;
            else if(i+j<k) i = f.next();
            else j = b.next();
        }
        return false;
    }

C++ New Notes

Lambda expressions (since C++11)

Constructs a closure: an unnamed function object capable of capturing variables in scope.
[ captures ] <tparams>(optional)(c++20) ( params ) specifiers(optional) exception attr -> ret { body } (1)
[ captures ] ( params ) -> ret { body } (2)
[ captures ] ( params ) { body } (3)
[ captures ] { body } (4)

Parameter pack
A template parameter pack is a template parameter that accepts zero or more template arguments (non-types, types, or templates). 
A function parameter pack is a function parameter that accepts zero or more function arguments.
A template with at least one parameter pack is called a variadic template.

decltype (declared type)

Inspects the declared type of an entity or the type and value category of an expression.