Skip to content

分组循环 Grouped Loop

Table of Contents

485. Max Consecutive Ones

1446. Consecutive Characters

1869. Longer Contiguous Segments of Ones than Zeros

2414. Length of the Longest Alphabetical Continuous Substring

3456. Find Special Substring of Length K

2273. Find Resultant Array After Removing Anagrams

2348. Number of Zero-Filled Subarrays

1513. Number of Substrings With Only 1s

1957. Delete Characters to Make Fancy String

674. Longest Continuous Increasing Subsequence

from typing import List


def findLengthOfLCIS(nums: List[int]) -> int:
    n = len(nums)
    if n <= 1:
        return n

    dp = [1 for _ in range(n)]

    for i in range(1, n):
        if nums[i] > nums[i - 1]:
            dp[i] = dp[i - 1] + 1

    return max(dp)


print(findLengthOfLCIS([1, 3, 5, 4, 7]))  # 3

696. Count Binary Substrings

978. Longest Turbulent Subarray

from typing import List


# DP - Kadane
def maxTurbulenceSize(arr: List[int]) -> int:
    n = len(arr)
    up = [1 for _ in range(n)]
    down = [1 for _ in range(n)]
    maxLen = 1

    for i in range(1, n):
        if arr[i - 1] < arr[i]:
            up[i] = down[i - 1] + 1
            down[i] = 1
        elif arr[i - 1] > arr[i]:
            down[i] = up[i - 1] + 1
            up[i] = 1
        else:
            up[i] = 1
            down[i] = 1

        maxLen = max(maxLen, up[i], down[i])

    return maxLen


arr = [9, 4, 2, 10, 7, 8, 8, 1, 9]
print(maxTurbulenceSize(arr))  # 5

2110. Number of Smooth Descent Periods of a Stock

228. Summary Ranges

from typing import List


# Variable Sliding Window
def summaryRanges(nums: List[int]) -> List[str]:
    left, right = 0, 0
    n = len(nums)
    res = []

    while left < n:
        while right + 1 < n and nums[right] + 1 == nums[right + 1]:
            right += 1

        if left == right:
            res.append(f"{nums[left]}")
        else:
            res.append(f"{nums[left]}->{nums[right]}")

        right += 1
        left = right

    return res


if __name__ == "__main__":
    print(summaryRanges([0, 1, 2, 4, 5, 7]))
    # ["0->2", "4->5", "7"]
    print(summaryRanges([0, 2, 3, 4, 6, 8, 9]))
    # ["0", "2->4", "6", "8->9"]

2760. Longest Even Odd Subarray With Threshold

1887. Reduction Operations to Make the Array Elements Equal

845. Longest Mountain in Array

  • LeetCode | 力扣

  • Tags: Array, Two Pointers, Dynamic Programming, Enumeration

from typing import List


# Left Right Pointers
def longestMountain(arr: List[int]) -> int:
    n = len(arr)
    res = 0
    left = 0

    while left < n:
        right = left

        if right < n - 1 and arr[right] < arr[right + 1]:
            while right < n - 1 and arr[right] < arr[right + 1]:
                right += 1

            if right < n - 1 and arr[right] > arr[right + 1]:
                while right < n - 1 and arr[right] > arr[right + 1]:
                    right += 1
                res = max(res, right - left + 1)

        left = max(right, left + 1)

    return res


arr = [2, 1, 4, 7, 3, 2, 5]
print(longestMountain(arr))  # 5

2038. Remove Colored Pieces if Both Neighbors are the Same Color

2900. Longest Unequal Adjacent Groups Subsequence I

1759. Count Number of Homogenous Substrings

3011. Find if Array Can Be Sorted

1578. Minimum Time to Make Rope Colorful

1839. Longest Substring Of All Vowels in Order

2765. Longest Alternating Subarray

3255. Find the Power of K-Size Subarrays II

3350. Adjacent Increasing Subarrays Detection II

3105. Longest Strictly Increasing or Strictly Decreasing Subarray

838. Push Dominoes

467. Unique Substrings in Wraparound String

413. Arithmetic Slices

68. Text Justification

135. Candy

"""
-   Return the minimum number of candies you must give.
"""

from typing import List


# Greedy
def candy(ratings: List[int]) -> int:
    # TC: O(n)
    # SC: O(n)
    n = len(ratings)

    if n <= 1:
        return n

    candy = [1 for _ in range(n)]

    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            candy[i] = candy[i - 1] + 1

    for j in range(n - 2, -1, -1):
        if ratings[j] > ratings[j + 1]:
            candy[j] = max(candy[j], candy[j + 1] + 1)

    return sum(candy)


ratings = [1, 0, 2]
print(candy(ratings))  # 5

2948. Make Lexicographically Smallest Array by Swapping Elements

2593. Find Score of an Array After Marking All Elements

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Sorting, Heap Priority Queue, Simulation

2393. Count Strictly Increasing Subarrays 👑

2436. Minimum Split Into Subarrays With GCD Greater Than One 👑

  • LeetCode | 力扣

  • Tags: Array, Math, Dynamic Programming, Greedy, Number Theory

2495. Number of Subarrays Having Even Product 👑

3063. Linked List Frequency 👑