Участник:Easik/largest-multiple-of-three

Материал из DISCOPAL
< Участник:Easik
Версия от 18:52, 3 декабря 2020; Easik (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

https://leetcode.com/problems/largest-multiple-of-three/

Python

class Solution(object):
    def largestMultipleOfThree(self, digits):
        """
        :type digits: List[int]
        :rtype: str
        """
 
        digit_sum = sum(digits)
 
        # Trivial case
        if digit_sum % 3 == 0:
 
            digits = sorted(digits)[::-1]
 
            if len(digits) == 0:
                return ""
 
            elif digits[0] == 0:
                return "0"
 
            else:
                return "".join(str(d) for d in digits)
 
        # Segregate digits by their remainders (% 3)
        remainder_0 = []  # % 3 = 0
        remainder_1 = []  # % 3 = 1
        remainder_2 = []  # % 3 = 2
 
        for d in digits:
 
            if d % 3 == 0:
                remainder_0.append(d)
 
            elif d % 3 == 1:
                remainder_1.append(d)
 
            elif d % 3 == 2:
                remainder_2.append(d)
 
        valid_digits = []
 
        # Remainder == 1
        if digit_sum % 3 == 1:
 
            if (len(remainder_1) > 0) and (len(remainder_2) > 1):
 
                remainder_2 = sorted(remainder_2)
                if min(remainder_1) <= sum(remainder_2[:2]):
 
                    idx = remainder_1.index(min(remainder_1))
 
                    valid_digits += remainder_0
                    valid_digits += remainder_1[:idx]
                    valid_digits += remainder_1[idx+1:]
                    valid_digits += remainder_2
 
                else:
 
                    valid_digits += remainder_0
                    valid_digits += remainder_1
                    valid_digits += remainder_2[2:]
 
            elif len(remainder_1) > 0:
 
                idx = remainder_1.index(min(remainder_1))
 
                valid_digits += remainder_0
                valid_digits += remainder_1[:idx]
                valid_digits += remainder_1[idx+1:]
                valid_digits += remainder_2
 
            elif len(remainder_2) > 1:
 
                remainder_2 = sorted(remainder_2)
 
                valid_digits += remainder_0
                valid_digits += remainder_1
                valid_digits += remainder_2[2:]
 
            else:
 
                valid_digits += remainder_0
 
            assert sum(valid_digits) % 3 == 0
            valid_digits = sorted(valid_digits)[::-1]
 
            if len(valid_digits) == 0:
                return ""
 
            elif valid_digits[0] == 0:
                return "0"
 
            else:
                return "".join(str(d) for d in valid_digits)
 
        # Remainer == 2
        elif digit_sum % 3 == 2:
 
            if (len(remainder_1) > 1) and (len(remainder_2) > 0):
 
                remainder_1 = sorted(remainder_1)
                if min(remainder_2) <= sum(remainder_1[:2]):
 
                    idx = remainder_2.index(min(remainder_2))
 
                    valid_digits += remainder_0
                    valid_digits += remainder_1
                    valid_digits += remainder_2[:idx]
                    valid_digits += remainder_2[idx+1:]
 
                else:
 
                    valid_digits += remainder_0
                    valid_digits += remainder_1[2:]
                    valid_digits += remainder_2
 
            elif len(remainder_2) > 0:
 
                idx = remainder_2.index(min(remainder_2))
 
                valid_digits += remainder_0
                valid_digits += remainder_1
                valid_digits += remainder_2[:idx]
                valid_digits += remainder_2[idx+1:]
 
            elif len(remainder_1) > 1:
 
                remainder_1 = sorted(remainder_1)
 
                valid_digits += remainder_0
                valid_digits += remainder_1[2:]
                valid_digits += remainder_2
 
            else:
 
                valid_digits += remainder_0
 
            assert sum(valid_digits) % 3 == 0
            valid_digits = sorted(valid_digits)[::-1]
 
            if len(valid_digits) == 0:
                return ""
 
            elif valid_digits[0] == 0:
                return "0"
 
            else:
                return "".join(str(d) for d in valid_digits)