leetcode-011

Alpha

Top K Frequent Elements
Binary Search Tree Iterator
Edit Distance
LFU Cache
Basic Calculator III

Design Tic-Tac-Toe
Last Substring in Lexicographical Order
Design HashMap
Rotate Image
*Interleaving String

Beta

EQ-1

Given a non-empty array of integers, return the k most frequent elements.

1
2
3
4
5
6
7
8
9
10
11
12
13
# 347. Top K Frequent Elements

class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
dict_nums = collections.Counter(nums)
top_k = dict_nums.most_common(k)
print(top_k) # [(1, 3), (2, 2)]
return list(map(lambda x: x[0], top_k))

class Solution1:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = collections.Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)

EQ-2

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
# 173. Binary Search Tree Iterator

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class BSTIterator:

def __init__(self, root: TreeNode):
self.stack = []
while root:
self.stack.append(root)
root = root.left

def next(self) -> int:
"""
@return the next smallest number
"""

curr = self.stack.pop()
res = curr.val
curr = curr.right
while curr:
self.stack.append(curr)
curr = curr.left
return res

def hasNext(self) -> bool:
"""
@return whether we have a next smallest number
"""

return len(self.stack) > 0


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

class BSTIterator1:

def __init__(self, root: TreeNode):
self.nodes_sorted = []
self.index = -1
self._inorder(root)

def _inorder(self, root):
if not root:
return
self._inorder(root.left)
self.nodes_sorted.append(root.val)
self._inorder(root.right)

def next(self) -> int:
"""
@return the next smallest number
"""

self.index += 1
return self.nodes_sorted[self.index]


def hasNext(self) -> bool:
"""
@return whether we have a next smallest number
"""

return self.index + 1 < len(self.nodes_sorted)


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

EQ-3

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:

  • Insert a character
  • Delete a character
  • Replace a character
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 72. Edit Distance

class Solution:
def minDistance(self, word1: str, word2: str) -> int:
cache = {}
def recurse(i, j):
if (i, j) in cache:
return cache[(i, j)]
elif i == 0: result = j
elif j == 0: result = i
elif word1[i-1] == word2[j-1]:
result = recurse(i - 1, j - 1)
else:
delete = recurse(i, j - 1)
edit = recurse(i - 1, j - 1)
insert = recurse(i - 1, j)
result = 1 + min(delete, edit, insert)
cache[(i, j)] = result
return result

w1, w2 = len(word1), len(word2)
return recurse(w1, w2)


class Solution1:
def minDistance(self, word1: str, word2: str) -> int:
n, m = len(word1), len(word2)
if n * m == 0: return n + m

d = [[0]*(m+1) for _ in range(n+1)]
for i in range(n+1): d[i][0] = i
for j in range(m+1): d[0][j] = j

for i in range(1, n+1):
for j in range(1, m+1):
left = d[i-1][j] + 1
down = d[i][j-1] + 1
left_down = d[i-1][j-1]
if word1[i-1] != word2[j-1]: left_down += 1
d[i][j] = min(left, down, left_down)
return d[n][m]

EQ-4

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.
Note that the number of times an item is used is the number of calls to the get and put functions for that item since it was inserted. This number is set to zero when the item is removed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# 460. LFU Cache

from collections import OrderedDict, defaultdict

class LFUCache:

def __init__(self, capacity):
self.cache =
{}
self.count = collections.defaultdict(collections.OrderedDict)
self.min = 0
self.capacity = capacity


def get(self, key: int) -> int:
if key not in self.cache:
return -1
value, count = self.cache[key]
del self.count[count][key]
if count == self.min and not self.count[count]:
self.min += 1
self.count[count+1][key] = 0
self.cache[key] = (value, count+1)
return value


def put(self, key: int, value: int) -> None:
if self.capacity <= 0:
return
if key in self.cache:
old, count = self.cache[key]
self.cache[key] = (value, count)
self.get(key)
elif len(self.cache) == self.capacity:
old_key, v = self.count[self.min].popitem(last=False)
del self.cache[old_key]
self.min = 1
self.cache[key] = (value, 1)
self.count[1][key] = 0
else:
self.min = 1
self.cache[key] = (value, 1)
self.count[1][key] = 0


# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key, value)

EQ-5

Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces. The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces.
The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 772. Basic Calculator III

class Solution:
def calculate(self, s: str) -> int:
# first define a couple helper methods
# operation helper to perform basic math operations
s = s + "$"

def helper(stack: list, i: int) -> int:
num = 0
sign = '+'
while i < len(s):
c = s[i]
if c == " ":
i += 1
continue

