Day 82, #84, Largest Rectangle in Histogram

Largest Rectangle in Histogram

 Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

----------------------------------------------------------
for each single bar, calculate the largest rectangle that has the same height as the bar,
OJ Time Limit Exceeded

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int largest = 0;
        
        for (int i = 0; i < height.size(); i++) {
            int left = i - 1, right = i + 1;
            int length = 1;
            while (left >= 0 && height[left] >= height[i]) {
                length++;
                left--;
            }
            
            while (right < height.size() && height[right] >= height[i]) {
                length++;
                right++;
            }
            
            largest = max(largest,length * height[i]);
        }
        
        return largest;
    }
};

Solution #2
网上讲解很多，请google
要点
#1 原数组末尾插入0是为了清空并计算stack内所剩的数
#2 第18行: (topBar - st.top() - 1) + (i - topBar) = i - st.top() -  1
- topBar左边：因为从st.top（）到topBar之间的长方形都高于topBar，当计算以topBar为高度的面积时得包含之前的长方形
- topBar右边：到当前的i为止，所有的长方形都大于或等于topBar
#3 当stack为空时，说明之前所有经历过的长方形都高于topBar. 因为在某一个index时，stack里面比当前小的永远不会被pop出去
#4 stack所存的是index
#5 stack里的高度永远为递增
例子：{4,2,0,3,2,5}
情况1：

情况2：

情况3：

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        stack<int> st;
        int largest = 0;
        height.push_back(0);
        
        for (int i = 0; i < height.size(); i++) {
            
            if (st.empty() || height[i] >= height[st.top()]) {
                st.push(i);
            }else {
                int topBar = st.top();
                st.pop();
                if (st.empty()) {
                    largest = max(largest,height[topBar] * i);
                }else {
                    largest = max(largest,height[topBar] * (i - st.top() - 1));
                }
                
                i--;
            }
        }

        return largest;
    }
};

Day 81, #81, Search in Rotated Sorted Array II

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
--------------------------------------------------------------------------
与I同样的思路，不同点是增加了1个if判断来解决重复的问题
重复的情况#1： start，mid，end 3处都相等，如111111111111112111。此时左右两半都需要检测，worst cast O(n)
重复的情况#2：仅start或者end跟mid相等，如4444123，此时原有代码也可解决

class Solution {
public:
    bool searchInRotated(int A[], int start, int end, int target) {
        if (start > end) {
            return false;
        }
        int mid = (start + end) / 2;
        if (A[mid] == target) {
            return true;
        }
        
        // ------ to handle duplicates ---- 
        if (A[start] == A[mid] && A[start] == A[end]) {
            return searchInRotated(A,start,mid - 1,target) || searchInRotated(A,mid + 1,end,target);
        }
        
        if (A[start] <= A[mid]) {
            if (A[start] <= target && target <= A[mid]) {
                return searchInRotated(A,start,mid - 1,target);
            }else {
                return searchInRotated(A,mid + 1,end,target);
            }
        }else {
            if (A[mid] <= target && target <= A[end]) {
                return searchInRotated(A,mid + 1,end,target);
            }else {
                return searchInRotated(A,start,mid - 1,target);
            }
        }
        
    }

    bool search(int A[], int n, int target) {
        return searchInRotated(A,0,n - 1,target);
    }
};

Solution #2, iterative(to do)

Day 80, #60, Permutation Sequence

Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the k^th permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
-----------------------------------------------------------------------------
Factorial. Lay out permutations, you will see the pattern
将k设为0-base

class Solution {
public:
    int getFactorial(int n) {
        int rt = 1;
        for (int i = 1; i <= n; i++) {
            rt *= i;
        }
        
        return rt;
    }

    int getNextNumber(vector<bool> &nums, int section) {
        for (int i = 0; i < nums.size(); i++) {
            if (section == 0 && nums[i] == false) {
                nums[i] = true;
                return i;
            }
            if (nums[i] == false) {
                section--;
            }
        }
    }

