LeetCode75 Level 1

Prefix Sum

1480. Running Sum of 1d Array

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

class Solution(object):
    def runningSum(self, nums):
        result=[]
        sum=0
        for i in range(len(nums)):
            sum+=nums[i]
            result.append(sum)
        return result

724. Find Pivot Index

Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

• Approach

1. first compute the sum of the list
2. from left to right, compute the sum that we've travel, store into a variable leftsum
3. rightsum = totalsum-leftsum-the index value
4. if leftsum = rightsum, then we find the pivot index

class Solution(object):
    def pivotIndex(self, nums):
        if len(nums) == 1:
            return 0
        else:
            leftsum=0
            totalsum = sum(nums)
            for i in range(len(nums)):
                if totalsum-leftsum-nums[i] == leftsum:
                    return i
                leftsum += nums[i]
            return -1

String

205. Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

• Approach

1. use the map to store each pair of character
2. need to be bidirectional, since s to t or t to s can't have one-to-many situation

class Solution(object):
    def isIsomorphic(self, s, t):
        if len(s)!=len(t):
            return False
        else:
            mapST, mapTS = {}, {}
            for i in range(len(s)):
                c1, c2 = s[i], t[i]
                if ((c1 in mapST and mapST[c1]!=c2)or
                    (c2 in mapTS and mapTS[c2]!=c1)):
                    return False
                mapST[c1]=c2
                mapTS[c2]=c1
            return True

392. Is Subsequence

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

• Approach

1. pointer for string s, compare the value of string s start from index 0
2. if the value of idx match the character in string t, idx++
3. so if idx equals to len(t) means string s is subsequence of string t

class Solution(object):
    def isSubsequence(self, s, t):
        if len(s)==0:
            return True
        if len(t)<len(s):
            return False
        idx=0
        for i in range(len(t)):
            if idx<len(s):
                if s[idx]==t[i]:
                    idx+=1
        return idx==len(s)

Linked list

21. Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        if ((not list1) and (not list2)): #both lists are empty
            return list1
        elif not list1 : #one of the list is empty
            return list2
        elif not list2:
            return list1
        else:
            result=current=ListNode() #current is the pointer for the result linked list
            while list1 and list2:
                if list1.val < list2.val:
                    current.next = list1 
                    current = list1 #update current pointer
                    list1 = list1.next #compare the next value
                else:
                    current.next = list2
                    current = list2
                    list2 = list2.next
            if list1:
                current.next = list1
            else:
                current.next = list2
            return result.next

206. Reverse Linked List

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        if not head:
            return head
        else:
            prev = None
            curr = None
            while head:
                curr = head
                head = head.next
                curr.next = prev
                prev = curr
            return curr

876. Middle of the Linked List

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def middleNode(self, head):
        count = 0 
        curr = head
        while curr:
            count += 1
            curr = curr.next
        idx_middle = count / 2
        for i in range(idx_middle):
            head = head.next
        return head

142. Linked List Cycle II

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

• tutorial

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        try:
            fast = head.next
            slow = head
            while fast is not slow:
                fast = fast.next.next
                slow = slow.next
        except:
            # if there is an exception, we reach the end and there is no cycle
            return None

        # since fast starts at head.next, we need to move slow one step forward
        slow = slow.next
        while head is not slow:
            head = head.next
            slow = slow.next

        return head

Greedy

121. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

• Approach

1. use two pointers buy and sell, respectively
2. keep track of the profit(sell-buy), if buy value > sell value, we update the buy pointer by moving to the next day
3. if sell value > buy value, note the profit, and update the sell pointer by moving to the next day

class Solution(object):
    def maxProfit(self, prices):
        if len(prices)==1:
            return 0
        else:
            buy,sell=0,1
            max_profit=0
            while sell < len(prices):
                if prices[buy] > prices[sell]:
                    buy += 1
                else:
                    profit=prices[sell]-prices[buy]
                    max_profit = max(max_profit,profit)
                    sell += 1
            return max_profit

409. Longest Palindrome

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome here.

• Approach
  when it comes to palindrome, there are two cases

1. if the number of the character is even, we can put that character into palindrome
2. otherwise(the number is odd), we can put (number-1) into palindrome since (number-1) becomes even, finally, add arbitrary character into the middle of the palindrome

class Solution(object):
    def longestPalindrome(self, s):
        if len(s)==1:
            return 1
        else:
            map={}
            for i in range(len(s)):
                if s[i] not in map:
                    map[s[i]] = 1
                else:
                    map[s[i]] += 1
            result = 0
            flag = True #means all the counts are even
            for char in map:
                if map[char] % 2 == 0:
                    result += map[char]
                else:
                    result += (map[char]-1)
                    flag = False
            if flag :
                return result
            else:
                return result+1

