雜湊表 — 實戰題解

# python
# LC 1010 - Pairs of Songs With Total Durations Divisible by 60
# IDEA: count songs per remainder; each song pairs with every earlier song whose remainder completes it to 0 mod 60
# time = O(n), space = O(1)   at most 60 remainders
def numPairsDivisibleBy60(time):
    count_of_rem = {}                       # {remainder: songs seen so far}
    pairs = 0
    for t in time:
        rem = t % 60
        need = (60 - rem) % 60              # remainder 0 pairs with 0, not with 60
        pairs += count_of_rem.get(need, 0)  # look up BEFORE recording: a song never pairs with itself
        count_of_rem[rem] = count_of_rem.get(rem, 0) + 1
    return pairs

# python
# LC 352 - Data Stream as Disjoint Intervals
# IDEA: {start: end} and {end: start}; a new value probes v-1 (an end) and v+1 (a start) and merges with each
# time = O(1) per addNum, O(k log k) per getIntervals, space = O(n)   k = disjoint intervals
class SummaryRanges:
    def __init__(self):
        self.seen = set()              # every value added; a repeat changes nothing
        self.start_to_end = {}
        self.end_to_start = {}

    def addNum(self, value):
        if value in self.seen:
            return
        self.seen.add(value)
        start, end = value, value
        if value - 1 in self.end_to_start:          # an interval ends right before value
            start = self.end_to_start.pop(value - 1)
        if value + 1 in self.start_to_end:          # an interval starts right after value
            end = self.start_to_end.pop(value + 1)
        self.start_to_end[start] = end              # overwrites the left interval's old end
        self.end_to_start[end] = start              # overwrites the right interval's old start

    def getIntervals(self):
        result = []
        for start in sorted(self.start_to_end):
            result.append([start, self.start_to_end[start]])
        return result

add  start_to_end            end_to_start             getIntervals
1    {1:1}                   {1:1}                    [[1,1]]
3    {1:1, 3:3}              {1:1, 3:3}               [[1,1],[3,3]]
7    {1:1, 3:3, 7:7}         {1:1, 3:3, 7:7}          [[1,1],[3,3],[7,7]]
2    {1:3, 7:7}              {3:1, 7:7}               [[1,3],[7,7]]     2 joins [1,1] and [3,3]
6    {1:3, 6:7}              {3:1, 7:6}               [[1,3],[6,7]]

# python
# LC 554 - Brick Wall
# IDEA: count every inner edge position across rows; cross where the most edges line up
# time = O(total bricks), space = O(distinct edge positions)
def leastBricks(wall):
    edges_at = {}                          # {distance from the left: rows with an edge there}
    for row in wall:
        position = 0
        for i in range(len(row) - 1):      # the last brick ends at the wall's edge: never a gap
            position += row[i]
            edges_at[position] = edges_at.get(position, 0) + 1
    most_edges = 0
    for count in edges_at.values():
        most_edges = max(most_edges, count)
    return len(wall) - most_edges

# python
# LC 846 - Hand of Straights
# IDEA: count the cards; from the smallest card up, every copy of it starts a run of groupSize consecutive cards
# time = O(n log n), space = O(n)
def isNStraightHand(hand, groupSize):
    if len(hand) % groupSize != 0:
        return False
    count = {}
    for card in hand:
        count[card] = count.get(card, 0) + 1
    for card in sorted(count):             # the smallest remaining card must start a group
        starts = count[card]               # groups that start at this card
        if starts == 0:
            continue
        for nxt in range(card, card + groupSize):
            if count.get(nxt, 0) < starts:
                return False               # a run would have a gap
            count[nxt] -= starts
    return True

