[数据结构与算法]C++ 刷题记录 No.3 (难度up，DP)

14. Longest Common Prefix

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string comparee = strs[0];
        for (int j = 1; j < strs.size(); j++) {
            int c = 0;
            for (; c < strs[0].size(); c++) {
                 if (comparee[c] != strs[j][c]) {
                     break;
                 }
            }
            comparee = comparee.substr(0, c);
            if (comparee == "") {
                return "";
            }
        }
        return comparee;
    }
};

26. Remove Duplicates from Sorted Array

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() == 1) {
            return 1;
        }
        int last = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i - 1] != nums[i]) {
                nums[last] = nums[i];
                last++;
            }
        }
        return last;
    }
};
### 20. Valid 
```Parentheses
```cpp
class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for (auto c: s){
            switch (c) {
                case '(': 
                    stk.push(')'); break;
                case '[': 
                    stk.push(']'); break;
                case '{': 
                    stk.push('}'); break;
                default:
                    if (stk.empty() || c != stk.top()) {
                        return false;
                    }
                    else {
                        stk.pop();
                    }
            }
        }
        return stk.empty();
    }
};

28. Implement strStr()

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.size(), n = needle.size();
        // overflow if using size directly
        for (int i = 0; i <= m-n; i++) {
            int j = 0;
            for (; j < needle.size(); j++) {
                if (haystack[i + j] != needle[j]) {
                    break;
                }
            }
            if (j == needle.size()) {
                return i;
            }
        }
        return -1;
    }
};

17. Letter Combinations of a Phone Number

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> pad = {"", "", "abc", "def", "ghi", "jkl",
                             "mno", "pqrs", "tuv", "wxyz"};
        vector<string> results{""};
        if (digits == "") {
            return vector<string>();
        }
        // this is very important when the corner case is different
        for (auto d: digits) {
            vector<string> tmp;
            for (auto letter: pad[d - '0']) {
                for (auto ans: results) {
                    tmp.push_back(ans + letter);
                }
            }
            results.swap(tmp);
        }
        return results;
    }
};

Dynamic Programming

53. Maximum Subarray

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0;
        int max = INT_MIN;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if (max < sum) {
                max = sum;
            }
            if (sum < 0) {
                sum = 0;
            }
        }
        return max;
    }
};

22. Generate Parentheses

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        addResult(result, "", n, 0);
        return result;
    }
    void addResult(vector<string>& result, string str, int n, int m) {
        if (!n && !m) {
            result.push_back(str);
        }
        if (n > 0) {
            addResult(result, str + '(', n-1, m+1);
        }
        if (m > 0) {
            addResult(result, str + ')', n, m-1);
        }
    }
};

118. Pascal’s Triangle

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result;
        
        result.push_back(vector<int>{1});
        if (numRows == 1) {
            return result;
        }
        result.push_back(vector<int>{1,1});
        if (numRows == 2) {
            return result;
        }
        
        for (int i = 2; i < numRows; i++) {
            vector<int> line;
            line.push_back(1);
            for (int j = 0; j < result[i - 1].size() - 1; j++) {
                line.push_back(result[i - 1][j] + result[i - 1][j + 1]);
            }
            line.push_back(1);
            result.push_back(line);
        }
        return result;
    }
};

119. Pascal’s Triangle II

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ans(rowIndex + 1, 0);
        ans[0] = 1;
        for (int i = 1; i < rowIndex + 1; i++) {
            for (int j = i; j > 0; j--) {
                ans[j] += ans[j - 1];
            }
        }
        return ans;
    }
};

Unique Paths

1. recursive solution

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        return uniquePaths(m-1, n) + uniquePaths(m, n-1);
    }
};

2. dp solution

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 1));
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

63. Unique Paths II

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        
        vector<vector<int>> dp(m, vector<int>(n, 1));
        
        int i = 0;
        for (; i < n; i++) {
            if (obstacleGrid[0][i] == 1) {
                break;
            }
        }
        for (int j = i; j < n; j++)
            dp[0][j] = 0;
        
        i = 0;
        for (; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                break;
            }
        }
        for (int j = i; j < m; j++)
            dp[j][0] = 0;
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                }
                else {
                    dp[i][j] = 0;
                }
            }
        }
        
        return dp[m-1][n-1];
    }
};
};

special initialization