[Leetcode] 1262. Greatest Sum Divisible by Three (Medium)

概述

題目

https://leetcode.com/problems/greatest-sum-divisible-by-three/
給定一 nums，求出取其最大數和可被 3 整除之結果

心得

先觀查餘數特性，可知道如何能得到被 3 整除的和數，再透過要最大進行排序求最小

Sort + Counter

思路

透過排序求最小，之後分擔處理餘數結果求最大和

程式

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
33
34
35
36
37
38
39
40
class Solution(object):
    def maxSumDivThree(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 先排序易於操作
        nums.sort()
        smv = sum(nums)
        
        # 餘數相同者各自進 list
        dic = defaultdict(list)
        for c in nums:
            t = c%3
            dic[t].append(c)
        div = smv%3

        # 總和即滿足，直接 return
        if div == 0:
            return smv
        # 缺 1 可由砍掉 1 個 1 或 2 個 2 來滿足題意
        if div == 1:
            if 1 in dic and 2 in dic and len(dic[2]) > 1:
                return smv - min(dic[1][0], dic[2][0] + dic[2][1])
            elif 1 in dic:
                return smv - dic[1][0]
            else:
                if 2 in dic and len(dic[2]) > 1:
                    return smv - dic[2][0] - dic[2][1]
        # 缺 2 可由砍掉 1 個 2 或 2 個 1 來滿足題意
        elif div == 2:
            if 2 in dic and 1 in dic and len(dic[1]) > 1:
                return smv - min(dic[2][0], dic[1][0] + dic[1][1])
            elif 2 in dic:
                return smv - dic[2][0]
            else:
                if 1 in dic and len(dic[1]) > 1:
                    return smv - dic[1][0] - dic[1][1]
        # 皆無法完成者
        return 0

Complexity

Time Complexity: O(n log n)
有排序故低消 n log n

Space Complexity: O(n)
Counter 最多記錄 n 個數據

O(n)

思路

將排序以 O(n) 方式替換掉

程式

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution(object):
    def maxSumDivThree(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        inf = float("inf")
        div1 = [inf, inf]
        div2 = [inf, inf]

        # 取最小、次小值在各餘數狀況下
        for c in nums:
            d = c%3
            if d == 1:
                if c <= div1[0]:
                    if c < div1[1]:
                        div1[0] = div1[1]
                        div1[1] = c
                    else:
                        div1[0] = c
            elif d == 2:
                if c <= div2[0]:
                    if c < div2[1]:
                        div2[0] = div2[1]
                        div2[1] = c
                    else:
                        div2[0] = c
        
        smv = sum(nums)
        div = smv%3

        # 總和即滿足，直接 return
        if div == 0:
            return smv
        # 缺 1 可由砍掉 1 個 1 或 2 個 2 來滿足題意
        if div == 1:
            if div1[1] != inf and div2[0] != inf:
                return smv - min(div1[1], sum(div2))
            elif div1[1] != inf:
                return smv - div1[1]
            else:
                if div2[0] != inf:
                    return smv - sum(div2)
        # 缺 2 可由砍掉 1 個 2 或 2 個 1 來滿足題意
        elif div == 2:
            if div2[1] != inf and div1[0] != inf:
                return smv - min(div2[1], sum(div1))
            elif div2[1] != inf:
                return smv - div2[1]
            else:
                if div1[0] != inf:
                    return smv - sum(div1)
        # 皆無法完成者
        return 0

from aviporath，類似的寫法，但更簡捷些

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
33
34
class Solution(object):
    def maxSumDivThree(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        smv = sum(nums)
        
        if smv % 3 == 0:
            return s
        
        inf = float("inf")
        r11 = inf
        r12 = inf
        r21 = inf
        r22 = inf
        
        for num in nums:
            if num % 3 == 1 and num < r12:
                if num < r11:
                    r12 = r11
                    r11 = num
                else:
                    r12 = num
            if num % 3 == 2 and num < r22:
                if num < r21:
                    r22 = r21
                    r21 = num
                else: 
                    r22 = num
        if smv % 3 == 1:
            return smv - min(r11, r21+r22)
        if smv % 3 == 2:
            return smv - min(r21, r11+r12)

Complexity

Time Complexity: O(n)
只走過 n 個數字數次

Space Complexity: O(1)
只看餘 0, 1, 2 且至多兩個

DP

思路

from wangy666，以 DP 解之，dp[i][j] 表示前 i 個數總和數餘 j 之最大結果

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def maxSumDivThree(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        dp = [[0 for i in range(3)] for i in range(n+1)]
        dp[0][1] = float('-inf')
        dp[0][2] = float('-inf')

        for i in range(n):
            c = nums[i]
            d = c%3

            # dp[i][j] 表前 i 個數總和餘 j 之最大結果
            dp[i+1][0] = max(dp[i][0], dp[i][(3-d+0)%3]+c)
            dp[i+1][1] = max(dp[i][1], dp[i][(3-d+1)%3]+c)
            dp[i+1][2] = max(dp[i][2], dp[i][(3-d+2)%3]+c)
        return dp[-1][0]

Complexity

Time Complexity: O(n)
只走過 n 個數字數次

Space Complexity: O(n)
dp size 為 3 * n

from ntvy95，空間複雜度為 O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def maxSumDivThree(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        r0 = r1 = r2 = 0
        for num in nums:
            candidates = num + r0, num + r1, num + r2
            for candidate in candidates:
                if candidate % 3 == 0:
                    r0 = max(r0, candidate)
                elif candidate % 3 == 1:
                    r1 = max(r1, candidate)
                elif candidate % 3 == 2:
                    r2 = max(r2, candidate)
        return r0

Complexity

Time Complexity: O(n)
只走過 n 個數字數次

Space Complexity: O(n)
dp size 為 3 * n