[leetCode 丶 20241111] 2827. 范围中美丽整数的数目

原题:
https://leetcode.cn/problems/number-of-beautiful-integers-in-the-range/description/

描述:

给你正整数 low ，high 和 k 。

如果一个数满足以下两个条件，那么它是 美丽的 ：

偶数数位的数目与奇数数位的数目相同。
这个整数可以被 k 整除。
请你返回范围 [low, high] 中美丽整数的数目。

示例 1：

输入： low = 10, high = 20, k = 3
输出： 2
解释： 给定范围中有 2 个美丽数字：[12,18]

12 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。

18 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。
以下是一些不是美丽整数的例子：

16 不是美丽整数，因为它不能被 k = 3 整除。

15 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。
给定范围内总共有 2 个美丽整数。

示例 2：

输入： low = 1, high = 10, k = 1
输出： 1
解释： 给定范围中有 1 个美丽数字：[10]

10 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 1 整除。
给定范围内总共有 1 个美丽整数。

示例 3：

输入： low = 5, high = 5, k = 2
输出： 0
解释： 给定范围中有 0 个美丽数字。

5 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。

提示

0 < low <= high <= 10^9
0 < k <= 20

个人版答案

执行用时: 超时... ms 执行内存消耗: ... M


class Solution {
    public int numberOfBeautifulIntegers(int low, int high, int k) {
        int len = high - low + 1;
        Set<Integer> s = new HashSet<>();
        for(int i = 0; i < len; i++){
            int tmp = low + i;
            if(isBeauful(tmp)){
                if((tmp % k == 0)){
                    s.add(tmp);
                }
            }
        }
        return s.size();
    }

    public boolean isBeauful(int tmp){
        int oddCount = 0; 
        int evenCount = 0; 
        String numberStr = String.valueOf(tmp);
        if(numberStr.length() % 2 != 0){
            return false;
        }
        for (int i = 0; i < numberStr.length(); i++) {
            int digit = numberStr.charAt(i) - '0';
            if (digit % 2 == 0) {
                evenCount++;
            } else {
                oddCount++;
            }
        }
        return oddCount == evenCount;
    }
}

优秀解法

执行耗时: 88 ms


class Solution {
    public int numberOfBeautifulIntegers(int low, int high, int k) {
        int highLength = getLength(high);
        int lowLength = getLength(low);
        int zero = highLength;
        int[][][] dps = new int[highLength][k][highLength << 1 | 1];
        dps[0][0][zero] = 1;

        int maxDiff = highLength << 1 | 1;
        int baseRes = 0;
        int preLength = 0, numDiff = 0, numMod = 0;
        int mid = zero >> 1, left = zero - mid, right = zero + mid;
        int[] rights = new int[]{(mid & 1) ^ right , (mid & 1 ^ 1) + right};
      
        for (int length = 1, tens = 1; length < highLength; tens *= 10, length++) {
            preLength = length - 1;
            for (int num = 1, numTen = tens; num < 10; num++, numTen += tens) {
                numDiff = 1 - ((num & 1) << 1);
                for (int mod = 0; mod < k; mod++) {
                    numMod = (mod + numTen) % k;
                    for (int diff = rights[preLength & 1]; diff >= left; diff -= 2) {
                        dps[length][numMod][diff + numDiff] += dps[preLength][mod][diff];
                    }
                }
            }
            if ((length & 1) == 0 && length >= lowLength) baseRes += dps[length][0][highLength];
          
            for (int mod = 0; mod < k; mod++) {
                for (int diff = rights[preLength & 1]; diff >= left; diff -= 2) {
                    dps[length][mod][diff + 1] += dps[preLength][mod][diff];
                }
            }
        }
      
        int highRes = dp(dps, k, high, highLength, zero);
        int lowRes = dp(dps, k, low, lowLength, zero);

        return baseRes + highRes - lowRes + checkNum(high, k);

    }

    public int dp(int[][][] dps, int k, int target, int targetMaxLength, int zero) {
        if ((targetMaxLength & 1) == 1) return 0;
        int res = 0;

        int targetPreDiff = 0;
        for (int avatarTarget = target, tens = 1; avatarTarget > 0; avatarTarget /= 10) targetPreDiff += 1 - ((avatarTarget & 1) << 1);

        int preLength = 0, numDiff = 0, preMod, preDiff, preDiffCache;
        int targetMod = 0, targetExMod = 0;
        for (int length = 1, tens = 1; length <= targetMaxLength; target /= 10, tens *= 10, length++) {
            preLength = length - 1;
            targetMod = target % 10;
            targetExMod = target - targetMod;
            targetPreDiff -= 1 - ((targetMod & 1) << 1);
            preDiffCache = zero - targetPreDiff - 1;
       
            for (int mod = target < 10 ? 1 : 0; mod < targetMod; mod++) {
                preMod = (k - (targetExMod + mod) * tens % k) % k;
                preDiff = preDiffCache + ((mod & 1) << 1);
                res += dps[preLength][preMod][preDiff];
            }
        }

        return res;
    }

    private int getLength(int num) {
        int length = 0;
        while (num > 0) {
            num /= 10;
            length++;
        }
        return length;
    }

    private int checkNum(int num, int k) {
        if (num % k > 0) return 0;
        int res = 0;
        while (num > 0) {
            res += 1 - ((num & 1) << 1);
            num /= 10;
        }
        return res == 0 ? 1 : 0;
    }
}

个人解题思路与优秀答案解析

题目分析及个人版思路

每个位置上的奇数和偶数的个数相等, 同时被K整除...这还有啥看的
超出时间限制...
我优化了先判断, 企图过滤掉根本不能被K整除的数
我尝试用位运算...


/* 使用位与, 判断最低位是不是奇数, 然后数字右移一位... */
int oddCount = 0; 
int evenCount = 0; 

while (tmp != 0) {
    if ((tmp & 1) == 1) {
        oddCount++;
    } else {
        evenCount++;
    }
    tmp >>>= 1;
}