陣列 — 實戰題解

# python
# LC 448 - Find All Numbers Disappeared in an Array
# IDEA: sign marking - negate nums[v - 1] for every v; the indices left positive are missing
# time = O(n), space = O(1) besides the output
def findDisappearedNumbers(nums):
    for x in nums:
        i = abs(x) - 1          # x may already be negative: it was marked by an earlier value
        if nums[i] > 0:         # mark once; a second negation would unmark a duplicate
            nums[i] = -nums[i]
    missing = []
    for i in range(len(nums)):
        if nums[i] > 0:
            missing.append(i + 1)
    return missing

# python
# LC 442 - Find All Duplicates in an Array
# IDEA: sign marking - the first visit negates nums[v - 1], a second visit finds it negative
# time = O(n), space = O(1) besides the output
def findDuplicates(nums):
    duplicates = []
    for x in nums:
        i = abs(x) - 1          # always through abs(): x itself may have been marked
        if nums[i] < 0:
            duplicates.append(i + 1)   # second visit to value i + 1
        else:
            nums[i] = -nums[i]         # first visit
    return duplicates

# python
# LC 1375 - Number of Times Binary String Is Prefix-Aligned (formerly Bulb Switcher III)
# IDEA: carry the largest index flipped so far; the prefix is aligned when it equals the step count
# time = O(n), space = O(1)
def numTimesAllBlue(flips):
    largest = 0
    aligned = 0
    for step, index in enumerate(flips, start=1):
        largest = max(largest, index)
        if largest == step:        # step indices flipped, none above step -> exactly 1..step
            aligned += 1
    return aligned

# python
# LC 1041 - Robot Bounded In Circle
# IDEA: simulate one pass; bounded iff back at the origin or no longer facing north
# time = O(n), space = O(1)
def isRobotBounded(instructions):
    moves = [(0, 1), (1, 0), (0, -1), (-1, 0)]   # north, east, south, west: clockwise
    x = 0
    y = 0
    heading = 0                                   # index into moves; 0 = north
    for c in instructions:
        if c == "L":
            heading = (heading + 3) % 4           # one step counter-clockwise
        elif c == "R":
            heading = (heading + 1) % 4           # one step clockwise
        else:                                     # "G"
            x += moves[heading][0]
            y += moves[heading][1]
    return (x == 0 and y == 0) or heading != 0

# python
# LC 670 - Maximum Swap
# IDEA: right-to-left scan carrying the index of the largest digit to the right;
#       the leftmost digit smaller than that maximum is swapped with it
# time = O(d), space = O(d)   d = number of digits (at most 9)
def maximumSwap(num):
    digits = list(str(num))
    max_idx = len(digits) - 1          # index of the largest digit in digits[i:]
    left = -1                          # the best swap found so far
    right = -1
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] > digits[max_idx]:
            max_idx = i                # strictly larger: ties keep the rightmost copy
        elif digits[i] < digits[max_idx]:
            left = i                   # further left than any earlier find, so better
            right = max_idx
    if left == -1:
        return num                     # already the largest arrangement
    digits[left], digits[right] = digits[right], digits[left]
    return int("".join(digits))