Sort

Algorithms
array

Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element from unsorted part and putting it at the beginning.

  • Time : O(n^2), as there are two nested loops
  • Space : O(1) (In-place)
1
2
3
4
5
6
7
8
def selectionSort(nums):
    n = len(nums)
    for i in xrange(n):
        minIndex = i
        for j in xrange(i, n):
            if nums[j] < nums[minIndex]:
                minIndex = j
        nums[i], nums[minIndex] = nums[minIndex], nums[i]

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

  • Time : O(n^2), Best Case : O(n)
  • Space : O(1)
    1
    2
    3
    4
    5
    6
    def bubbleSort(nums):
        for i in xrange(len(nums)):
            for j in xrange(len(nums)-i-1):
                if nums[j] > nums[j+1]:
                    nums[j+1], nums[j] = nums[j], nums[j+1]
        return nums

Insertion Sort

  • Time : O(n^2), Best Case : O(n) when the elements are already sorted!
  • Space : O(1)
1
2
3
4
5
6
7
8
def insertionSort(nums):
    for i, num in enumerate(nums):
        j = i
        while j > 0 and nums[j-1] > num:
            nums[j] = nums[j-1]
            j -= 1
        nums[j] = num
    return nums

Merge sort

It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.

  • Time : O(nlogn)
  • Space : O(n)

88. Merge Sorted Array

Merge Two Sorted Array in Merge Sort Algorithms

  • Three Pointers: nums1, nums2 and results
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        p1, p2 = m-1, n-1
        idx = m+n-1
        while p1 >= 0 and p2 >= 0:
            if nums2[p2] > nums1[p1]:
                nums1[idx] = nums2[p2]
                p2 -= 1
            else:
                nums1[idx] = nums1[p1]
                p1 -= 1
            idx -= 1

        while p2 >= 0:
            nums1[idx] = nums2[p2]
            p2 -= 1
            idx -= 1

Merge k sorted array

  • Time : O(nlogk)
  1. sol1: Iterative way (Brute Force)
  2. sol2: Binary Reduction (Divide and Conquer)
  • if very large,so data in disk : read and write logk times
  1. sol3: k pointers smallest element(Heap)
  • if very large,so data in disk : read and write only 1 time

Counting Inversions

  • based on merge sort, count all the inversion paris!

Quick Sort

It picks an element as pivot and partitions the given array around the picked pivot.

  • The key process in quickSort is partition().
    Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def partition(nums, l, r):
    pivot = nums[r] # pick last element as pivot
    low = l
    for i in xrange(l, r):
        if nums[i] < pivot:
            nums[i], nums[low] = nums[low], nums[i]
            low += 1
    nums[low], nums[r] = nums[r], nums[low]
    return low

def quickSort(nums, l, r):
    if l >= r:
        return

    pivot = partition(nums, l, r)
    quickSort(nums, l, pivot-1)
    quickSort(nums, pivot+1, r)

215. Kth Largest Element in an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def findKthLargest(self, nums, k):
        l, r = 0, len(nums)-1
        while l <= r:
            idx = self.partition(nums, l, r)
            if idx > k-1:
                r = idx - 1
            elif idx < k-1:
                l = idx + 1
            else:
                return nums[idx]

    # Similar to Move Zeros!
    def partition(self, nums, l, r):
        if l >= r: return l

        pivot = nums[r]
        low = l
        for i in xrange(l, r):
            if nums[i] > pivot:
                nums[i], nums[low] = nums[low], nums[i]
                low += 1
        nums[low], nums[r] = nums[r], nums[low]
        return low

LintCode 80. Median

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
class Solution:
    """
    @param nums: A list of integers
    @return: An integer denotes the middle number of the array
    """
    def median(self, nums):
        n = len(nums)
        k = (n + 1) // 2 - 1 # index we want to find
        left, right = 0, len(nums)-1
        while left <= right:
            idx = self.partition(nums, left, right)
            if idx == k:
                break
            elif idx < k:
                left = idx + 1
            else:
                right = idx - 1

        return nums[k]

    def partition(self, nums, left, right):
        pivot = nums[right]
        low = left
        for i in range(left, right):
            if nums[i] < pivot:
                nums[i], nums[low] = nums[low], nums[i]
                low += 1
        nums[low], nums[right] = nums[right], nums[low]
        return low

283. Move Zeroes

Maintaining the relative order of the non-zero elements.

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def moveZeroes(self, nums):
        non0 = 0
        n = len(nums)
        for i in xrange(n):
            if nums[i] != 0:
                nums[non0] = nums[i]
                non0 += 1
        for i in xrange(non0, n):
            nums[i] = 0
1
2
3
4
5
6
7
8
class Solution(object):
    def moveZeroes(self, nums):
        non0 = 0
        n = len(nums)
        for i in xrange(n):
            if nums[i] != 0:
                nums[non0], nums[i] = nums[i], nums[non0]
                non0 += 1

Follow up : order can be changed

The order of all other elments can be changed.

  • left and right pointer swap each number, it could change the order, but it reduces the operation number!
  • this method actually is similar to the partition function in Quick Sort!!!
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
class Solution(object):
    def moveZeroes(self, nums):
        left, right = 0, len(nums)-1
        while left < right:
            while left < right and nums[left] != 0:
                left += 1
            while left < right and nums[right] == 0:
                right -= 1
            nums[left], nums[right] = nums[right], nums[left]
            print("operation")
            left += 1
            right -= 1

# Simplified Version
class Solution(object):
    def moveZeroes(self, nums):
        left, right = 0, len(nums)-1
        while left < right:
            if nums[left] != 0:
                left += 1
            elif nums[right] == 0:
                right -= 1
            else:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

Rainbow Sort

75. Sort Colors

Sol1. Counting Sort

two-pass algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
# Time : O(n)
# Space : O(n)
class Solution(object):
    def sortColors(self, nums):
        cnt = collections.defaultdict(int)
        for num in nums:
            cnt[num] += 1

        p = 0
        for i in xrange(3):
            for _ in xrange(cnt[i]):
                nums[p] = i
                p += 1

Sol2. Dutch Partitioning Problem

one-pass algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def sortColors(self, nums):
        l, r = 0, len(nums)-1
        i = 0
        while i <= r:
            if nums[i] == 0:
                nums[l], nums[i] = nums[i], nums[l]
                l += 1
                i += 1 # missing part
            elif nums[i] == 1:
                i += 1
            else:
                nums[i], nums[r] = nums[r], nums[i]
                r -= 1

