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.

448. Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

Solution 1:
The index 0,...,N-1 maps to the array 1,...,N. Use the negtive sign at index m-1 to indicate number m exist in the array.
a. loop i from 0...N, the number exists is m=abs(nums[i]), (use abs() because nums[i] may already be set to negative). Set nums at index (m-1) to -nums[m-1].
b. loop again, if(nums[i]>0), i+1 is not in the array.
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> res;
        int N = nums.size();
        for(int i=0, n; i<N; i++) {
            n = abs(nums[i]) - 1;
            if(nums[n]>0)
                nums[n] = -nums[n];
        }
        for(int i=0; i<N; i++) {
            if(nums[i]>0)
                res.push_back(i+1);
        }
        return res;
    }
Solution 2:
Similar to 1, but adding N to nums[i] if value i+1 exists. Those indices i for nums[i]<N indicate i+1 is missing.
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> res;
        int N = nums.size();
        for(int i=0; i<N; i++) {
            nums[(nums[i]-1)%N] += N;
        }
        for(int i=0; i<N; i++) {
            if(nums[i]<=N)
                res.push_back(i+1);
        }
        return res;
    }
Solution 3:
Loop and swap the values so that the index i matches nums[i]%N,  the index doesn't match its value is the value missing. For example, [4,3,2,7,8,2,3,1] will be [8,1,2,3,4,2,3,7], the indice [5,6] do not match their values, so [5,6] is the result.
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> res;
        int N = nums.size();
        for(int i=0; i<N; i++) {
            while(nums[i] != nums[nums[i]%N]) {
                swap(nums[i],nums[nums[i]%N]);
            }
        }
        for(int i=0; i<N; i++) {
            if(nums[i]%N!=i)
                res.push_back(i==0? N:i);
        }
        return res;
    }

GDB

GDB cheat sheet at brown.edu
Running Programs Under GDB at MIT.edu

Tree traversal

Depth first search:
  pre-order, implementation

1. Check if the current node is empty / null.
2. Display the data part of the root (or current node).
3. Traverse the left subtree by recursively calling the pre-order function.
4. Traverse the right subtree by recursively calling the pre-order function

preorder(node) if (node = null) return visit(node) preorder(node.left) preorder(node.right)

iterativePreorder(node) if (node = null) return s ← empty stack s.push(node) while (not s.isEmpty()) node ← s.pop() visit(node) //right child is pushed first so that left is processed first if (node.right ≠ null) s.push(node.right) if (node.left ≠ null) s.push(node.left)

  in-order, implementation

1. Check if the current node is empty / null.
2. Traverse the left subtree by recursively calling the in-order function.
3. Display the data part of the root (or current node).
4. Traverse the right subtree by recursively calling the in-order function.

inorder(node) if (node = null) return inorder(node.left) visit(node) inorder(node.right)

iterativeInorder(node) s ← empty stack while (not s.isEmpty() or node ≠ null) if (node ≠ null) s.push(node) node ← node.left else node ← s.pop() visit(node) node ← node.right

  post-order, implementation

1. Check if the current node is empty / null.
2. Traverse the left subtree by recursively calling the post-order function.
3. Traverse the right subtree by recursively calling the post-order function.
4. Display the data part of the root (or current node).

postorder(node) if (node = null) return postorder(node.left) postorder(node.right) visit(node)

iterativePostorder(node) s ← empty stack lastNodeVisited ← null while (not s.isEmpty() or node ≠ null) if (node ≠ null) s.push(node) node ← node.left else peekNode ← s.peek() // if right child exists and traversing node // from left child, then move right if (peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right) node ← peekNode.right else visit(peekNode) lastNodeVisited ← s.pop()

Breadth-first search:

  queue based:

levelorder(root)
  q ← empty queue
  q.enqueue(root)
  while (not q.isEmpty())
    node ← q.dequeue()
    visit(node)
    if (node.left ≠ null)
      q.enqueue(node.left)
    if (node.right ≠ null)
      q.enqueue(node.right)

C++ const

const member function
A "const function", denoted with the keyword const after a function declaration, makes it a compiler error for this class function to change a member variable of the class.
To allow some of the variables to be writable even when the function is marked as a "const function", these class variables are marked with the keyword mutable.

Wikipedia:
pointers and references
methods (member functions)

C++ string notes

char c = 'x';
char *s = "hello";