在职刷题

现在的工作不开心，准备半年以后开始面试跳槽。开个帖子刷题打卡，自我监督。希望自己可以坚持下去

第一天：

补充内容 (2018-11-5 14:27):
手一抖 没编辑好就发出去了：
5. Longest Palindromic Substring
两种解法：DP 和从中心发散。
注意点：边界，从中心发散主意结果的奇偶


补充内容 (2018-11-5 14:29):
53. Maximum Subarray
动态规划

121. Best Time to Buy and Sell Stock
DP

第二天
10. Regular Expression Matching
class Solution {
    public boolean isMatch(String s, String p) {
       if (s == null || p == null) {
           return false;
        }
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;
        for (int i = 0; i < p.length(); i++) {
           if (p.charAt(i) == '*' && dp[0][i-1]) {
              dp[0][i+1] = true;
           }
        }
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < p.length(); j++) {
                if (s.charAt(i ) == p.charAt(j) || p.charAt(j) == '.') {
                    dp[i + 1][j + 1] = dp[i][j];
                }
                if (p.charAt(j) == '*') {
                    if (s.charAt(i) != p.charAt(j - 1) && p.charAt(j - 1) != '.') {
                        dp[i + 1][j + 1] = dp[i + 1][j - 1];
                    } else{
                        dp[i + 1][j + 1] = (dp[i][j + 1] || dp[i + 1][j] || dp[i + 1][j - 1]);
                    }
                  
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}

解题要点：s* 可以代表的情况分类讨论
注意点：初始化， 坐标的表示

补充内容 (2018-11-6 15:15):
139. Word Break

继续 刷11.30.2018  152. Maximum Product Subarray：节约空间的写法