Tree

589. N-ary Tree Preorder Traversal

Given the root of an n-ary tree, return the preorder traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)
Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: [1,3,5,6,2,4]

• Approach
  preorder = depth first search, use recursive to solve it
• Solution

class Solution(object):
    def preorder(self, root):
        result=[]
        def depth(node):
            if node:
                result.append(node.val)
                for c in node.children:
                    depth(c)
        depth(root)

        return result

102. Binary Tree Level Order Traversal

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

• Approach
  use Queue

1. first put the root node into queue
2. for each layer, note the length of queue, which equals to the number of nodes of that layer
3. put every node to the list, then combine together

• Solution

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def levelOrder(self, root):
        result=[]
        #create the queue
        q = collections.deque()
        q.append(root)

        while q:
            node_count = len(q)
            layer = []
            for i in range(node_count):
                node = q.popleft()
                #put the value into layer list, and enqueue the left/right children of that node
                if node:
                    layer.append(node.val)
                    q.append(node.left)
                    q.append(node.right)
            if layer:
                result.append(layer)
        return result

Binary Search

704. Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

• Approach

1. use two pointers left and right, respectively
2. compare the middle value between left and right
3. if the middle value > target, means we need to find left part of the list, so modify the 'right ' pointer, vice versa

class Solution(object):
    def search(self, nums, target):
        if len(nums)==1:
            if nums[0]==target:
                return 0
            else:
                return -1
        else:
            left,right=0,len(nums)-1
            while left<=right:
                mid=(left+right)/2
                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:
                    right = mid - 1
                else:
                    left = mid + 1
            return -1

278. First Bad Version

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

• Approach
  use the concept of binary search to find the left-most bad version
• Solution

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution(object):
    def firstBadVersion(self, n):
        if n == 1:
            return 1
        else:
            low,high=1,n
            bad_version=n
            while low<=high:
                mid = (low+high)/2
                if isBadVersion(mid):
                    high=mid - 1
                    if mid < bad_version:
                        bad_version = mid
                else:
                    low = mid + 1
            return bad_version

Binary Search Tree

98. Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

1. The left subtree of a node contains only nodes with keys less than the node's key.
2. The right subtree of a node contains only nodes with keys greater than the node's key.
3. Both the left and right subtrees must also be binary search trees.

• Approach
  BST's property: Use inorder traversal to travel the BST will get an ascending order
  Therefore, we can just see if the order is ascending or not.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isValidBST(self, root):
        result=[]
        def inorder(node):
            if node:
                inorder(node.left)
                result.append(node.val)
                inorder(node.right)
        inorder(root)
        for i in range(1,len(result)):
            if result[i] <= result[i-1]:
                return False
        return True

235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

• Approach
  starting from root, there are 3 cases:

1. both p and q are greater than node, then only need to search right subtree
2. both p and q are smaller than node, then only need to search left subtree
3. node equals to p or q, then this node is the answer

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        curr = root
        while curr:
            if curr.val < p.val and curr.val < q.val:
                curr = curr.right
            elif curr.val > p.val and curr.val > q.val:
                curr = curr.left
            elif curr.val == p.val or curr.val == q.val:
                return curr
            else:
                return curr

Graph/BFS/DFS

733. Flood fill

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.

Return the modified image after performing the flood fill.

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

• Approah
  starting from the given index, there are 4 directions to travel

1. if the starting index is already equals to the new color, we don't need to do anything
2. if the index out of range, return
3. if the given index is not the origin color, then we can ignore it
4. use a function to travel each directions and change the color

class Solution(object):
    def floodFill(self, image, sr, sc, color):
        if image[sr][sc] == color:
            return image
        def depth(image,r,c,origincolor,newcolor):
            if r<0 or r>=len(image) or c<0 or c>=len(image[0]) or image[r][c] != origincolor:
                return
            image[r][c] = newcolor
            depth(image,r,c+1,origincolor,newcolor)
            depth(image,r,c-1,origincolor,newcolor)
            depth(image,r+1,c,origincolor,newcolor)
            depth(image,r-1,c,origincolor,newcolor)
        depth(image,sr,sc,image[sr][sc],color)
        return image

200. Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

• Appraoch
  using the Breadth First Search(BFS)
  In the BFS
  step:

q = createQueue()
while q is not empty:
    U = dequeue()
    for each adjacent W for U:
        if not visited(W):
            visited(W)
            Enqueue(W)

