X

LEETCODE 1262. Greatest Sum Divisible by Three 解题思路分析

题目大意:

可被三整除的最大和

给你一个整数数组 nums,请你找出并返回能被三整除的元素最大和。

示例 1:

输入:nums = [3,6,5,1,8] 
输出:18 
解释:选出数字 3, 6, 1 和 8,它们的和是 18(可被 3 整除的最大和)。 

示例 2:

输入:nums = [4]
输出:0
解释:4 不能被 3 整除,所以无法选出数字,返回 0。

示例 3:

输入:nums = [1,2,3,4,4]
输出:12
解释:选出数字 1, 3, 4 以及 4,它们的和是 12(可被 3 整除的最大和)。

提示:

  • 1 <= nums.length <= 4 * 10^4
  • 1 <= nums[i] <= 10^4

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

解题思路分析:

这道题可以使用动态规划来解题,但是DP数组不太好设置,理解起来有些困难,因此采取了另外一种方式。我们可以将数组中的数字分成3类,

  1. 除以3余1的数
  2. 除以3余2的数
  3. 能被3整除的数

不论最优解是什么,结果中一定包含所有能被3整除的数字。因此我们应该在余数为1和2的数字中找到和能被3整除的最大和。这道题的解法用到一个简单的数学知识,即:

  1. 如果一个数除以3余1的话,那么它再减去一个除以3余1的数,差值可被3整除,或者减去2个除以3余2的数字,同样差值可以被3整除。
  2. 如果一个数除以3余2的话,那么它再减去一个除以3余2的数,差值可被3整除,或者减去2个除以3余1的数字,同样差值可以被3整除。

因此,解题思路也就清晰了,我们先计算出数组中所有数字之和,如何和能被3整除,可直接作为结果返回。如果总和除以3余1的话,我们可以减去一个最小的余数为1的数,或者减去2个最小的余数为2的数,求两者最大值作为最优解返回。如果总和除以3余2的话,同理,我们可以减去一个最小的余数为2的数,或者减去2个最小的余数为1的数,返回一个最优解。

实现代码:

public int maxSumDivThree(int[] nums) {
    int minRemain1=Integer.MAX_VALUE; // 除以3余1的最小数
    int secMinRemain1=Integer.MAX_VALUE; // 除以3余1的次小数
    int minRemain2=Integer.MAX_VALUE; // 除以3余2的最小数
    int secMinRemain2=Integer.MAX_VALUE; // 除以3余2的次小数
    int sum=0; // 总和
    for(int num : nums){ // 循环每一个数字
        sum+=num; // 计算和
        if(num%3==1){ // 如果当前数除以3余1
            // 更新余1的数字的最小数和次小数
            if(num<=minRemain1){
                secMinRemain1=minRemain1;
                minRemain1=num;
            }else if(num<=secMinRemain1){
                secMinRemain1=num;
            }
        }else if(num%3==2){ // 如果当前数除以3余2
            // 更新余2的数字的最小数和次小数
            if(num<=minRemain2){
                secMinRemain2=minRemain2;
                minRemain2=num;
            }else if(num<=secMinRemain2){
                secMinRemain2=num;
            }
        }
    }
    // 如果总和除以3余0,直接返回总和
    if(sum%3==0){
        return sum;
    }else if(sum%3==1){ // 如果总和除以3余1
        // 如果数组中不存在2个余2的数字
        if(minRemain2==Integer.MAX_VALUE
          || secMinRemain2==Integer.MAX_VALUE){
            return sum-minRemain1; // 返回总和减去一个最小的余1的数
        }else{
            // 看余1的最小数,2个最小余2的数之和哪个更小,
            // 用总和减去小的一方作为结果返回
            return sum-Math.min(minRemain1,minRemain2+secMinRemain2);
        }
    }else{ // 如果总和除以3余2
        // 如果数组中不存在2个余1的数字
        if(minRemain1==Integer.MAX_VALUE
          || secMinRemain1==Integer.MAX_VALUE){
            return sum-minRemain2; // 返回总和减去一个最小的余2的数
        }else{
            // 看余2的最小数,2个最小余1的数之和哪个更小,
            // 用总和减去小的一方作为结果返回
            return sum-Math.min(minRemain2,minRemain1+secMinRemain1);
        }
    }
}

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

Runtime: 4 ms, faster than 98.03% of Java online submissions for Greatest Sum Divisible by Three.

Memory Usage: 43.5 MB, less than 100.00% of Java online submissions for Greatest Sum Divisible by Three.

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