Leetcode第420周赛

Leetcode第420周赛

第一题

3324. 出现在屏幕上的字符串序列

认真读题发现就是对于字符串的每一个字符依次从'a'增加到相同为止

class Solution {
    public List<String> stringSequence(String target) {
        List<String> list = new ArrayList<>();
        char[] ch = target.toCharArray();
        StringBuilder s = new StringBuilder();
        for(char c :ch){
            char tmp = 'a';
            list.add(s.toString() + tmp);
            while(c!=tmp){
                tmp++;
                list.add(s.toString() + tmp);
            }
            s.append(tmp);

        
        }
        return list;
    }
}

第二题

3325. 字符至少出现 K 次的子字符串 I

一个滑动窗口问题，采用两次循环解决，及如果当前字符串已经满足，右边界从right开始到结束也都满足，不是最优做法，可以在left更新的时候进行优化。

class Solution {
    public int numberOfSubstrings(String s, int k) {
        if(k==1)return (s.length() * (s.length() + 1)) / 2; 
        char[] ch = s.toCharArray();
        int[] index = new int[26];
        int sum = 0;
        for(int i=0;i<s.length();i++){
            index = new int[26];
            index[ch[i]-'a']++;
            
            for(int j=i+1;j<s.length();j++){
                if(++index[ch[j]-'a']>=k){
                    sum += s.length() - j;
                    break;
                }
            }
        }
        return sum;
    }
}

第三题

3326. 使数组非递减的最少除法操作次数

看了下数据范围，直接记忆化搜索存储每次的真因数，反向迭代

class Solution {
    int[] memo = new int[1000001];
    public int minOperations(int[] nums) {
        Arrays.fill(memo, -1);
        int sum = 0;
        for(int i=nums.length-2;i>=0;i--){
            while(nums[i]>nums[i+1]){
                int z = z(nums[i]);
                if(z==1)return -1;
                nums[i] /= z;
                sum++;
            }
        }
        return sum;
    }
    int z(int i){
        if(memo[i]!=-1)return memo[i];
        for(int j = i / 2;j>=1;j--){
            if(i%j==0)return memo[i]=j;
        }
        return memo[i]=1;
    }

}

第四题

我承认飘了去看第四题，模拟了一下最后超时差最后三个样例。实际上差很多，采用记忆化搜索出现了问题，好像得使用字符串哈希，不会。

class Solution {
     StringBuilder[] dfsstr_memo ;
    List<List<Integer>> buildTree(int[] parent){
        int n = parent.length;
        List<List<Integer>> tree = new ArrayList<>();
        for(int i=0;i<n;i++){
            tree.add(new ArrayList<>());
        }
        for(int i=1;i<n;i++){
            tree.get(parent[i]).add(i);
        }
        return tree;
    }
    boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    public boolean[] findAnswer(int[] parent, String s) {
        int n = parent.length;
        List<List<Integer>> tree = buildTree(parent);
        boolean[] answer = new boolean[n];
        dfsstr_memo = new StringBuilder[parent.length];
        Arrays.fill(dfsstr_memo, new StringBuilder("1"));

        for (int i = 0; i < n; i++) {
            StringBuilder dfsstr = new StringBuilder();
            dfs(i, tree, s.toCharArray(), dfsstr);
            answer[i] = isPalindrome(dfsstr.toString());
        }
        return answer;
    }
    public  StringBuilder dfs(int x, List<List<Integer>> tree, char[] s, StringBuilder dfsstr) {
        
        if(dfsstr_memo[x].equals("1")){
            return dfsstr_memo[x];
        }

        for (int child : tree.get(x)) {
            dfs(child, tree, s, dfsstr);
        }
  
        return dfsstr_memo[x] = dfsstr.append(s[x]);
    }


}