最长回文字符串

  1. 输入：s = "cbbd"
  2. 输出："bb"
  1. //dp[i][j] ->s[i:j] true or false
  2. //dp[i][i] = true
  3. //dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
  4. //i < j
  6. public class Solution {
  8.     public String longestPalindrome(String s) {
  9.         // 特殊用例判断
  10.         int len = s.length();
  11.         if (len < 2) {
  12.             return s;
  13.         }
  15.         int maxLen = 1;
  16.         int begin = 0;
  18.         // dp[i][j] 表示 s[i, j] 是否是回文串
  19.         boolean[][] dp = new boolean[len][len];
  20.         char[] charArray = s.toCharArray();
  22.         for (int i = 0; i < len; i++) {
  23.             dp[i][i] = true;
  24.         }
  25.         for (int j = 1; j < len; j++) {
  26.             for (int i = 0; i < j; i++) {
  27.                 if (charArray[i] != charArray[j]) {
  28.                     dp[i][j] = false;
  29.                 } else {
  30.                     if (j - i < 3) {
  31.                         dp[i][j] = true;
  32.                     } else {
  33.                         dp[i][j] = dp[i + 1][j - 1];
  34.                     }
  35.                 }
  37.                 // 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置
  38.                 if (dp[i][j] && j - i + 1 > maxLen) {
  39.                     maxLen = j - i + 1;
  40.                     begin = i;
  41.                 }
  42.             }
  43.         }
  44.         return s.substring(begin, begin + maxLen);
  45.     }
  46. }

买卖股票的最佳时机

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

class Solution {
    //dp[prices.length()][2]
    //dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + price[i]);
    //dp[i][1] = Math.max(dp[i-1][1],  - price[i]);
    //dp[0][0] = 0
    //dp[0][1] = - price[0]
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for(int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
        }
        return dp[prices.length-1][0];
    }
}

最大子序和

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 1) return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for(int i = 1; i < nums.length; i++){
            dp[i] = nums[i] + Math.max(dp[i-1], 0);
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

打家劫舍

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4

//dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]);
//dp[nums.length-1]
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        int [] dp = new int [nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for(int i = 2 ;i<nums.length; i++){
            dp[i] =Math.max(dp[i-1], nums[i] + dp[i-2]);
        }
        return dp[nums.length-1];
    }
}

统计元音字母序列的数目

给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：

字符串中的每个字符都应当是小写元音字母（'a', 'e', 'i', 'o', 'u'）
每个元音 'a' 后面都只能跟着 'e'
每个元音 'e' 后面只能跟着 'a' 或者是 'i'
每个元音 'i' 后面 不能 再跟着另一个 'i'
每个元音 'o' 后面只能跟着 'i' 或者是 'u'
每个元音 'u' 后面只能跟着 'a'
由于答案可能会很大，所以请你返回 模 10^9 + 7 之后的结果。

输入：n = 2
输出：10
解释：所有可能的字符串分别是："ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" 和 "ua"。

//拿到前缀
//  a -> e u i
//  i -> e o
//  u -> o i
//  e -> a i
//  o -> i
// a e i o u
// 0 1 2 3 4
/* 
dp[i][0] = dp[i-1][1] + dp[i-1][2] + dp[i-1][4]
dp[i][1] = dp[i-1][0] + dp[i-1][2]
dp[i][2] = dp[i-1][1] + dp[i-1][3]
dp[i][3] = dp[i-1][2]
dp[i][4] = dp[i-1][2] + dp[i-1][3]
我们只需保存i-1变量即可
*/

class Solution {
    public int countVowelPermutation(int n) {
        long mod = 1000000007;
        long[] ndp = new long[5];
        long[] dp = new long[5];
        for(int i = 0; i < 5; i++) {
            dp[i] = 1;
        }
        for(int i = 2; i <= n; i++) {
            ndp[0] = (dp[1] + dp[2] + dp[4]) % mod;
            ndp[1] = (dp[0] + dp[2]) % mod;
            ndp[2] = (dp[1] + dp[3]) % mod;
            ndp[3] = dp[2];
            ndp[4] = (dp[2] + dp[3]) % mod;
            System.arraycopy(ndp, 0, dp, 0, 5);
        }
        long ans = 0;
        for(int i = 0; i < 5; i++) {
            ans = (ans + dp[i]) % mod;
        }
        return (int)ans;

    }
}

正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
    '.' 匹配任意单个字符
    '*' 匹配零个或多个前面的那一个元素
    所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

输入：s = "aab" p = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

image.png

//设 s为原串 p匹配串 则有三种匹配方式
// 普通字符直接匹配
// “." 匹配同一位置任意字符
// "*" 匹配前一个字符的一个或多个
//所以定义状态 f(i, j) 表示 s中以i结尾的子串与 p中以j结尾的子串是否匹配  
//p[j] 为普通字符 
// f(i, j) = f(i - 1, j - 1) && s[i] == p[j]
//p[j]为 “.”
// f(i,j) = f(i - 1, j - 1) && p[j] == '.'
//p[j]为 “*”
// 读取p[j-1]字符比如 a 根据a*实际匹配s中a的个数
// 0 f(i,j) = f(i, j - 2)
// 1 f(i,j) = f(i - 1, j - 2) && (s[i] == p[j - 1] || p[j - 1] == '.')
// 2 f(i,j) = f(i - 2, j - 2) && ((s[i] == p[j - 1] && s[i - 1] == p[j - 1]) || p[j - 1] == '.')
//化简 f(i, j) = f(i-1, j-2) || ( f[i-1][j] &&  ( s[i] == p[j-1] || p[j-1] == ".") )
//               0个a            有a  需要满足前面有0个或n个a  而且  （a匹配或者有.） 

class Solution {
    public boolean isMatch(String ss, String pp) {
        // 技巧：往原字符头部插入空格，这样得到 char 数组是从 1 开始，而且可以使得 f[0][0] = true，可以将 true 这个结果滚动下去
        int n = ss.length(), m = pp.length();
        ss = " " + ss;
        pp = " " + pp;
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        // f(i,j) 代表考虑 s 中的 1~i 字符和 p 中的 1~j 字符 是否匹配
        boolean[][] f = new boolean[n + 1][m + 1];
        f[0][0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 如果下一个字符是 '*'，则代表当前字符不能被单独使用，跳过
                if (j + 1 <= m && p[j + 1] == '*') continue;

                // 对应了 p[j] 为普通字符和 '.' 的两种情况
                if (i - 1 >= 0 && p[j] != '*') {
                    f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
                } 

                // 对应了 p[j] 为 '*' 的情况
                else if (p[j] == '*') {
                    f[i][j] = (j - 2 >= 0 && f[i][j - 2])   //0
                        || (
                            i - 1 >= 0 && f[i - 1][j] &&          //
                            (s[i] == p[j - 1] || p[j - 1] == '.') //.
                            );
                }
            }
        }
        return f[n][m];
    }
}