11/2020 Flashcards
5.Longest Palindromic Substring Given a string s, return the longest palindromic substring in s. Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.
Brute Force
Pick all possible starting and ending positions for a substring, and verify if it is a palindrome.
Time: O(n3); Space: O(1)
Expand Around Center
A palindrome can be expanded from its center, and there are only 2n - 1 such centers (长度奇/偶)
Time: O(n2); O(n) for each center; Space: O(1)
class Solution:
def longestPalindrome(self, s: str) -> str:
result = “”
for i in range(len(s)):
tmp = self.findlongest(s,i,i+1) # ‘baab’
if len(tmp)>len(result): result = tmp
tmp = self.findlongest(s,i,i) # ‘aba’
if len(tmp)>len(result): result = tmp
return result
def findlongest(self,s, l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return s[l+1:r]
200.Number of Islands
Given anm x n2dgridmap of’1’s (land) and’0’s (water), returnthe number of islands.
Recursive (DFS) Linear scan grid，直到找到’1’，对该元素进行DFS During DFS： 将当前元素变为’0’， 继续DFS其周边为’1’的元素 Time: O(mn) Space: worst caseO(mn)
(*) 也可以通过Stack实现DFS / Queue实现BFS
- Moving Average from Data Stream
Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.
MovingAverage m = new MovingAverage(3);
m. next(1) = 1
m. next(10) = (1 + 10) / 2
m. next(3) = (1 + 10 + 3) / 3
m. next(5) = (10 + 3 + 5) / 3
Class variables:
- self.queue => to store the values from the data stream,
- self.n => for the size of the moving window;
Solution 1: Array or List
We first append the value to the queue. We then retrieve the last n values from the queue, in order to calculate the average.
for list-based solution with retrieving last n elements without poping the first:
for each invocation of next(val)
- - Time O(n) with n = window size, since we need to retrieve N elements from the queue at each invocation of next(val) function. （array/list有index，取任一元素的complexity为O(1)， N各元素complexity为O(N))
- - Memory O(M) with M = number of elements in data stream (continuosly growing)
Solution 2:
for deque-based solution with poping the first element:
- - constant time complexity O(1) as we don’t shift all the elements while popping
- memory O(n)
notes: len() has complexity O(1)
不用list.pop(0)因为list when pop(0), copies all elements and moves them on the left for 1 element, very heavy operation in terms of time-complexity;
如果用arraylist储存整个数据流，加上两个变量window_sum和tail，似乎也可以达到time O(1), 但spaceO(M);
若使用arraylist但每次pop(0)，则time为O(N),因为每次都要平移所有elements
- Group Anagrams
Given an array of strings strs, group the anagrams together. You can 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: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
hash table with keys == transformed words
sorted(word) outputs list, use’‘.join(sorted(word)) to return str
或者用tuple(sorted(word))做d.keys: tuple is hashable, but list not
N is the length of strs, K is the maximum length of a string in strs
- hash table with sorted strings as keys:
time : O(NKlogK) = O(N) loop over input * O(KlogK) to sort each word
memo: O(NK)
- counter solution:
time: O(NK)
memo: O(NK)
- Ransom Note
Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.
Each letter in the magazine string can only be used once in your ransom note.
Input: ransomNote = “aa”, magazine = “ab”
Output: false
- hash table of all available letters from magazine (manually or through collections.Counter);
- then iterate through ransom note and substract counter values from hash table if found.
- return False if one of dict values turns to negative or if item from ransom note is not found in magazine keys
m length of magazine, n length of ransom note.
k number of unique characters across ransom note and magazine
Time Complexity : O(m)
code，复杂度为O(m)+O(n),
当m O(m)
当m>n, O(m)+O(n) < O(2m) => O(m)
Space : O(k) （或 O(1) 因为k<26可以当作constant）.
- 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.
=> hash table {element: index} iterate over k,v: if k == target - k -> return val
time: O(n)
memo: O(n)
Project Euler #67: Maximum path sum II
By starting at the top of the triangle below and moving to adjacent numbers on the row below, Find the maximum total from top to bottom of the triangle given in input.
dynamic programming from bottom to top :
Sum each 2 lines looping over shorter line and adding to each element max(2 children).
! convert from str() to int()
def maxPathSum(triangle, numRow):
for i in range(numRow-2, -1, -1):
for j in range(i+1):
triangle[i][j] = max(triangle[i][j]+ triangle[i+1][j], triangle[i][j]+triangle[i+1][j+1])
return triangle[0][0]
- Shuffle an Array
Given an integer array nums, design an algorithm to randomly shuffle the array.
Implement the Solution class:
Solution(int[] nums) Initializes the object with the integer array nums.
int[] reset() Resets the array to its original configuration and returns it.
int[] shuffle() Returns a random shuffling of the array.
class Solution:
def \_\_init\_\_(self, nums):
self.array = nums
self.original = list(nums)
def reset(self):
self.array = self.original
self.original = list(self.original)
return self.array
def shuffle(self):
aux = list(self.array)
for idx in range(len(self.array)):
remove_idx = random.randrange(len(aux))
self.array[idx] = aux.pop(remove_idx)
return self.array
- Search in Rotated Sorted Array
You are given an integer array nums sorted in ascending order, and an integer target.
Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
If target is found in the array return its index, otherwise, return -1.
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
所以直接用二分，O(lg(n))
- 如果是mid，return mid
- 如果mid在绿色线上，就对绿色线进行二分
- 如果mid在红色线上，就对红色线进行二分
- 都没找到，return -1
绿色线 / 红色线 # compare nums[mid] with nums[start] => figure out on with branch # NOT nums[mid] with target!!!! 对每条线二分时，别忘记对nums[start] 和nums[end]取等号 if nums[mid] > target >= nums[start] if nums[mid] < target <= nums[end]
class Solution:
def search(self, nums: List[int], target: int) -> int:
start, end = 0, len(nums)-1
while start + 1 < end: # like this when ends, start is always NEXT TO end
mid = (start + end) // 2
if nums[mid] == target:
return mid
if nums[mid] > nums[start]:
if nums[mid] > target >= nums[start] :
end = mid
else:
start = mid
else:
if nums[mid] < target <= nums[end] :
start = mid
else:
end = mid
if nums[start]==target:
return start
if nums[end]==target:
return end
return -1
- Intersection of Two Arrays
Given two arrays, write a function to compute their intersection.
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
N length of nums1, M length of nums2
NAIVE: iterate along the first array nums1 and to check for each value if this value in nums2
O(n×m) time complexity
SOLUTION 1 : convert both arrays into sets; iterate over the smallest set checking the presence of each element in the larger set
Time :O(n+m), O(n) convert nums1 into set, O(m) convert nums2, and contains/in operations are O(1) in the average case.
Space: O(m+n) in the worst case when all elements in the arrays are different.
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
s1, s2 = set(nums1), set(nums2)
return list(s1 & s2)
SOLUTION 2: sort the two list, and use two pointer to search in the lists to find common elements.
nums1.sort()
nums2.sort()
i = 0
j = 0
res = []
while i < len(nums1) and j < len(nums2):
if nums1[i] < nums2[j]:
i += 1
elif nums1[i] > nums2[j]:
j += 1
else:
same = nums1[i]
# when we find equal element
res.append(same)
while i < len(nums1) and nums1[i] == same:
i += 1
while j < len(nums2) and nums2[j] == same:
j += 1
return res
- Kth Smallest Element in a Sorted Matrix
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8,
return 13.
Approach 0: flatten the matrix
n: number of elements in matrix
Time: flatten O(n), sort O(nLogn) => O(nLogn)
Space: O(n)
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
flat = sorted([x for row in matrix for x in row])
return flat[k-1]
Approach 1: Min-Heap approach
1) Considering each row (or column) an individual list.
2) Take the first element of min(N, K) rows where N represents the number of rows, and add each of these elements (value, row, column) to the min-heap.
3) At each step, remove the minimum element from the heap. The element will tell us which row should be further consumed. ( If the current minimum element was from row r and had a column position c, then the next element to be added to the heap will be (r, c+1))
Loop until we iterate over K elements.
Time: let X=min(K,N), complexity X+Klog(X)
Building a min-heap which takes O(X) time
Heapify K times which takes O( KLogX) time.
Space : O(K), as the Min-Heap stores one row at a time.
import heapq
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
N = len(matrix)
minHeap = []
for r in range(min(k, N)):
# We add triplets of information for each cell
minHeap.append((matrix[r][0], r, 0))
heapq.heapify(minHeap)
while k:
element, r, c = heapq.heappop(minHeap)
if c < N - 1:
heapq.heappush(minHeap, (matrix[r][c+1], r, c+1))
k -= 1
return element
- Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Greedy
- curSum 初始值为0，每遍历一个数字 num，比较 - curSum + num 和 num 中的较大值存入 curSum
然后再把 maxSum 和 curSum 中的较大值存入 maxSum
Time: O(n), Space: O(1)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
cumsum, maxsum = 0, -float(inf)
for i in range(n):
cumsum = max(nums[i], nums[i]+cumsum)
maxsum = max(maxsum, cumsum)
return maxsum
21.Merge Two Sorted Lists
Merge two sorted linked lists and return it as a newsortedlist. The new list should be made by splicing together the nodes of the first two lists.
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
tmp = ListNode(0)
cur = tmp
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
if l1:
cur.next = l1
if l2:
cur.next = l2
return tmp.next
20.Valid Parentheses
Given a stringscontaining just the characters’(‘,’)’,’{‘,’}’,’[‘and’]’, determine if the input string is valid.
Approach 1: Stacks
# In the end, the stack should be empty
Time: O(n)
Space: O(n)
class Solution:
def isValid(self, s: str) -> bool:
d = {'(':')','{':'}','[':']'}
stack = []
for x in s:
if x in d.keys():
stack.append(x)
else:
if not stack:
return False
tmp = stack.pop()
if x != d[tmp]:
return False
# In the end, the stack should be empty
if not stack:
return True
return False
121.Best Time to Buy and Sell Stock
Say you have an array for which theithelement is the price of a given stock on dayi.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
找到此前中最小的一个与当前相减，之后取最大的差值
Time: O(n)
Space: O(1)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
pmin = prices[0]
globmax = 0
for p in prices:
if p
