1. <dd id="erndk"></dd>
                1. [LeetCode]1262. Greatest Sum Divisible by Three (JS) 動態規劃&小學數學解法

                  互聯網 2022/1/4 6:07:28

                  題目描述 LeetCode原題鏈接:1262. Greatest Sum Divisible by Three Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three. Example 1: Input: nums = [3,6,5,1,8] Output: 18 Exp…

                  題目描述

                  LeetCode原題鏈接:1262. Greatest Sum Divisible by Three

                  Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.

                  Example 1:

                  Input: nums = [3,6,5,1,8]
                  Output: 18
                  Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

                  Example 2:

                  Input: nums = [4]
                  Output: 0
                  Explanation: Since 4 is not divisible by 3, do not pick any number.
                  

                  Example 3:

                  Input: nums = [1,2,3,4,4]
                  Output: 12
                  Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).

                  Constraints:

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

                  解法一:動態規劃

                  這道題目的hint提示我們可以使用動態規劃來解決:

                  Represent the state as DP[pos][mod]: maximum possible sum starting in the position "pos" in the array where the current sum modulo 3 is equal to mod.

                  先來看一下提示里對于dp數組的定義。dp[pos][mod]表示從pos位置開始的最大和且這個最大和與3取余得mod。有點繞人,什么意思呢?我們知道,任意數a與3取余只有3種情況:余0(即整除)、余1、余2。針對這三種情況,在[start, end]范圍內就會有三個最大和。舉個例子,比如對于數組[2, 1, 3, 4, 2, 5],在下標為[1, 4]范圍內,即1、3、4、2這幾個數中,余1的最大和為1+3+4+2=10,余2的最大和為1+3+4=8,整除的最大和為3+4+2=9。我們可以在遍歷的過程中,每遇到一個新的數,就去與已經得到的和相加并與3取余,更新dp數組。這里起始位置pos其實意義不大,我們只需要知道已經遍歷過的數中最大和與3的關系就好了,所以完全可以用一個一維數組來記錄。dp[mod]表示當前位置整個數組(從下標0到當前下標)的最大和且這個最大和與3取余得mod。

                  需要注意,由于是一維數組無法保存之前的狀態,所以當遍歷到一個新的位置時,可以用一個臨時數組暫時保存上一位置的結果,然后再去更新dp。

                  下面來看怎么更新dp。遍歷到的數字num除3余幾并不重要,同之前的和oldSum相加與3取余,得到要更新的dp的位置即可。所以狀態轉移方程為:

                  dp[(oldSum + num) % 3] = max(dp[(oldSum + num) % 3], oldSum + num)

                  這里的oldSum從前面提到的臨時數組中取。最終結果因為要求整除的最大和,所以直接返回dp[0]即可。

                  代碼示例(JavaScript)

                   1 var maxSumDivThree = function(nums) {
                   2     let dp = new Array(3);
                   3     dp.fill(0);
                   4     nums.forEach((num) => {
                   5         // save history sum
                   6         let temp = [...dp];
                   7         temp.forEach((sum) => {
                   8             dp[(sum + num) % 3] = Math.max(dp[(sum + num) % 3], sum + num);
                   9         });
                  10     });
                  11     return dp[0];
                  12 };

                  解法二:數學知識

                  小學數學應該講過這么一個定理:若數字a和b分別除以數字c得到的余數相同,那么 (a-b) 必定能夠整除c。

                  對應這道題,如果數組之和為a,當 a%3 = 0 的時候,a就是要求的最大值,直接返回;如果 a%3 != 0,那么我們需要在數組中找b,使 b%3 == a%3,同時b盡可能的小,這樣 (a-b) 就能被3整除且最大;其中,b可以是單個數,也可以是某幾個數的和。前面提到,如果某一個數不能被3整除,那么余數只有可能是1或2,我們在遍歷的過程中,去找這兩種情況的最小值。

                  怎么找呢?要知道,這個最小值可以是某一個數,也可以是某幾個數的和。某一個數好說,直接看這個數除3余幾就行了。某幾個數的和怎么在一次遍歷過程中求呢?這里又要涉及一個小學數學知識了。還是有兩個數,我們設其為x和y,如果 x%3=m1, y%3=m2, 那么 (x+y)%3 就等于 (m1+m2)%3。比如8%3=2,4%3=1,那么 (8+4)%3 = 12%3 = (2+1)%3 = 0。很好,現在我們要找余數為1的和,那么這個數就可以是余數為1的數和余數為0的數相加;找余數為2的和,那么這個數就可以是兩個余數為1的數相加。

                  最小余1的數、最小余2的數我們可以分別用兩個變量modOne、modeTwo來表示,當遍歷到一個新的位置時,根據當前位置上的數除以3的余數去更新modOne和modeTwo。同時,在這個遍歷過程中,再用一個變量sum去累加每個位置上的數。遍歷結束后sum就是整個數組的和,根據 sum%3 的情況來得到最終結果:

                  • sum%3 = 0  --->  return sum;
                  • sum%3 = 1   --->  return sum-modOne;
                  • sum%3 = 2  --->  return sum-modTwo;

                  注意,因為在求modOne和modTwo最小值的過程中有加法操作,因此為了防止溢出,它們的初始值設為Constraints中nums[i]的最大值即可。

                  代碼示例(JavaScript)

                   1 var maxSumDivThree = function(nums) {
                   2     let sum = 0;
                   3     let modOne = Math.pow(10, 4), modTwo = Math.pow(10, 4);
                   4     nums.forEach((num) => {
                   5         sum += num;
                   6         if(num % 3 == 1) {
                   7             modTwo = Math.min(modTwo, num + modOne);
                   8             modOne = Math.min(modOne, num);
                   9         }
                  10         if(num % 3 == 2) {
                  11             modOne = Math.min(modOne, num + modTwo);
                  12             modTwo = Math.min(modTwo, num);
                  13         }
                  14     });
                  15     if(sum % 3 == 0) return sum;
                  16     sum -= sum % 3 == 1 ? modOne : modTwo;
                  17     return sum;
                  18 };

                  注意第7、8行和第11、12行更新modOne和modTwo時候的順序。第7行和第11行加法里面的modOne、modTwo要用舊的值而不是此輪遍歷更新后的值,因此要寫在前面。

                  https://leetcode.com/problems/greatest-sum-divisible-by-three/

                  隨時隨地學軟件編程-關注百度小程序和微信小程序
                  關于找一找教程網

                  本站文章僅代表作者觀點,不代表本站立場,所有文章非營利性免費分享。
                  本站提供了軟件編程、網站開發技術、服務器運維、人工智能等等IT技術文章,希望廣大程序員努力學習,讓我們用科技改變世界。
                  [[LeetCode]1262. Greatest Sum Divisible by Three (JS) 動態規劃&小學數學解法]http://www.yachtsalesaustralia.com/tech/detail-279745.html

                  贊(0)
                  關注微信小程序
                  程序員編程王-隨時隨地學編程

                  掃描二維碼或查找【程序員編程王】

                  可以隨時隨地學編程啦!

                  技術文章導航 更多>
                  国产在线拍揄自揄视频菠萝

                        1. <dd id="erndk"></dd>