算法 leetcode algorithm

LeetCode每日一题--可以被三整除的最大的数

leetCode算法系列--动态规划

Posted by maybelence on 2021-04-09

前言

今天终于开始上手面试中最为高频的—动态规划了。可能是之前没有接触过，就听别人说动态规划很难，所以我一直不愿去面对这类题目。今天鼓了鼓勇气，上手了第一个动态规划题。当我做完第一个之后，我发现其实动态规划其实没有想象的那么可怕。也推荐那些不敢尝试的coder多去尝试一下，你不尝试一下你就永远不知道其实你是可以的。

题目描述

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

示例 1：

1
2
3
输入：nums = [3,6,5,1,8]
输出：18
解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。

示例 2：

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

示例 3：

1
2
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
通过次数9,965提交次数19,256

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/greatest-sum-divisible-by-three
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

对于数组 nums ，假设先从中取 n 个元素中任取了一个元素，那么就有 N 种选择，对于剩下的元素，又有 N-1 种选择。以此类推，如果暴力穷举，那么一共有 n! 种场景。最后满足场景的情况，就是sum%3==0，比较所有sum中最大的那个值就是我们要的答案，或者 nums 一直遍历到最后，即新生成的数组长度为0都没有满足条件的就直接return掉。这样暴力递归的解法大致如下：

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
class Solution {
    int result = 0;

    public int maxSumDivThree(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        findmaxSumDivThree(nums, 0);
        return result;
    }

    private void findmaxSumDivThree(int[] nums, int sum) {
        if (sum % 3 == 0)
            result = Math.max(result, sum);
        if (nums.length == 0)
            return;
        for (int i = 0; i < nums.length; i++) {
            int newSum = sum + nums[i];
            findmaxSumDivThree( removeCurrent(nums, i), newSum);
        }
    }
    //去掉i坐标形成新数组
    private int[] removeCurrent(int[] nums, int i) {
        int[] newNums = new int[nums.length - 1];
        int m = 0;
        for (int j = 0; j < nums.length; j++) {
            if (j != i)
                newNums[m++] = nums[j];
        }
        return newNums;
    }
}

但是这种暴力递归会存在许多重复场景，对于数组 [1,2,3] 而言，第一次选取 1，第二次选取 2，第三次选取 3，和第一次选取 2，第二次选取 1，第三次选取 3。只是换了个顺序。相当于无意义工作重复递归了 (n-1)!次。无疑效率是大打折扣的。并且这个解法的solution时间超出了限制，说白了还是效率不过关，所以要调整。
我们新建一个二维数组，长 n+1 宽 3 来维护当前的状态。即

  • dp[i][0]表示nums[0…i]模三余零的最大和
  • dp[i][1]表示nums[0…i]模三余一的最大和
  • dp[i][2]表示nums[0…i]模三余二的最大和

假设当前总和对三取模是0,即当前和为 dp[i][0] ，那么在他之前有三个状态

  • dp[i-1][0] + nums[i] nums[i]%3==0
  • dp[i-1][1] + nums[i] nums[i]%3==1
  • dp[i-1][2] + nums[i] nums[i]%3==2
    此时我需要的是dp[i][0]的最大值，所以还需要上面值还需要与 dp[i-1] 做比较（如果 dp[i-1][1] + nums[i] 都比不上 dp[i-1][0] ,那这个结果自然不能占有我期待的 dp[i][0] 位置）。

相同的对于 dp[i][1] 也就能写出:

  • dp[i-1][0] + nums[i] nums[i]%3==1
  • dp[i-1][1] + nums[i] nums[i]%3==0
  • dp[i-1][2] + nums[i] nums[i]%3==2
    对于 dp[i][2] 同样的道理：
  • dp[i-1][0] + nums[i] nums[i]%3==2
  • dp[i-1][1] + nums[i] nums[i]%3==1
  • dp[i-1][2] + nums[i] nums[i]%3==0
    到了这里，就可以发现当 nums[i]%3==0 取模是0的时候。就总共有三种场景，相当于一个把思路再反过来理解：
  • dp[i][0] = max(dp[i - 1][0], dp[i - 1][0] + nums[i - 1])
  • dp[i][1] = max(dp[i - 1][1], dp[i - 1][1] + nums[i - 1])
  • dp[i][2] = max(dp[i - 1][2], dp[i - 1][2] + nums[i - 1])
    剩下两种场景也是一样的道理，最后dp[n][0]就是最 3 取模为 0 的最大和，直接看代码里的效果吧。

最终代码

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
class Solution {
     public int maxSumDivThree(int[] nums) {
        int[][] dp = new int [nums.length+1][3];
        dp[0][0] = 0; dp[0][1] = Integer.MIN_VALUE; dp[0][2] = Integer.MIN_VALUE;


        for (int i = 1; i <= nums.length; i++) {
            if (nums[i - 1] % 3 == 0) {
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][0] + nums[i - 1]);
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][1] + nums[i - 1]);
                dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][2] + nums[i - 1]);
            }
            else if (nums[i - 1] % 3 == 1) {
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] + nums[i - 1]);
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + nums[i - 1]);
                dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + nums[i - 1]);
            }
            else if (nums[i - 1] % 3 == 2) {
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + nums[i - 1]);
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2] + nums[i - 1]);
                dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][0] + nums[i - 1]);
            }
        }
        return dp[nums.length][0];
    }
}

总结

做完之后，感觉自己还是有很多收获的，希望以后遇到动态规划的时候都能冷静分析。今日打卡成功，欢迎大家一起和我参与 4月刷题打卡挑战。一起提升自己。

Copyright by @maybelence.

...

...

00:00
00:00
标签
算法 leetcode algorithm
其他常用