You are given an integer num
. You will apply the following steps exactly two times:
- Pick a digit
x (0 <= x <= 9)
. - Pick another digit
y (0 <= y <= 9)
. The digity
can be equal tox
. - Replace all the occurrences of
x
in the decimal representation ofnum
byy
. - The new integer cannot have any leading zeros, also the new integer cannot be 0.
Let a
and b
be the results of applying the operations to num
the first and second times, respectively.
Return the max difference between a
and b
.
Example 1:
Input: num = 555 Output: 888 Explanation: The first time pick x = 5 and y = 9 and store the new integer in a. The second time pick x = 5 and y = 1 and store the new integer in b. We have now a = 999 and b = 111 and max difference = 888
Example 2:
Input: num = 9 Output: 8 Explanation: The first time pick x = 9 and y = 9 and store the new integer in a. The second time pick x = 9 and y = 1 and store the new integer in b. We have now a = 9 and b = 1 and max difference = 8
Example 3:
Input: num = 123456 Output: 820000
Example 4:
Input: num = 10000 Output: 80000
Example 5:
Input: num = 9288 Output: 8700
Constraints:
1 <= num <= 10^8
Solution 1: Brute Force
Try all possible pairs of (x, y)
Time complexity: O(10*10*logn)
Space complexity: O(logn)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int maxDiff(int num) { int min_num = INT_MAX; int max_num = INT_MIN; for (char x = '0'; x <= '9'; ++x) for (char y = '0'; y <= '9'; ++y) { string n = to_string(num); for (char& c : n) if (c == x) c = y; if (n[0] == '0') continue; int v = stoi(n); min_num = min(min_num, v); max_num = max(max_num, v); } return max_num - min_num; } }; |
Solution 2: Greedy
Maximize A and Minimize B
A – B will the answer.
To maximize A, find the left most digit that is not 9, replace that digit with 9.
e.g. 121 => 919
e.g. 9981 => 9991
To minimize B, fin the left most digit that is not 1 or 0, replace that digit with 0 (if not the first one) or 1.
e.g. 1024 -> 1004
e.g. 2024 -> 1014
Time complexity: O(logn)
Space complexity: O(logn)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: int maxDiff(int num) { string s = to_string(num); const int n = s.length(); string n1(s); string n2(s); s += '#'; // append an unmatchable char to avoid out_of_bound. int x = 0; int y = 0; while (x < n && (s[x] == '0' || s[x] == '1')) ++x; while (y < n && s[y] == '9') ++y; for (char& c : n1) if (c == s[x]) c = x ? '0' : '1'; for (char& c : n2) if (c == s[y]) c = '9'; return stoi(n2) - stoi(n1); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment