【每日一题Day342】LC2578最小和分割 | 贪心

简介: 【每日一题Day342】LC2578最小和分割 | 贪心

最小和分割【LC2578】

给你一个正整数 num ,请你将它分割成两个非负整数 num1 和 num2 ,满足:

num1和 num2直接连起来,得到 num各数位的一个排列。

换句话说,num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。

num1 和 num2 可以包含前导 0 。

请你返回 num1 和 num2 可以得到的和的 最小 值。

注意:

num 保证没有前导 0 。

num1 和 num2 中数位顺序可以与 num 中数位顺序不同。

  • 思路
  • 局部最优:统计num中每个数字的出现次数,从0开始逐位构造,使两个数字的最高位最小
  • 全局最优:使num1和num2的和最小
  • 实现
class Solution {
    public int splitNum(int num) {
        // 贪心构造:高位一定是较小值
        int[] count = new int[10];
        while(num > 0){
            count[num % 10]++;
            num /= 10;
        }
        int num1 = 0, num2 = 0;
        int index = 0, i = 0;
        while (i < 10){
            if (count[i] == 0){
                i++;
            }else if ((index & 1) == 0){
                num1 = num1 * 10 + i;
                count[i]--;
                index++;
            }else{
                num2 = num2 * 10 + i;
                count[i]--;
                index++;
            }
        }
        return num1 + num2;
    }
}

复杂度

时间复杂度:O ( log ⁡ n u m )

空间复杂度:O ( C )

目录
相关文章
|
7月前
【每日一题Day302】LC849到最近的人的最大距离 | 贪心+分类讨论
【每日一题Day302】LC849到最近的人的最大距离 | 贪心+分类讨论
55 0
|
7月前
【每日一题Day141】LC2379得到 K 个黑块的最少涂色次数 | 滑动窗口
【每日一题Day141】LC2379得到 K 个黑块的最少涂色次数 | 滑动窗口
41 0
|
7月前
【每日一题Day149】LC2389和有限的最长子序列 | 贪心+前缀和+二分查找
【每日一题Day149】LC2389和有限的最长子序列 | 贪心+前缀和+二分查找
47 0
|
7月前
【每日一题Day118】LC1124表现良好的最长时间段 | 前缀和+单调栈/哈希表
【每日一题Day118】LC1124表现良好的最长时间段 | 前缀和+单调栈/哈希表
55 0
|
7月前
【每日一题Day130】LC1255得分最高的单词集合 | 回溯
【每日一题Day130】LC1255得分最高的单词集合 | 回溯
46 0
|
7月前
|
人工智能 BI
【每日一题Day354】LC2316统计无向图中无法互相到达点对数 | 并查集
【每日一题Day354】LC2316统计无向图中无法互相到达点对数 | 并查集
57 0
|
7月前
|
vr&ar
【每日一题Day166】LC1053交换一次的先前排列 | 贪心
【每日一题Day166】LC1053交换一次的先前排列 | 贪心
72 1
|
7月前
【每日一题Day160】LC1092最短公共超序列 | 动态规划
【每日一题Day160】LC1092最短公共超序列 | 动态规划
41 0
【每日一题Day160】LC1092最短公共超序列 | 动态规划
|
7月前
【每日一题Day358】LC2698求一个整数的惩罚数 | 递归
【每日一题Day358】LC2698求一个整数的惩罚数 | 递归
53 0
|
7月前
【每日一题Day223】LC1130叶值的最小代价生成树 | 贪心 区间dp
【每日一题Day223】LC1130叶值的最小代价生成树 | 贪心 区间dp
47 0