leetcode-012

Alpha

Encode and Decode TinyURL
Add Binary
Diameter of Binary Tree
Read N Characters Given Read4 II - Call multiple times
Count of Smaller Numbers After Self

Top K Frequent Words
Swap Nodes in Pairs
Add Strings
Climbing Stairs
Interval List Intersections

Beta

EQ-1

Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 535. Encode and Decode TinyURL

class Codec:
def __init__(self):
self.urls = []

def encode(self, longUrl):
# Encodes a URL to a shortened URL.
self.urls.append(longUrl)
return 'http://tinyurl.com/' + str(len(self.urls) - 1)

def decode(self, shortUrl):
# Decodes a shortened URL to its original URL.
return self.urls[int(shortUrl.split('/')[-1])]


# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(url))

EQ-2

Given two binary strings, return their sum(also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.

1
2
3
4
5
6
7
8
9
# 67. Add Binary


class Solution:
def addBinary(self, a: str, b: str) -> str:
x, y = int(a, 2), int(b, 2)
while y != 0:
x, y = x ^ y, (x & y) << 1
return bin(x)[2:]

EQ-3

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None


class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:

maxDiameter = 0

if root is None:
return 0

def maxDepth(root: TreeNode) -> int:
nonlocal maxDiameter
if root is None:
return 0
left = maxDepth(root.left)
right = maxDepth(root.right)
currDiameter = left + right

maxDiameter = max(maxDiameter, currDiameter)

return max(left, right) + 1

maxDepth(root)
return maxDiameter


class Solution1:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
def _dfs(node: TreeNode):
if node is None:
return 0, 0
l_depth, l_diameter = _dfs(node.left)
r_depth, r_diameter = _dfs(node.right)
depth = max(l_depth, r_depth) + 1
diameter = max(l_depth + r_depth, l_diameter, r_diameter)
return depth, diameter

_, result = _dfs(root)
return result

EQ-4

Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters. Your method read may be called multiple times.

Method read4:
The API read4 reads 4 consecutive characters from the file, then writes those characters into the buffer array buf.
The return value is the number of actual characters read.
Note that read4() has its own file pointer, much like FILE * fp in C.

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
"""
The read4 API is already defined for you.

@param buf, a list of characters
@return an integer
def read4(buf):

# Below is an example of how the read4 API can be called.
file = File("abcdefghijk") # File is "abcdefghijk", initially file pointer (fp) points to 'a'
buf = [' '] * 4 # Create buffer with enough space to store characters
read4(buf) # read4 returns 4. Now buf = ['a','b','c','d'], fp points to 'e'
read4(buf) # read4 returns 4. Now buf = ['e','f','g','h'], fp points to 'i'
read4(buf) # read4 returns 3. Now buf = ['i','j','k',...], fp points to end of file
"""


class Solution:
def __init__(self):
self._left = []

def read(self, buf, n):
c, i = 0, 0
while n > 0 and self._left:
buf[i] = self._left.pop(0)
n -= 1
i += 1
c += 1

for i in range(n//4):
buf4 = ['']*4
n4 = read4(buf4)
for j in range(n4):
buf[c+j] = buf4[j]
c += n4
if n % 4:
buf4 = ['']*4
n4 = read4(buf4)
for i in range(n % 4):
buf[c+i] = buf4[i]
c += min(n4, n % 4)
for i in range(n % 4, n4):
self._left.append(buf4[i])

return c


class Solution1:

def __init__(self):
self.chars = itertools.chain.from_iterable(
iter(lambda buf=[0]*4: buf[:read4(buf)], []))

def read(self, buf, n):
"""
:type buf: Destination buffer (List[str])
:type n: Number of characters to read (int)
:rtype: The number of actual characters read (int)
"""
return len([buf.__setitem__(*x) for x in zip(range(n), self.chars)])

EQ-5

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Input: [5,2,6,1] Output: [2,1,1,0]

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
# 315. Count of Smaller Numbers After Self

class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
rank, N, res = {val: i + 1 for i, val in enumerate(sorted(nums))}, len(nums), []
BITree = [0] * (N + 1)

def update(i):
while i <= N:
BITree[i] += 1
i += (i & -i)

def getSum(i):
s = 0
while i:
s += BITree[i]
i -= (i & -i)
return s

for x in reversed(nums):
res += getSum(rank[x] - 1),
update(rank[x])

return res[::-1]


from bisect import bisect_left
class Solution1:
def countSmaller(self, nums: List[int]) -> List[int]:
if not nums:
return []

idx, res = [], []
for n in reversed(nums):
p = bisect_left(idx, n)
res.append(p)
idx[p:p] = [n]#idx.insert(p, n)
return res[::-1]

EQ-6

Given a non-empty list of words, return the k most frequent elements.
Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 692. Top K Frequent Words

class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
out = []
counts = collections.Counter(words)
out = [(-f,w) for w,f in counts.items()]
heapq.heapify(out)
return [heapq.heappop(out)[1] for _ in range(k)]


class Solution1:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
return [w for w, v in sorted(collections.Counter(words).items(), key = lambda x: (-x[1], x[0])) [:k]]

EQ-7

Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list’s nodes, only nodes itself may be changed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 24. Swap Nodes in Pairs

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

class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
pre, pre.next = self, head
while pre.next and pre.next.next:
a = pre.next
b = a.next
pre.next, b.next, a.next = b, a, b.next
pre = a
return self.next

EQ-8

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

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
# 415. Add Strings

class Solution:
def addStrings(self, num1: str, num2: str) -> str:
num1 = list(num1)
num2 = list(num2)
out = []
carry = 0
while num1 or num2 or carry:
if num1:
carry += int(num1[-1])
num1.pop()
if num2:
carry += int(num2[-1])
num2.pop()
out.append(str(carry % 10))
carry = carry // 10
out = out[::-1]
return ''.join(out)


class Solution1:
def addStrings(self, num1: str, num2: str) -> str:
num1, num2 = list(num1), list(num2)
carry, res = 0, []
while len(num2) > 0 or len(num1) > 0:
n1 = ord(num1.pop())-ord('0') if len(num1) > 0 else 0
n2 = ord(num2.pop())-ord('0') if len(num2) > 0 else 0

temp = n1 + n2 + carry
res.append(temp % 10)
carry = temp // 10
if carry: res.append(carry)
return ''.join([str(i) for i in res])[::-1]

EQ-9

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 70. Climbing Stairs

class Solution:
def climbStairs(self, n: int) -> int:
x = [1,2]
for i in range(2,n):
x.append(x[i-1]+x[i-2])
return x[n-1]


class Solution1:
def climbStairs(self, n: int) -> int:
# fibonacci
a = 1
b = 0
for i in range(n):
res = a + b
b = a
a = res
return res

EQ-10

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.
Return the intersection of these two interval lists.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 986. Interval List Intersections

class Solution:
def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
res = []
i = j = 0
while i < len(A) and j < len(B):
if A[i][0] <= B[j][1] and B[j][0] <= A[i][1]:
res.append([max(A[i][0], B[j][0]), min(A[i][1], B[j][1])])
if A[i][1] < B[j][1]:
i+=1
else:
j+=1
return res

Sigma

Feb 11, 2020
La Jolla, CA

Omega

https: // leetcode.com/