Wiggle Sort

280. Wiggle Sort

Solution1. Sort

  • Time : O(nlogn)
    1
    2
    3
    4
    5
    class Solution(object):
        def wiggleSort(self, nums):
            nums.sort()
            for i in range(2, len(nums), 2):
                nums[i], nums[i-1] = nums[i-1], nums[i]

Solution2. One Pass

  • Time : O(n)
    1
    2
    3
    4
    5
    class Solution(object):
        def wiggleSort(self, nums):
            for i in range(1, len(nums)):
                if (i % 2 == 0 and nums[i] > nums[i-1]) or (i % 2 == 1 and nums[i] < nums[i-1]):
                    nums[i], nums[i-1] = nums[i-1], nums[i]

324. Wiggle Sort II

1
2
3
4
5
6
7
8
class Solution(object):
    def wiggleSort(self, nums):
        temp = sorted(nums)
        n = len(nums)
        for i in range(1, n, 2):
            nums[i] = temp.pop()
        for i in range(0, n, 2):
            nums[i] = temp.pop()

Big data

Sort with small memory

Given a single computer with a single CPU and a single core, which has 2GB of memory and 1GB available for use, it also has two 100GB hard drives. How to sort 80GB integers of 64bits.?

  • External Sort
  1. 400 chunks. Use 1GB memory to sort each 0.2GB. => write to disk
  2. 400-way merge
    chunk1 xxxxxx xxxxxxxxxxxxxxx
    chunk2 yyyyyy yyyyyyyyyyyyyyy
    …
    chunk400 zzzzzz zzzzzzzzzzzzzzz
    read from each chunk, block by block, insert into a min Heap.
  3. result block
  • Why read one block by block instead of one by one? File IO!!!
Share

pramp

Algorithms

Communication

  • diagram

small talk

  • How are you? Im doing great!
  • Thank you for the interview!
  • Have a good night! / Have a nice day!

interviewer

  • can you hear me?
  • can i assume that … ?
  • walk through a small example / some test cases
  • It looks good for me / Sounds good!
  • Im not sure why you … ?
  • in the line …
  • can you analyze the time and space complexity?
  • the question said that …
  • there are some typo in your code
  • clarify your idea
  • I will be the interviewer fist
  • make sense / make no sense
  • on the right track
  • you get the point!
  • you can use either BFS or DFS
  • Go ahead!

interviewee

  • Let me give you a small example
  • double check my code
  • write some test cases to test my funciton
  • as we can see
  • analyze different cases first
  • Lets say … variable …
  • Can you share a small example for me?
  • make sure that i understand the question!

Tree

  • can we assume that class node has parent pointer?

Sales Path

  • Find the minimal sum cost from root to leaf in a Tree (Not necessarily binary)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    # Time : O(n), Space : O(n)
    def get_cheapest_cost(rootNode):
      if not rootNode.children:
        return rootNode.cost

      minCost = float('inf')
      for child in rootNode.children:
        minCost = min(minCost, get_cheapest_cost(child))
      return minCost + rootNode.cost

  • follow up:
    TODO

In a Binary Search Tree (BST), an Inorder Successor of a node is defined as the node with the smallest key greater than the key of the input node (see examples below).

Given a node inputNode in a BST, you’re asked to write a function findInOrderSuccessor that returns the Inorder Successor of inputNode. If inputNode has no Inorder Successor, return null.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def find_in_order_successor(self, inputNode):
  if not inputNode:
    return None

  if not inputNode.right: # dose not have right subtree
    parent = inputNode.parent
    if not parent: # root node
      return None
    while parent:
      if parent.key > inputNode.key:
        return parent
      parent = parent.parent
    return None
  else:# have right subree
    cur = inputNode.right
    while cur.left:
      cur = cur.left
    return cur

  1. Case1 : inputNode has a right child. In this case successorNode would be the node with the minimum key in inputNode’s right subtree.

  2. Case2: inputNode doesn’t have a right child. In this case successorNode would be one of inputNode’s ancestors. More specifically, within inputNode’s ancestor chain (starting from inputNode all the way up to the root), successorNode is the first parent that has a left child in that chain.

Other

H-Tree Construction

Write a function drawHTree that constructs an H-tree, given its center (x and y coordinates), a starting length, and depth. Assume that the starting line is parallel to the X-axis.

  • Use the function drawLine provided to implement your algorithm. In a production code, a drawLine function would render a real line between two points. However, this is not a real production environment, so to make things easier, implement drawLine such that it simply prints its arguments (the print format is left to your discretion).

  • Analyze the time and space complexity of your algorithm. In your analysis, assume that drawLine’s time and space complexities are constant, i.e. O(1).

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
            1
   1     1     1     1
1 1 1 1  

import math
def drawLine(p1, p2):
  # draw line

# Time : O(4^depth)
# Space : O(depth)  
def drawHTree(x, y, length, depth):
    if depth == 0:
      return

    # horizontal segment "-"
    x1 = x - length / 2
    x2 = x + length / 2
    drawLine((x1, y), (x2, y))

    # left & right vertical segment '|'
    y1 = y - length / 2
    y2 = y + length / 2
    drawLine((x1, y1), (x1, y2))
    drawLine((x2, y1), (x2, y2))

    # Recursion
    new_len = length / math.sqrt(2)
    drawHTree((x1, y1), new_length, depth - 1)
    drawHTree((x1, y2), new_length, depth - 1)
    drawHTree((x2, y1), new_length, depth - 1)
    drawHTree((x2, y2), new_length, depth - 1)

Getting a Different Number

Given an array arr of unique nonnegative integers, implement a function getDifferentNumber that finds the smallest nonnegative integer that is NOT in the array.

1
2
3
4
5
6
7
8
# Time : O(n)
# Space : O(n)
def get_different_number(arr):
  n = len(arr)
  arr_set = set(arr)
  for i in xrange(n+1):
    if i not in arr_set:
      return i

Array Index & Element Equality

Given a sorted array arr of distinct integers, write a function indexEqualsValueSearch that returns the lowest index i for which arr[i] == i. Return -1 if there is no such index.

  • Binary Search
  • Edge case
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Time : O(logn)
# Space : O(1)
def index_equals_value_search(arr):
  if not arr:
    return -1

  start, end = 0, len(arr)-1
  while start < end:
    mid = start + (end - start) // 2
    if arr[mid] == mid:
      end = mid
    elif arr[mid] > mid:
      end = mid - 1
    else:
      start = mid + 1

  # post processing
  if arr[start] == start:
    return start
  else:
    return -1

