动态规划

53. 最大子数组和

求最大子数组的和, 就是求以f(i)结尾的最大子数组的和, f(i) 位置有两种情况,

f(i-1)+nums[i]是最大的, 大于nums[i], 此时最大值是f(i-1)+nums[i]
f(i-1)+nums[i]是小于nums[i]的, 此时最大值是nums[i]

f(i)只和f(i-1)相关, 所以使用一个变量pre保存f(i-1)

3335. 字符串转换后的长度 I

给你一个字符串 s 和一个整数 t，表示要执行的转换次数。每次转换需要根据以下规则替换字符串 s 中的每个字符：

如果字符是 'z'，则将其替换为字符串 "ab"。否则，将其替换为字母表中的下一个字符。例如，'a' 替换为 'b'，'b' 替换为 'c'，依此类推。返回恰好执行 t 次转换后得到的字符串的长度。

由于答案可能非常大，返回其对 109 + 7 取余的结果。

class Solution {
    public int lengthAfterTransformations(String s, int t) {
        // f(i,c)表示在进行了i次转换后, 字符串s中字符c的数量;
        // 从f(i-1,c)递推到f(i,c)时有三种情况:
        // 1. c=='a', 只能从z转换得到, 所以: f(i,a)=f(i-1,z), 即a的数量为z的数量
        // 2. c=='b', b可以从a或z转换得到, 所以: f(i,b)=f(i-1,z)+f(i-1,a), 即b的数量为z的数量+a的数量;
        // 3. c>='c', 可以从上一个字符串转换得到, 所以: f(i,c)=f(i-1,c-1), 即大于b的字符的数量等于小一点的字符的数量;

        int[] charCountArr = new int[26];
        for(char c: s.toCharArray()){
            charCountArr[c-'a']++;
        }

        // 递推t次
        for(int i=0;i<t;i++){
            int[] newArr = new int[26];
            newArr[0] = charCountArr[25];
            newArr[1] = (charCountArr[25]+charCountArr[0])%1000000007;
            for(int j=2;j<newArr.length;j++){
                newArr[j]=charCountArr[j-1];
            }
            charCountArr = newArr;
        }
        int re=0;
        for(int n: charCountArr){
            re=(re+n)%1000000007;
        }
        return re;
    }
}

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

O(n^2): 动态规划

class Solution {
    public int lengthOfLIS(int[] nums) {
        // i位置的最长递增子序列=以i-1结尾的子序列的最长递增子序列+1
        // dp[i]: 以nums[i]结尾的最长上升子序列的长度
        int[] dp=new int[nums.length];
        int res=0;
        for(int i=0;i<nums.length;i++){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i]=Math.max(dp[i], dp[j]+1);
                }
            }            
            res=Math.max(dp[i], res);
        }
        return res;
    }
}

考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

基于上面的贪心思路，我们维护一个数组 d[i] ，表示长度为 i 的最长上升子序列的末尾元素的最小值，用 len 记录目前最长上升子序列的长度，起始时 len 为 1，d[1]=nums[0]。

对于d数组严格递增的证明: 如果d[j]≥d[i] 且 j<i, 我们考虑从长度为 i 的最长上升子序列的末尾删除 i-j 个元素，那么这个序列长度变为 j ，且第 j 个元素 x(末尾元素)必然小于 d[i]，也就小于 d[j]。那么我们就找到了一个长度为 j 的最长上升子序列，并且末尾元素比 d[j] 小，从而产生了矛盾。因此数组 d 的单调性得证。

如: d=[0,1,8,5], j=2, i=3, d[j]>d[i] 从长度为3的最长上升子序列末尾删除1个元素, 得到一个长度为2的最长上升子序列, 这个长度为2的子序列末尾元素小于5; 与长度为2的最长子序列的末尾元素的最小值是8不符合;

O(nlogn): 贪心+二分

class Solution {
    public int lengthOfLIS(int[] nums) {
        // i位置的最长递增子序列=以i-1结尾的子序列的最长递增子序列+1
        // d[i]: 长度为i的最长递增子序列的'末尾元素的最小值'
        int[] d=new int[nums.length+1];
        d[1]=nums[0];
        int length=1;
        for(int i=1;i<nums.length;i++){
            if(nums[i]>d[length]){
                d[++length]=nums[i];
            }else{
                int l=1,r=length,pos=0;
                while(l<=r){
                    int m=l+(r-l)/2;
                    if(d[m]>=nums[i]){
                        r=m-1;
                    }else{
                        pos=m;
                        l=m+1;
                    }
                }
                d[pos+1]=nums[i];
            }
        }
        return length;
    }
}

动态规划

53. 最大子数组和

3335. 字符串转换后的长度 I

300. 最长递增子序列

On this page