【每日一题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 )

目录
打赏
0
0
0
0
5
分享
相关文章
【每日一题Day63】LC1753移除石子的最大得分 | 贪心 + 数学
当对a,b,c进行升序排序后,如果a+b≥c,应先优先让a 和b去匹配,匹配的次数为a+b−c,得分为count=⌈(a+b−c)/2⌉
108 0
【每日一题Day27】LC805数组的均值分割 | 01背包
当能够分成两个等均值的数组时,均值为固定值,即为数组nums的均值AVE,推导如下,nA和nB分别代表数组A和数组B的长度,sum为数组nums的和,a=average(A) = average(B)
85 0
【每日一题Day99】LC1663具有给定数值的最小字符串 | 贪心
如果k−(n−i)∗26<=1,那么表示尾部全部插入z,没有分数剩余甚至还有同于,那么第i个字符可以插入的最小字符'a',贡献的分数为1
77 0
|
9月前
|
【每日一题Day166】LC1053交换一次的先前排列 | 贪心
【每日一题Day166】LC1053交换一次的先前排列 | 贪心
87 1
|
9月前
【每日一题Day302】LC849到最近的人的最大距离 | 贪心+分类讨论
【每日一题Day302】LC849到最近的人的最大距离 | 贪心+分类讨论
67 0
|
9月前
【每日一题Day255】LC2679矩阵中的和 | 排序
【每日一题Day255】LC2679矩阵中的和 | 排序
39 0
|
9月前
【每日一题Day358】LC2698求一个整数的惩罚数 | 递归
【每日一题Day358】LC2698求一个整数的惩罚数 | 递归
69 0
|
9月前
【每日一题Day165】LC1039多边形三角剖分的最低得分 | 区间dp
【每日一题Day165】LC1039多边形三角剖分的最低得分 | 区间dp
66 0
|
9月前
【每日一题Day192】LC1033移动石子直到连续 | 分类讨论 贪心
【每日一题Day192】LC1033移动石子直到连续 | 分类讨论 贪心
42 0
【每日一题Day31】LC891子序列宽度之和 | 数学
不会,无论是将 nums[i]视作最大值还是最小值,我们的组合数均取决于某一侧的数的个数,因此不会答案正确性产生影响。
99 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等