# python
# LC 1726 - Tuple with Same Product
# IDEA: count index pairs per product; c pairs give C(c, 2) choices, each yielding 8 orderings
# time = O(n^2), space = O(n^2)
def tupleSameProduct(nums):
    pairs_with = {}                        # {product: index pairs i < j with that product}
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            product = nums[i] * nums[j]
            pairs_with[product] = pairs_with.get(product, 0) + 1
    total = 0
    for c in pairs_with.values():
        total += 8 * (c * (c - 1) // 2)    # choose 2 pairs, then 2 * 2 * 2 orderings
    return total

// java
// LC 1726 - Tuple with Same Product
// IDEA: count index pairs per product; c pairs give C(c, 2) choices, each yielding 8 orderings
// time = O(n^2), space = O(n^2)
public int tupleSameProduct(int[] nums) {
    Map<Integer, Integer> pairsWith = new HashMap<>();   // values <= 10^4, so a product fits an int
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            pairsWith.merge(nums[i] * nums[j], 1, Integer::sum);
        }
    }
    int total = 0;
    for (int c : pairsWith.values()) {
        total += 4 * c * (c - 1);          // 8 * c * (c - 1) / 2, without the division
    }
    return total;
}

# python
# LC 734 - Sentence Similarity
# IDEA: store each similar pair under the key (min, max); compare the sentences word by word
# time = O(n + p), space = O(p)   n words, p pairs
def areSentencesSimilar(sentence1, sentence2, similarPairs):
    if len(sentence1) != len(sentence2):
        return False
    similar = set()
    for a, b in similarPairs:
        similar.add((min(a, b), max(a, b)))       # {a, b} in either order -> one key
    for a, b in zip(sentence1, sentence2):
        if a != b and (min(a, b), max(a, b)) not in similar:
            return False
    return True

# python
# LC 525 - Contiguous Array
# IDEA: 0 -> -1, then the longest subarray with sum 0 = the widest gap between two equal running sums
# time = O(n), space = O(n)
def findMaxLength(nums):
    first_index = {0: -1}          # running sum 0 before index 0: subarrays that start at 0
    running = 0
    longest = 0
    for i, x in enumerate(nums):
        running += 1 if x == 1 else -1
        if running in first_index:
            longest = max(longest, i - first_index[running])
        else:
            first_index[running] = i      # keep the FIRST index only: it gives the longest span
    return longest

// java
// LC 525 - Contiguous Array
// IDEA: 0 -> -1, then the longest subarray with sum 0 = the widest gap between two equal running sums
// time = O(n), space = O(n)
public int findMaxLength(int[] nums) {
    Map<Integer, Integer> firstIndex = new HashMap<>();
    firstIndex.put(0, -1);                 // subarrays that start at index 0
    int running = 0;
    int longest = 0;
    for (int i = 0; i < nums.length; i++) {
        running += (nums[i] == 1) ? 1 : -1;
        if (firstIndex.containsKey(running)) {
            longest = Math.max(longest, i - firstIndex.get(running));
        } else {
            firstIndex.put(running, i);    // first occurrence only
        }
    }
    return longest;
}

nums = [0,0,0,0,1,1]
i  x  running  first_index (after)              longest
0  0  -1       {0:-1, -1:0}                     0
1  0  -2       {..., -2:1}                      0
2  0  -3       {..., -3:2}                      0
3  0  -4       {..., -4:3}                      0
4  1  -3       -3 seen at 2  -> 4 - 2 = 2       2
5  1  -2       -2 seen at 1  -> 5 - 1 = 4       4   nums[2..5] = [0,0,1,1]

# python
# LC 670 - Maximum Swap
# IDEA: {digit: last index}; at the first position beaten by a larger digit later, swap with that digit's last copy
# time = O(n), space = O(1)   n digits, at most 10 keys
def maximumSwap(num):
    digits = list(str(num))
    last = {}
    for i, ch in enumerate(digits):
        last[int(ch)] = i                       # a later copy overwrites: the LAST index wins
    for i, ch in enumerate(digits):
        current = int(ch)
        for d in range(9, current, -1):         # the largest digit first
            if last.get(d, -1) > i:
                j = last[d]
                digits[i], digits[j] = digits[j], digits[i]
                return int("".join(digits))     # only one swap is allowed
    return num                                  # already the largest arrangement

// java
// LC 670 - Maximum Swap
// IDEA: {digit: last index}; at the first position beaten by a larger digit later, swap with that digit's last copy
// time = O(n), space = O(1)   10 digits
public int maximumSwap(int num) {
    char[] digits = String.valueOf(num).toCharArray();
    int[] last = new int[10];
    for (int i = 0; i < digits.length; i++) {
        last[digits[i] - '0'] = i;
    }
    for (int i = 0; i < digits.length; i++) {
        int current = digits[i] - '0';
        for (int d = 9; d > current; d--) {
            if (last[d] > i) {
                char tmp = digits[i];
                digits[i] = digits[last[d]];
                digits[last[d]] = tmp;
                return Integer.parseInt(new String(digits));
            }
        }
    }
    return num;
}

