贪心算法

力扣2384：最大回文数字

给你一个仅由数字（0 - 9）组成的字符串 num 。请你找出能够使用 num 中数字形成的 最大回文 整数，并以字符串形式返回。该整数不含 前导零 。
注意：你 无需 使用 num 中的所有数字，但你必须使用 至少 一个数字。数字可以重新排序。

示例1：
输入：num = “444947137”
输出：”7449447”

示例2：
输入：num = “00009”
输出：”9”

思路：贪心。统计每个数字出现的次数，从大的开始选，如果数字次数大于1，则选两个，放在头尾，最后再选一个最大的放在中间。注意边界条件，如果只有0的次数大于1，则直接选一个最大的作为答案。

代码：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public String largestPalindromic(String num) {
        int n = num.length();
        int[] count = new int[10];
        // 统计每个数出现的次数
        for (int i = 0; i < n; ++i) {
            char c = num.charAt(i);
            count[c - '0']++;
        }
        int p = 9; // 从大的开始选,这种形式是最大的98765...56789，优先把大的放在开头和结尾
        StringBuilder ansLeft = new StringBuilder();
        while (p >= 0) {
            // 边界情况，只有0的次数大于1
            if (ansLeft.length() == 0 && p == 0) {
                break;
            }
            while (count[p] > 1) {
                ansLeft.append(p);
                count[p] -= 2;
            }
            p--;
        }
        // 只剩单个(可能没有),选一个最大的放中间
        int max = -1;
        for (int i = 9; i >= 0; --i) {
            if (count[i] > 0) {
                max = i;
                break;
            }
        }
        StringBuilder ans = new StringBuilder();
        // 如果不剩单个的了，直接左右拼接
        if (max != -1) {
            ans.append(ansLeft).append(max).append(ansLeft.reverse());
        } else {
            ans.append(ansLeft).append(ansLeft.reverse());  // 有单个，放中间一起拼接
        }
        return ans.toString();
    }
}

时间复杂度：O(n)