Question

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)$。

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)

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;
  }
}

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;
  }
};

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
}

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);
}