[数据结构与算法]力扣算法学习day40-2

力扣算法学习day40-2

516-最长回文子序列

题目

代码实现

class Solution {
    public int longestPalindromeSubseq(String s) {
        char[] sList = s.toCharArray();

        // dp: 速度28ms     较简单，能直接想到。
        // dp[i][j]:表示i-j(左闭右开)的s的子字符串的最长回文子序列的长度。
        // (1)如果sList[i] == sList[j],
        // 1.如果j-i == 0,说明当前i，j指向同一个元素，单个元素本身，最长回文子序列长度为1.
        // 2.如果j-i == 1,说明当前i，j是前后两个元素，是接着的，故最长回文子序列长度为2.
        // 2.当j-i > 1时，至少有三个元素，此时头元素和尾元素相等，那么最长回文子序列长度是i+1-j-1的s的子字符串
        // 的最长回文子序列长度+2，即在其最长长度上还要多一个头尾相同的情况。
        //
        // (2)如果sList[i] != sList[j],说明当前i的元素和j的元素不匹配，所以直接取i+1-j或i-j-1两种情况的最大值
        // 即为当前i-j的s的子字符串回文子序列的最大长度。即dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
        // 注：这里还有一个大条件限制，即j >= i,dp数组对于j和i的定义使得j必须大于i。
        int[][] dp = new int[sList.length][sList.length];

        // 初始化，全部初始化为0即可。
        // 遍历顺序：由迭代公式可以看出，dp[i][j]依赖于下方，左下方，左方的情况，所以遍历顺序必须是
        // 由下到上，由左到右，这样才能保证依赖顺序成立。
        // for(int j = 0;j < sList.length;j++){
        //     for(int i = sList.length - 1;i >= 0;i--){
        //         if(j < i){
        //             continue;
        //         }

        //         if(sList[i] == sList[j]){
        //             // if(j - i == 0){
        //             //     dp[i][j] = 1;
        //             // } else if(j - i == 1){
        //             //     dp[i][j] = 2;
        //             // } else {
        //             //     dp[i][j] = dp[i+1][j-1] + 2;
        //             // }
        //             if(j - i == 0){
        //                 dp[i][j] = 1;
        //             } else {// 2,3情况归为一起也行。
        //                 dp[i][j] = dp[i+1][j-1] + 2;
        //             }

        //         } else{
        //             dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
        //         }
        //     }
        // }

        // 写法2：提前赋值单个字符为1，只要是相等就有dp[i][j] = dp[i+1][j-1] + 2的情况了，但是
        // 需要注意的是这种写法因为已经将中间的单个字符部分赋值了，所以需要改变一下遍历方式。
        // 这种遍历速度更快：速度 18ms
        for(int i = 0;i < sList.length;i++){
            dp[i][i] = 1;
        }
        for(int i = sList.length - 1;i >= 0;i--){
            for(int j = i+1;j < sList.length;j++){
                if(sList[i] == sList[j]){
                    dp[i][j] = dp[i+1][j-1] + 2;
                } else{
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }

        return dp[0][sList.length-1];
    }
}

739-每日温度

题目

代码实现

先发个暴力，晚上再做。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        // 暴力法ter好想，先试一下，卧槽，还真行，速度 1182ms，哈哈哈，好慢。
        int[] tem = new int[temperatures.length];

        for(int i = 0;i < temperatures.length-1;i++){
            for(int j = i+1;j < temperatures.length;j++){
                if(temperatures[i] < temperatures[j]){
                    tem[i] = j - i;
                    break;
                }
            }
        }

        return tem;
    }
}