# 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.
```python
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
```python
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
```python
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](https://leetcode.com/problems/linked-list-cycle-ii/solutions/44783/share-my-python-solution-with-detailed-explanation/)
```
# 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])
```python
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**
```python
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.
```python
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
```python
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.
```python
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
```
```python
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".
```
```python
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
```python
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
```python
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.
```
```python
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
```
Sign in with Wallet
Connect another wallet