Deck 4 Flashcards
(22 cards)
Climbing stairs
Algorithm:
-Init dp array of length n
-if i is 0, dp[0] is 1
-else if i is 1, dp[1] is 2
-else, dp[i] = dp[i - 1] + dp[i - 2]
-end else if
-return dp[n - 1]
House robber
Algorithm:
-init rob1 and rob2 as 0
-for i in range(n)
-temp = max(rob1 + nums[i], rob2)
-rob1 = rob2
-rob2 = temp
-end for
return rob2
House robber 2
Idea:
We run the house robber 1 for the array without the first element and the array without the last element. And then return the maximum
Algorithm:
-define helper function of house robber 1
-return max(nums[0], helper(nums[1:]), helper(nums[:-1])) ……(nums[0] to handle the case where we only have array of size 1)
Palindromic substrings
Idea:
Same as the longest palindromic substring problem, but instead of storing the max result, we increment the count
Algorithm:
-define helper function to calculate the number of palindromic substrings within the given string with left and right as the params, and return the number of palindromic substrings from it
-init result as 0
-for i in range(len(s))
-result += helperfunc(i, i) …… (for odd length strings)
-result += helperfunc(i, i + 1) …… (for even length strings)
-end for
-return result
Decode ways
Algorithm:
-init cache = { len(s): 1 }
-for i in range len(s) - 1 to 0
-if s[i] is 0, cache[i] = 0
-else cache[i] = cache[i + 1]
-end if else
-if i + 1 in bound AND (s[i] is “1” OR (s[i] is 2 AND s[i + 1] is in “0123456”))
-cache[i] += cache[i + 2]
-end if
-end for
-return cache[0]
Coin change
Idea:
For each coin, decode ways is 1 + amount - coin
Algorithm:
-initialize dp array of length amount + 1 with the same amount + 1 values
-dp[0] = 0
-for i from 1 to amount
-for each coin c
-if i - c >= 0
-dp[i] = min of itself and (1 + dp[i - c])
-end if
-end for
-end for
-return dp[amount] if dp[amount] not default value else return -1
Maximum product subarray
Algorithm:
-init answer as max(nums)
-init curr_max and curr_min both as 1
-for every number in nums
-if number is 0
-reassign curr_max and curr_min to 1
-continue
-end if
-temp = curr_max * number
-curr_max = max(curr_max * number, curr_min * number, number)
-curr_min = min(temp, curr_min * number, number)
-answer = max(answer, curr_max)
-end for
-return answer
Word break
Algorithm:
-init n as len(s)
-init dp array of Falses of length n + 1 and assign dp[n] as True
-for i from n - 1 to 0
-for every word in wordDict
-if dp[i]
-return True
-end if
-if (i + len(word)) <= n and s[i : i + len(word)] is word
-dp[i] = dp[i + len(word)]
-end if
-end for
-end for
-return dp[0]
Unique paths
Idea:
Store the number of unique paths for each cell in the grid
Algorithm:
-init dp array of m*n with all 0s
-for i in range m
-for j in range n
-if i is 0 or j is 0
-dp[i][j] = 0
-else dp[i][j] += dp[i - 1][j] + dp[i][j - 1]
-end else if
-end for
-end for
-return dp[m - 1][n - 1]
Longest common subsequence
Idea:
Create a p matrix and store the longest sequence length up until that point
Algorithm:
-initialize m and n as length of text1 and text2 respectively
-create dp array of 0s of dimensions (m + 1) * (n + 1)
-for i in range 1 to m
-for j in range 1 to n
-if text1[i - 1] == text2[j - 1]
-dp[i][j] = 1 + dp[i - 1][j - 1]
-else
-dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
-end if else
-end for
-end for
-return dp[m][n]
Maximum subarray
Idea:
We use sliding window type approach. Once the current sum becomes -be, we reset the start of window to current one
-Algorithm:
-init curr_sum as 0 and max_sum as nums[0]
-for every number in nums
-if curr_sum < 0, curr_sum = 0
-end if
-curr_sum += number
-max_sum = max(max_sum, curr_sum)
-end for
-return max_sum
Insert interval
Idea:
Iterate through the intervals and add wherever it fits
Algorithm:
-init answer as empty list
-for every interval i
-if new end < i start, append new interval and return answer + intervals[i:]
-elif new start > i end, append interval i
-else
new interval = [min(new start, i start), max(new end, i end)]
-end if else
-end for
-append new to answer
-return answer
Non overlapping intervals
Idea:
Keep track of the end and increment count based on the minimum end value if the intervals overlap
Algorithm:
-init answer as 0 and prev_end as intervals[0][1]
-for every start, end of interval after 1st
-if start >= prev_end
-prev_end = end
-else
-answer++
-prev_end = min(prev_end, end)
-end if else
-end for
-return answer
Meeting rooms
Algorithm:
-intervals.sort()
-for every interval after first
-if current interval start < prev interval end
-return False
-end if
-end for
-return True
Meeting rooms 2
Idea:
Store the start and end times in seperate array and sort them
And based on which is smaller, increment count for number of meetings currently going on
Algorithm:
-start = sorted([i[0] for i in intervals])
-end = sorted([i[1] for i in intervals])
-init answer, count, s and e to 0
-while s < length
-if start[s] < end[e]
-inc s and count
-else
-inc e and dec count
-end if else
-answer = max(answer, count)
-end while
-return answer
Rotate image
Idea:
Set the l, r, top and bottom boundaries and swap the elements
Algorithm:
-set l and r to 0 and length of matrix - 1 respectively
-while l < r
-for i in range (r - l):
-declare top and bottom are same as l and r respectively
-top_left = matrix[top][l + i]
-matrix[top][l + i] = matrix[bottom - i][l]
-matrix[bottom - i][l] = matrix[bottom][r - i]
-matrix[bottom][r - i] = matrix[top + i][r]
-matrix[top + i][r] = top_left
-end for
-inc l and dec r
-end while
Spiral matrix
Idea:
Set the l, r, t, b boundaries and iterate through the edges one by one
We set bottom and r boundaries outside the bounds
Algorithm:
-declare empty answer array
-declare l and r as 0 and len(matrix[0]) respectively
-declare top and bottom as 0 and len(matrix) respectively
-while l < r and top < bottom:
-for i between (l, r)
-append matrix[top][i]
-top += 1
-end for
-for i between (top, bottom)
-append matrix[i][r - 1]
-r -= 1
-end for
-if not (l < r and top < bottom)
-break
-end if
-for i between (r - 1, l - 1, -1)
-append matrix[bottom - 1][i]
-bottom -= 1
-end for
-for i between (bottom - 1, top - 1, -1)
-append matrix[i][l]
-l += 1
-end for
-end while
-return answer
Set matrix zeroes
Idea:
Store whether the row or column needs to be zeroed in a boolean array
Algorithm:
-declare m and n
-declare rows and cols array as [False] * m and [False] * n respectively
-iterate through matrix
-if [i][j] is 0, set rows[i] and cols[j] to True
-end iterate
-iterate though matrix
-if rows[i] or cols[j]
-set [i][j] to 0
-end if
-end iterate
Number of 1 bits
Idea:
Either you mod by 2 until number isn’t zero
Another way, in binary terms, n - 1 has the rightmost 1 replaced by zero and all the other bits to the right as 1. So logic ANDing the two eliminates one 1.
e.g. 100000 - 1 = 011111
Algorithm:
-init answer as 0
-while n
-n = n & (n - 1)
-answer += 1
-end while
-return answer
Counting bits
Idea:
Look at the pattern of bits. Once the power of 2 is obtained, the number of bits is 1 + the previous combination
Algorithm:
-init answer array of size n + 1 with 0s
-init offset as 1
-for i in range(1, n + 1)
-if i == offset * 2,
-offset = i
-end if
-answer[i] = 1 + answer[i - offset]
-end for
-return answer
Reverse bits
Idea:
One way to extract LSB is to & the number with 1. Same way, we can shift the number to extract other bits. Then we can shit this bit to left and then| with 0 or answer
Algorithm:
-init answer as 0
-for i in range(32)
-bit = (n»_space; i) & 1
-answer = answer | (bit «_space;(31 - i))
-end for
-return answer
Missing number
Idea:
Either using sum of n integers formula or
just keep xoring the i and nums[i] and the number at the end is the missing number(xor the two same values results in 0)
Algorithm:
-init answer as n
-for i in range(n)
-answer ^= i ^ nums[i]
-end for
-return answer
