Question

2566. 替换一个数字后的最大差值

English Version

题目描述

给你一个整数 num 。你知道 Danny Mittal 会偷偷将 0 到 9 中的一个数字 替换 成另一个数字。

请你返回将 num 中 恰好一个 数字进行替换后，得到的最大值和最小值的差为多少。

注意：

• 当 Danny 将一个数字 d1 替换成另一个数字 d2 时，Danny 需要将 nums 中所有 d1 都替换成 d2 。
• Danny 可以将一个数字替换成它自己，也就是说 num 可以不变。
• Danny 可以将数字分别替换成两个不同的数字分别得到最大值和最小值。
• 替换后得到的数字可以包含前导 0 。
• Danny Mittal 获得周赛 326 前 10 名，让我们恭喜他。

 

示例 1：

输入：num = 11891
输出：99009
解释：
为了得到最大值，我们将数字 1 替换成数字 9 ，得到 99899 。
为了得到最小值，我们将数字 1 替换成数字 0 ，得到 890 。
两个数字的差值为 99009 。

示例 2：

输入：num = 90
输出：99
解释：
可以得到的最大值是 99（将 0 替换成 9），最小值是 0（将 9 替换成 0）。
所以我们得到 99 。

 

提示：

• 1 <= num <= 108

解法

方法一：贪心

我们先将数字转为字符串 $s$。

要得到最小值，我们只需要将找到字符串 $s$ 的第一个数字 $s[0]$，然后把字符串中所有的 $s[0]$ 替换成 $0$ 即可。

要得到最大值，我们需要找到字符串 $s$ 中第一个不是 $9$ 的数字 $s[i]$，然后把字符串中所有的 $s[i]$ 替换成 $9$ 即可。

最后返回最大值和最小值的差即可。

时间复杂度 $O(\log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数字 $num$ 的大小。

class Solution:
  def minMaxDifference(self, num: int) -> int:
    s = str(num)
    mi = int(s.replace(s[0], '0'))
    for c in s:
      if c != '9':
        return int(s.replace(c, '9')) - mi
    return num - mi

class Solution {
  public int minMaxDifference(int num) {
    String s = String.valueOf(num);
    int mi = Integer.parseInt(s.replace(s.charAt(0), '0'));
    for (char c : s.toCharArray()) {
      if (c != '9') {
        return Integer.parseInt(s.replace(c, '9')) - mi;
      }
    }
    return num - mi;
  }
}

class Solution {
public:
  int minMaxDifference(int num) {
    string s = to_string(num);
    string t = s;
    char first = s[0];
    for (char& c : s) {
      if (c == first) {
        c = '0';
      }
    }
    int mi = stoi(s);
    for (int i = 0; i < t.size(); ++i) {
      if (t[i] != '9') {
        char second = t[i];
        for (int j = i; j < t.size(); ++j) {
          if (t[j] == second) {
            t[j] = '9';
          }
        }
        return stoi(t) - mi;
      }
    }
    return num - mi;
  }
};

func minMaxDifference(num int) int {
  s := []byte(strconv.Itoa(num))
  first := s[0]
  for i := range s {
    if s[i] == first {
      s[i] = '0'
    }
  }
  mi, _ := strconv.Atoi(string(s))
  t := []byte(strconv.Itoa(num))
  for i := range t {
    if t[i] != '9' {
      second := t[i]
      for j := i; j < len(t); j++ {
        if t[j] == second {
          t[j] = '9'
        }
      }
      mx, _ := strconv.Atoi(string(t))
      return mx - mi
    }
  }
  return num - mi
}

function minMaxDifference(num: number): number {
  const s = num + '';
  const min = Number(s.replace(new RegExp(s[0], 'g'), '0'));
  for (const c of s) {
    if (c !== '9') {
      return Number(s.replace(new RegExp(c, 'g'), '9')) - min;
    }
  }
  return num - min;
}

impl Solution {
  pub fn min_max_difference(num: i32) -> i32 {
    let s = num.to_string();
    let min = s.replace(char::from(s.as_bytes()[0]), "0").parse::<i32>().unwrap();
    for &c in s.as_bytes() {
      if c != b'9' {
        return s.replace(c, "9").parse().unwrap() - min;
      }
    }
    num - min
  }
}

int getLen(int num) {
  int res = 0;
  while (num) {
    num /= 10;
    res++;
  }
  return res;
}

int minMaxDifference(int num) {
  int n = getLen(num);
  int* nums = malloc(sizeof(int) * n);
  int t = num;
  for (int i = n - 1; i >= 0; i--) {
    nums[i] = t % 10;
    t /= 10;
  }
  int min = 0;
  for (int i = 0; i < n; i++) {
    min *= 10;
    if (nums[i] != nums[0]) {
      min += nums[i];
    }
  }
  int max = 0;
  int target = 10;
  for (int i = 0; i < n; i++) {
    max *= 10;
    if (target == 10 && nums[i] != 9) {
      target = nums[i];
    }
    max += nums[i] == target ? 9 : nums[i];
  }
  free(nums);
  return max - min;
}

方法二

impl Solution {
  pub fn min_max_difference(num: i32) -> i32 {
    let mut s = num.to_string().into_bytes();
    let first = s[0];
    for i in 0..s.len() {
      if s[i] == first {
        s[i] = b'0';
      }
    }
    let mi = String::from_utf8_lossy(&s).parse::<i32>().unwrap();

    let mut t = num.to_string().into_bytes();
    for i in 0..t.len() {
      if t[i] != b'9' {
        let second = t[i];

        for j in 0..t.len() {
          if t[j] == second {
            t[j] = b'9';
          }
        }

        let mx = String::from_utf8_lossy(&t).parse::<i32>().unwrap();
        return mx - mi;
      }
    }

    num - mi
  }
}