750. Number Of Corner Rectangles

    int countCornerRectangles(vector<vector<int>>& grid) {
        if(grid.size() <= 1) return 0;
        if(grid[0].size() <= 1) return 0;
        int NI = grid.size(), NJ = grid[0].size();
        int res=0;
        for(int i=0; i<NI; i++) {
            for(int ii=i+1; ii<NI; ii++) {
                int n=0;
                for(int j=0; j<NJ; j++) {
                    n += grid[i][j]*grid[ii][j];
                }
                res += n*(n-1)/2;
            }
        }
        return res;
    }

638. Shopping Offers

https://leetcode.com/problems/shopping-offers/description/
bool operator<(vector<int>& s, vector<int>& n) {
    for(int i=0; i<n.size(); i++) {
        if(s[i]>n[i]) return false;
    }
    return true;
}
class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        int res = INT_MAX;
        shop(price, special, 0, needs, res, 0);
        return res;
    }
    void shop(vector<int>& price, vector<vector<int>>& special, int s, vector<int> needs, int&res, int sum){
        int I = price.size();
        if(s == special.size()) {
            for(int i=0; i<I; i++) sum += price[i] * needs[i];
            if(sum < res) res = sum;
            return;
        }
        shop(price, special, s+1, needs, res, sum);
        if(special[s]<needs)
        do {
            for(int i=0; i<I; i++) {
                needs[i] -= special[s][i];
            }
            sum += special[s][I];
            shop(price, special, s+1, needs, res, sum);
        } while(special[s]<needs);
       
    }
};

392. Is Subsequence

https://leetcode.com/problems/is-subsequence/description/
    bool isSubsequence(string s, string t) {
        if(s.empty()) return true;
        int i=0, j=0;
        while(j < t.size()) {
            if(s[i] == t[j]) {
                i++;
                j++;
            }
            else
                j++;
        }
        return i == s.size();
    }
or
    bool isSubsequence(string s, string t) {
        if(s.empty()) return true;
        int i=0, j=0;
        for(; i<s.size(); i++) {
            while(j < t.size() && s[i] != t[j]) j++;
            if(j==t.size()) return false;
            j++;
        }
        return i == s.size();
    }

547. Friend Circles

https://leetcode.com/problems/friend-circles/description/
    int findCircleNum(vector<vector<int>>& M) {
        int m = M.size();
        int res = 0;
        vector<bool> v(m, true);     
        for(int i=0; i<m; i++){
            if(v[i]) {
                res++;
                stack<int> st;
                st.push(i);
                v[i] = false;
                while(!st.empty()) {
                    int k = st.top();
                    st.pop();
                    for(int j=0; j<m; j++) {
                        if(v[j] && M[k][j]) {
                            v[j] = false;
                            st.push(j);
                        }
                    }
                }
            }
        }
        return res;
    }
or DFS,
    void dfs(vector<vector<int>>& M, vector<bool>& visited, int i) {
        visited[i] = true;
        for(int j=0; j<visited.size(); j++) {
            if(i!=j && M[i][j] && !visited[j]) dfs(M, visited, j);
        }
    }
    int findCircleNum(vector<vector<int>>& M) {
        int m = M.size();
        int res = 0;
        vector<bool> visited(m, false);
        for(int i=0; i<m; i++) {
            if(!visited[i]) {
                dfs(M, visited, i);
                res++;
            }
        }
        return res;
    }

495. Teemo Attacking

https://leetcode.com/problems/teemo-attacking/description/
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        if(timeSeries.size() == 0) return 0;
        int res = 0, next = timeSeries[0];
        for(int n: timeSeries) {
            if(n+duration-1 >= next) {
                if(n <= next) res += n + duration - next;
                else res += duration;
                next = n + duration;
            }
        }
        return res;
    }

667. Beautiful Arrangement II

https://leetcode.com/problems/beautiful-arrangement-ii/description/
Solution 1.
1, k+1, 2, k, 3, k-1, 4, ...
    vector<int> constructArray(int n, int k) {
        int l = 1, r = k+1;
        vector<int> res;
        while (l <= r) {
            res.push_back(l++);
            if (l <= r) res.push_back(r--);
        }
        for (int i = k+2; i <= n; i++)
            res.push_back(i);
        return res;
    }

Solution 2.
k
1        1  2  3  4  5  6  7

2        1  2  3  4  5  6
        7
3        1  2  3  4  5  6
            7
4        1  2  3  4  5
        7  6
5        1  2  3  4  5  6
            7  6

6        1  2  3  4
        7  6  5
5        1  2  3  4  5
            7  6  5

    vector<int> constructArray(int n, int k) {
        vector<int> res(n, 0);
        for(int i=0; i<n; i++) res[i] = i+1;
        int t = k/2, mk = k%2;
        vector<int> a(n-t, 0), b(t,0);
        for(int i=0; i<n-t; i++) a[i] = res[i];
        for(int i=0; i<t; i++) b[i] = res[n-1-i];
     
        int p=0, q=0;
        for(int i=0; i<n; i++) {
            if(q<t && i%2==mk) {res[i] = b[q]; q++; }
            else {res[i] = a[p]; p++; }
        }
        return res;
    }

14. Longest Common Prefix

https://leetcode.com/problems/longest-common-prefix/description/
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0 || strs[0].size() == 0) return "";
        for(int j=0; j<strs[0].size(); j++) {
            for(int i=1; i<strs.size(); i++) {
                if(j>=strs[i].size() || strs[0][j] != strs[i][j]) {
                    return strs[0].substr(0,j);
                }
            }
        }
        return strs[0];
    }

58. Length of Last Word

https://leetcode.com/problems/length-of-last-word/description/
    int lengthOfLastWord(string s) {
        if(s.size() == 0) return 0;
        int i = s.size()-1;
        while(i>=0 && s[i] == ' ') i--;
        if(i == -1) return 0;
        int j;
        for(j=i; j>=0; j--) {
            if(s[j] == ' ') break;
        }
        return  i-j;
    }

434. Number of Segments in a String

https://leetcode.com/problems/number-of-segments-in-a-string/description/
    int countSegments(string s) {
        int cnt = 0;
        char pre = ' ';
        for(char c: s) {
            if(c != ' ' && pre == ' ') {
                cnt++;
                pre = c;
            }
            if(c == ' ')
                pre = ' ';
        }
        return cnt;
    }

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

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

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

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

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

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.

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

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;

    }