Number of Paths

Given n, the size of the grid’s axes, write a function numOfPathsToDest that returns the number of the possible paths the driverless car can take.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def num_of_paths_to_dest(n):
  # Init dp
  #dp = [[0] * n for _ in xrange(n)]
  dp = [1] * n

  # calculate the number
  for i in xrange(1, n):
    for j in xrange(i+1, n):
      dp[j] += dp[j-1]

  return dp[-1]

def test():
  print(num_of_paths_to_dest(4))

test()

# Time : O(n^2) Space : O(n^2)
# Improved Space : O(n)

Explanation

Since the car can only move up and move down, when it arrives at a point, there are two possibilities:

  1. It arrives at the point from below cell (move up to the point)
  2. It arrives at the point from left cell (move right to the point)

Sentence Reverse

  • Solution1. python built-in function

    1
    2
    3
    4
    5
    6
    # Time : O(n), Spacce : O(n)
    def reverse_words1(arr):
      string = ''.join(arr)
      chs = string.split()
      res = ' '.join(chs[::-1])
      return list(res)

  • Solution2. Reverse Twice

  • First: reverse all the word!
    I love google -> I evol elgoog
  • Second: reverse the string character by charater
    I evol elgoog -> google love I
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Space O(n) -> O(1)
def reverse_words(arr):

  # First Reverse
  start = 0
  for i in xrange(len(arr)+1):
    if i == len(arr) or arr[i] == ' ': # condition
      end = i - 1
      while start < end:
        arr[start], arr[end] = arr[end], arr[start]
        start += 1
        end -= 1
      start = i + 1

  # Second Reverse
  start, end = 0, len(arr)-1
  while start < end:
    arr[start], arr[end] = arr[end], arr[start]
    start += 1
    end -= 1
  return arr

Matrix Spiral Copy

Given a 2D array (matrix) inputMatrix of integers, create a function spiralCopy that copies inputMatrix’s values into a 1D array in a spiral order, clockwise. Your function then should return that array. Analyze the time and space complexities of your solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def spiralOrder(self, matrix):
        if not matrix:
            return []

        m, n = len(matrix), len(matrix[0])
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        k = 0
        visited = set()
        x = y = 0
        res = []
        while len(res) < m * n:
            res.append(matrix[x][y])
            visited.add((x, y))

            dx, dy = directions[k]
            nx, ny = x+dx, y+dy
            if (nx, ny) not in visited and 0 <= nx <= m-1 and 0 <= ny <= n-1:
                x, y = nx, ny
            else: # need to change direction
                k = (k + 1) % 4
                dx, dy = directions[k]
                x, y = x+dx, y+dy
        return res
Share

Buy and Sell Stock

Algorithms
dp, topic

121. Best Time to Buy and Sell Stock

  • Complete at most one transaction
  • We can get max profit when we buy on the lowest price and sell on the highest price!
  • we need to find $max(prices[j] - prices[i])$, for every i and j such that j > ij>i.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution(object):
        def maxProfit(self, prices):
            if not prices:
                return 0

            minp = prices[0]
            maxProfit = 0
            for i in xrange(1, len(prices)):
                minp = min(minp, prices[i])
                maxProfit = max(maxProfit, prices[i] - minp)
            return maxProfit

122. Best Time to Buy and Sell Stock II

  • Complete as many transactions as you like
  • Greedy Algorithms
1
2
3
4
5
6
7
class Solution(object):
    def maxProfit(self, prices):
        res = 0
        for i in xrange(1, len(prices)):
            if prices[i] > prices[i-1]:
                res += prices[i]-prices[i-1]
        return res

122. Best Time to Buy and Sell Stock III

  • Complete at most two transactions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def maxProfit(self, prices):
        n = len(prices)
        if n <= 0: return 0

        left = [0] * n
        minp = prices[0]
        for i in xrange(1, len(prices)):
            minp = min(minp, prices[i])
            left[i] = max(left[i-1], prices[i] - minp)

        maxp = prices[-1]
        right = [0] * (n)
        res = 0
        for i in xrange(len(prices)-2, -1, -1):
            maxp = max(maxp, prices[i])
            right[i] = max(maxp - prices[i], right[i+1])
            res = max(res, right[i] + (left[i-1] if i > 1 else 0))
        return res

188. Best Time to Buy and Sell Stock IV

  • Complete at most k transactions
  • Watch Out: when k > n/2, you can use greedy algorithm from II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maxProfit(self, k, prices):
        if not prices or k == 0:
            return 0

        n = len(prices)
        if k > n // 2:
            return self.helper(prices)

        glob  = [[0] * (k+1) for _ in range(n)]
        local = [[0] * (k+1) for _ in range(n)]
        for i in range(1, n):
            diff = prices[i] - prices[i-1]
            for j in range(1, k+1):
                local[i][j] = max(glob[i-1][j-1], local[i-1][j]) + diff
                glob[i][j] = max(glob[i-1][j], local[i][j])
        return glob[-1][-1]


    def helper(self, prices):
        res = 0
        for i in range(1, len(prices)):
            res += max(0, prices[i] - prices[i-1])
        return res
  • Why do we need local and global two dp states?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maxProfit(self, k, prices):
        if not prices or k == 0:
            return 0

        n = len(prices)
        if k > n // 2:
            return self.helper(prices)

        hold  = [[0] * (k+1) for _ in range(n)]
        unhold = [[0] * (k+1) for _ in range(n)]

        hold[0][0] = -prices[0]
        for i in range(1, n):
            hold[i][0] = max(hold[i-1][0], -prices[i])

        for i in range(k+1):
            hold[0][i] = -prices[0]

        for i in range(1, n):
            for j in range(1, k+1):
                hold[i][j] = max(hold[i-1][j], unhold[i-1][j]-prices[i])
                unhold[i][j] = max(unhold[i-1][j], hold[i-1][j-1]+prices[i])
        return unhold[-1][-1]

