题目描述
给你一个正整数 num 。你可以交换 num 中 奇偶性 相同的任意两位数字（即，都是奇数或者偶数）。
返回交换 任意 次之后 num 的 最大 可能值。
示例 1：
输入：num = 1234
输出：3412
解释：交换数字 3 和数字 1 ，结果得到 3214 。
交换数字 2 和数字 4 ，结果得到 3412 。
注意，可能存在其他交换序列，但是可以证明 3412 是最大可能值。
注意，不能交换数字 4 和数字 1 ，因为它们奇偶性不同。
示例 2：
输入：num = 65875
输出：87655
解释：交换数字 8 和数字 6 ，结果得到 85675 。
交换数字 5 和数字 7 ，结果得到 87655 。
注意，可能存在其他交换序列，但是可以证明 87655 是最大可能值。
提示：
解法
方法一：计数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution:
def largestInteger(self, num: int) -> int:
cnt = Counter()
x = num
while x:
x, v = divmod(x, 10)
cnt[v] += 1
x = num
ans = 0
t = 1
while x:
x, v = divmod(x, 10)
for y in range(10):
if ((v ^ y) & 1) == 0 and cnt[y]:
ans += y * t
t *= 10
cnt[y] -= 1
break
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | class Solution {
public int largestInteger(int num) {
int[] cnt = new int[10];
int x = num;
while (x != 0) {
cnt[x % 10]++;
x /= 10;
}
x = num;
int ans = 0;
int t = 1;
while (x != 0) {
int v = x % 10;
x /= 10;
for (int y = 0; y < 10; ++y) {
if (((v ^ y) & 1) == 0 && cnt[y] > 0) {
cnt[y]--;
ans += y * t;
t *= 10;
break;
}
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | class Solution {
public:
int largestInteger(int num) {
vector<int> cnt(10);
int x = num;
while (x) {
cnt[x % 10]++;
x /= 10;
}
x = num;
int ans = 0;
long t = 1;
while (x) {
int v = x % 10;
x /= 10;
for (int y = 0; y < 10; ++y) {
if (((v ^ y) & 1) == 0 && cnt[y] > 0) {
cnt[y]--;
ans += y * t;
t *= 10;
break;
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | func largestInteger(num int) int {
cnt := make([]int, 10)
x := num
for x != 0 {
cnt[x%10]++
x /= 10
}
x = num
ans, t := 0, 1
for x != 0 {
v := x % 10
x /= 10
for y := 0; y < 10; y++ {
if ((v^y)&1) == 0 && cnt[y] > 0 {
cnt[y]--
ans += y * t
t *= 10
break
}
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | function largestInteger(num: number): number {
const arrs: number[] = String(num).split('').map(Number);
const odds: number[] = []; // 奇数
const evens: number[] = [];
for (const i of arrs) {
if ((i & 1) == 1) {
odds.push(i);
} else {
evens.push(i);
}
}
odds.sort((a, b) => a - b);
evens.sort((a, b) => a - b);
const ans: number[] = [];
for (const i of arrs) {
ans.push((i & 1) === 1 ? odds.pop() : evens.pop());
}
return Number(ans.join(''));
}
|
方法二：分组 + 排序