nums라는 숫자 목록이 있다고 가정하고 다음 규칙 중 하나를 사용하여 모든 숫자를 그룹화할 수 있는지 확인해야 합니다. 1. 연속 쌍(a, a) 2. 연속 삼중항(a, a, a) 3. 연속 세쌍둥이(a, a + 1, a + 2)
따라서 입력이 nums =[7, 7, 3, 4, 5]와 같으면 [7, 7]을 함께 그룹화하고 [3, 4, 5]를 함께 그룹화할 수 있으므로 출력은 True가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=숫자 크기
-
dp :=크기가 n+1인 목록, 첫 번째 값은 True, 나머지 값은 False
-
범위 2에서 n까지의 i에 대해 수행
-
i>=2이고 dp[i − 2]가 0이 아니면
-
nums[i − 1]이 nums[i − 2]와 같으면
-
dp[i] :=참
-
-
-
i>=3이고 dp[i − 3]가 0이 아니면
-
if (nums[i − 1], nums[i − 2], nums[i − 3])이 같거나 (nums[i − 1], nums[i − 2] + 1, nums[i − 3] + 2개 동일),
-
dp[i] :=참
-
-
-
-
반환 dp[n]
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def solve(self, nums): n = len(nums) dp = [True] + [False] * n for i in range(2, n + 1): if i >= 2 and dp[i − 2]: if nums[i − 1] == nums[i − 2]: dp[i] = True if i >= 3 and dp[i − 3]: if (nums[i − 1] == nums[i − 2] == nums[i − 3]) or (nums[i − 1] == nums[i − 2] + 1 == nums[i − 3] + 2): dp[i] = True return dp[n] ob = Solution() nums = [8, 8, 4, 5, 6] print(ob.solve(nums))
입력
[8, 8, 4, 5, 6]
출력
True