724. Find Pivot Index

    int pivotIndex(vector<int>& nums) {
        if(nums.size() == 0) return -1;
        if(nums.size() == 1) return 0;
        int l = 0, r = 0;
        for(int i=1; i< nums.size(); i++) r += nums[i];
        int i = 0;
        while(l != r) {
            l += nums[i];
            i++;
            if(i == nums.size()) break;
            r -= nums[i];
        }
        if(i == nums.size()) return -1;
        else return i;
    }

717. 1-bit and 2-bit Characters

    bool isOneBitCharacter(vector<int>& bits) {
        if(bits.back() == 1) return false;
        if(bits.size() == 1) return true;
        for(int i=0; i<bits.size();) {
            if(bits[i] == 1) i += 2;
            else i++;
            if(i == bits.size()-1) return true;
        }
        return false;
    }

238. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/description/
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n,1);
        int forward = 1, backward = 1;
       
        for(int i=0; i<n; i++) {
            res[i] *= forward;
            res[n-1-i] *= backward;
            forward *= nums[i];
            backward *= nums[n-1-i];
        }
        return res;
    }

442. Find All Duplicates in an Array

https://leetcode.com/problems/find-all-duplicates-in-an-array/description/
Solution 1. swap number i to index i-1
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        int i=0;
        while(i<nums.size()) {
            if(nums[i] != nums[nums[i]-1])
                swap(nums[i], nums[nums[i]-1]);
            else i++;
        }
        for(int i=0; i<nums.size(); i++) {
            if(i+1 != nums[i]) res.push_back(nums[i]);
        }
        return res;
    }
Solution 2. Mark by +/-
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        for(int i=0; i<nums.size(); i++) {
            nums[abs(nums[i])-1] = -nums[abs(nums[i])-1];
            if(nums[abs(nums[i])-1]>0) res.push_back(abs(nums[i]));
        }
        return res;
    }
Solution 3. counting number nums[i] by adding n to index i-1
    vector<int> findDuplicates(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]>2*n) res.push_back(i+1);
        }
        return res;
    }

419. Battleships in a Board

https://leetcode.com/problems/battleships-in-a-board/description/
    int countBattleships(vector<vector<char>>& board) {
        int res = 0;
        for(int i=0; i<board.size(); i++)
            for(int j=0; j<board[0].size(); j++) {
                if(board[i][j] == 'X') {
                    if(i!=0 && j!=0)
                        res += (board[i-1][j] != 'X' && board[i][j-1] != 'X');
                    else if(i==0 && j!=0)
                        res += (board[i][j-1] != 'X');
                    else if(i!=0 && j==0)
                        res += (board[i-1][j] != 'X');
                    else res++;
                }
            }
        return res;
    }

581. Shortest Unsorted Continuous Subarray

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/description/
    int findUnsortedSubarray(vector<int>& nums) {
        nums.insert(nums.begin(), INT_MIN);
        nums.push_back(INT_MAX);
        int l = 0, h = nums.size() - 1;
        for(int i=1; i<nums.size()-1; i++ ) {
            if(nums[i]<nums[l]) {
                while(nums[i]<nums[l]) l--;
            }
            else if(l == i-1) l++;
        }
        for(int i=nums.size()-2; i>=0; i-- ) {
            if(nums[i]>nums[h]) {
                while(nums[i]>nums[h]) h++;
            }
            else if(h == i+1) h--;
        }
        return max(h-l-1, 0);
    }

475. Heaters

https://leetcode.com/problems/heaters/description/
int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        int maxRg = 0, j = 0;
        for(int i=0; i<houses.size(); i++) {
            int h, minh = abs(heaters[j] - houses[i]);
            while(j+1<heaters.size()) {
                h = abs(heaters[j+1] - houses[i]);
                if(h<=minh) {
                    minh = min(minh, h);
                    j++;
                }
                else {
                    break;
                }
            }
            maxRg = max(maxRg, minh);
        }
        return maxRg;
    }

88. Merge Sorted Array

https://leetcode.com/problems/merge-sorted-array/description/
Merge from high index.
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        if(nums2.size() == 0) return;
        for(int i=m-1, j=n-1, k=m+n-1; k>=0; k--) {
            if(i<0) {
                nums1[k] = nums2[j--];
                continue;
            }
            if(j<0) return;
            if(nums1[i]<=nums2[j]) nums1[k] = nums2[j--];

            else nums1[k] = nums1[i--];
        }    
    }

38. Count and Say

https://leetcode.com/problems/count-and-say/description/
Solution 1. (0 ms)
    string countAndSay(int n) {
        if(n==1) return "1";
        string s = countAndSay(n-1);
        string res = "";
        int cnt = 1;
        for(int i=1; i<s.size(); i++) {
            if(s[i] != s[i-1]) {
                res.push_back('0' + cnt);
                res.push_back(s[i-1]);
                cnt = 1;
            }
            else {
                cnt++;
            }
        }
        res.push_back('0' + cnt);
        res.push_back(s.back());
        return res;
    }
Solution 1.1  (3 ms)
res += to_string(cnt) + s[i-1]; is slower than res.push_back('0' + cnt); res.push_back(s[i-1]);
    string countAndSay(int n) {
        if(n==1) return "1";
        string s = countAndSay(n-1);
        string res = "";
        int cnt = 1;
        for(int i=1; i<s.size(); i++) {
            if(s[i] != s[i-1]) {
                res += to_string(cnt) + s[i-1];
                cnt = 1;
            }
            else {
                cnt++;
            }
        }
        res += to_string(cnt) + s.back();
        return res;
    }

26. Remove Duplicates from Sorted Array

https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/
Solution 1.  Loop through the array, when see a none duplicated number, copy it to location s and s++.
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()<2) return nums.size();
        int s=1;
        for(int i=1; i<nums.size(); i++) {
            if(nums[i] != nums[i-1]) {
                nums[s] = nums[i];
                s++;
            }
        }
        nums.erase(nums.begin()+s, nums.end());
        return s;
    }
Solution 2. Remove when see duplicates. (slow)
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()<2) return nums.size();
        for(vector<int>::iterator it = nums.begin()+1; it<nums.end();) {
            if(*it == *(it-1)) nums.erase(it);
            else it++;
        }
        return nums.size();
    }

119. Pascal's Triangle II

https://leetcode.com/problems/pascals-triangle-ii/description/
Solution 1. Iteration
rowIndex        row
i = 0           1 0 0 0 0
i = 1           1 1 0 0 0
i = 2           1 2 1 0 0
i = 3           1 3 3 1 0
i represents the ith row of the pascals triangle
j is the index on ith row, index loops from high to low
    vector<int> getRow(int rowIndex) {
        vector<int> r(rowIndex+1, 0);
        r[0] = 1;
        for(int i=1; i<rowIndex+1; i++) {
            for(int j=i; j>=1; j--)
                r[j] += r[j-1];
        }
        return r;

    }
Solution 2. recursion
    vector<int> getRow(int rowIndex) {
        if(rowIndex == 0) return {1};
        vector<int> r = getRow(rowIndex - 1);
        r.push_back(1);
        for(int i=1, n, m=r[0]; i<r.size()-1; i++) {
            n = r[i];
            r[i] = m + r[i];
            m = n;
        }
        return r;
    }

66. Plus One

https://leetcode.com/problems/plus-one/description/
    vector<int> plusOne(vector<int>& digits) {
        int c = 1, t;
        for(int i=digits.size()-1; i>=0 && c; i--) {
            digits[i] += c;
            c = digits[i]/10;
            digits[i] %= 10;
        }
        if(c) digits.insert(digits.begin(), 1);
        return digits;
    }