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

题目描述

给你一个字符串 target。Alice 使用一种特殊的键盘输入 target，这个键盘 只有两个 按键：

按键 1：在屏幕上追加字符 'a'。
按键 2：将屏幕上的最后一个字符更改为下一个字母（例如 'c' 变为 'd'，'z' 变为 'a'）。

最初，屏幕是空字符串 ""，Alice 只能按下按键 1。

请你返回 Alice 输入 target 时出现的所有字符串列表，按出现顺序排序，并使用最少的按键次数。

示例分析

示例 1：
- 输入：target = "abc"
- 输出：["a", "aa", "ab", "aba", "abb", "abc"]
- 解析：
  - Alice 从空字符串开始，先追加 'a' 得到 "a"。
  - 再次追加 'a' 得到 "aa"。
  - 将最后一个字符 'a' 修改为 'b' 得到 "ab"。
  - 追加 'a' 得到 "aba"，再将 'a' 修改为 'b' 得到 "abb"，最后修改为 'c' 得到 "abc"。
示例 2：
- 输入：target = "he"
- 输出：["a", "b", "c", "d", "e", "f", "g", "h", "ha", "hb", "hc", "hd", "he"]
- 解析：Alice 从 'a' 开始，一步步修改直到 'h'，然后追加 'a' 并修改为 'e'。

代码实现

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> stringSequence(String target) {
        char[] chars = new char[target.length()];
        List<String> ans = new ArrayList<>();
        int i = 0;
        for (char c : target.toCharArray()) {
            int sw = c - 'a';
            for (int w = 0; w <= sw; w++) {
                chars[i] = (char) ('a' + w);
                ans.add(new String(chars, 0, i + 1));
            }
            i++;
        }
        return ans;
    }
}

分析

思路：使用一个字符数组 chars 存储当前生成的字符串，并逐步生成目标字符串。
实现步骤：
- 遍历 target 字符串中的每个字符。
- 对于每个字符，计算从 'a' 到当前字符的差值 sw，逐步按序生成这些字符。
- 将生成的每一个中间状态加入结果列表。
时间复杂度：O(n * 26)，其中 n 是 target 的长度。每个字符最多需要遍历 26 次。

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

题目描述

给你一个字符串 s 和一个整数 k，统计并返回所有至少有一个字符至少出现 k 次的子字符串总数。

示例分析

示例 1：
- 输入：s = "abacb", k = 2
- 输出：4
- 解析：
  - "aba" 中 'a' 出现 2 次。
  - "abac" 中 'a' 出现 2 次。
  - "abacb" 中 'a' 出现 2 次。
  - "bacb" 中 'b' 出现 2 次。
示例 2：
- 输入：s = "abcde", k = 1
- 输出：15
- 解析：所有子字符串都满足条件，因为每个字符至少出现一次。

代码实现

public class Solution {
    public int numberOfSubstrings(String s, int k) {
        int n = s.length();
        int result = 0;
        int[] count = new int[26]; 
        int l = 0;

        for (int r = 0; r < n; r++) {
            count[s.charAt(r) - 'a']++;
            while (check(count, k)) {
                result += n - r;
                count[s.charAt(l) - 'a']--;
                l++;
            }
        }

        return result;
    }

    private boolean check(int[] count, int k) {
        for (int c : count) {
            if (c >= k) {
                return true;
            }
        }
        return false;
    }
}

分析

思路：利用滑动窗口来维护一个窗口，使得窗口内至少有一个字符出现次数大于等于 k。
窗口调整：
- 当窗口右边界增加字符时，检查当前窗口是否满足条件。
- 如果满足，说明从 l 到 r 的所有子字符串都符合条件，累加结果。
- 然后缩小窗口的左边界，并继续检查。
时间复杂度：O(n)，双指针法遍历字符串。

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

题目描述

给你一个整数数组 nums 。每次可以选择 nums 中的一个元素，将它除以它的最大真因数。目标是使数组变为非递减的，返回最少操作次数。如果无法达成，返回 -1。

示例分析

示例 1：
- 输入：nums = [25, 7]
- 输出：1
- 解析：将 25 除以其最大真因数 5，得到 [5, 7]。
示例 2：
- 输入：nums = [7, 7, 6]
- 输出：-1
- 解析：无论怎么操作，都无法使 6 大于等于 7。
示例 3：
- 输入：nums = [1, 1, 1, 1]
- 输出：0
- 解析：数组本身就是非递减的。

代码实现

class Solution {
    public int minOperations(int[] nums) {
        int ans = 0;
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i] < nums[i - 1]) {
                int max = getMax(nums[i - 1]);
                if (max == -1 || nums[i - 1] / max > nums[i]) {
                    return -1;
                }
                nums[i - 1] /= max;
                ans++;
            }
        }
        return ans;
    }

    public int getMax(int target) {
        int ans = 0;
        for (int i = 2; i * i <= target; i++) {
            if (target % i == 0) {
                ans = Math.max(Math.max(i, target / i), ans);
            }
        }
        return ans == 0 || ans == target ? -1 : ans;
    }
}

分析

思路：
- 从右向左遍历数组，确保每个元素不大于其右侧元素。
- 当 nums[i-1] 大于 nums[i] 时，查找 nums[i-1] 的最大真因数。
- 如果除以该因数后仍满足条件，则更新数组和操作次数，否则返回 -1。
函数 getMax：
- 找出 target 的最大真因数。使用简单的因数枚举法。
- 若没有合适的真因数，返回 -1。
时间复杂度：O(n * sqrt(max(nums)))，其中 n 是数组长度。

优化

只优化求最大的过程，不优化重复计算

if (target % i == 0)
{
    // 当找到最小的时候最大的也就出现看了
    return ans = Math.max(Math.max(i , target/i), ans);
}

优化重复计算

预处理：预处理每个整数的最小质因数(lpf , Least Prime Factor)

        for (int i = 2; i < 10001; i++) {
            if (lpf[i] == 0) {
                for (int j = i; j < MX; j += i) {
                    if (lpf[j] == 0) {
                        lpf[j] = i;
                    }
                }
            }
        }