class Solution(object):
    def numIslands(self, grid):
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        visited = set()
        islands = 0

        def bfs(r,c):
            q = deque()
            q.append((r,c))
            visited.add((r,c))

            while q:
                row, col = q.popleft()
                adjacency = [[1,0], [-1,0], [0,1], [0,-1]]
                for dr, dc in adjacency:
                    r = row + dr
                    c = col + dc
                    if (r in range(rows) and
                        c in range(cols) and
                        (r,c) not in visited and
                        grid[r][c] == "1"):
                        visited.add((r,c))
                        q.append((r,c))

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1" and (r, c) not in visited:
                    bfs(r, c)
                    islands += 1
        return islands

Dynamic Programming

509. Fibonacci Number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

class Solution(object):
    def fib(self, n):
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            output = [0,1]
            for i in range(2,n+1):
                output.append(output[i-1]+output[i-2])
            return output[n]

70. Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

• Approach

i.e. n=5

1. for n=5, there is one way to get to this stair
2. for n=4. there is one way to get to 5th stair
3. for n=3, there is two ways to get to 5th stair.
   (description)
   In 3rd. stair, we have two options, which are taking one step or taking two steps, if we take one step to 4th. stair, and we have already computed how many ways 4th stair get to 5th stair. If we take two steps from 3rd stair, we have already computed how many ways 5th stair get to 5th stair.
4. Therefore, for each nth stair, we can use (n+1)th stair and (n+2)stair to compute

class Solution(object):
    def climbStairs(self, n):
        if n<=2:
            return n
        else:
            one = 1
            two = 1
            for i in range(n-1):
                step = one +two
                two = one
                one = step
            return step

746. Min Cost Climbing Stairs

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

• Approach
  Similar idea to 70.Climbing stairs
  we can think it reversely
  i.e. Input: cost = [1,100,1,1,1,100,1,1,100,1]

1. min cost to the top stair is 0
2. min cost to the top stair at index=9 is cost[9], which is 1 in this example
3. min cost to the top stair at index=8 is cost[8], which is 100 in this example
4. starting from index=7, the min cost to the top stair at that index is: cost[index]+min(cost[index+1],cost[index+2])

class Solution(object):
    def minCostClimbingStairs(self, cost):
        if len(cost) == 2:
            return min(cost[0],cost[1])
        else:
            now = 0
            one, two = cost[-1], cost[-2]
            for i in range(len(cost)-3,-1,-1):
                now = cost[i] + min(one,two)
                one = two
                two = now
            return min(one,two)

62. Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Input: m = 3, n = 7
Output: 28

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

• Approach

class Solution(object):
    def uniquePaths(self, m, n):
        if m == 1 and n == 1:
            return 1
        else:
            result = [[0 for _ in range(n)] for _ in range(m)]
            for row in range(m):
                for col in range(n):
                    if row == 0 and col == 0:
                        result[row][col] = 0
                    elif row == 0 and col != 0:
                        result[row][col] = 1
                    elif col == 0 and row != 0:
                        result[row][col] = 1
                    else:
                        result[row][col] = result[row-1][col] + result[row][col-1]
            return result[m-1][n-1]

Sliding window/Two pointer

438. Find All Anagrams in a String

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

• Approach
  Use the Hash map

1. use sCount and pCount to record the times characters appear
2. first loop is to initialize the hash map and compare the first sliding window
3. second loop is to compare the rest of the string by using two pointers, left and right.
4. each round check the two hash map, if they're same, means there is an anagram, and we record it.

class Solution(object):
    def findAnagrams(self, s, p):
        if len(p) > len(s): return []

        pCount, sCount = {}, {}
        for i in range(len(p)):
            #.get(要找的值,沒找到的話回傳預設值)
            pCount[p[i]] = 1 + pCount.get(p[i],0)
            sCount[s[i]] = 1 + sCount.get(s[i],0)
        result = [0] if pCount == sCount else []
        
        left = 0
        for right in range(len(p),len(s)):
            sCount[s[right]] = 1 + sCount.get(s[right],0)
            
            sCount[s[left]] -= 1
            if sCount[s[left]] == 0:
                sCount.pop(s[left])
            left += 1

            if sCount == pCount:
                result.append(left)
        
        return result

424. Longest Repeating Character Replacement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

• Approach

1. use two pointers left and right to represent sliding window
2. change_count = window size - max(count)
3. sliding window is valid if change_count <= k, and this means we have change_count of characters can be replaced
4. if the sliding window is valid, move right pointer, otherwise move left pointer

