博客

1.回溯算法

第77题.组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        res=[]
        path=[]
        def back(idx):
            if len(path)==k:
                res.append(path[:])
                return
            for i in range(idx,n+1):
                path.append(i)
                back(i+1)
                path.pop()
        back(1)
        return res

216.组合总和III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9

每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        res=[]
        path=[]
        def back(idx):
            if len(path)==k and sum(path)==n:
                res.append(path[:])
                return
            if len(path)>k or sum(path)>n:
                return
            for i in range(idx,10):
                path.append(i)
                back(i+1)
                path.pop()
        back(1)
        return res

17.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        d = [" ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
        res=[]
        def dfs(tmp,index):
            if index==len(digits):
                res.append(tmp)
                return
            for i in d[int(digits[index])]:#第一次层遍历的和第二层遍历的区别,每次for循环是不同的层数
                dfs(tmp+i,index+1)
        dfs('',0)
        return res

2.二叉树

144.二叉树的前序遍历

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        arr=[]
        def pre(root):
            if not root:
                return
            arr.append(root.val)
            pre(root.left)
            pre(root.right)
        pre(root)
        return arr
        

102.二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res=[]
        if not root:
            return res
        arr=[root]
        while arr:
            n=len(arr)
            tmp=[]
            for i in range(n):
                data=arr.pop(0)
                tmp.append(data.val)
                if data.left:
                    arr.append(data.left)
                if data.right:
                    arr.append(data.right)
            res.append(tmp)
        return res

226.翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return
        root.left,root.right=root.right,root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root       

101.对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return
        def compare(left,right):
            if not left and not right:return True
            if left and not right:return False
            if right and not left:return False
            if left.val !=right.val:
                return False
            return compare(left.left,right.right) and compare(left.right,right.left)
        return compare(root.left,root.right)

104.二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1   

3.贪心算法

455.分发饼干

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        #贪心算法
        g.sort()
        s.sort()
        ans=0
        for i in s:
            for j in g:
                if i>=j:
                    g.pop(0)
                    ans+=1
                    break
                continue
        return ans