if c.isdigit():
num = 10 * num + int(c)
i += 1
elif c == '(':
num, i = helper([], i+1) # Recursion
else:
if sign == '+':
stack.append(num)
if sign == '-':
stack.append(-num)
if sign == '*':
stack.append(stack.pop() * num)
if sign == '/':
stack.append(int(stack.pop() / num))
num = 0
i += 1
if c == ')':
return sum(stack), i
sign = c
return sum(stack)

return helper([], 0)

EQ-6

Design a Tic-tac-toe game that is played between two players on a n x n grid.
You may assume the following rules:

  • A move is guaranteed to be valid and is placed on an empty block.
  • Once a winning condition is reached, no more moves is allowed.
  • A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 348. Design Tic-Tac-Toe

class TicTacToe:

def __init__(self, n: int):
"""
Initialize your data structure here.
"""
self.row = [0 for i in range(n)]
self.col = [0 for i in range(n)]
self.major = 0
self.minor = 0
self.n = n

def move(self, row: int, col: int, player: int) -> int:
"""
Player {player} makes a move at ({row}, {col}).
@param row The row of the board.
@param col The column of the board.
@param player The player, can be either 1 or 2.
@return The current winning condition, can be either:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins.
"""
p = 1 if player == 1 else -1

self.row[row] += p
self.col[col] += p

if row == col:
self.major += p

if row == self.n-1-col:
self.minor += p

if abs(self.row[row]) == self.n or abs(self.col[col]) == self.n or \
abs(self.major) == self.n or abs(self.minor) == self.n:
return player

return 0

EQ-7

Given a string s, return the last substring of s in lexicographical order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 1163. Last Substring in Lexicographical Order

class Solution:
def lastSubstring(self, s: str) -> str:
# Time: O(n)
# Space: O(1)

idx = {c: i for i, c in enumerate(sorted(set(s)))}
radix, val, cur, m = len(idx), 0, 0, 0
for i in range(len(s))[::-1]:
cur = idx[s[i]] + cur/radix
if cur >= val:
m, val = i, cur
return s[m:]


class Solution1:
def lastSubstring(self, s: str) -> str:
i, j, k = 0, 1, 0
n = len(s)
while j + k < n:
if s[i+k] == s[j+k]:
k += 1
continue
elif s[i+k] > s[j+k]:
j = j + k + 1
else:
i = max(i + k + 1, j)
j = i + 1
k = 0
return s[i:]

EQ-8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# 706. Design HashMap

class MyHashMap:

def __init__(self, key=None, value=None):
self.key = key
self.value = value
global hashMap
hashMap = {}


def put(self, key: int, value: int) -> None:
hashMap[key] = value


def get(self, key: int) -> int:
return hashMap[key] if key in hashMap else -1


def remove(self, key: int) -> None:
if key in hashMap:
del hashMap[key]


class MyHashMap1:

def __init__(self):
"""
Initialize your data structure here.
"""

self.table = [-1] * 1000001

def put(self, key: int, value: int) -> None:
"""
value will always be non-negative.
"""

self.table[key] = value


def get(self, key: int) -> int:
"""
Returns the value to which the specified key is mapped,
or -1 if this map contains no mapping for the key
"""

return self.table[key]


def remove(self, key: int) -> None:
"""
Removes the mapping of the specified value key if this map contains a mapping for the key
"""

self.table[key] = -1


# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

EQ-9

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).

1
2
3
4
5
6
7
8
9
10
11
12
# 48. Rotate Image

# Do not return anything, modify matrix in-place instead.

class Solution1:
def rotate(self, matrix: List[List[int]]) -> None:
matrix[::] = zip(*matrix[::-1])


class Solution:
def rotate(self, A):
A[:] = [[row[i] for row in A[::-1]] for i in range(len(A))]

EQ-10 *

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 97. Interleaving String

class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s1) + len(s2) != len(s3):
return False

current_states = [(0, 0)]
for char in s3:
if len(current_states) == 0:
return False
next_states = set()
for i, j in current_states:
if i < len(s1) and s1[i] == char:
next_states.add((i + 1, j))
if j < len(s2) and s2[j] == char:
next_states.add((i, j + 1))
current_states = next_states

return len(current_states) > 0


class Solution1:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
stack = [(0,0,0)]
seen = {(0,0,0)}
while stack:
(i,j,k) = stack.pop()
if k == len(s3) and i == len(s1) and j == len(s2):
return True
if i < len(s1) and k < len(s3) and s1[i] == s3[k] and (i+1, j, k+1) not in seen:
stack.append((i+1, j, k+1))
seen.add((i+1, j, k+1))
if j < len(s2) and k < len(s3) and s2[j] == s3[k] and ( i, j+1, k+1) not in seen:
stack.append(( i, j+1, k+1))
seen.add(( i, j+1, k+1))
return FalseGiven s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Sigma

Feb 11, 2020
La Jolla, CA

Omega

https://leetcode.com/