    string getPermutation(int n, int k) {
        int factorial = getFactorial(n);
        string rt = "";
        vector<bool> nums(n,false);
        k--;
        for (int i = n; i > 0; i--) {
            factorial /= i;
            int section = k / factorial;
            k = k % factorial;
            char c = getNextNumber(nums,section) + '1';
            rt += c;
        }
        
        return rt;
    }
};

Day 79, #44, Wildcard Matching

Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

---------------------------------------------------------------
Solution #1 recursion, OJ time limit exceeded

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        if (*p == '\0') {
            return *s == '\0';
        }
        
        if (*p == *s || *p == '?') {
            return isMatch(s + 1, p + 1);
        }
        
        if (*p == '*') {
            while (*s != '\0') {
                if(isMatch(s,p + 1)) {
                    return true;
                }
                s++;
            }
        }
        
        return false;
    }
};

Solution #2, dp with 2d arrays,

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = p.length(), n = s.length();
        vector<vector<bool> > dp(m + 1,vector<bool>(n + 1,false));
        
        dp[0][0] = true;
        for (int i = 0; i < m; i++) {
         if (p[i] != '*') break;
            dp[i + 1][0] = true;
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] && (p[i] == s[j] || p[i] == '?')) {
                    dp[i + 1][j + 1] = true;
                }else if (p[i] == '*') {
                    if (dp[i][j + 1] || dp[i + 1][j]) {
                        dp[i + 1][j + 1] = true;
                    }
                }
            }
        }
        return dp[m][n];
    }
};

改良版DP，用了一个一维数组，当*p == '*',dp[j]只取决于dp[j - 1]，过不了最后一个test case

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = p.length(), n = s.length();
        vector<bool> dp(n + 1,false);
        bool diag = true;
        dp[0] = true;
        
        for (int i = 0; i < m; i++) {
            diag = dp[0];
            for (int j = 0; j < n; j++) {
                if (diag && (p[i] == s[j] || p[i] == '?')) {
                    diag = dp[j + 1];
                    dp[j + 1] = true;
                }else if (p[i] == '*') {
                    diag = dp[j + 1];
                    if (dp[j] || dp[j + 1]) {
                        dp[j + 1] = true;
                    }
                }else {
                    diag = dp[j + 1];
                    dp[j + 1] = false;
                }
            }
            if (p[i] == '*' && dp[0]) {
                dp[0] = true;
            }else {
                dp[0] = false;
            }
            
        }
        
        return dp[n];
    }
};

Solution #3, constant space
star用来记录最近*的位置，index用来记录当前*匹配成功后s的位置。*之前全部匹配成功，不用再重复检测。*之后如果匹配失败，回头从star + 1 和 index重新匹配，每匹配失败一次，index增加一位。

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        const char *star = NULL;
        const char *index = s;
        
        while (*s != '\0') {
            if (*s == *p || *p == '?') {
                s++;
                p++;
            }else if (*p == '*') {
                star = p;
                p++;
                index = s;
            }else if (star != NULL) {
                p = star + 1;
                index++;
                s = index;
            }else return false;
        }
        
        while (*p == '*') {
            p++;
        }
        
        return *p == '\0';
    }
};

Java,2维dp

class Solution {
    public boolean isMatch(String s, String p) {
        List<List<Boolean>> dp = getDP(s, p);
            
        for (int i = 0; i < p.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                if (dp.get(i).get(j) && (s.charAt(j) == p.charAt(i) || p.charAt(i) == '?')) {
                    dp.get(i + 1).set(j + 1, true);
                } else if (p.charAt(i) == '*' && (dp.get(i).get(j + 1) || dp.get(i + 1).get(j))) {
                    dp.get(i + 1).set(j + 1, true);
                }
            }
        }
        
