class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        result = []
        for i in range(numRows):
            now = [1]*(i+1)
            if i >= 2:
                for n in range(1,i):
                    now[n] = pre[n-1]+pre[n]
            result += [now]
            pre = now
        return result

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False

        sum -= root.val
        if not root.left and not root.right:  # if reach a leaf
            return sum == 0
        return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root: 
            return 0 

        children = [root.left, root.right]
        # if we're at leaf node
        if not any(children):
            return 1

        min_depth = float('inf')
        for c in children:
            if c:
                min_depth = min(self.minDepth(c), min_depth)
        return min_depth + 1 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
        # 自顶向下递归计算子树的高度
    def height(self, root: TreeNode) -> int:
        # 空树返回 -1
        if not root:
            return -1
        return 1 + max(self.height(root.left), self.height(root.right))

    def isBalanced(self, root: TreeNode) -> bool:
        # 空树也是平衡二叉树
        if not root:
            return True

        # 递归验证左子树高度和右子树高度之差的绝对值是否小于2
        # 同时左子树和右子树必须都为平衡二叉树
        return abs(self.height(root.left) - self.height(root.right)) < 2 \
            and self.isBalanced(root.left) \
            and self.isBalanced(root.right)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if not nums:
            return
        mid=len(nums)//2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        return root

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        stack = [root]
        res = []
        while stack:
            temp = []
            for i in range(len(stack)):
                cur = stack.pop(0)
                temp.append(cur.val)
                if cur.left:
                    stack.append(cur.left)
                if cur.right:
                    stack.append(cur.right)
            res.append(temp)
        return res[::-1]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None: 
            return 0 
        else: 
            left_height = self.maxDepth(root.left) 
            right_height = self.maxDepth(root.right) 
            return max(left_height, right_height) + 1 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def childTreeIsSymmetric(self, p, q):
        # 递归结束条件：
        # 1. 两个节点都为空
        # 2. 一个为空，另一个非空
        # 3. 都为非空，但是值不相等
        # 4. 都为非空，但是值相等（再次进入递归）
        if not p or not q:
            # 条件12
            return p == q
            # 条件1返回True，条件2返回False
        if p.val != q.val:
            return False
            # 条件3
        # 条件4
        return self.childTreeIsSymmetric(p.left, q.right) & self.childTreeIsSymmetric(p.right, q.left)

    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        else:
            return self.childTreeIsSymmetric(root.left, root.right)

最简单的策略是使用递归。首先判断 p 和 q 是不是 None，然后判断它们的值是否相等。 若以上判断通过，则递归对子结点做同样操作。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # p and q are both None
        if not p and not q:
            return True
        # one of p and q is None
        if not q or not p:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.right, q.right) and \
               self.isSameTree(p.left, q.left)

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums1[m:m+n] = nums2
        nums1.sort()
        return nums1

这是一个简单的问题，仅测试你操作列表的结点指针的能力。由于输入的列表已排序，因此我们可以通过将结点的值与它之后的结点进行比较来确定它是否为重复结点。如果它是重复的，我们更改当前结点的 next 指针，以便它跳过下一个结点并直接指向下一个结点之后的结点。

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        cur = head
        while cur and cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

第 n 个台阶只能从第 n-1 或者 n-2 个上来。到第 n-1 个台阶的走法 + 第 n-2 个台阶的走法 = 到第 n 个台阶的走法，已经知道了第 1 个和第 2 个台阶的走法，一路加上去。 斐波那契作业：明作业 = 今作业 + 昨作业。

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <=2: return n
        a, b = 1, 2
        for i in range(3, n+1):
            c = a + b
            a, b = b, c
        return c

牛顿迭代法

在迭代过程中，以直线代替曲线，用一阶泰勒展式（即在当前点的切线）代替原曲线，求直线与 xx 轴的交点，重复这个过程直到收敛。

知乎问答

class Solution:
    def mySqrt(self, x: int) -> int:
        if x <= 1:
            return x

        r = x
        while r > x /r:
            r = ( r + x / r ) // 2
        return int(r)

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return bin(int(a, 2) + int(b,2))[2:]

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        c = ''
        for i in digits:
            c += str(i)
        b = str(int(c) + 1)
        res = []
        for i in range(len(b)):
            res.append(int(b[i]))
        return res

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        if not s: return 0
        return len(s.strip(' ').split(' ')[-1])  ## 去掉尾部的空格在分隔字符串

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 定义索引最大和全局最大
        curr_sum = max_sum = nums[0]

        for i in range(1, len(nums)):
            curr_sum = max(nums[i], curr_sum + nums[i])  # 计算索引最大
            print(max_sum, curr_sum)
            max_sum = max(max_sum, curr_sum)  # 计算全局最大

        return max_sum  # 返回全局最大

class Solution:
    def countAndSay(self, n: int) -> str:
        # 直接返回第一个1
        if n == 1: return '1'
        # 指定第一个的数
        res = '1'
        # 从2 开始到n循环,依次计算描述
        for i in range(2, n+1):
            ans = '' # 保存当前数的描述
            j = 0 # 定义索引
            while j < len(res): # 循环当前数的长度
                k = j
                while k < len(res)-1 and res[k] == res[k+1]: # 计算连续的数字
                    k+=1
                ans += str(k+1-j)+res[k] # 拼接
                j = k+1
            res = ans # 赋值当前数的描述
        return res

再次解释下

1. 给一个数，这个数是 1
2. 描述上一步的数，这个数是 1 即一个 1，故写作 11
3. 描述上一步的数，这个数是 11 即两个 1，故写作 21
4. 描述上一步的数，这个数是 21 即一个 2 一个 1，故写作 12-11
5. 描述上一步的数，这个数是 1211 即一个 1 一个 2 两个 1，故写作 11-12-21

按照我理解的，给出下面脚本。

domain="test.com qingcdn.com trpcdn.net bsgslb.cn bsclink.cn bsgslb.com bsccdn.com baishan-cloud.net dolfindns.net solocdn.cn baishan
cdnx.cn baishancdnx.com azchcdnb.com ctxcdn.cn cdn.miguvideo.com qn.qnydns.com zllxyun.cn bc.yuancdn.com vendor1.iqiyi.router7.com"

file="gwbn-yd"

data=$(awk -F'"' '{print $2}' $file | sort | uniq)

for i in $domain; do
   if [[ $data =~ $i ]]
   then
      echo "加过: $i"
   else
      echo "没加过: $i"
   fi
done

你看看符合不。

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # target 在nums列表中,返回其索引
        if target in nums:
            return nums.index(target)
        else:
            # 不在时，追加进列表并排序，返回其索引
            nums.append(target)
            nums.sort()
            return nums.index(target)

使用字符串方法

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:

        if  bool(needle)==False:
            return 0
        return haystack.find(needle)

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
            if not needle: return 0
            i = 0
            l = len(needle)
            while needle in haystack:
                # 通过字符串切片对比,正确返回索引值
                if haystack[i:l] == needle:
                    return i
                else:
                    i += 1
                    l += 1
            return -1

双指针解法

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        # 定义慢指针
        m = 0
        for k in range(len(nums)):
            # 快指针不等于val时，将快指针的值指向慢指针，同时慢指针向后移位
            if (nums[k] != val):
                nums[m] = nums[k]
                m +=1
        return m

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        while val in nums:
            # val等于当前索引的值时,将删除这个值，并且将索引向前移位，否则向后移一位
            if nums[i] == val:
                nums.pop(i)
                if i > 1: i -= 1
            else:
                i += 1
        return len(nums)