January LeetCoding Challenge 2021 Flashcards
- Palindrome Permutation
Given a string, determine if a permutation of the string could form a palindrome.
Input: “code”
Output: false
Input: “aab”
Output: true
In case of a palindrome, the number of characters with odd number of occurrences can’t exceed 1.
map(c, #occurences of c)
Time O(n), Space O(1) cuz the number of distinct characters are bounded
- Check Array Formation Through Concatenation
You are given an array of distinct integers “arr” and an array of integer arrays “pieces”, where the integers in “pieces” are distinct. Your goal is to form “arr” by concatenating the arrays in “pieces” in any order. However, you are not allowed to reorder the integers in each array pieces[i].
Return true if it is possible to form the array “arr” from “pieces”. Otherwise, return false.
Input: arr = [15,88], pieces = [[88],[15]]
Output: true
Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
Output: true
Input: arr = [49,18,16], pieces = [[16,18,49]]
Output: false
Explanation: Even though the numbers match, we cannot reorder pieces[0].
Store the “pieces” according to their first element in a hashmap. Find the piece starting with arr[i] in mapping. Return false if no match. Check whether each integer in the piece matches arr’s sublist starting from i with the same length.
Time O(N), Space O(N), N length of arr
class Solution:
def canFormArray(self, arr, pieces):
n = len(arr)
mapping = {p[0]: p for p in pieces}
i = 0
while i < n:
if arr[i] not in mapping:
return False
target_piece = mapping[arr[i]]
for x in target_piece:
if x != arr[i]:
return False
i += 1
return True
- Find a Corresponding Node of a Binary Tree in a Clone of That Tree
Given two binary trees original and cloned and given a reference to a node target in the original tree.
The cloned tree is a copy of the original tree.
Return a reference to the same node in the cloned tree.
Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.
Follow up: Solve the problem if repeated values on the tree are allowed.
Let’s traverse both trees in parallel, and once the target node is identified in the first tree, return the corresponding node from the second tree.
1) DFS: Time O(N), Space O(H) to keep the recursion stack, where H is a tree height.
inorder / preorder / postorder
def inorder(o: TreeNode, c: TreeNode):
if o:
inorder(o.left, c.left)
if o is target:
self.ans = c
inorder(o.right, c.right)
inorder(original, cloned)
return self.ans
2) BFS: Time O(N), Space O(N) to keep the queue. Let’s use the last level to estimate the queue size. This level could contain up to N/2 tree nodes in the case of complete binary tree.
qor, qcl = deque(), deque()
nor, ncl = original, cloned
while nor!=target:
if nor:
qor.append(nor.left)
qor.append(nor.right)
qcl.append(ncl.left)
qcl.append(ncl.right)
nor = qor.popleft()
ncl = qcl.popleft()
return ncl
- Beautiful Arrangement
Suppose you have n integers from 1 to n. We define a beautiful arrangement as an array that is constructed by these n numbers successfully if one of the following is true for the ith position (1 <= i <= n) in this array:
The number at the ith position is divisible by i.
i is divisible by the number at the ith position.
Given an integer n, return the number of the beautiful arrangements that you can construct. (1 <= n <= 15)
Input: n = 2
Output: 2
Explanation:
The first beautiful arrangement is [1, 2]:
Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).
Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).
The second beautiful arrangement is [2, 1]:
Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).
Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
1) Brute force O(n!)
2) Backtracking
我们使用一个使用一个大小为 n 的 “已使用数组” ，这里 visited[i]表示目前为止第 i 个数字是否已经使用过.
我们使用函数 helper，它将从 1 到 n 所有还没有visited数字放到当前位置 idx，并检查是否满足divisible。如果 i 放到当前位置 idx 是满足要求的，我们就把 i 放在当前位置 idx 并继续考虑下一个位置 idx + 1，否则我们需要换一个数字放在当前位置。
class Solution:
ans = 0
def countArrangement(self, n: int) -> int:
def helper(visited, idx):
if idx>n: #判断否已进入最底层
self.ans += 1
return
for i in range(n): #每一层遍历
#剪枝
if visited[i]==0 and (((i+1)%idx==0) | (idx%(i+1)==0)):
visited[i] = 1
helper(visited, idx+1) #递归
visited[i] = 0 #递归结束后将visited[i]重置
visited = [0] * n
helper(visited, 1)
return self.ans
Time O(k). k the number of valid permutations. 递归深度为n层，但每一层需要执行的递归次数却是由该层的固定位置下可能存在的优美排列的数量决定的。 因此，时间复杂度就是O（k），k为优美排列的数量 Space O(n), visited array of size n is used. The depth of recursion tree will also go upto n.
- Merge Two Sorted Lists
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Approach 1: Iteration, time O(n+m), space O(1)
class Solution:
def mergeTwoLists(self, l1, l2):
# maintain an unchanging reference to node ahead of the return node.
prehead = ListNode(-1)
prev = prehead
while l1 and l2:
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next
# exactly one of l1 and l2 can be non-null at this point, so connect
# the non-null list to the end of the merged list.
prev.next = l1 if l1 is not None else l2
return prehead.next
Approach 2: Recursion, time O(n+m), space O(n+m) The first call to mergeTwoLists does not return until the ends of both l1 and l2 have been reached, so n + m stack frames.
class Solution:
def mergeTwoLists(self, l1, l2):
if l1 is None:
return l2
elif l2 is None:
return l1
elif l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
- Remove Duplicates from Sorted List II
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
Input: head = [1,1,1,2,3]
Output: [2,3]
Approach 1: Sentinel Head + Predecessor
Time O(N) Space O(1)
# class ListNode:
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
# sentinel
sentinel = ListNode(0, head)
# predecessor = the last node
# before the sublist of duplicates
pred = sentinel
while head:
# if it's a beginning of duplicates sublist
# skip all duplicates
if head.next and head.val == head.next.val:
# move till the end of duplicates sublist
while head.next and head.val == head.next.val:
head = head.next
# skip all duplicates
pred.next = head.next
# otherwise, move predecessor
else:
pred = pred.next #!!直接向后移一位
# move forward
head = head.next
return sentinel.next
- Kth Missing Positive Number
Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.
Find the kth positive integer that is missing from this array.
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,…]. The 5th missing positive integer is 9.
Constraints: 1 <= arr.length <= 1000 1 <= arr[i] <= 1000 1 <= k <= 1000 arr[i] < arr[j] for 1 <= i < j <= arr.length
Approach 1 : Linear search, time O(n)
def findKthPositive(self, arr: List[int], k: int) -> int:
num = 1
i = 0
while k:
if (i- Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
（做了很多遍依然记不住最优解...）
Sliding Window 使用i，j记录start，end；set记录已有的字字母
time O(2n) = O(n), space O(min(m,n)) window size is upper bounded by n (the size of s) and m (the size of the charset/alphabet)
def lengthOfLongestSubstring(self, s: str) -> int:
window = set()
ans = 0
i, j, n = 0, 0, len(s)
while (i- Check If Two String Arrays are Equivalent
Given two string arrays word1 and word2, return true if the two arrays represent the same string, and false otherwise.
A string is represented by an array if the array elements concatenated in order forms the string.
Input: word1 = [“ab”, “c”], word2 = [“a”, “bc”]
Output: true
Explanation:
word1 represents string “ab” + “c” -> “abc”
word2 represents string “a” + “bc” -> “abc”
The strings are the same, so return true.
1) simple solution, time O(m+n) space O(m+n)
‘‘.join(word1) == ‘‘.join(word2)
2) use a generator to “yield” individual characters, space O(1)
def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
for c1, c2 in zip(self.gen(word1), self.gen(word2)):
if c1 != c2:
return False
return True
def gen(self, word: List[str]):
for s in word:
for c in s:
yield c
# Ensure False when len(word1) != len(word2)
yield None
- Merge Sorted Array
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Two pointers / Start from the end
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
l = len(nums1)-1
m, n = m-1, n-1
while m>=0 and n>=0:
if nums1[m]>=nums2[n]:
nums1[l] = nums1[m]
m -= 1
l -= 1
else:
nums1[l] = nums2[n]
n -= 1
l -= 1
if m>=0:
nums1[:l+1] = nums1[:m+1]
if n>=0:
nums1[:l+1] = nums2[:n+1]- Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Time complexity : O(max(m,n)).
Space complexity : O(max(m,n)) returned new list
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = cur = ListNode(0)
carry = 0
while l1 or l2 or carry:
if l1:
carry+=l1.val
l1=l1.next
if l2:
carry+=l2.val
l2=l2.next
cur.next = ListNode(carry%10)
cur = cur.next
carry = carry//10
return dummy.next