        return dp.get(p.length()).get(s.length());
    }
    
    private List<List<Boolean>> getDP(String s, String p) {
        int m = s.length();
        int n = p.length();
        List<List<Boolean>> dp = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            List<Boolean> inner = new ArrayList<>();
            if (i == 0 || (i > 0 && dp.get(i - 1).get(0) && p.charAt(i - 1) == '*')) inner.add(true);
            else inner.add(false);
            for (int j = 0; j < m; j++) {
                inner.add(false);
            }
            dp.add(inner);
        }
        
        return dp;

    }
}

Day 78, #41, First Missing Positive

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
----------------------------------------------------------------

# Pass 1, move every value to the position of its value

因为找的是第一个非0，所以把1存在0,2存在1

while里的条件是检测下一个位置是否已经匹配好，如果检查当前位置的话，会进入死循环，因为会有重复的数字如[1,1]

# Pass 2, find first location where the index doesn't match the value

reference  

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        for (int i = 0; i < n; i++) {
            int target = A[i];
            while (target > 0 && target <= n && A[target - 1] != target) {
                int temp = A[target - 1];
                A[target - 1] = target;
                A[i] = temp;
                target = A[i];
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (i + 1 != A[i]) {
                return i + 1;
            }
        }
        
        return n + 1;
    }
};

Day 77, #31, Next Permutation

Next Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
--------------------------------------------------------------------------
Solution #1
Find the last peak number i, swap [i - 1] and the number that follows [i - 1] in ascending order, then reverse all numbers from peak to end

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if (num.size() == 0 || num.size() == 1) return;
        int peak = -1;
        int swapIndex = 0;
        
        for (int i = 0; i < num.size(); i++) {
            if (i + 1 < num.size() && num[i] < num[i + 1]) {
                peak = i + 1;
                swapIndex = peak;
            }else if (peak != -1) {
                if (num[i] > num[peak - 1]) {
                    swapIndex = i;
                }
            }    
        }
        
        if (peak == -1) {
            reverse(num.begin(),num.end());
        }else {
            int temp = num[swapIndex];
            num[swapIndex] = num[peak - 1];
            num[peak - 1] = temp;
            
            reverse(num.begin() + peak,num.end());
        }
    }
};

Java, updated on Aug-6th-2018
6 9 7 3 2 -> 7 2 3 6 9 可以看出规律

注意数字有重复的时候，比如2 3 1 3 3 -> 2 3 3 1 3. 所有第36行对比时要加等号

class Solution {
    public void nextPermutation(int[] nums) {
        int drop = getFirstDrop(nums);
        if (drop == -1) {
            reverseArray(nums, 0);
            return;
        }
        
        int nextInOrder = getNextInOrder(nums, drop);
        swap(nums, drop, nextInOrder);
        reverseArray(nums, drop + 1);
    }
    
    private void reverseArray(int[] nums, int index) {
        int right = nums.length - 1;
        
        while (index < right) {
            swap(nums, index, right);    
            index++;
            right--;
        }
    }
    
    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
    
    private int getNextInOrder(int[] nums, int drop) {
        
        int index = drop + 1;
        int min = nums[index];
        
        for (int i = index; i < nums.length; i++) {
            if (min >= nums[i] && nums[i] > nums[drop]) { // 注意“>=”
                min = nums[i];
                index = i;
            }
        }
        
        return index;
    }
    
    private int getFirstDrop(int[] nums) {
        
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                return i;
            }
        }
        
        return -1;
    }
}

Day 76, #10, Regular Expression Matching

Regular Expression Matching
Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

 ------------------------------------------------------------------------------
Solution #1, recursion

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        if (*p == '\0') {
            return *s == '\0';
        }
        
        if (*(p + 1) != '*') {
            return (*s == *p || (*p == '.' && *s != '\0')) && isMatch(s + 1, p + 1);
        }

        while (*p == *s || (*p == '.' && *s != '\0')) {
            if (isMatch(s,p + 2)) {
                return true;
            }
            s++;
        }
        return isMatch(s,p + 2);
    }
};

