2025力扣刷题记录

3270. 求出数字答案

1.字符串判断

先把这三个数转为填充后的字符串，然后对每一位进行判断。

public int generateKey(int num1, int num2, int num3) {
        List<Integer> numList = List.of(num1, num2, num3);
        ArrayList<String> strings = new ArrayList<>();
        numList.forEach(num->{
            StringBuilder s = new StringBuilder(Integer.toString(num));
            // 在前面补0的个数
            int count = 4 - s.length();
            for(int i = 0;i < count;i++){
                s.insert(0, "0");
            }
            strings.add(String.valueOf(s));
        });
        //System.out.println("strings = " + strings);
        StringBuilder builder = new StringBuilder();
        for(int i = 0;i < 4;i++){
            int min = Character.MAX_VALUE;
            for(int j = 0;j < 3;j++){
                String s = strings.get(j);
                min =  Math.min(min,s.charAt(i) - '0');
            }
            builder.append(min);
        }
        return Integer.parseInt(builder.toString());
    }

2. 从最低位开始计算

public int generateKey(int num1, int num2, int num3) {
        int ans = 0;
        int pow = 1;
        for (int i = 0; i < 4; i++) {
            // 获取这三个数最小各位值
            int t = Math.min(num1 % 10, num2 % 10);
            int min = Math.min(t, num3 % 10);
            ans = ans + min * pow;
            num1 /= 10;
            num2 /= 10;
            num3 /= 10;
            pow *= 10;
        }
        return ans;
    }

75. 颜色分类

思路就是用分别用一个计数器，分别记录0和（0,1)出现的次数，此时n0就是到目前为止出现的最后一个0的下标，n1同理。然后总是假设当前这块板是蓝色的，为它刷上蓝色，接着判断当前值是否等于1，如果是，则把它刷为白色，0也是同理，类似刷油漆的过程，旧的会被新的覆盖。

public void sortColors(int[] nums) {
       // 到第i个数为止，出现0的次数，也就是到目前为止，最后一个0的下标
       int n0 = 0;
       // 到第i个数为止，出现0和1的次数，也就是到目前为止，最后一个1的下标
       int n1 = 0;
       for(int i = 0;i < nums.length;i++){
           int num = nums[i];
           nums[i] = 2;
           if(num < 2){
               nums[n1++] = 1;
           }
           if(num < 1){
               nums[n0++] = 0;
           }
       }
   }

2444. 统计定界子数组的数目

public long countSubarrays(int[] nums, int minK, int maxK) {
        long ans = 0;
        // 窗口中最后一出现minK下标
        int minIndex = -1;
        // 窗口中最后一出现maxK下标
        int maxIndex = -1;
        // 窗口左边界
        int left = 0;
        for(int i = 0;i < nums.length;i++){
            int num = nums[i];
            // 寻找最后一次出现minK或者maxK的下标
            // 为什么要这样做：因为当窗口确定时，[left,right]中一定存在minK和maxK，此时如果窗口中出现多个minK和maxK
            // 如果对应的下标越靠后，能够确定的子数组越多，防止统计不到
            if(num == minK){
                minIndex = i;
            }
            if(num == maxK){
                maxIndex = i;
            }
            // 当出现一个小于minK或者大于maxK的值时，重置窗口
            if( num > maxK || num < minK){
                left = i+1;
                minIndex = -1;
                maxIndex = -1;
            }
            // 能够组成窗口时，累加答案
            else if(minIndex != -1 && maxIndex != -1){
                // [left - minIndex - maxIndex - right] 或 [left - maxIndex - minIndex - right]
                // 此时[left ... min]都是满足条件的子数组
                ans += Math.min(maxIndex, minIndex) - left + 1;
            }
        }
        return ans;
    }

2302. 统计得分小于 K 的子数组数目

public long countSubarrays(int[] nums, long k) {
    int left = 0;
    long sum = 0;
    long ans = 0;
    for(int right = 0;right < nums.length;right++){
        int num = nums[right];
        // 将当前数加入窗口中
        sum += num;
        // 内循环，如果当前窗口和*窗口长度 大于等于 k时，移动左窗口，直至窗口满足条件
        while (sum * (right - left + 1) >= k){
            sum -= nums[left];
            left++;
        }
        // 这里是随着当前数加入窗口后当增加的子数组个数，而不是当前窗口内能够组成的子数组个数
        // 比如[2,1,4,3]当4加入窗口中时，增加的子数组为[2,1,4,3],[1,4,3],[4,3],[4]共计4个
        // 因为之前的已经统计过了，不用再次计算
        ans += right - left + 1;
    }
    return ans;
}

2962. 统计最大元素出现至少 K 次的子数组

这道题目和前面的那些滑动窗口题目类似，先是扩张窗口使得窗口内最大元素个数为k，然后在内循环中收缩窗口，直至窗口内最大元素个数为k-1（此时是窗口恰好不满足的情况）。

public long countSubarrays(int[] nums, int k) {
    int max = Arrays.stream(nums).max().getAsInt();
    int left = 0;
    long ans = 0;
    //当前窗口内最大元素的个数
    int count = 0;
    for(int right = 0;right < nums.length;right++){
        int num = nums[right];
        if(num == max){
            count++;
        }
        //内循环，使得窗口内最大元素个数小于k
        while (count >= k){
            if(nums[left] == max){
                count--;
            }
            left++;
        }
        //右指针固定时，left 的位置保证了所有左端点 < left 对应的子数组 [left_start, right] 必             //然包含至少 k 个最大值。ans += left 正是累加这些合法的左端点数目
        ans += left;
    }
    return ans;
}

763. 划分字母区间

这道题目是贪心算法思想，在划分时如果包含一个字符，则该次划分必须包含所有字符。

算法步骤：

1：计算字符串s中每个字符最后一次出现的位置。

2：对字符串进行遍历，在遍历中不断更新右窗口最大下标。

3：当到达右窗口时，统计当前划分，重新赋值，开始下一轮划分。

public List<Integer> partitionLabels(String s) {
       int n = s.length();
       //统计每个字符的最大下标
       int[] maxIndex = new int[26];
       for(int i = 0;i < n;i++){
           maxIndex[s.charAt(i) - 'a'] = i;
       }
       ArrayList<Integer> ans = new ArrayList<>();
       //记录当前统计的边界
       int left = 0,right = 0;
       for(int i = 0;i < n;i++){
           char c = s.charAt(i);
           right = Math.max(right,maxIndex[c - 'a']);
           //到达当前一次划分边界，统计结果
           if(i == right){
               ans.add(right - left + 1);
               left = i+1;
           }
       }
       return ans;
   }

1295. 统计位数为偶数的数字

1.直接统计位数

public int findNumbers(int[] nums) {
        int ans = 0;
        for(int num : nums){
            int count = 0;
            while (num > 0){
                count++;
                num /= 10;
            };
            if (count % 2 == 0){
                ans++;
            }
        }
        return ans;
    }

2.使用对数函数

以10为底的对数函数向下取整为int可以获取除了第一位之外的位数，对结果加一即可获取x的位数。

public int findNumbers(int[] nums) {
        int ans = 0;
        for(int num : nums){
            int count = (int) Math.log10(num) + 1;
            if(count % 2 == 0){
                ans++;
            }
        }
        return ans;
    }