num = 2736   last = {2:0, 7:1, 3:2, 6:3}
i=0  digit 2: try 9, 8 (absent), 7 -> last[7] = 1 > 0  -> swap 0 and 1 -> 7236, stop

# python
# LC 2471 - Minimum Number of Operations to Sort a Binary Tree by Level
# IDEA: BFS per level; min swaps to sort a level = place sorted[i] at i via a {value: current index} map
# time = O(n log n), space = O(w)   w = the widest level
from collections import deque

def minimumOperations(root):
    queue = deque([root])
    operations = 0
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        operations += min_swaps(level)
    return operations

def min_swaps(arr):
    target = sorted(arr)
    position = {}                               # {value: current index}; values are unique
    for i, v in enumerate(arr):
        position[v] = i
    swaps = 0
    for i in range(len(arr)):
        want = target[i]
        if arr[i] != want:
            j = position[want]                  # where the value that belongs at i sits now
            position[arr[i]] = j                # update the map BEFORE the swap overwrites arr[i]
            position[want] = i
            arr[i], arr[j] = arr[j], arr[i]
            swaps += 1
    return swaps

// java
// LC 2471 - Minimum Number of Operations to Sort a Binary Tree by Level
// IDEA: BFS per level; min swaps to sort a level = place sorted[i] at i via a {value: current index} map
// time = O(n log n), space = O(w)
public int minimumOperations(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int operations = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        int[] level = new int[size];
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level[i] = node.val;
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        operations += minSwaps(level);
    }
    return operations;
}

private int minSwaps(int[] arr) {
    int[] target = arr.clone();
    Arrays.sort(target);
    Map<Integer, Integer> position = new HashMap<>();   // {value: current index}
    for (int i = 0; i < arr.length; i++) {
        position.put(arr[i], i);
    }
    int swaps = 0;
    for (int i = 0; i < arr.length; i++) {
        int want = target[i];
        if (arr[i] != want) {
            int j = position.get(want);
            position.put(arr[i], j);       // update the map before the swap
            position.put(want, i);
            arr[j] = arr[i];
            arr[i] = want;
            swaps++;
        }
    }
    return swaps;
}

min_swaps([3, 1, 2])   target = [1, 2, 3]   position = {3:0, 1:1, 2:2}
i=0  want 1 at j=1   position -> {3:1, 1:0}   arr = [1, 3, 2]   swaps = 1
i=1  want 2 at j=2   position -> {3:2, 2:1}   arr = [1, 2, 3]   swaps = 2
i=2  3 already in place                                          -> 2

# python
# LC 1257 - Smallest Common Region
# IDEA: {child: parent} from the lists; region1's ancestors in a set; walk region2 up until it hits one
# time = O(total names), space = O(total names)
def findSmallestRegion(regions, region1, region2):
    parent = {}
    for group in regions:
        for child in group[1:]:            # group[0] contains every other name in the list
            parent[child] = group[0]
    ancestors = set()
    node = region1
    while node is not None:
        ancestors.add(node)                # region1 counts as its own ancestor
        node = parent.get(node)            # the root has no parent -> None
    node = region2
    while node not in ancestors:           # the root is in the set, so this stops
        node = parent[node]
    return node

// java
// LC 1257 - Smallest Common Region
// IDEA: {child: parent} from the lists; region1's ancestors in a set; walk region2 up until it hits one
// time = O(total names), space = O(total names)
public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
    Map<String, String> parent = new HashMap<>();
    for (List<String> group : regions) {
        for (int i = 1; i < group.size(); i++) {
            parent.put(group.get(i), group.get(0));
        }
    }
    Set<String> ancestors = new HashSet<>();
    for (String node = region1; node != null; node = parent.get(node)) {
        ancestors.add(node);
    }
    String node = region2;
    while (!ancestors.contains(node)) {
        node = parent.get(node);
    }
    return node;
}