309. Best Time to Buy and Sell Stock with Cooldown

  • The natural states for this problem is the 3 possible transactions : buy, sell, rest. Here rest means no transaction on that day (aka cooldown).
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxProfit(self, prices):
        if not prices:
            return 0

        n = len(prices)
        buy = [0] * n
        sell = [0] * n
        buy[0] = -prices[0]
        for i in range(1, n):
            buy[i] = max(buy[i-1], (sell[i-2] if i > 1 else 0) - prices[i])
            sell[i] = max(sell[i-1], buy[i-1] + prices[i])
        return sell[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxProfit(self, prices):
        if not prices:
            return 0

        n = len(prices)
        buy = -prices[0]
        prev_sell = sell = 0
        for i in range(1, n):
            prev_buy = buy
            buy = max(buy, prev_sell - prices[i])
            prev_sell = sell
            sell = max(sell, buy + prices[i])
        return sell

714. Best Time to Buy and Sell Stock with Transaction Fee

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxProfit(self, prices, fee):
        if not prices:
            return 0

        n = len(prices)
        sell = [0] * n
        buy = [0] * n
        buy[0] = -prices[0]
        for i in range(1, n):
            buy[i] = max(buy[i-1], sell[i-1]-prices[i])
            sell[i] = max(sell[i-1], buy[i-1]+prices[i]-fee)
        return sell[-1]

Summary

States Definition

  • Then the transaction sequences can end with any of these three states.
    For each of them we make an array, buy[n], sell[n] and rest[n].
  1. buy[i] means before day i what is the maxProfit for any sequence end with buy.
  2. sell[i] means before day i what is the maxProfit for any sequence end with sell.
  3. rest[i] means before day i what is the maxProfit for any sequence end with rest.
  • Hold and Unhold
  1. hold[i] means before day i what is the maxProfit for any sequence end with holding stock.
  2. unhold[i] means before day i what is the matProfit for any sequence end with unholding stock.

Induction Rule

TODO

Space Improving

TODO

Share

Binary Search Tree

Algorithms
tree

Binary Search Tree: for every single node in the tree, the values in its left subtree are all smaller than its value, and the values in its right subtree are all larger than its value.

  • any(left_substree) < root.val < any(right_subtree)
  • for every sigle node in the tree
  • for normal BST, we do not consider equal!

Validation

You have to know the definition of BST and how to use recursion to do validation!

98. Validate Binary Search Tree

Sol1. Primitive Idea

Time : O(n * h)
for each node,

  • check all its left-subtree, to determine whether they all smaller,
  • check all its right-subtree, to determine wheter they are all larger.

Sol2. Range

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Time : O(n), Space : O(h)
class Solution(object):
    def isValidBST(self, root):
        return self.helper(root, -float('inf'), float('inf'))

    def helper(self, root, tmin, tmax):
        if not root:
            return True

        # BST 是不能有等于的！
        if root.val >= tmax or root.val <= tmin:
            return False

        return (self.helper(root.left, tmin, root.val)
            and self.helper(root.right, root.val, tmax))

Sol3. Inorder Traversal

BST Inorder traversal you will get an strictly increasing array!**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Time : O(n), Space : O(n)
class Solution(object):
    def isValidBST(self, root):
        res = []
        self.dfs(root, res)

        for i in xrange(len(res)-1):
            if res[i+1] <= res[i]:
                return False
        return True

    def dfs(self, root, res):
        if not root:
            return

        self.dfs(root.left, res)
        res.append(root.val)
        self.dfs(root.right, res)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Time : O(n), Space : O(h)
class Solution(object):
    def isValidBST(self, root):
        self.prev = None
        self.is_bst = True
        self.dfs(root)
        return self.is_bst

    def dfs(self, root):
        if not root:
            return

        self.dfs(root.left)
        if self.prev is not None and root.val <= self.prev:
            self.is_bst = False
            return
        self.prev = root.val
        self.dfs(root.right)

Insert & Delete

701. Insert into a Binary Search Tree

1
2
3
4
5
6
7
8
9
10
# Time : O(height), Space : O(height)
class Solution(object):
    def insertIntoBST(self, root, val):
        if not root:
            return TreeNode(val)
        if val > root.val:
            root.right = self.insertIntoBST(root.right, val)
        else:
            root.left = self.insertIntoBST(root.left, val)
        return root

450. Delete Node in a BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def deleteNode(self, root, key):
        if not root:
            return None

        if key > root.val:
            root.right = self.deleteNode(root.right, key)
        elif key < root.val:
            root.left = self.deleteNode(root.left, key)
        else:
            if not root.left and not root.right:
                return None
            elif not root.left or not root.right:
                return root.left if root.left else root.right
            else:
                # Trick Point : swap the largest number in its left subree with current node
                # then we recursion delete the new val in its subtree
                cur = root.right
                while cur.left:
                    cur = cur.left
                root.val = cur.val
                root.right = self.deleteNode(root.right, cur.val)
        return root

700. Search in a Binary Search Tree

Totally based on the definition of BST!

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
# Recursion
Time : O(h), Space : O(h)
class Solution(object):
    def searchBST(self, root, val):
        if not root: return None

        if root.val == val: return root
        elif root.val > val:
            return self.searchBST(root.left, val)
        else:
            return self.searchBST(root.right, val)

# Iteration
Time : O(h), Space : O(1)
class Solution(object):
    def searchBST(self, root, val):
        cur = root
        while cur:
            if cur.val == val:
                return cur
            elif cur.val < val:
                cur = cur.right
            else:
                cur = cur.left
        return None

LintCode 11. Search Range in Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def searchRange(self, root, k1, k2):
       self.res = []
       self.dfs(root, k1, k2)
       return self.res

    def dfs(self, root, k1, k2):
        if not root:
            return

        if k1 < root.val:
            self.dfs(root.left, k1, k2)

        if  k1 <= root.val <= k2:
            self.res.append(root.val)

        if root.val < k2:
            self.dfs(root.right, k1, k2)

938. Range Sum of BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def rangeSumBST(self, root, L, R):
        if not root:
            return 0

        if L > root.val:
            return self.rangeSumBST(root.right, L, R)

        if R < root.val:
            return self.rangeSumBST(root.left, L, R)

        left = self.rangeSumBST(root.left, L, R)
        right = self.rangeSumBST(root.right, L, R)
        return left + right + root.val

270. Closest Binary Search Tree Value

  • Binary Search Tree actually seperate ordered list to three part, less than root.val, root.val, more than root.val instead of two part!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def closestValue(self, root, target):
        cur = root
        res = cur.val
        while cur:
            if abs(cur.val - target) < abs(res - target):
                res = cur.val

            if cur.val == target:
                return cur.val
            elif cur.val < target:
                cur = cur.right
            else:
                cur = cur.left
        return res

272. Closest Binary Search Tree Value II

Sol1. Inorder Traversal

  • Time : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def closestKValues(self, root, target, k):
        res = []
        self.dfs(root, res)
        # Two Pointer Shrink
        left, right = 0, len(res)-1
        while right - left + 1 > k:
            if abs(res[left] - target) < abs(res[right] - target):
                right -= 1
            else:
                left += 1
        return res[left:right+1]

    def dfs(self, root, res):
        if not root:
            return
        self.dfs(root.left, res)
        res.append(root.val)
        self.dfs(root.right, res)
  • follow up : Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
  • What if we have parent node?

Sol2. Successor & Predecessor

  • Key point : How to find the Successor and Predecessor in BST
  • Q : for every node in BST,
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
class Solution(object):
    def getPredecessor(self, pre):
        cur = pre.pop()
        cur = cur.left
        while cur:
            pre.append(cur)
            cur = cur.right

    def getSuccessor(self, suc):
        cur = suc.pop()
        cur = cur.right
        while cur:
            suc.append(cur)
            cur = cur.left

    def closestKValues(self, root, target, k):
        pre, suc = [], []

        # Init pre & suc
        cur = root
        while cur:
            if cur.val <= target:
                pre.append(cur)
                cur = cur.right
            else:
                suc.append(cur)
                cur = cur.left


        res = []
        for _ in xrange(k):
            if len(suc) == 0 or (len(pre) > 0 and abs(pre[-1].val - target) < abs(suc[-1].val - target)):
                res.append(pre[-1].val)
                self.getPredecessor(pre)
            else:
                res.append(suc[-1].val)
                self.getSuccessor(suc)
        return res

530. Minimum Absolute Difference in BST

  • Inorder Traversal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def getMinimumDifference(self, root):
        self.res = float('inf')
        self.dfs(root, [-float('inf')])
        return self.res

    def dfs(self, root, prev):
        if not root:
            return

        self.dfs(root.left, prev)
        if prev:
            self.res = min(self.res, root.val - prev[-1])
            prev[-1] = root.val
        self.dfs(root.right, prev)

Build a BST

108. Convert Sorted Array to Binary Search Tree

1
2
3
4
5
6
7
8
9
class Solution(object):
    def sortedArrayToBST(self, nums):
        if not nums:
            return None
        mid = len(nums) / 2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        return root

109. Convert Sorted List to Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def sortedListToBST(self, head):
        if not head:
            return None

        if not head.next:
            return TreeNode(head.val)

        # Find mid
        slow, fast = head, head.next.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        root = TreeNode(slow.next.val)
        nxt = slow.next.next
        slow.next = None
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(nxt)
        return root

Iterator

173. Binary Search Tree Iterator

If we use Two Stack to solve PostOrder Traversal, Problem “Inorder Traversal” is more complexity than other two traversal! Whether it is or not a binary search tree, the solutions are the same!

  • 1 push element to the stack until its left node is none
  • 2 pop a node from the stack, traverse its right subtree
  • Inorder Traversal Seperated two parts!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class BSTIterator(object):
    def __init__(self, root):
        cur = root
        self.stack = []
        while cur:
            self.stack.append(cur)
            cur = cur.left

    def hasNext(self):
        return len(self.stack) > 0

    def next(self):
        node = self.stack.pop()
        cur = node.right
        while cur:
            self.stack.append(cur)
            cur = cur.left
        return node.val
Share

DP - Double Sequence

Algorithms
dp
  • Input Parameters have two Sequences or Strings
  • Two Sequences Matching?

1 Longest

LintCode 79. Longest Common Substring

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def longestCommonSubstring(self, A, B):
        m, n = len(A), len(B)
        dp = [[0] * (n+1) for _ in range(m+1)]
        res = 0
        for i in range(m):
            for j in range(n):
                if A[i] == B[j]:
                    dp[i+1][j+1] = dp[i][j] + 1
                    res = max(res, dp[i+1][j+1])
        return res

LintCode 77. Longest Common Subsequence

  • State : dp[i][j] means Longest Common Subsequence for A[0…i-1] and B[0…j-1]
  • Init : dp[i][0] = dp[0][j] = 0
  • Deduction Formula : 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Time : O(mn), Space : O(mn)
class Solution:
    def longestCommonSubsequence(self, A, B):
        m, n = len(A), len(B)
        if m == 0 or n == 0:
            return 0

        dp = [[0] * (n+1) for _ in xrange(m+1)]
        for i in xrange(1, m+1):
            for j in xrange(1, n+1):
                if A[i-1] == B[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[-1][-1]
  • Space Improvement
    dp[i][j] -> dp[i % 2][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Space : O(n)
class Solution:
    def longestCommonSubsequence(self, A, B):
        m, n = len(A), len(B)
        if m == 0 or n == 0:
            return 0

        dp = [[0] * (n+1) for _ in xrange(2)]
        for i in xrange(1, m+1):
            for j in xrange(1, n+1):
                if A[i-1] == B[j-1]:
                    dp[i % 2][j] = dp[(i-1) % 2][j-1] + 1
                else:
                    dp[i % 2][j] = max(dp[(i-1) % 2][j], dp[i % 2][j-1])
        return dp[m % 2][-1]

2 Exist

10. Regular Expression Matching

  • Case Analysis!!!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution(object):
        def isMatch(self, s, p):
            m, n = len(s), len(p)
            dp = [[False] * (n+1) for _ in range(m+1)]
            dp[0][0] = True
            for i in range(n):
                if p[i] == "*":
                    dp[0][i+1] = dp[0][i-1]

            for i in range(m):
                for j in range(n):
                    if s[i] == p[j] or p[j] == '.':
                        dp[i+1][j+1] = dp[i][j]
                    elif p[j] == '*':
                        dp[i+1][j+1] = dp[i+1][j-1]
                        if p[j-1] == '.' or p[j-1] == s[i]:
                            dp[i+1][j+1] = dp[i+1][j+1] or dp[i][j+1]
            return dp[-1][-1]

97. Interleaving String

  • Three String!!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution(object):
        def isInterleave(self, s1, s2, s3):
            m, n, l = len(s1), len(s2), len(s3)
            if m + n != l:
                return False

            dp = [[False] * (n+1) for _ in range(m+1)]
            dp[0][0] = True
            for i in range(m):
                if s1[i] == s3[i]:
                    dp[i+1][0] = dp[i][0]

            for j in range(n):
                if s2[j] == s3[j]:
                    dp[0][j+1] = dp[0][j]

            for i in range(m):
                for j in range(n):
                    if s3[i+j+1] == s1[i]:
                        dp[i+1][j+1] = dp[i+1][j+1] or dp[i][j+1]
                    if s3[i+j+1] == s2[j]:
                        dp[i+1][j+1] = dp[i+1][j+1] or dp[i+1][j]
            return dp[-1][-1]

3 Count

72. Edit Distance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def minDistance(self, word1, word2):
        m, n = len(word1), len(word2)
        dp = [[0] * (n+1) for _ in xrange(m+1)]

        for i in xrange(m):
            dp[i+1][0] = i+1
        for i in xrange(n):
            dp[0][i+1] = i+1

        for i in xrange(m):
            for j in xrange(n):
                dp[i+1][j+1] = min(dp[i][j+1]+1, dp[i+1][j]+1, dp[i][j] + (word1[i] != word2[j]))
        return dp[-1][-1]

161. One Edit Distance

  • a littel like “Edit Distance”, but totally different solution!!! no dp here!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def isOneEditDistance(self, s, t):
        if len(s) < len(t):
            return self.isOneEditDistance(t, s)

        m, n = len(s), len(t)
        if m - n > 1:
            return False

        if m - n == 1:
            for i in xrange(n):
                if s[i] != t[i]:
                    return s[i+1:] == t[i:]
            return True

        if m == n:
            for i in xrange(m):
                if s[i] != t[i]:
                    return s[i+1:] == t[i+1:]
            return False

801. Minimum Swaps To Make Sequences Increasing

  • State
    swap[i]: The cost of making both sequences increasing up to the first i columns in condition that we swap A[i] and B[i]
    notswap: The cost of making both sequences increasing up to the first i columns in condition that we do not swap A[i] and B[i]
  • Init : swap[0] = 1; notswap[0] = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def minSwap(self, A, B):
        n = len(A)
        swap, notswap = [1001] * n, [1001] * n
        swap[0] = 1
        notswap[0] = 0

        for i in range(1, n):
            # Case 1 : strictly increasing, swap 2 or not
            if A[i-1] < A[i] and B[i-1] < B[i]:
                swap[i] = swap[i-1] + 1
                notswap[i] = notswap[i-1]

            # Case 2 : swap position i-1 or swap position i
            if A[i-1] < B[i] and B[i-1] < A[i]:
                swap[i] = min(swap[i], notswap[i-1] + 1)
                notswap[i] = min(notswap[i], swap[i-1])

        return min(swap[n-1], notswap[n-1])
  • 我总是想记录上一个有没有swap，来record最优解，困于DFS的写法了！
  • 跳开DFS的方式还是定义对DP的State，如果能想到定义两个State一个表示Swap一个表示不Swap，后面思路就很顺了！
Share

Dynamic Programming Overview

Algorithms
dp

Overview

  • Big Name 公司必考，难度中上
  • 题目类型多，没有固定模板

1 问题引入Fibonacci

  • F(n) = F(n-1) + F(n-1)
  • Base Case : F(0) = 0, F(1) = 1
1
2
3
4
public int fibN(int n) {
    if (n == 0 || n == 1) return n; // base case
    return fibN(n-1) + fibN(n-2); // recursice rule
}
1
2
3
4
5
6
7
8
9
10
11
public int fibN(int n) {
    int[] dp = new int[n+1];
    dp[0] = 0; // base case
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
        // dp[2] = dp[0] + dp[1]
        // dp[2] = dp[1] + dp[2];
    }
    return dp[n];
}

2 核心思想

类似于高中学习的数学归纳法

  1. 把一个大问题(size == n)的解决方案用比他小的问题(问题们)来解决，也就是思考从问题size=n-1增加到size=n的时候，如何用小问题的solution构建大问题的solution
  2. 与Recursion的关系
    • Recursion, 从大到小解决问题(自顶至下)，不记录任何sub-solution只考虑Base Case和Recursive Rule
    • DP, 从小到大解决问题(自底至上)，记录sub-solution
  3. 将计算中间结果保存下来，并改变计算顺序！

3 动态规划题目特点

  1. 计数
    • 有多少种方式走到右下角
    • 有多少种发发选出k个数使得和是Sum
  2. 求最大最小值
    • 从左上角走到右下角路径的最大数字和
    • 最长上升子序列长度
  3. 求存在性
    • 取石子游戏，先手是否必胜
    • 能不能选出k个数使得和是Sum

4 动态规划组成部分

  1. 确定状态
    • 解决动态规划的时候往往需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么物理意义(状态)
    • 研究最优策略的最后一步
    • 子问题
  2. 递推公式(转移方程)
    • 根据子问题定义直接得到
  3. 初始条件和边界情况
    • 细心，考虑周期
  4. 计算顺序
    • 利用之前的计算结果
Share

Graph - Topological Sort

Algorithms
graph

Given an directed graph, a topological order of the graph nodes is defined as follow:

  1. For each directed edge A -> B in graph, A must before B in the order list.
  2. The first node in the order can be any node in the graph with no nodes direct to it.
  • 无向图不存在topological sort的问题(无先后关系)
  • 常见topological sort都是用indegree的方法遍历，其实用DFS也可以！
  • key point : 具有依赖关系的任务

LintCode 127. Topological Sorting

  • 解法1. DFS
    • 每次 DFS 得到一个符合正确拓扑顺序的 list，保证单序列顺序；每次新的 DFS 之后得到的 list 要排在之前结果的前面，保证全序列顺序
    • 每次翻转都会改变单序列和全序列之间的顺序，对于每一个单序列或者全序列，两次翻转可以互相抵消
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def topSort(self, graph):
        visited = set()
        ans = []

        for root in graph:
            self.dfs(root, visited, ans)

        return ans[::-1]

    def dfs(self, root, visited, ans):
        if root in visited:
            return

        for nei in root.neighbors:
            if nei not in visited:
                self.dfs(nei, visited, ans)

        visited.add(root)
        ans.append(root)
  • 解法2. BFS
    • step1. 统计每个vertex/node的indegree
    • step2. 从indegree==0开始放入queue，有edge的indegree-1，为0的放入queue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def topSort(self, graph):
        indegree = collections.defaultdict(int)
        for node in graph:
            for nei in node.neighbors:
                indegree[nei] += 1

        queue = collections.deque([])
        for node in graph:
            if node not in indegree:
                queue.append(node)

        res = []
        while queue:
            node = queue.popleft()
            res.append(node)
            for nei in node.neighbors:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

        return res

210. Course Schedule II

首先要检查有没有环，没有环的话才有topological sort的结果！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        indegree = [0] * numCourses
        graph = collections.defaultdict(list)
        for u, v in prerequisites:
            indegree[u] += 1
            graph[v].append(u)

        queue = collections.deque([i for i in xrange(numCourses) if indegree[i] == 0])
        res = []
        while queue:
            node = queue.popleft()
            res.append(node)
            for v in graph[node]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    queue.append(v)
        return res if sum(indegree) == 0 else []

269. Alien Dictionary

  • Build the graph represent the dependency of characters!
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
class Solution(object):
    def alienOrder(self, words):
        indegree = {}
        for word in words:
            for c in word:
                indegree[c] = 0

        graph = [set() for _ in xrange(26)]
        for i in xrange(len(words)-1):
            cur = words[i]
            next = words[i+1]
            for j in xrange(min(len(cur), len(next))):
                if cur[j] != next[j]:
                    if next[j] not in graph[ord(cur[j])-ord('a')]:
                        graph[ord(cur[j])-ord('a')].add(next[j])
                        indegree[next[j]] += 1
                    break

        res = []
        cnt = len(indegree.keys())
        q = collections.deque([c for c in indegree.keys() if indegree[c] == 0])
        while q:
            cur = q.popleft()
            res.append(cur)
            for n in list(graph[ord(cur)-ord('a')]):
                indegree[n] -= 1
                if indegree[n] == 0:
                    q.append(n)
        return ''.join(res) if len(res) == cnt else ""

欧拉通路（Eulerian path

  • 若一个图为欧拉图或半欧拉图都可以通过一笔画遍历。通过图（有向图或无向图）中的所有边且每一条边仅通过一次的通路称为欧拉通路，若此通路为回路则称为欧拉回路
  • 每次深度优先搜索的结果必然是图的一个连通分量。深度优先搜索可以从多点发起。如果将每个节点在深度优先搜索过程中的“结束时间”排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下，将该节点加入list结尾，然后逆转整个链表),则我们可以得到所谓的“拓扑排序”，即topological sort.
Share

Recursion

Algorithms
recursion

What is recursion?

Call Stack :

    1. Global accessible resource
    1. Usage : store the local information for each recursion function

1 Look Like

  • function calls itself

2 In Fact

  • Boil down a big problem to smaller ones(size n depends on size n-1, or n-2 or … n/2); Boil down size=n problem to size=n-1，n-2orn/2 problem

3 How to Implementate

  • 1）Base Case:smallest problem to solve
  • 2）Recursive rule:
    how to make the problem smaller (if we can resolve the same problem but with a smaller size, then what is left to do for the current problem size n)

4 In more details

Recursive Function Signature must keep the same logic

1. Recursion与数学计算的结合

50. Pow(x, n) a^b

  • 数学计算常见陷阱:(Corner Case)
    1) 0 as the denominator
    2) 1/3 as an integer? or float? 精度问题
    3) 0^0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public double power(double a, double b) {
    if (a == 0 && b <= 0) {
        return -1;
    } else if (b < 0) {
        return 1 / (double)pow(a,b);
    } else {
        return (double) pow(a, b);
    }
}

