leetcode
leetcode 2151 ~ 2200
最近的公平整数

最近的公平整数

难度:

标签:

题目描述

代码结果

运行时间: 30 ms, 内存: 16.1 MB


/*
 * Leetcode Problem 2417: Closest Fair Integer
 * Problem Statement: Given a non-negative integer n, return the closest fair integer. 
 * A fair integer is an integer where the number of even digits is equal to the number of odd digits.
 * If there are multiple answers, return the smallest one.
 */

import java.util.stream.IntStream;

public class ClosestFairIntegerStream {
    // Helper method to count even and odd digits in a number using Java Streams
    private static boolean isFair(int num) {
        long evenCount = String.valueOf(num).chars()
                .filter(ch -> (ch - '0') % 2 == 0)
                .count();
        long oddCount = String.valueOf(num).chars()
                .filter(ch -> (ch - '0') % 2 != 0)
                .count();
        return evenCount == oddCount;
    }

    // Method to find the closest fair integer
    public static int closestFair(int n) {
        return IntStream.iterate(n, i -> i + 1)
                .filter(ClosestFairIntegerStream::isFair)
                .findFirst()
                .orElse(n);
    }

    public static void main(String[] args) {
        int n = 2334; // Example input
        System.out.println(closestFair(n)); // Output the closest fair integer
    }
}

解释

方法:

此题解中的方法是寻找离给定数字n最近的“公平整数”。这里的“公平整数”定义似乎是关于数字中偶数和奇数的位数平衡的。代码首先尝试通过递归调用helper方法来找到从n开始的公平数。如果直接调用失败,则开始递增地搜索更大的数。在循环中,如果从n开始没有找到合适的结果,那么代码会尝试n+1和n+2,并逐步减小n的位数,继续搜索,直到n降为0。helper函数负责统计给定数m的奇数位和偶数位数量,并根据它们的差异和已经考察的额外数字(由变量count表示)来判断能否形成一个公平数。如果可以形成,它还将根据需要添加0或1来构造最终的公平数。

时间复杂度:

O(d^2)

空间复杂度:

O(d)

代码细节讲解

🦆
如何确保递归方法`helper`在处理较大的数值时不会导致性能问题,特别是在考虑到Python的整数不受固定大小限制的情况下?
为了确保`helper`方法在处理较大数值时不导致性能问题,应该关注减少递归调用的次数和避免在每次调用时进行重复计算。在实现中可以采用记忆化技术(缓存之前的计算结果),以避免重复计算相同数值的公平性检查。此外,由于每次递归都减少数字的位数,这自然限制了递归的深度。例如,对于一个10位数的整数,最多只需要10次递归即可将数字减至0。这种设计有效地控制了递归的深度和执行次数,从而避免了性能问题。
🦆
在减少n的位数的过程中,为什么选择通过`n = n // 10`的方式逐步减少,这种方法在什么情况下可能不会导致找到一个公平整数?
通过`n = n // 10`减少数字位数的主要目的是为了逐渐减少搜索空间,同时也是一种回退策略,当找不到更大的公平数时尝试更小的数位组合。这种方法可能在所有更大的数字都不是公平数,而通过逐步减少位数也不能构成公平数的情况下失败。例如,如果最初的数已经非常接近于一个较大范围内的最小公平数,减少位数可能会跳过潜在的公平数,导致无法找到答案。
🦆
算法中对`count`变量的使用有何意义,它是如何帮助确定是否可以构造一个公平数的?
`count`变量在算法中用于跟踪减少数字位数的次数,这影响了需要添加的额外数字(0或1)来构成公平数。每当数字n通过`n = n // 10`减少一位时,`count`增加1,表示额外需要一个数字来平衡奇数和偶数的数量。通过计算`(count + diff) // 2`和`(count - diff) // 2`来确定需要添加多少个0和1,这样就可以判断出能否通过添加特定数量的0和1来构成一个公平数。如果计算结果表明需要添加的0或1的数量为负,则当前的n和count组合无法构成公平数。

相关问题