23.05.23 Today’s Leetcode

1140. Stone Game II (medium)

DFS Approach

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:

        @cache
        def dfs(cur, M):
            prev = cur
            res = 0
            for X in range(1, 2 * M + 1):
                if cur >= len(piles):
                    break
                temp = dfs(cur + 1, max(M, X))
                res = max(res, sum(piles[prev:]) - temp)
                cur += 1

            return res

        return dfs(0, 1)

380. Insert Delete GetRandom O(1) (medium)

class RandomizedSet:

  def __init__(self):
    self.val_to_index = {}  # Hash table to store values and their indices in the array
    self.vals = []          # Array to store the actual values

  def insert(self, val: int) -> bool:
    if val in self.val_to_index:    # If the value already exists in the hash table, return false
        return False
    self.val_to_index[val] = len(self.vals)    # Add the value to the hash table with its index in the array
    self.vals.append(val)           # Append the value to the end of the array
    return True                     # Return true to indicate success

  def remove(self, val: int) -> bool:
    """
    Removes a value from the set. Returns true if the set contained the specified element.
    """
    if val not in self.val_to_index:    # If the value does not exist in the hash table, return false
        return False
    index = self.val_to_index[val]      # Get the index of the value in the array
    last_val = self.vals[-1]            # Get the last value in the array
    self.vals[index] = last_val         # Swap the value at the index with the last value in the array
    self.val_to_index[last_val] = index # Update the index of the last value in the hash table
    self.vals.pop()                     # Remove the last value from the array
    del self.val_to_index[val]           # Remove the removed value from the hash table
    return True                          # Return true to indicate success

  def getRandom(self) -> int:
    """
    Get a random element from the set.
    """
    return random.choice(self.vals)     # Return a random value from the array