LeetCode Revision

Question 1

Minstack

Answer 1

Insert 2x - current_min, Pop, check if less than min, then return min and update min to next min. Top, return if not min, else return min.

Question 2

101. Symmetric Tree

Answer 2

Create recursive function. Check if left and right exist and are equal. Then check if the mirrors are equal. Mirrors are left.left and right.right, left.right and right.left

Question 3

198 House robber

Answer 3

Create a DP cache. Keep updating values. First two are, A[0] and max(A[0], A[1]). The repetition formula is if A[n-2] + A[n] > A[n-1] then A[n] = A[n-1] + A[n]

Question 4

234. Palindrome Linked List

Answer 4

Reverse first half of the list. Take 3 pointers, fast, slow, and rev. Increment fast by 2. set rev, rev.next, slow = slow, rev, slow.next, this reverses the linked list.
After reversing if fast is still not null, then there are odd number of elements. If so, increment fast by 1.
Starting from rev, slow which are now both heads of respective lists, keep incrementing and checking for sameness.

Question 5

125. Valid Palindrome

Answer 5

use regular expression to strip the spaces and punctuations and then reverse and compare. This is regular expression: ‘[\W_]+’ and to reverse string you should use str[::-1]

Question 6

190. Reverse Bits

Answer 6

Take 0. Left shift by 1 and or with last bit of n. Then right shift n by one. Repeat for 32 times.

Question 7

108 Convert sorted array to BST

Answer 7

Use recursion to insert middle element.