LeetCode 题解工作台
求出加密整数的和
给你一个整数数组 nums ，数组中的元素都是 正 整数。定义一个加密函数 encrypt ， encrypt(x) 将一个整数 x 中 每一个 数位都用 x 中的 最大 数位替换。比方说 encrypt(523) = 555 且 encrypt(213) = 333 。 请你返回数组中所有元素加密…
2
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·数学
答案摘要
我们直接模拟加密的过程，定义一个函数 ，将一个整数 中每一个数位都用 中的最大数位替换。函数的实现如下： 我们可以通过不断地对 取模和整除 来得到 的每一位数，找到最大的数位，记为 。在循环的过程中，我们还可以用一个变量 来记录 的基础底数，即 $p = 1, 11, 111, \cdots$。最后返回 $mx \times p$ 即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个整数数组 nums ，数组中的元素都是 正 整数。定义一个加密函数 encrypt ，encrypt(x) 将一个整数 x 中 每一个 数位都用 x 中的 最大 数位替换。比方说 encrypt(523) = 555 且 encrypt(213) = 333 。
请你返回数组中所有元素加密后的 和 。
示例 1：
输入：nums = [1,2,3]
输出：6
解释：加密后的元素位 [1,2,3] 。加密元素的和为 1 + 2 + 3 == 6 。
示例 2：
输入：nums = [10,21,31]
输出：66
解释：加密后的元素为 [11,22,33] 。加密元素的和为 11 + 22 + 33 == 66 。
提示：
1 <= nums.length <= 501 <= nums[i] <= 1000
解题思路
方法一：模拟
我们直接模拟加密的过程，定义一个函数 ，将一个整数 中每一个数位都用 中的最大数位替换。函数的实现如下：
我们可以通过不断地对 取模和整除 来得到 的每一位数，找到最大的数位，记为 。在循环的过程中，我们还可以用一个变量 来记录 的基础底数，即 。最后返回 即可。
时间复杂度 ，其中 是数组的长度，而 是数组中元素的最大值。空间复杂度 。
class Solution:
def sumOfEncryptedInt(self, nums: List[int]) -> int:
def encrypt(x: int) -> int:
mx = p = 0
while x:
x, v = divmod(x, 10)
mx = max(mx, v)
p = p * 10 + 1
return mx * p
return sum(encrypt(x) for x in nums)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * d) where n is the array length and d is the max number of digits in nums[i]. Space complexity is O(1) extra space if summing in place, otherwise O(n) for storing encrypted numbers. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate correctly identifies the largest digit in each number.
- question_mark
Observe if the candidate efficiently loops through digits without unnecessary conversions.
- question_mark
Notice if the candidate maintains the correct sum while preserving number lengths in encryption.
常见陷阱
外企场景- error
Assuming the encrypted number is simply the max digit rather than repeating it for the length of the original number.
- error
Using string conversion without handling numbers with multiple digits correctly.
- error
Forgetting to sum the encrypted numbers and returning only the last encrypted value.
进阶变体
外企场景- arrow_right_alt
Compute the sum of encrypted integers where only odd digits are replaced by the largest odd digit in each number.
- arrow_right_alt
Encrypt numbers by replacing each digit with the smallest digit and return their sum.
- arrow_right_alt
Given a 2D array of integers, encrypt each element as described and sum all values.