letcode 2-day

https://www.cnblogs.com/liuzhen1995/p/13767751.html

https://github.com/ZLiu21/Algorithm-and-Learning/tree/master/1_%E5%89%91%E6%8C%87Offer

二分查找

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

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(binary_find(a, 10))

栈的压入和弹出序列

class Solution:
    def IsPopOrder(self, pushV, popV):
        stack = []
        index = 0
        while pushV:
            stack.append(pushV.pop(0))
            while stack and stack[-1] == popV[index]:
                stack.pop(-1)
        return not stack

二叉树中和为某一值的路径

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        res = []
        if not root: return res
        self.target = expectNumber
        self.dfs(root, res, [root.val])
        return res

    def dfs(self, root, res, path):
        if not root.left and not root.right and sum(path) == self.target:
            res.append(path)
        if root.left:
            self.dfs(root.left, res, path + [root.left.val])
        if root.right:
            self.dfs(root.right, res, path + [root.right.val])