class Solution(object):
    def characterReplacement(self, s, k):
        charCount = {}
        result = 0
        left = 0
        for right in range(len(s)):
            charCount[s[right]] = 1 + charCount.get(s[right],0)

            if ((right - left + 1) - max(charCount.values())) > k:
                charCount[s[left]] -= 1
                left += 1
            
            result = max(result,right - left + 1)
        
        return result

Hashmap

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

class Solution(object):
    def twoSum(self, nums, target):
        map={}
        for i in range(len(nums)):
            if nums[i] not in map:
                map[target-nums[i]]=i
            else:
                return map[nums[i]],i

299. Bulls and Cows

You are playing the Bulls and Cows game with your friend.

Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
  |
"7810"

• Approach
  Keep track of the character in two string from left to right
  Use one list to store the counts of number 0~9
  i.e. secret="1807", guess="7810"

1. if two characters are the same and in the same position, bulls++
2. if not, the number[secret]++, number[guess]–

# numbers[g] > 0, means that character already exist in secret string
if numbers[g] > 0: cows += 1

#numbers[s] < 0, means that character already exist in guess string
if numbers[s] < 0: cows += 1
numbers[s] += 1
numbers[g] -= 1

class Solution(object):
    def getHint(self, secret, guess):
        numbers = [0 for _ in range(10)]
        bulls, cows = 0, 0
        for i in range(len(secret)):
            s = int(secret[i])
            g = int(guess[i])
            if s == g:
                bulls += 1
            else:
                if numbers[g] > 0: cows += 1
                if numbers[s] < 0: cows += 1
                numbers[s] += 1
                numbers[g] -= 1
        return str(bulls) + "A" + str(cows) + "B"

Stack

844. Backspace String Compare

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

class Solution(object):
    def backspaceCompare(self, s, t):
        stackS, stackT = [], []
        for i in range(len(s)):
            if s[i] == "#" and len(stackS)!=0:
                stackS.pop()
            elif s[i] == "#" and len(stackS) == 0:
                stackS = []
            else:
                stackS.append(s[i])
        
        for i in range(len(t)):
            if t[i] == "#" and len(stackT)!=0:
                stackT.pop()
            elif t[i] == "#" and len(stackT) == 0:
                stackT = []
            else:
                stackT.append(t[i])
        return stackS == stackT

394. Decode String

Input: s = "3[a2[c]]"
Output: "accaccacc"

• Approach
  Use stack to solve it

1. if the character is not "]", just push into stack
2. if "]" appears, we need to pop untill the open braket shows up, and keep poping to find the digit
3. push the digit*substring back to stack, and so on

class Solution(object):
    def decodeString(self, s):
        stackS = []
        for i in range(len(s)):
            if s[i] == "]":
                temp = ""
                while stackS[-1] != "[":
                    temp = stackS.pop() + temp
                stackS.pop()

                k = ""
                while stackS and stackS[-1].isdigit():
                    k = stackS.pop() + k
                
                stackS.append(int(k) * temp)
            else:
                stackS.append(s[i])

        return "".join(stackS)

Heap

1046. Last Stone Weight

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

If x == y, both stones are destroyed, and
If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

• Approach
  use Max-Heap to solve it

1. each round pop the largest value in the heap twice
2. simulate the condition
   Note: python only have min-heap, so we multiply -1 for the list to fit this question

class Solution(object):
    def lastStoneWeight(self, stones):
        stones = [-s for s in stones]
        heapq.heapify(stones)
        while len(stones) > 1:
            largest = heapq.heappop(stones)
            second = heapq.heappop(stones)
            if second > largest:
                heapq.heappush(stones, largest - second)
            
        stones.append(0)
        return abs(stones[0])

692. Top K Frequent Words

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Input: words = ["i","love","leetcode","i","love","coding"], k = 2
Output: ["i","love"]
Explanation: "i" and "love" are the two most frequent words.
Note that "i" comes before "love" due to a lower alphabetical order.

class Solution(object):
    def topKFrequent(self, words, k):
        corpus = {}
        maxFreq = 0
        for i in range(len(words)):
            corpus[words[i]] = 1 + corpus.get(words[i],0)
            maxFreq = max(maxFreq, corpus[words[i]])
        
        result = []
        freq = maxFreq
        while freq >= 1:
            temp = []
            for word in corpus:
                if corpus[word] == freq:
                    temp.append(word)
            temp = sorted(temp)
            for i in range(len(temp)):
                result.append(temp[i])
                if len(result) == k:
                    return result
            freq -= 1