README.md

comments	difficulty	edit_url	rating	source	tags
true	简单	https://github.com/doocs/leetcode/edit/main/solution/3000-3099/3079.Find%20the%20Sum%20of%20Encrypted%20Integers/README.md	1190	第 126 场双周赛 Q1	数组 数学

3079. 求出加密整数的和

English Version

题目描述

给你一个整数数组 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 <= 50
• 1 <= nums[i] <= 1000

解法

方法一：模拟

我们直接模拟加密的过程，定义一个函数 $encrypt(x)$，将一个整数 $x$ 中每一个数位都用 $x$ 中的最大数位替换。函数的实现如下：

我们可以通过不断地对 $x$ 取模和整除 $10$ 来得到 $x$ 的每一位数，找到最大的数位，记为 $mx$。在循环的过程中，我们还可以用一个变量 $p$ 来记录 $mx$ 的基础底数，即 $p = 1, 11, 111, \cdots$。最后返回 $mx \times p$ 即可。

时间复杂度 $O(n \times \log M)$，其中 $n$ 是数组的长度，而 $M$ 是数组中元素的最大值。空间复杂度 $O(1)$。

Python3

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)

Java

class Solution {
    public int sumOfEncryptedInt(int[] nums) {
        int ans = 0;
        for (int x : nums) {
            ans += encrypt(x);
        }
        return ans;
    }

    private int encrypt(int x) {
        int mx = 0, p = 0;
        for (; x > 0; x /= 10) {
            mx = Math.max(mx, x % 10);
            p = p * 10 + 1;
        }
        return mx * p;
    }
}

C++

class Solution {
public:
    int sumOfEncryptedInt(vector<int>& nums) {
        auto encrypt = [&](int x) {
            int mx = 0, p = 0;
            for (; x; x /= 10) {
                mx = max(mx, x % 10);
                p = p * 10 + 1;
            }
            return mx * p;
        };
        int ans = 0;
        for (int x : nums) {
            ans += encrypt(x);
        }
        return ans;
    }
};

Go

func sumOfEncryptedInt(nums []int) (ans int) {
	encrypt := func(x int) int {
		mx, p := 0, 0
		for ; x > 0; x /= 10 {
			mx = max(mx, x%10)
			p = p*10 + 1
		}
		return mx * p
	}
	for _, x := range nums {
		ans += encrypt(x)
	}
	return
}

TypeScript

function sumOfEncryptedInt(nums: number[]): number {
    const encrypt = (x: number): number => {
        let [mx, p] = [0, 0];
        for (; x > 0; x = Math.floor(x / 10)) {
            mx = Math.max(mx, x % 10);
            p = p * 10 + 1;
        }
        return mx * p;
    };
    return nums.reduce((acc, x) => acc + encrypt(x), 0);
}