Find saddle point

1
2
3
4
5
count = 0
for i in xrange(1, len(A)-1):
    for j in xrange(1, len(A[0])-1):
        if A[i][j] is saddle_point:
            count+=1

DFS

Find the maximum distinct nodes along the binary tree path.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a  binary tree node
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
def helper(T, prefix, max):
    if T == None:
        return max
    # leaf node
    if T.left is None and T.right is None:
        if len(set(prefix))> max:
            max = len(set(prefix))
    	prefix.pop()
  
    prefix.append(T.x)    
    helper(T.left, prefix)
    helper(T.right, prefix)
def solution(T):
    prefix = []
    max = 0
    helper(T, prefix, max)

Greedy

Monkey 过河 Ais the river, D is the step for one jump

A[i] = t means the stone in the i position is available at time t

A[i] = -1means i position will never have stone.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(A, D):
    pos = -1  #start position
	N = len(A)
    t = 0
    while t < max(A):
        old_pos = pos
        # one step jump over the river
        if (pos+D)>=N:
            break
        while pos < N:
          if A[pos+D]<t and A[pos+D]!=-1: #有石头可以跳
              pos+=D
          if pos == old_pos: #没跳
              break
        t+=1
    return t