Solution #2, DP
dp[i][j] has the boolean value whether p[0 : i] can match s[0 : j], dp[0][0] is set to true since empty string matches empty pattern

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int m = strlen(p);
        int n = strlen(s);
        
        vector<vector<bool> > dp(m + 1,vector<bool>(n + 1,false));
        dp[0][0] = true;
        
        for (int i = 2; i <= m; i++) {
            if (p[i - 1] == '*' && dp[i - 2][0]) {
                dp[i][0] = true;
            }
        }
        
        for (int i = 1; i <= m; i++) {
            
            for (int j = 1; j <= n; j++) {
                if (p[i - 1] == s[j - 1] || p[i - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                }else if (p[i - 1] == '*') {
                    // 1 or more char
                    if (dp[i][j - 1] && (p[i - 2] == s[j - 1] || p[i - 2] == '.')) {
                        dp[i][j] = true;
                    }
                    // zero char
                    else if (i - 2 >= 0 && dp[i - 2][j]) {
                        dp[i][j] = true;
                    }
                }
            }
            
        }
        
        return dp[m][n];
    }
};

class Solution {
public:
    bool helper(string s,string p,int i,int j) {
        if (j == p.length()) return i == s.length();
        
        if (j == p.length() - 1 || (j + 1 < p.length() && p[j + 1] != '*')) {
            if (i < s.length() && (p[j] == s[i] || p[j] == '.')) {
                return helper(s,p,i + 1,j + 1);
            }
            return false;
        }
        
        while (i < s.length() && (p[j] == s[i] || p[j] == '.')) {
            if (helper(s,p,i,j + 2)) {
                return true;
            }
            i++;
        }
        return helper(s,p,i,j + 2);
    }
    
    bool isMatch(string s, string p) {
        return helper(s,p,0,0);
    }
};

Java
关键：把下一个 == '*' 和 != '*' 两种情况分开处理

class Solution {
    public boolean isMatch(String s, String p) {
        return rec(s,p,0,0);
    }
    
    private boolean rec(String s, String p, int i, int j) {
        if (i == s.length() && j == p.length()) {
            return true;
        }
        
        if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
            int temp = i;
            while (temp < s.length() && (s.charAt(temp) == p.charAt(j) || p.charAt(j) == '.')) {
                if (rec(s, p, temp + 1, j + 2)) return true;
                temp++;
            }
            return rec(s,p,i,j + 2); // '*' matches zero chars
        }
        
        if (i < s.length() && j < p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.')) {
            return rec(s, p, i + 1, j + 1);
        }
    
        return false;
    }
}

预处理的时候要回头看2位之前的位置。
主函数中还要考虑'*' match 0个的情况

class Solution {
    public boolean isMatch(String s, String p) {
        List<List<Boolean>> dp = getDP(s, p);
        int m = p.length();
        int n = s.length();
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <=n; j++) {
                if (p.charAt(i - 1) == s.charAt(j - 1) || p.charAt(i - 1) == '.') {
                    dp.get(i).add(j, dp.get(i - 1).get(j - 1));
                } else if (p.charAt(i - 1) == '*') {
                    if (i - 2 >= 0 && dp.get(i - 2).get(j)) {
                        dp.get(i).add(j, true);
                    }else if (dp.get(i).get(j - 1) && (p.charAt(i - 2) == s.charAt(j - 1) || p.charAt(i - 2) == '.')) {
                        dp.get(i).add(j, true);
                    }
                }
            }
        }
        
        return dp.get(m).get(n);
    }
    
    private List<List<Boolean>> getDP(String s, String p) {
        int m = p.length();
        int n = s.length();
        List<List<Boolean>> dp = new ArrayList<>();
        
        for (int i = 0; i <= m; i++) {
            List<Boolean> list = new ArrayList<>();
            if (i == 0 || (p.charAt(i - 1) == '*' && dp.get(i - 2).get(0))) list.add(true);
            else list.add(false);
            for (int j = 0; j < n; j++) {
                list.add(false);
            }
            dp.add(list);
        }
        
        return dp;
    }
}