public int pow(int a, int b) {
    if (b == 0) { return 1;}

    int halfResult = pow(a, b/2);
    if (b % 2 == 0){
        return halfResult * halfResult;
    } else {
        return halfResult * halfResult * a;
}
1
2
3
4
5
6
7
8
9
10
# Time : O(logn), Space : O(logn)
class Solution(object):
    def myPow(self, x, n):
        if n < 0:
            return self.myPow(1.0/x, -n)
        elif n == 0:
            return 1

        half = self.myPow(x, n//2)
        return half * half * (1 if n%2 == 0 else x)

2. Recursion与1D or 2D Array的结合

1D Array - Merge Sort, Quick Sort

2D Array

LC51 N-Queens

  • 1 逐层(row by row)递归：8 queen -> n queen

    xQxxxxxx
    xxxQxxxx
    xxQxxxxx
    xxxxxxxx
    xxxxxxxx
    xxxxxxxx
    xxxxxxxx
    xxxxxxQx

    • Recursive rule:
      For the i-th queen on the i-th row, we must make sure the Qi does no conflict with all previous queens that have been placed on the board.
      int Position[N] = {1 2 3 5 …}

    • Base Case: The last row is done, 0 row left

    • Recursive rule: iff position(i,j)valid - >go to the next roe:(i+1)
      Time = O($$8^8$$) -> O(8!)

  • 2 How to print 2D array in spiral order (NxN)
    x x x x x
    x x x x x
    x x x x x
    x x x x x

    Recursive rule:
    size = size - 2
    offset = offset + 1

  • 旋转矩阵！

3. Recursion和LinkedList的结合

  • Q1 Reverse a linked list
  • Q2 Reverse linked list pair by pair

4. Recursion和String的结合

  • Q1 Reverse a String using recursion

    abcd -> dcba

  • Q2 A word such as “book” can be abbreviated to 4, “1o1k”, “b3”, “b2k”, etc. Given a string and an abbreviation, return if the string matches the abbreviation. Assume the original string only contains alphabetic characters.

5. Recursion和Tree的结合

Binary tree 往往是最常见的，和recursion结合最紧密的面试题目类型

  • 树本身就是Recursive的结构！
  • 每层的node具备的性质，传递的值和下一层的性质往往一致。比较容易定义recursive rule
  • Base case(generally):null pointer under the leaf node

Tree + Recursion 第一类问题:从下往上反值(int ,bool,etc.)

* 从下往上反值 - getHeight(Node root)
* 从下往上反值 - 统计tree里每个node的左子树有多少个node？
* 从下往上返值 - Find the node with **max difference** in the total number of descendents in its left subtree and right subtree

【Way of thinking】 (相当于后序遍历)

  • 1.What do you expect from your lchild/rhild?
    (usually it is the return type of the recursion type)
  • 2.What do you want to do in the current layer?
  • 3.What do you want to report to your parent?(same as Q1 == Q3)

####LC236 Lowest Common Ancestor of a Binary Tree
从下往上返值，最最经典例题! LCA

  • Method1

use two additional arrays to buffer the prefix from root to a and from root to b

  • Method2 (Recursion)

    Case1: if a is NOT the ancestor of b

    * 1.1 left == null, right == null, return null
* 1.2 left and right reutrn c
* 1.3 either left or right return NOT null, return not NULL

    Case2: if a is the ancestor of b

    * same thing

Follow Up

  • What if either a or b is not int the tree. Can this method take care of this case? A - It depends on your assumption.
  • Assuming that both a and b are in the tree:
    • case1: result = c (c != a && c != b) it means a and b不直接隶属
    • case2a: result = a (a has a descendent which is b)
    • case2b: result = b (b has a descendent which is a)
Share

Tree Path

Algorithms
tree
  1. Case1: looks like “人” path.
  • We usually return integer value to parent node
  1. Case2: must through the root node

Path

112. Path Sum

  • root to leaf
  • True or False
1
2
3
4
5
6
7
8
9
class Solution(object):
    def hasPathSum(self, root, sum):
        if not root:
            return False

        if not root.left and not root.right:
            return sum == root.val

        return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)

113. Path Sum II

  • root to leaf
  • all results
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def pathSum(self, root, sum):
        res = []
        self.dfs(root, sum, [], res)
        return res

    def dfs(self, root, sum, path, res):
        if not root:
            return

        if not root.left and not root.right:
            if sum == root.val:
                res.append(path+[root.val])
            return

        self.dfs(root.left, sum-root.val, path+[root.val], res)
        self.dfs(root.right,sum-root.val, path+[root.val], res)

437. Path Sum III

  • from any node to any node in the tree (can be the same node)
1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def pathSum(self, root, sum):
        if not root: return 0

        return (self.findPaths(root, sum)
                + self.pathSum(root.left, sum)
                + self.pathSum(root.right, sum))

    def findPaths(self, root, sum):
        if not root:
            return 0
        return (sum == root.val) + self.findPaths(root.left, sum - root.val) + self.findPaths(root.right, sum - root.val)

666. Path Sum IV

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def pathSum(self, nums):
        nodes = {}
        for num in nums:
            nodes[(num/100, num%100/10)] = num%10
        self.res = 0
        self.dfs(1, 1, 0, nodes)
        return self.res

    def dfs(self, d, p, curSum, nodes):
        if (d, p) not in nodes:
            return
        curSum += nodes[(d, p)]
        left, right = (d+1, p*2-1), (d+1, p*2)
        if left not in nodes and right not in nodes:
            self.res += curSum
            return
        self.dfs(left[0], left[1], curSum, nodes)
        self.dfs(right[0], right[1], curSum, nodes)

124. Binary Tree Maximum Path Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def maxPathSum(self, root):
        self.res = -float('inf')
        self.dfs(root)
        return self.res

    def dfs(self, root):
        if not root:
            return 0
        left = max(0, self.dfs(root.left))
        right = max(0, self.dfs(root.right))
        self.res = max(self.res, left+right+root.val)
        return max(left, right) + root.val

Maximum Sum from leaf to leaf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def maxLeafSum(self, root):
        self.res = -float('inf')
        self.dfs(root)
        return self.res

    def dfs(self, root):
        if not root:
            return 0
        left = self.dfs(root.left)
        right = self.dfs(root.right)

        cur = left + right + root.val
        if cur > self.res and (root.left and root.right):
            self.res = cur

        if not root.left:
            return right
        elif not root.right:
            return left
        else:
            return max(left, right) + root.val

Path Sum + Prefix sum

Maximun Sum from any node to any node

Share

Linked List Cycle

Algorithms
linked list
  • 单链表检测是否有环，如果有，返回环交点。
  • 这种题主要考察这个知识点作为一种common sense是否了解了，如果没做过这类题型恐怕很难想到空间最优的快慢指针解法！

141. Linked List Cycle

单链表求是否存在环？

Sol1. HashSet

1
2
3
4
5
6
7
8
9
10
# Time : O(n), Space : O(n)
class Solution(object):
    def hasCycle(self, head):
        visited = set()
        while head:
            if head in visited:
                return True
            visited.add(head)
            head = head.next
        return False

Sol2. 快慢指针

小trick : 如果有环，快指针一定会追上慢指针

1
2
3
4
5
6
7
8
9
10
# Time : O(n), Space : O(1)
class Solution(object):
    def hasCycle(self, head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

142. Linked List Cycle II

单链表是否存在环，如果存在返回环交点

Sol1. HashSet

1
2
3
4
5
6
7
8
9
10
# Time : O(n), Space : O(n)
class Solution(object):
    def detectCycle(self, head):
        visited = set()
        while head:
            if head in visited:
                return head
            visited.add(head)
            head = head.next
        return None

Sol2. 快慢指针

小trick : 关于长度的证明，相遇点到交点的距离=起点到交点的距离！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Time : O(n), Space : O(1)
class Solution(object):
    def detectCycle(self, head):
        if not head: return None
        fast = slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast: # Detect Cycle
                fast = head
                while slow != fast:
                    fast = fast.next
                    slow = slow.next
                return fast
        return None

287. Find the Duplicate Number

  • 解1.HashSet(T:O(n),S:O(n)), 解2. Sort(T:O(nlogn),S:O(1));
  • 但是又要求 Time : O(n), Space : O(1), Input Array Read only，只能考虑其他解法！
  • (比较难想到)Array里index, value中把value当作”next”的index，就可以把问题转化成了Linked List II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Time : O(n), Space : O(1)
class Solution(object):
    def findDuplicate(self, nums):
        if not nums: return 0
        slow = fast = nums[0] # Start from index 0!
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        fast = nums[0]
        while fast != slow:
            fast = nums[fast]
            slow = nums[slow]
        return fast

160. Intersection of Two Linked Lists

Sol1. HashSet

  • 挺喜欢这种解法，简单易懂，but空间复杂度略高，会让你优化空间！
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # Time : O(m+n), Space : O(m)
    class Solution(object):
        def getIntersectionNode(self, headA, headB):
            visited = set()
            while headA:
                visited.add(headA)
                headA = headA.next

            while headB:
                if headB in visited:
                    return headB
                headB = headB.next
            return None

Sol2. Two Pointer

  • 这个解法灰常魔幻，不管有没有intersection都成立
  • 链表走到tail了就去另一个链表，不相交那么会在None点走到
  • 充分利用了两个链表的长度特性
1
2
3
4
5
6
7
8
9
10
11
# Time : O(m+n), Space : O(1)
class Solution(object):
    def getIntersectionNode(self, headA, headB):
        if not headA or not headB:
            return None

        pA, pB = headA, headB
        while pA is not pB:
            pA = pA.next if pA else headB
            pB = pB.next if pB else headA
        return pA
Share