X

LEETCODE 1363. Largest Multiple of Three 解题思路分析

题目大意:

形成三的最大倍数

给你一个整数数组 digits,你可以通过按任意顺序连接其中某些数字来形成 3 的倍数,请你返回所能得到的最大的 3 的倍数。

由于答案可能不在整数数据类型范围内,请以字符串形式返回答案。

如果无法得到答案,请返回一个空字符串。

示例 1:

输入:digits = [8,1,9]
输出:"981"

示例 2:

输入:digits = [8,6,7,1,0]
输出:"8760"

示例 3:

输入:digits = [1]
输出:""

示例 4:

输入:digits = [0,0,0,0,0,0]
输出:"0"

提示:

  • 1 <= digits.length <= 10^4
  • 0 <= digits[i] <= 9
  • 返回的结果不应包含不必要的前导零。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1363

解题思路分析:

首先我们应该明确一个数学上的概念,如果一个数字能被三整除,那么该数字上每一位之和也能被三整除,比如183能被3整除(183/3=61),那么1+8+3=12,12也能被三整除。

我们先循环遍历一遍数组中的数字,该循环中我们需要做4件事情:

  1. 统计出0-9每种数字的个数
  2. 计算出数组中所有数字和
  3. 统计出与三相除余数为1的最小数min1_1,及次小数 min1_2。
  4. 统计出与三相除余数为2的最小数min2_1,及次小数 min2_2。

循环结束后,如果所有数字和能被3整除,说明我们使用数组中所有的数字可以组成一个能被3整除的数字。如果和与3的余数是1,说明我们需要从数组中剔除出一个最小的与3余数是1的数字 min1_1 。如果这个数字不存在,那么数组中一定存在 min2_1 和 min2_2,将这两个数字在数组中的个数减一。反之,如果和与3的余数是2,说明我们需要从数组中剔除出一个最小的与3余数是2的数字min2_1 。如果这个数字不存在,那么数组中一定存在 min1_1 和 min1_2,将这两个数字在数组中的个数减一。

经过上述操作,我们保证数组中剩下的数字和一定能被三整除,我们利用这些数字组成一个最大数即可(最大数即是将大的数字尽量放在高位)。

实现代码:

public String largestMultipleOfThree(int[] digits) {
    // 统计每种数字出现的次数
    int[] count = new int[10];
    // 所有数字和
    int sum=0;
    // 除以3余数为1的最小数及次小数
    // 除以3余数为2的最小数及次小数
    int min1_1=10,min1_2=10,min2_1=10,min2_2=10;
    // 循环每个数字
    for(int d : digits){
        // 当前数字与3的余数为1
        if(d%3==1){
            // 更新余数为1的最小数及次小数
            if(d<=min1_1){
                min1_2=min1_1;
                min1_1=d;
            }else if(d<=min1_2){
                min1_2=d;
            }
        }
        // 当前数字与3的余数为2
        else if(d%3==2){
            // 更新余数为2的最小数及次小数
            if(d<=min2_1){
                min2_2=min2_1;
                min2_1=d;
            }else if(d<=min2_2){
                min2_2=d;
            }
        }
        // 累加数字和
        sum+=d;
        // 当前数字个数加一
        count[d]++;
    }
    // 如果和是0,直接返回0
    if(sum==0) return "0";
    // 如果和与3的余数是1
    if(sum%3==1){
        // 如果存在min1_1,min1_1的个数减一
        if(min1_1<10) count[min1_1]--;
        else{
            // 否则减去两个最小的余数为2的数
            count[min2_1]--;
            count[min2_2]--;
        }
    }else if(sum%3==2){
        if(min2_1<10) count[min2_1]--;
        else{
            count[min1_1]--;
            count[min1_2]--;
        }
    }
    // 构建最大数
    StringBuilder sb = new StringBuilder();
    for(int i=9;i>=0;i--){
        for(int j=0;j<count[i];j++){
            sb.append(i);
        }
    }
    return sb.toString();
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 81.62% of Java online submissions for Largest Multiple of Three.

Memory Usage: 41.6 MB, less than 100.00% of Java online submissions for Largest Multiple of Three.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1363-largest-multiple-of-three-解题思路分析/
Categories: leetcode
kwantong: