[数据结构与算法]每日一题补题记录12

3.5

521. 最长特殊序列 Ⅰ

给你两个字符串 a 和 b，请返回 这两个字符串中 最长的特殊序列 的长度。如果不存在，则返回 -1 。

「最长特殊序列」 定义如下：该序列为 某字符串独有的最长子序列（即不能是其他字符串的子序列） 。

字符串 s 的子序列是在从 s 中删除任意数量的字符后可以获得的字符串。

例如，"abc" 是 "aebdc" 的子序列，因为删除 "aebdc" 中斜体加粗的字符可以得到 "abc" 。 "aebdc" 的子序列还包括 "aebdc" 、 "aeb" 和 "" (空字符串)。

这题目我大概看了一下，很快就明白了如果要分割逐步处理我肯定是做不出来的，所以我很快决定另辟蹊径，想了一会我想明白了，"aebdc" 的子序列还包括 "aebdc"这句话告诉我们一个字符串的最长子序列就是自己，所以我们就可以确定，如果两个字符串长度不等，那么较长者的子序列必然是自己，短者也无法覆盖，返回较长者长度即可。

如果长度相同，分类讨论：

1.字符串完全相同，返回-1

2.只是长度相同，返回相同长度

class Solution {
    public int findLUSlength(String a, String b) {
        int lena=a.length(),lenb=b.length();
        if(lena!=lenb){
            return Math.max(lena, lenb);
        }
        if(lena==lenb){
            if(a.equals(b))return -1;
            return lena;
        }
        return -1;
    }
}

3.6

2100. 适合打劫银行的日子

你和一群强盗准备打劫银行。给你一个下标从 0?开始的整数数组?security?，其中?security[i]?是第 i?天执勤警卫的数量。日子从 0?开始编号。同时给你一个整数?time?。

如果第 i?天满足以下所有条件，我们称它为一个适合打劫银行的日子：

第 i?天前和后都分别至少有 time?天。
第 i?天前连续 time?天警卫数目都是非递增的。
第 i?天后连续 time?天警卫数目都是非递减的。
更正式的，第 i 天是一个合适打劫银行的日子当且仅当：security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time].

请你返回一个数组，包含 所有 适合打劫银行的日子（下标从 0?开始）。返回的日子可以 任意?顺序排列。

class Solution {
    public List<Integer> goodDaysToRobBank(int[] security, int time) {
        int n=security.length;
        //预处理，记录第i天左边、右边分别连续几天符合条件
        int[]left=new int[n];
        int[]right=new int[n];
        List<Integer>ans=new ArrayList<>();
        //预处理
        for(int i=1;i<n;i++){
            if(security[i]<=security[i-1])left[i]=left[i-1]+1;
            if(security[n-i-1]<=security[n-i])right[n-i-1]=right[n-i]+1;
        }
        //寻找适合打劫的日子
        for(int i=time;i<n-time;i++){
            if(left[i]>=time&&right[i]>=time)ans.add(i);
        }
        return ans;
    }
}

3.7

??????504. 七进制数

给定一个整数?num，将其转化为?7 进制，并以字符串形式输出。

非常easy的进制转换，注意0和正负即可

class Solution {
    public String convertToBase7(int num) {
        if(num==0)return "0";
        StringBuffer sb=new StringBuffer();
        List<Integer>list=new ArrayList<>();
        if(num<0){
            num=-num;
            sb.append("-");
        }
        while(num>0){
            list.add(num%7);
            num/=7;
        }
        for(int i=list.size()-1;i>=0;i--){
            sb.append(list.get(i));
        }
        return sb.toString();
    }
}