茉莉Python

voidqueens@hotmail.com

0%

面试题 04.10. 检查子树

链接:https://leetcode-cn.com/problems/check-subtree-lcci/

检查子树。你有两棵非常大的二叉树:T1,有几万个节点;T2,有几万个节点。设计一个算法,判断 T2 是否为 T1 的子树。

如果 T1 有这么一个节点 n,其子树与 T2 一模一样,则 T2 为 T1 的子树,也就是说,从节点 n 处把树砍断,得到的树与 T2 完全相同。

示例1:

 输入:t1 = [1, 2, 3], t2 = [2]
 输出:true
示例2:

 输入:t1 = [1, null, 2, 4], t2 = [3, 2]
 输出:false
提示:

树的节点数目范围为[0, 20000]。

题解一|递归:

一:在 t1 中找到 t2 的起点。先判断 t1 当前节点,如果不对就判断 t1 左子树和 t1 右子树。
二:从找到的起点开始判断剩下的点,t1 和 t2 同步左右子树搜索。
class Solution:
    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:

        def helper(t1,t2):
            if not t2:
                return True
            elif not t1 and t2:
                return False
            elif t1.val != t2.val:
                return False
            else:
                return helper(t1.left,t2.left) and helper(t1.right,t2.right)

        if not  t1:
            return False
        if not t2:
            return True
        return helper(t1,t2) or self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)
class Solution:
    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:
        if not  t1:
            return False
        if not t2:
            return True
        return self.helper(t1,t2) or self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)

    def helper(self,t1,t2):
        if not t2:
            return True
        elif not t1 and t2:
            return False
        elif t1.val != t2.val:
            return False
        else:
            return self.helper(t1.left,t2.left) and self.helper(t1.right,t2.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 isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not A or not B:
            return False
        return self.helper(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)

    def helper(self,A,B):
        if not A and B:
            return False
        elif not B:
            return True
        elif A.val != B.val:
            return False
        else:
            return self.helper(A.left,B.left) and self.helper(A.right,B.right)
class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        def helper(A,B):
            if not B:
                return True
            if not A or (A.val != B.val):
                return False
            return helper(A.left,B.left) and helper(A.right,B.right)
        return bool(A and B) and (helper(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))

面试题 17.12. BiNode

链接:https://leetcode-cn.com/problems/binode-lcci/

二叉树数据结构TreeNode可用来表示单向链表(其中left置空,right为下一个链表节点)。实现一个方法,把二叉搜索树转换为单向链表,要求值的顺序保持不变,转换操作应是原址的,也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

注意:本题相对原题稍作改动

示例:

输入: [4,2,5,1,3,null,6,0]
输出: [0,null,1,null,2,null,3,null,4,null,5,null,6]
提示:

节点数量不会超过 100000。

题解一|迭代|中序遍历:

root.left=None
pre.right=root
pre=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 convertBiNode(self, root: TreeNode) -> TreeNode:
        head=TreeNode(0)
        pre=head
        stack=[]
        while stack or root:
            if root:
                stack.append(root)
                root=root.left
            else:
                root=stack.pop()

                root.left=None
                pre.right=root
                pre=root

                root=root.right
        return head.right

题解二|递归:

class Solution:
    def convertBiNode(self, root: TreeNode) -> TreeNode:
        head=TreeNode(0)
        self.helper(root,head)
        return head.right

    def helper(self,root,pre):
        if root:
            pre=self.helper(root.left,pre)
            root.left=None
            pre.right=root
            pre=root
            pre=self.helper(root.right,pre)
        return pre
class Solution:
    def convertBiNode(self, root: TreeNode) -> TreeNode:
        head=TreeNode(0)
        self.pre=head
        self.helper(root)
        return head.right

    def helper(self,root):
        if not root:
            return
        self.helper(root.left)

        root.left=None
        self.pre.right=root
        self.pre=root

        self.helper(root.right)

面试题 04.12. 求和路径

链接:https://leetcode-cn.com/problems/paths-with-sum-lcci/

给定一棵二叉树,其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法,打印节点数值总和等于某个给定值的所有路径的数量。注意,路径不一定非得从二叉树的根节点或叶节点开始或结束,但是其方向必须向下(只能从父节点指向子节点方向)。

示例:
给定如下二叉树,以及目标和 sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

3
解释:和为 22 的路径有:[5,4,11,2], [5,8,4,5], [4,11,7]
提示:

节点总数 <= 10000

题解一|递归:

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

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        if not root:
            return 0
        return self.helper(root,sum)+self.pathSum(root.left,sum)+self.pathSum(root.right,sum)

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

面试题54. 二叉搜索树的第k大节点

链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

给定一棵二叉搜索树,请找出其中第k大的节点。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4
示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4

限制:

1 ≤ k ≤ 二叉搜索树元素个数

注意:和二叉搜索树的第k小节点的区别。

题解一|迭代:

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

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        if not root:
            return 0
        stack=[]
        while stack or root:
            if root:
                stack.append(root)
                root=root.right
            else:
                root=stack.pop()
                k-=1
                if k==0:
                    return root.val
                root=root.left

题解二|递归:

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

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        self.k=k
        self.res=0
        self.helper(root)
        return self.res
    def helper(self,root):
        if not root:
            return 0
        self.helper(root.right)
        if self.k==0: return # ??提高性能,提前返回。
        self.k-=1        
        if self.k==0:
            self.res=root.val # 直接return不行,需要存入全局变量中
        self.helper(root.left)
        return self.res
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        self.k=k
        self.res=0
        self.helper(root)
        return self.res
    def helper(self,root):
        if not root or self.k == 0:
            return 0
        self.helper(root.right)
        self.k-=1        
        if self.k==0:
            self.res=root.val # 直接return不行,需要存入全局变量中
        self.helper(root.left)
        return self.res

面试题55 - I. 二叉树的深度

链接:https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/

输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。

例如:

给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

提示:节点总数 <= 10000

题解一|递归:

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

题解二|迭代:

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        stack=[root]
        depth=0
        while stack:
            tmp=[]
            for i in range(len(stack)):
                root=stack.pop()
                if root.left:
                    tmp.append(root.left)
                if root.right:
                    tmp.append(root.right)
            stack=tmp
            depth+=1
        return depth
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        stack=[root]
        depth=0
        while stack:
            tmp=[]
            for root in stack:
                if root.left:
                    tmp.append(root.left)
                if root.right:
                    tmp.append(root.right)
            stack=tmp
            depth+=1
        return depth

面试题55 - II. 平衡二叉树

链接:https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。

限制:1 <= 树的结点个数 <= 10000

题解一(递归):

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True
        return abs(self.helper(root.left)-self.helper(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)

    def helper(self,root):
        if not root:
            return 0
        left=self.helper(root.left)
        right=self.helper(root.right)
        return max(left,right)+1

面试题68 - I. 二叉搜索树的最近公共祖先

链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。


说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

最近公共祖先(最近公共节点):

根据题目给定的前提:

    所有节点的值都是唯一的。
    p、q 为不同节点且均存在于给定的二叉搜索树中。

说明有以下几种情况:

    二叉树本身为空,root == null ,return root
    p.val == q.val ,一个节点也可以是它自己的祖先
    p.val 和 q.val 都小于 root.val
    (两个子节点的值都小于根节点的值,说明它们的公共节点只能在二叉树的左子树寻找)
    p.val 和 q.val 都大于 root.val
    (两个子节点的值都大于根节点的值,说明它们的公共节点只能在二叉树的右子树寻找)
    如果上述的情况皆不满足,说明其公共节点既不在左子树也不在右子树上,只能为最顶端的公共节点,return root
    p.val < root.val && q.val > root.val 或 p.val > root.val && q.val < root.val

题解一|递归:

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # if not root:
        #     return
        if root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right,p,q)
        elif root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left,p,q)
        return root

题解二|后序遍历:

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root==p or root==q:
            return root
        l=self.lowestCommonAncestor(root.left,p,q)
        r=self.lowestCommonAncestor(root.right,p,q)
        if not l:
            return r
        elif not r:
            return l
        else:
            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 lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            if root.val < p.val and root.val < q.val:
                root=root.right
            elif root.val > p.val and root.val > q.val:
                root=root.left
            else:
                break
        return root

面试题68 - II. 二叉树的最近公共祖先

链接:https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。


说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

题解一(后序遍历):

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

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if not root or root==p or root==q:
            return root
        l=self.lowestCommonAncestor(root.left,p,q)
        r=self.lowestCommonAncestor(root.right,p,q)
        if not l:
            return r
        elif not r:
            return l
        else:
            return root
class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if not root or root == p or root == q: return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left and not right: return # 1.
        if not left: return right # 3.
        if not right: return left # 4.
        return root # 2. if left and right:

参考:https://segmentfault.com/a/1190000003914228

一、Manacher

Manacher用来在字符串中求最长回文串。

二、代码

def manacher(s):
    s='#'+'#'.join(s)+'#'

    RL=[0]*len(s)
    maxRight=0
    pos=0
    maxLen=0

    for i in range(len(s)):
        if i<MaxRight:
            RL[i]=min(RL[2*pos-i], MaxRight-i)·
        else:
            RL[i]=1
        #尝试扩展,注意处理边界
        while i-RL[i]>=0 and i+RL[i]<len(s) and s[i-RL[i]]==s[i+RL[i]]:
            RL[i]+=1
        #更新MaxRight,pos
        if RL[i]+i-1>MaxRight:
            MaxRight=RL[i]+i-1
            pos=i
        #更新最长回文串的长度
        maxLen=max(maxLen, RL[i])
    return maxLen-1

参考:
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
https://www.bilibili.com/video/BV1jb411V78H?from=search&seid=3722651774629068033
https://www.bilibili.com/video/BV1Px411z7Yo?from=search&seid=3722651774629068033
https://www.bilibili.com/video/BV1hW411a7ys?from=search&seid=3722651774629068033
https://www.cnblogs.com/dahu-daqing/p/9302668.html

一、KMP

KMP算法,又称模式匹配算法,能够在线性时间内判定字符串 T 是否为 S 的子串,并求出字符串 T 在 S 中各次出现的位置。

二、代码

1、解决奇偶数问题
    在原字符串的每个相邻两个字符中间插入一个分隔符,同时在首尾也添加分隔符,如何#
2、字符串观察
    s:aaaba
    t:#a#a#a#b#a#
    回文半径数组:RL

    RL[i]-1等于回文串的长度

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/manacher.jpg

时间复杂度:O(m+n)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @contact: voidqueens@hotmail.com
# @software: PyCharm
# @time: 2020/4/26 下午6:50
# @site: www.gongyanli.com
# @file: kmp.py

def getNext(p):
    '''
    p为模式串
    返回next数组,即部分匹配表,使用p字符的前缀和后缀计算得到。
    等同于从模式字符串的第1位(注意,不包括第0位)开始对自身进行匹配运算。
    :param p:
    :return:
    '''
    next = [0] * len(p)
    next[0] = -1
    i = 0
    j = -1
    while i < len(p) - 1:
        if j == -1 or p[i] == p[j]: # i遍历的是数组下标,j则为next赋值
            i += 1
            j += 1
            next[i] = j
        else:
            j = next[j]
    return next


def kmp(s, p):
    '''
    s为主串
    p为模式串
    如果t里有p,返回打头下标
    :param s:
    :param p:
    :return:
    '''
    next = getNext(p)
    i = j = 0
    while i < len(s) and j < len(p):
        if j == -1 or s[i] == p[j]: 
            i += 1
            j += 1
        else:
            j = next[j]
    if j == len(p):
        return i - j
    else:
        return -1


s = 'ababababca'
p = 'abababca'
print(getNext(p))
print(kmp(s, p))

三、中心扩散–验证回文串

中心扩散主要用于验证字符串是否是回文串。

思路:

    每个字母当成回文串的中心
    考虑两种情况:回文串的长度为奇数或者偶数情况。

缺点:
    奇数和偶数需要分开讨论
    没有充分利用前面查找的结果
    没有思考回文字符本身的特性--对称性
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n=len(s)
        self.res=''
        def helper(i,j):
            while i>= 0 and j<n and s[i]==s[j]:
                i-=1
                j+=1
            if len(self.res) < j-i-1:
                self.res=s[i+1:j]
                # print(i,self.res)

        for i in range(n):
            helper(i,i)
            helper(i,i+1) # 解决case为"cbbd",即解决回文串为偶数的情况
        return self.res

https://www.cnblogs.com/wanghui-garcia/p/10775859.html

https://www.cnblogs.com/wanghui-garcia/p/10775859.html
https://blog.csdn.net/Haiqiang1995/article/details/90300686
https://medium.com/@pkqiang49/%E4%B8%80%E6%96%87%E7%9C%8B%E6%87%82%E5%8D%B7%E7%A7%AF%E7%A5%9E%E7%BB%8F%E7%BD%91%E7%BB%9C-cnn-%E5%9F%BA%E6%9C%AC%E5%8E%9F%E7%90%86-%E7%8B%AC%E7%89%B9%E4%BB%B7%E5%80%BC-%E5%AE%9E%E9%99%85%E5%BA%94%E7%94%A8-6047fb2add35

https://blog.csdn.net/r1254/article/details/104888502

https://blog.csdn.net/dyk4ever/article/details/102841518
https://blog.csdn.net/weixin_44307764/article/details/102353344
https://blog.csdn.net/yz2zcx/article/details/100187471/

https://www.jianshu.com/p/a2b536945e3c
https://blog.csdn.net/lzy2014/article/details/25916235
https://yq.aliyun.com/articles/373368
https://www.cnblogs.com/luxiaoxun/archive/2012/11/10/2764056.html
https://www.cnblogs.com/fzz9/p/8973315.html
https://www.jianshu.com/p/6f9d99f7ad54
https://blog.csdn.net/weixin_42042680/article/details/80994726

1、卷积运算函数

torch.nn.Conv2d的功能是:对由多个输入平面组成的输入信号进行二维卷积。

layer = nn.Conv2d(in_channels=1,out_channels=3,kernel_size=3,stride=1,padding=0)

in_channels:
    1)输入通道数,对于图片层一般为1(灰度)3(RGB)
    2)定义一种输入规则,要求上一层的输出必须和这个输入一致,也可以理解为并发in_channels个channel在上一层feature_map(特征映射)上进行卷积运算

out_channels:
    1)直观理解是输出层通道数,              
    2)换一种理解是kernels(卷积核)个数,其中,每个卷积核会输出局部特征,比如面部中有头发feature,衣服颜色的feature都是由不同的kernel进行卷积运算得到的。

stride(步长):控制cross-correlation的步长,可以设为1个int型数或者一个(int, int)型的tuple。

padding(补0):控制zero-padding的数目。

dilation(扩张):控制kernel点(卷积核点)的间距; 也被称为 "à trous"算法. 可以在此github地址查看:Dilated convolution animations

groups(卷积核个数):这个比较好理解,通常来说,卷积个数唯一,但是对某些情况,可以设置范围在1 —— in_channels中数目的卷积核:

输出[b,out_channels,w,h],其中w和h是输出的shape.
    mylayer=torch.nn.Conv2d(3,2,kernel_size=3,stride=2,padding=0)
    print(l1.weight.shape)
    input=torch.rand(1,3,7,7)
    out=l1.forward(input)
    print(out.shape)
-----------------------------------------------
    torch.Size([2, 3, 3, 3])
    torch.Size([1, 2, 3, 3])

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/cnn1.gif

1、padding的方式:

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/padding.jpeg

说明:

1、摘录自http://stackoverflow.com/questions/37674306/what-is-the-difference-between-same-and-valid-padding-in-tf-nn-max-pool-of-t

2、不同的padding方式,VALID是采用丢弃的方式,比如上述的input_width=13,只允许滑动2次,多余的元素全部丢掉

3、SAME的方式,采用的是补全的方式,对于上述的情况,允许滑动3次,但是需要补3个元素,左奇右偶,在左边补一个0,右边补2个0

4、For the SAME padding, the output height and width are computed as:

out_height = ceil(float(in_height) / float(strides[1]))

out_width = ceil(float(in_width) / float(strides[2]))

For the VALID padding, the output height and width are computed as:

out_height = ceil(float(in_height - filter_height + 1) / float(strides[1]))

out_width = ceil(float(in_width - filter_width + 1) / float(strides[2]))

2、conv2d的参数:

1、strides[0] = strides[3] = 1

3、conv2d的参数解释:

tf.nn.conv2d(input, filter, strides, padding, use_cudnn_on_gpu=None, name=None)
除去name参数用以指定该操作的name,与方法有关的一共五个参数:

第一个参数input:指需要做卷积的输入图像,它要求是一个Tensor,具有[batch, in_height, in_width, in_channels]这样的shape,具体含义是[训练时一个batch的图片数量, 图片高度, 图片宽度, 图像通道数],注意这是一个4维的Tensor,要求类型为float32和float64其中之一

第二个参数filter:相当于CNN中的卷积核,它要求是一个Tensor,具有[filter_height, filter_width, in_channels, out_channels]这样的shape,具体含义是[卷积核的高度,卷积核的宽度,图像通道数,卷积核个数],要求类型与参数input相同,filter的通道数要求与input的in_channels一致,有一个地方需要注意,第三维in_channels,就是参数input的第四维

第三个参数strides:卷积时在图像每一维的步长,这是一个一维的向量,长度4,strides[0]=strides[3]=1

第四个参数padding:string类型的量,只能是”SAME”,”VALID”其中之一,这个值决定了不同的卷积方式(后面会介绍)

第五个参数:use_cudnn_on_gpu:bool类型,是否使用cudnn加速,默认为true

结果返回一个Tensor,这个输出,就是我们常说的feature map

4、conv2d的例子:

那么TensorFlow的卷积具体是怎样实现的呢,用一些例子去解释它:

import tensorflow as tf
#case 2
input = tf.Variable(tf.random_normal([1,3,3,5]))
filter = tf.Variable(tf.random_normal([1,1,5,1]))
op = tf.nn.conv2d(input, filter, strides=[1, 1, 1, 1], padding=’VALID’)

with tf.Session() as sess:
sess.run(tf.initialize_all_variables())
res = (sess.run(op))
print (res.shape)

import tensorflow as tf

input = tf.Variable(tf.random_normal([1,5,5,5]))
filter = tf.Variable(tf.random_normal([3,3,5,1]))
op = tf.nn.conv2d(input, filter, strides=[1, 1, 1, 1], padding=’VALID’)

with tf.Session() as sess:
sess.run(tf.initialize_all_variables())
res = (sess.run(op))
print (res.shape)

说明:

1、使用VALID方式,feature map的尺寸为
out_height = ceil(float(in_height - filter_height + 1) / float(strides[1]))=(5-3+1)/1 = 3

out_width = ceil(float(in_width - filter_width + 1) / float(strides[2])) = (5-3+1)/1 = 3

所以,feature map的尺寸为3*3

2、filter的参数个数为3351,也即对于输入的每个通道数都对应于一个33的滤波器,然后共5个通道数,conv2d的过程就是对5个输入进行点击然后求和,得到一张feature map。如果要得到3张feature map,那么应该使用的参数为335*3个参数.

转载于:https://blog.csdn.net/u011995719/article/details/85107009

本文截取自《PyTorch 模型训练实用教程》,获取全文pdf请点击:https://github.com/tensor-yu/PyTorch_Tutorial

本文对transforms.py中的各个预处理方法进行介绍和总结。主要从官方文档中总结而来,官方文档只是将方法陈列,没有归纳总结,顺序很乱,这里总结一共有四大类,方便大家索引:

裁剪——Crop 中心裁剪:transforms.CenterCrop 随机裁剪:transforms.RandomCrop 随机长宽比裁剪:transforms.RandomResizedCrop 上下左右中心裁剪:transforms.FiveCrop 上下左右中心裁剪后翻转,transforms.TenCrop
翻转和旋转——Flip and Rotation 依概率p水平翻转:transforms.RandomHorizontalFlip(p=0.5) 依概率p垂直翻转:transforms.RandomVerticalFlip(p=0.5) 随机旋转:transforms.RandomRotation
图像变换 resize:transforms.Resize 标准化:transforms.Normalize 转为tensor,并归一化至[0-1]:transforms.ToTensor 填充:transforms.Pad 修改亮度、对比度和饱和度:transforms.ColorJitter 转灰度图:transforms.Grayscale 线性变换:transforms.LinearTransformation() 仿射变换:transforms.RandomAffine 依概率p转为灰度图:transforms.RandomGrayscale 将数据转换为PILImage:transforms.ToPILImage transforms.Lambda:Apply a user-defined lambda as a transform.
对transforms操作,使数据增强更灵活 transforms.RandomChoice(transforms), 从给定的一系列transforms中选一个进行操作 transforms.RandomApply(transforms, p=0.5),给一个transform加上概率,依概率进行操作 transforms.RandomOrder,将transforms中的操作随机打乱
一、 裁剪——Crop
1.随机裁剪:transforms.RandomCrop
class torchvision.transforms.RandomCrop(size, padding=None, pad_if_needed=False, fill=0, padding_mode=’constant’) 功能:依据给定的size随机裁剪 参数: size- (sequence or int),若为sequence,则为(h,w),若为int,则(size,size) padding-(sequence or int, optional),此参数是设置填充多少个pixel。 当为int时,图像上下左右均填充int个,例如padding=4,则上下左右均填充4个pixel,若为3232,则会变成4040。 当为sequence时,若有2个数,则第一个数表示左右扩充多少,第二个数表示上下的。当有4个数时,则为左,上,右,下。 fill- (int or tuple) 填充的值是什么(仅当填充模式为constant时有用)。int时,各通道均填充该值,当长度为3的tuple时,表示RGB通道需要填充的值。 padding_mode- 填充模式,这里提供了4种填充模式,1.constant,常量。2.edge 按照图片边缘的像素值来填充。3.reflect,暂不了解。 4. symmetric,暂不了解。

2.中心裁剪:transforms.CenterCrop
class torchvision.transforms.CenterCrop(size) 功能:依据给定的size从中心裁剪 参数: size- (sequence or int),若为sequence,则为(h,w),若为int,则(size,size)

3.随机长宽比裁剪 transforms.RandomResizedCrop
class torchvision.transforms.RandomResizedCrop(size, scale=(0.08, 1.0), ratio=(0.75, 1.3333333333333333), interpolation=2) 功能:随机大小,随机长宽比裁剪原始图片,最后将图片resize到设定好的size 参数: size- 输出的分辨率 scale- 随机crop的大小区间,如scale=(0.08, 1.0),表示随机crop出来的图片会在的0.08倍至1倍之间。 ratio- 随机长宽比设置 interpolation- 插值的方法,默认为双线性插值(PIL.Image.BILINEAR)

4.上下左右中心裁剪:transforms.FiveCrop
class torchvision.transforms.FiveCrop(size) 功能:对图片进行上下左右以及中心裁剪,获得5张图片,返回一个4D-tensor 参数: size- (sequence or int),若为sequence,则为(h,w),若为int,则(size,size)

5.上下左右中心裁剪后翻转: transforms.TenCrop
class torchvision.transforms.TenCrop(size, vertical_flip=False) 功能:对图片进行上下左右以及中心裁剪,然后全部翻转(水平或者垂直),获得10张图片,返回一个4D-tensor。 参数: size- (sequence or int),若为sequence,则为(h,w),若为int,则(size,size) vertical_flip (bool) - 是否垂直翻转,默认为flase,即默认为水平翻转

二、翻转和旋转——Flip and Rotation
6.依概率p水平翻转transforms.RandomHorizontalFlip
class torchvision.transforms.RandomHorizontalFlip(p=0.5) 功能:依据概率p对PIL图片进行水平翻转 参数: p- 概率,默认值为0.5

7.依概率p垂直翻转transforms.RandomVerticalFlip
class torchvision.transforms.RandomVerticalFlip(p=0.5) 功能:依据概率p对PIL图片进行垂直翻转 参数: p- 概率,默认值为0.5

8.随机旋转:transforms.RandomRotation
class torchvision.transforms.RandomRotation(degrees, resample=False, expand=False, center=None) 功能:依degrees随机旋转一定角度 参数: degress- (sequence or float or int) ,若为单个数,如 30,则表示在(-30,+30)之间随机旋转 若为sequence,如(30,60),则表示在30-60度之间随机旋转 resample- 重采样方法选择,可选 PIL.Image.NEAREST, PIL.Image.BILINEAR, PIL.Image.BICUBIC,默认为最近邻 expand- ? center- 可选为中心旋转还是左上角旋转

三、图像变换
9.resize:transforms.Resize
class torchvision.transforms.Resize(size, interpolation=2) 功能:重置图像分辨率 参数: size- If size is an int, if height > width, then image will be rescaled to (size * height / width, size),所以建议size设定为h*w interpolation- 插值方法选择,默认为PIL.Image.BILINEAR

10.标准化:transforms.Normalize
class torchvision.transforms.Normalize(mean, std) 功能:对数据按通道进行标准化,即先减均值,再除以标准差,注意是 hwc

11.转为tensor:transforms.ToTensor
class torchvision.transforms.ToTensor 功能:将PIL Image或者 ndarray 转换为tensor,并且归一化至[0-1] 注意事项:归一化至[0-1]是直接除以255,若自己的ndarray数据尺度有变化,则需要自行修改。

12.填充:transforms.Pad
class torchvision.transforms.Pad(padding, fill=0, padding_mode=’constant’) 功能:对图像进行填充 参数: padding-(sequence or int, optional),此参数是设置填充多少个pixel。 当为int时,图像上下左右均填充int个,例如padding=4,则上下左右均填充4个pixel,若为3232,则会变成4040。 当为sequence时,若有2个数,则第一个数表示左右扩充多少,第二个数表示上下的。当有4个数时,则为左,上,右,下。 fill- (int or tuple) 填充的值是什么(仅当填充模式为constant时有用)。int时,各通道均填充该值,当长度为3的tuple时,表示RGB通道需要填充的值。 padding_mode- 填充模式,这里提供了4种填充模式,1.constant,常量。2.edge 按照图片边缘的像素值来填充。3.reflect,? 4. symmetric,?

13.修改亮度、对比度和饱和度:transforms.ColorJitter
class torchvision.transforms.ColorJitter(brightness=0, contrast=0, saturation=0, hue=0) 功能:修改修改亮度、对比度和饱和度

14.转灰度图:transforms.Grayscale
class torchvision.transforms.Grayscale(num_output_channels=1) 功能:将图片转换为灰度图 参数: num_output_channels- (int) ,当为1时,正常的灰度图,当为3时, 3 channel with r == g == b

15.线性变换:transforms.LinearTransformation()
class torchvision.transforms.LinearTransformation(transformation_matrix) 功能:对矩阵做线性变化,可用于白化处理! whitening: zero-center the data, compute the data covariance matrix 参数: transformation_matrix (Tensor) – tensor [D x D], D = C x H x W

16.仿射变换:transforms.RandomAffine
class torchvision.transforms.RandomAffine(degrees, translate=None, scale=None, shear=None, resample=False, fillcolor=0) 功能:仿射变换

17.依概率p转为灰度图:transforms.RandomGrayscale
class torchvision.transforms.RandomGrayscale(p=0.1) 功能:依概率p将图片转换为灰度图,若通道数为3,则3 channel with r == g == b

18.将数据转换为PILImage:transforms.ToPILImage
class torchvision.transforms.ToPILImage(mode=None) 功能:将tensor 或者 ndarray的数据转换为 PIL Image 类型数据 参数: mode- 为None时,为1通道, mode=3通道默认转换为RGB,4通道默认转换为RGBA

19.transforms.Lambda
Apply a user-defined lambda as a transform. 暂不了解,待补充。

四、对transforms操作,使数据增强更灵活
PyTorch不仅可设置对图片的操作,还可以对这些操作进行随机选择、组合

20.transforms.RandomChoice(transforms)
功能:从给定的一系列transforms中选一个进行操作,randomly picked from a list

21.transforms.RandomApply(transforms, p=0.5)
功能:给一个transform加上概率,以一定的概率执行该操作

22.transforms.RandomOrder
功能:将transforms中的操作顺序随机打乱

https://pytorch-cn.readthedocs.io/zh/latest/

PyTorch文档中主要包含2个模块,一个是 torch, 一个 torchvision, torch 是主模块, 用来搭建神经网络的, torchvision 是辅模块, 有数据库, 还有一些已经训练好的神经网络等着你直接用, 比如 (VGG, AlexNet, ResNet).

torch:
    Tensor
    Storage
    nn
    nn.functional
    autograd
    optim
    nn.init
    multiprocessing
    legacy
    cuda
    utils.fit
    utils.data
    utils.model_zoo

torchvison:
    datasets
    models
    transforms
    utils

一、二叉堆

二叉堆是一种特殊的二叉树, 它总是保证一棵树的最小元素(最小堆)或者最大元素(最大堆)处于树根上, 常见的应用场景就是用于构建优先队列, 在jdk中Doug Lea所实现的ScheduledThreadPoolExecutor中就用到了最小堆;

1、最小堆

1.1 基本操作

BinaryHeap() 创建一个新的,空的二叉堆。
insert(k) 向堆添加一个新项。
findMin() 返回具有最小键值的项,并将项留在堆中。
delMin() 返回具有最小键值的项,从堆中删除该项。
如果堆是空的,isEmpty() 返回 true,否则返回 false。
size() 返回堆中的项数。
buildHeap(list) 从键列表构建一个新的堆。

注意,无论我们向堆中添加项的顺序是什么,每次都删除最小的。

1.2 实现

为了使我们的堆有效地工作,我们将利用二叉树的对数性质来表示我们的堆。 为了保证对数性能,我们必须保持树平衡。平衡二叉树在根的左和右子树中具有大致相同数量的节点。 在我们的堆实现中,我们通过创建一个 完整二叉树 来保持树平衡。 一个完整的二叉树是一个树,其中每个层都有其所有的节点,除了树的最底层,从左到右填充,如图。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/heap1.png

完整二叉树的另一个有趣的属性是,我们可以使用单个列表来表示它。 我们不需要使用节点和引用,甚至列表的列表。因为树是完整的,父节点的左子节点(在位置 p 处)是在列表中位置 2p 中找到的节点。 类似地,父节点的右子节点在列表中的位置 2p + 1。为了找到树中任意节点的父节点,我们可以简单地使用Python 的整数除法。 假定节点在列表中的位置 n,则父节点在位置 n/2。如图,请注意父级和子级之间是 2p 和 2p+1 关系。 树的列表表示以及完整的结构属性允许我们仅使用几个简单的数学运算来高效地遍历一个完整的二叉树。 我们将看到,这也是我们的二叉堆的有效实现。

我们用于堆中存储项的方法依赖于维护堆的排序属性。 堆的排序属性如下:在堆中,对于具有父 p 的每个节点 x,p 中的键小于或等于 x 中的键。 下图展示了具有堆顺序属性的完整二叉树。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/heap2.png

我们将开始实现一个二叉堆的构造函数。由于整个二叉堆可以由单个列表表示,所以构造函数将初始化列表和一个 currentSize 属性来跟踪堆的当前大小。一个空的二叉堆有一个单一的零作为 heapList 的第一个元素,这个零只是放那里,用于以后简单的整数除法。

class BinHeap:
    def __init__(self):
        self.heapList=[0]
        self.currentSize=0

将项添加到列表中最简单,最有效的方法是将项附加到列表的末尾。 它维护完整的树属性。但可能违反堆结构属性。可以编写一个方法,通过比较新添加的项与其父项,我们可以重新获得堆结构属性。 如果新添加的项小于其父项,则我们可以将项与其父项交换。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/heap3.png

注意,当我们完成一个项时,我们需要恢复新添加的项和父项之间的堆属性。 我们还需保留任何兄弟节点的堆属性。当然,如果新添加的项非常小,我们可能仍需要将其交换另一上层。事实上,我们可能需要交换到树的顶部。

percUp 方法,它在树中向上遍历一个新项,因为它需要去维护堆属性。注意,我们可以通过使用简单的整数除法来计算任意节点的父节点。 当前节点的父节点可以通过将当前节点的索引除以 2 来计算。

插入方法中的大部分工作都是由 percUp 完成的。 一旦一个新项被追加到树上,percUp 接管并正确定位新项。

def percUp(self,i):
    while i//2>0:
        if self.heapList[i] < self.heapList[i//2]:
            tmp=self.heapList[i//2]
            self.heapList[i//2]=self.heapList[i]
            self.heapList[i]=tmp
            # self.heapList[i//2],self.heapList[i]=self.heapList[i],self.heapList[i//2]
        i=i//2

def insert(self,k):
    self.heapList.append(k)
    self.currentSize+=1
    self.percUp(self.currentSize)

因为堆属性要求树的根是树中的最小项,所以找到最小项很容易。delMin 的难点在根被删除后恢复堆结构和堆顺序属性。 我们可以分两步恢复我们的堆。首先,我们将通过获取列表中的最后一个项并将其移动到根位置来恢复根项,保持我们的堆结构属性。 但是,我们可能已经破坏了我们的二叉堆的堆顺序属性。 第二,我们通过将新的根节点沿着树向下推到其正确位置来恢复堆顺序属性。 下图展示了将新的根节点移动到堆中的正确位置所需的交换序列。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/heap4.png

为了维护堆顺序属性,我们所需要做的是将根节点和最小的子节点交换。在初始交换之后,我们可以将节点和其子节点重复交换,直到节点被交换到正确的位置,使它小于两个子节点。

def percDown(self, i):
    while (i * 2) <= self.currentSize:
        mc = self.minChild(i)
        if self.heapList[i] > self.heapList[mc]:
            tmp = self.heapList[i]
            self.heapList[i] = self.heapList[mc]
            self.heapList[mc] = tmp
        i = mc


def minChild(self, i):
    '''
    找到最小子节点:
        如果右子节点不存在,那么最小子节点为左;
        如果右子节点存在,判断左右的大小后再返回;
    :param self:
    :param i:
    :return:
    '''
    if i * 2 + 1 > self.currentSize:
        return i * 2
    else:
        if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
            return i * 2
        else:
            return i * 2 + 1


def delMin(self):
    retval = self.heapList[1]
    self.heapList[1] = self.heapList[self.currentSize]
    self.currentSize -= 1
    self.heapList.pop()
    self.percDown(1)
    return retval

为了完成我们对二叉堆的讨论,我们将看从一个列表构建整个堆的方法.如图,给定一个列表,通过一次插入一个键轻松地构建一个堆。由于你从一个项的列表开始,该列表是有序的,可以使用二分查找找到正确的位置,以大约 O(logn) 操作的成本插入下一个键。 但是,请记住,在列表中间插入项可能需要 O(n) 操作来移动列表的其余部分,为新项腾出空间。 因此,要在堆中插入 n 个键,将需要总共 O(nlogn) 操作。 然而,如果我们从整个列表开始,那么我们可以在 O(n) 操作中构建整个堆。Listing 6 展示了构建整个堆的代码。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/heap5.png

buildHeap 方法在 [9,6,5,2,3] 的初始树中的节点移动到其正确位置时所做的交换。虽然我们从树的中间开始,并以我们的方式回到根节点,percDown 方法确保最大的子节点总是沿着树向下移动。因为堆是一个完整的二叉树,超过中途点的任何节点都将是树叶,因此没有子节点。注意,当i = 1 时,我们从树的根节点向下交换,因此可能需要多次交换。正如你在上图最右边的两个树中可以看到的,首先 9 从根位置移出,但是 9 在树中向下移动一级之后,percDown 检查下一组子树,以确保它被推到下一层。在这种情况下,它与 3 进行第二次交换。现在 9 已经移动到树的最低层,不能进行进一步交换。将上图所示的这一系列交换的列表与树进行比较是有用的。

def buildHeap(self, alist):
    i = len(alist) // 2
    self.currentSize = len(alist)
    self.heapList = [0] + alist[:]
    while i > 0:
        self.percDown(i)
        i -= 1

完整代码:

class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0

    def percUp(self,i):
        while i // 2 > 0:
          if self.heapList[i] < self.heapList[i // 2]:
             self.heapList[i // 2],self.heapList[i]=self.heapList[i],self.heapList[i // 2]
          i = i // 2

    def insert(self,k):
      self.heapList.append(k)
      self.currentSize = self.currentSize + 1
      self.percUp(self.currentSize)

    def percDown(self,i):
      while (i * 2) <= self.currentSize:
          mc = self.minChild(i)
          if self.heapList[i] > self.heapList[mc]:
              self.heapList[i],self.heapList[mc] = self.heapList[mc],self.heapList[i]
          i = mc

    def minChild(self,i):
      if i * 2 + 1 > self.currentSize:
          return i * 2
      else:
          if self.heapList[i*2] < self.heapList[i*2+1]:
              return i * 2
          else:
              return i * 2 + 1

    def delMin(self):
      retval = self.heapList[1]
      self.heapList[1] = self.heapList[self.currentSize]
      self.currentSize = self.currentSize - 1
      self.heapList.pop()
      self.percDown(1)
      return retval

    def buildHeap(self,alist):
      i = len(alist) // 2
      self.currentSize = len(alist)
      self.heapList = [0] + alist[:]
      while (i > 0):
          self.percDown(i)
          i = i - 1

bh = BinHeap()
bh.buildHeap([9,5,6,2,3])

print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())

我们可以在 O(n)中构建堆的断言可能看起来有点神秘,证明超出了范围。 然而,理解的关键是记住 logn 因子是从树的高度派生的。 对于buildHeap 中的大部分工作,树比 logn 短。
基于可以从 O(n) 时间构建堆的事实,你可以使用堆对列表在 O(nlogn)时间内排序,作为本章结尾的练习。

2、最大堆

class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0

    def percUp(self, i):
        while i // 2 > 0:
            if self.heapList[i] > self.heapList[i // 2]:
                self.heapList[i],self.heapList[i // 2]=self.heapList[i // 2],self.heapList[i]
            i = i // 2

    def insert(self, k):
        self.heapList.append(k)
        self.currentSize += 1
        self.percUp(self.currentSize)

    def percDown(self, i):
        while (i * 2) <= self.currentSize:
            mc = self.maxChild(i)
            if self.heapList[i] < self.heapList[mc]:
                self.heapList[i],self.heapList[mc]=self.heapList[mc],self.heapList[i]
            i = mc

    def maxChild(self, i):
        if i * 2 + 1 > self.currentSize:
            return i * 2
        else:
            if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
                return i * 2 + 1
            else:
                return i * 2

    def delMax(self):
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize -= 1
        self.heapList.pop()
        self.percDown(1)
        return retval

    def buildHeap(self, alist):
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        while (i > 0):
            self.percDown(i)
            i = i - 1


bh = BinHeap()
bh.buildHeap([9, 5, 6, 2, 3])

print(bh.heapList)
print(bh.currentSize)
print(bh.delMax())
print(bh.heapList)
print(bh.delMax())

二、海量数据TopK问题

https://www.codenong.com/cs105636770/
https://www.runoob.com/w3cnote/heap-sort.html
https://www.cnblogs.com/yezigege/p/13386408.html
https://github.com/ShaoQiBNU/Topk
https://www.cnblogs.com/eudiwffe/p/6202111.html

TopK问题:在海量的数据中找出前k个最大值或者最小值。

假设我们对所有的数据进行排序,时间复杂度(快速排序):O(nlogn)。如果这是数亿个数据,那这样的方法也就不那么高效了

大根堆的堆顶是堆中的最大元素;而小根堆的堆顶是堆中的最小元素。

2.1 小根堆

利用堆来解决TopK问题(以最大的k个举例):

我们可以建立一个大小为K小根堆,然后从第k个元素开始遍历,如果大于小根堆的堆顶,那么就交换两个元素,交换一次调整一次,直到所有数据遍历结束,堆中的元素就是海量数据中最大的k个。

为什么是小根堆,而不是大根堆呢?大根堆的堆顶是堆中的最大值呀

答:我们的目的是小根堆中保存所有数据中最大的k个,正因为小根堆的堆顶是最小的值,当我们遍历剩余的数据时,只有大于我们这个堆中的最小值,才有资格放进来,这样当遍历结束后堆中的元素就是最大的k个;

为什么建立大小为k呢?

答:因为我们只是想要找出海量数据中最大或最小的k个,所以只需要大小为k;

十四、database

优先顺序:where>group by>having>order by

182. 查找重复的电子邮箱

链接:https://leetcode-cn.com/problems/duplicate-emails/

SQL架构
编写一个 SQL 查询,查找 Person 表中所有重复的电子邮箱。

示例:

+----+---------+
| Id | Email   |
+----+---------+
| 1  | a@b.com |
| 2  | c@d.com |
| 3  | a@b.com |
+----+---------+
根据以上输入,你的查询应返回以下结果:

+---------+
| Email   |
+---------+
| a@b.com |
+---------+
说明:所有电子邮箱都是小写字母。
# Write your MySQL query statement below
# 1.使用group by 和临时表
select Email from
(
select Email, count(Email) as nums 
from Person
group by Email
) as tmp
where nums>1;
# 2.使用group by和having条件
select Email
from Person
group by Email
having count(Email) > 1;


十三、数学

29.两数相除

链接:https://leetcode-cn.com/problems/divide-two-integers/submissions/

给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
示例 2:

输入: dividend = 7, divisor = -3
输出: -2
说明:

被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231,  231 − 1]。本题中,如果除法结果溢出,则返回 231 − 1。

题解一|减法|超时:

超时:当被除数为2147483648,除数为 1,必然超时。

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        res=0
        flag=1 if dividend ^ divisor >=0 else -1
        dividend=abs(dividend)
        divisor=abs(divisor)
        while dividend >= divisor:
            res+=1
            dividend-=divisor
        res=res*flag
        return min(max(res,-2**31),2**31-1)

题解二|增倍除数:

<< 是左移,末位补0,类比十进制数在末尾添0相当于原数乘以10,x<<1是将x的二进制表示左移一位,相当于原数x乘2。比如整数4在二进制下是100,4<<1左移1位变成1000(二进制),结果是8。

>>是右移,右移1位相当于除以2。
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        res=0
        flag=1 if dividend ^ divisor >=0 else -1
        dividend=abs(dividend)
        divisor=abs(divisor)
        while dividend >= divisor:
            tmp,i=divisor,1
            while dividend>=tmp:
                dividend-=tmp
                res+=i
                i <<=1
                tmp <<=1
        res=res*flag
        return min(max(res,-2**31),2**31-1)

题解三|位移:
算法是把除法化归成移位和减法两种运算方法。对于 10 进制数,移位运算就是乘(左移)除(右移)10,而我们都知道计算机中的移位运算是乘(左移)除(右移)2,因为计算机是通过二进制的方法存储数的。这样,类比十进制,二进制的除法(仍以 45/2 为例)可以写作(注意,这里我们并没有用到乘除法)

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        res=0
        flag=1 if dividend ^ divisor >=0 else -1
        dividend=abs(dividend)
        divisor=abs(divisor)
        count=0

        # 不断左移,直到大于被除数
        while dividend >= divisor:
            count+=1
            divisor <<=1

        while count > 0:
            count -=1
            divisor >>=1
            res <<=1
            if divisor <= dividend:
                res+=1
                dividend -= divisor

        res=res*flag
        return min(max(res,-2**31),2**31-1)

50. Pow(x, n)

链接:https://leetcode-cn.com/problems/powx-n/

实现 pow(x, n) ,即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000
示例 2:

输入: 2.10000, 3
输出: 9.26100
示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:

-100.0 < x < 100.0
n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。

参考:https://leetcode-cn.com/problems/powx-n/solution/powx-n-by-leetcode-solution/

题解一|快速幂|递归:

时间复杂度:O(logn),即为递归的层数。
空间复杂度:O(logn),即为递归的层数。这是由于递归的函数调用会使用栈空间。

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        def helper(n):
            if n==0:
                return 1
            y=helper(n//2)
            return y*y if n%2==0 else y*y*x
        return helper(n) if n>=0 else 1/helper(-n)

题解二|快速幂|迭代:

时间复杂度:O(logn)
空间复杂度:O(1)

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        def helper(n):
            ans=1
            new=x
            while n>0:
                if n%2==1:
                    ans*=new
                new*=new
                n//=2
            return ans

        return helper(n) if n>=0 else 1/helper(-n)

69.x的平方根

链接:https://leetcode-cn.com/problems/sqrtx/

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数,小数部分将被舍去。

题解一|二分法):

思路分析:使用二分法搜索平方根的思想很简单,就类似于小时候我们看的电视节目中的“猜价格”游戏,高了就往低了猜,低了就往高了猜,范围越来越小。因此,使用二分法猜算术平方根就很自然。

一个数的平方根肯定不会超过它自己,不过直觉还告诉我们,一个数的平方根最多不会超过它的一半,例如 8的平方根,8 的一半是 4,4^2=16>8,如果这个数越大越是如此,因此我们要计算一下,这个边界是多少。为此,解如下不等式:(a/2)^2 >= a

时间复杂度:O(logn)
空间复杂度:O(1)

class Solution:
    def mySqrt(self, x: int) -> int:
        left=0
        right=x//2+1
        while left < right:
            # mid = left + (right - left + 1) // 2
            # mid=(left+right+1)>>1
            mid=(left+right+1)//2 # 使用除法的耗时比移位多
            square=mid*mid

            if square>x:
                right=mid-1
            else:
                left=mid

        return left
# 单独照顾0这个特例

class Solution:
    def mySqrt(self, x: int) -> int:
        if x==0:
            return 0
        left=1
        right=x//2
        while left < right:
            # mid=(left+right+1)>>1
            mid=(left+right+1)//2 # 使用除法的耗时比移位多
            # 一定取右中位数,如果取左中位数(left+right)//2,代码可能会进入死循环
            square=mid*mid

            if square>x:
                right=mid-1
            else:
                left=mid

        return left
class Solution:

    def mySqrt(self, x):
        left = 0
        right = 999999
        while left < right:
            # 这种取中位数的方法又快又好,是我刚学会的,原因在下面这篇文章的评论区
            # https://www.liwei.party/2019/06/17/leetcode-solution-new/search-insert-position/
            mid = (left + right + 1) >> 1
            square = mid * mid
            if square > x:
                right = mid - 1
            else:
                left = mid

        return left

?题解二(牛顿法):

牛顿法的应用:一个是求方程的根,另一个是求解最优化问题

使用牛顿法可以得到一个正实数的算术平方根,因为题目中说“结果只保留整数部分”,因此,我们把使用牛顿法得到的浮点数转换为整数即可。

在迭代过程中,以直线代替曲线,用一阶泰勒展式(即在当前点的切线)代替原曲线,求直线与 xx 轴的交点,重复这个过程直到收敛。
https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/newton.png

class Solution:
    def mySqrt(self, x: int) -> int:
        if x<0:
            # raise Exception('不能输入负数)
            return -1
        if x==0:
            return 0

        cur=1
        while True:
            pre=cur
            cur=(cur+x/cur)/2
            if abs(cur-pre)< 1e-6:
                return int(cur)

136. 只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

题解一|位运算:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x,y:x^y,nums)
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res=0
        for i in nums:
            res^=i
        return res
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans=nums[0]
        for i in range(1,len(nums)):
            ans^=nums[i]
        return ans

题解二|hash:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        temp=[]
        for i in nums:
            if i not in temp:
                temp.append(i)
            else:
                temp.remove(i)
        return temp[0]
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        temp={}
        for i in nums:
            if i not in temp:
                temp[i]=1
            else:
                temp[i]+=1
        for k,v in temp.items():
            if v==1:
                return k

166. 分数到小数

链接:https://leetcode-cn.com/problems/fraction-to-recurring-decimal/

给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以 字符串形式返回小数 。

如果小数部分为循环小数,则将循环的部分括在括号内。

如果存在多个答案,只需返回 任意一个 。

对于所有给定的输入,保证 答案字符串的长度小于 104 。

示例 1:

输入:numerator = 1, denominator = 2
输出:"0.5"
示例 2:

输入:numerator = 2, denominator = 1
输出:"2"
示例 3:

输入:numerator = 2, denominator = 3
输出:"0.(6)"
示例 4:

输入:numerator = 4, denominator = 333
输出:"0.(012)"
示例 5:

输入:numerator = 1, denominator = 5
输出:"0.2"


提示:

-231 <= numerator, denominator <= 231 - 1
denominator != 0

题解一|hash:

注意:

正负号;
是否有小数点,也就是能否被整除;
如果有小数点的话,是否有循环;
如果有循环,如何添加括号;
class Solution(object):
    def fractionToDecimal(self, numerator, denominator):
        """
        :type numerator: int
        :type denominator: int
        :rtype: str
        """
        if numerator == 0:
            return '0'
        res=[]
        if numerator ^ denominator < 0:
            res.append('-')

        numerator=abs(numerator)
        denominator=abs(denominator)

        a,b=divmod(numerator,denominator)
        res.append(str(a))
        if b==0:
            return ''.join(res)

        res.append('.')
        hash={}
        while b != 0:
            if b in hash:
                res.insert(hash[b],'(')
                res.append(')')
                break
            hash[b]=len(res)
            print(hash)
            b*=10
            a,b=divmod(b,denominator)
            res.append(str(a))
        return ''.join(res)

171.Excel表列序号

链接:https://leetcode-cn.com/problems/excel-sheet-column-number/

给定一个Excel表格中的列名称,返回其相应的列序号。

例如,

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 
    ...
示例 1:

输入: "A"
输出: 1
示例 2:

输入: "AB"
输出: 28
示例 3:

输入: "ZY"
输出: 701

题解一:

class Solution:
    def titleToNumber(self, s: str) -> int: 
        res=0
        for each in s:
            num=(ord(each)-65)+1
            res=res*26+num
        return res

172. 阶乘后的零

链接:https://leetcode-cn.com/problems/factorial-trailing-zeroes/

给定一个整数 n,返回 n! 结果尾数中零的数量。

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。

题解一:

如果依靠算出阶乘结果,再计算有多少个0,很容易溢出。

思路:末尾有多少个0,只需要给当前数乘以一个10,就可以加一个0.

比如5!,也就是 5 * 4 * 3 * 2 * 1 = 120,我们发现结果会有一个 0,原因就是 2 和 5 相乘构成了一个 10。而对于 10 的话,其实也只有 2 * 5 可以构成,所以我们只需要找有多少对 2/5。

11! = 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 11 * (2 * 5) * 9 * (4 * 2) * 7 * (3 * 2) * (1 * 5) * (2 * 2) * 3 * (1 * 2) * 1

对于含有 2 的因子的话是 1 * 2, 2 * 2, 3 * 2, 4 * 2 …

对于含有 5 的因子的话是 1 * 5, 2 * 5…

含有 2 的因子每两个出现一次,含有 5 的因子每 5 个出现一次,所有 2 出现的个数远远多于 5,换言之找到一个 5,一定能找到一个 2 与之配对。所以我们只需要找有多少个 5。

直接的,我们只需要判断每个累乘的数有多少个 5 的因子即可。

class Solution:
    def trailingZeroes(self, n: int) -> int:
        count=0
        for i in range(n+1):
            tmp=i
            while tmp>0:
                if tmp%5==0:
                    count+=1
                    tmp//=5
                else:
                    break
        return count

以上算法超时,继续优化。

对于一个数的阶乘,5 的因子一定是每隔 5 个数出现一次,也就是下边的样子。

n! = 1 * 2 * 3 * 4 * (1 * 5) * ... * (2 * 5) * ... * (3 * 5) *... * n

因为每隔 5 个数出现一个 5,所以计算出现了多少个 5,我们只需要用 n/5 就可以算出来。

但还没有结束,继续分析。

... * (1 * 5) * ... * (1 * 5 * 5) * ... * (2 * 5 * 5) * ... * (3 * 5 * 5) * ... * n

每隔 25 个数字,出现的是两个 5,所以除了每隔 5 个数算作一个 5,每隔 25 个数,还需要多算一个 5。

也就是我们需要再加上 n / 25 个 5。

同理我们还会发现每隔 5 * 5 * 5 = 125 个数字,会出现 3 个 5,所以我们还需要再加上 n / 125 。

综上,规律就是每隔 5 个数,出现一个 5,每隔 25 个数,出现 2 个 5,每隔 125 个数,出现 3 个 5,以此类推。

最终 5 的个数就是 n / 5 + n / 25 + n / 125 …

写程序的话,如果直接按照上边的式子计算,分母可能会造成溢出。所以算 n / 25 的时候,我们先把 n 更新,n = n / 5,然后再计算 n / 5 即可,后边的同理。

class Solution:
    def trailingZeroes(self, n: int) -> int:
        count=0
        while n>0:
            count+=n//5
            n//=5
        return count

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为  1,那么这个数就是快乐数。

如果 n 是快乐数就返回 True ;不是,则返回 False 。



示例:

输入:19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

思路:

根据我们的探索,我们猜测会有以下三种可能。

    最终会得到 11。
    最终会进入循环。
    值会越来越大,最后接近无穷大。

根据我们的观察,发现不会出现无穷大的情况。

实现:

给一个数字 n,它的下一个数字是什么?     做数位分离,求平方和。
按照一系列的数字来判断我们是否进入了一个循环。     每次生成链中的下一个数字时,我们都会检查它是否已经在 HashSet 中。

时间复杂度:O(logn)
空间复杂度:O(logn)

题解一|set:

class Solution:
    def isHappy(self, n: int) -> bool:
        def getNext(n):
            ans=0
            while n>0:
                n,digits=divmod(n,10)
                ans+=pow(digits,2)
            return ans

        seen=set()
        while n!=1 and n not in seen:
            seen.add(n)
            n=getNext(n)
        return n==1

题解二|快慢指针:

时间复杂度:O(logn)
空间复杂度:O(1)

class Solution:
    def isHappy(self, n: int) -> bool:
        def getNext(n):
            ans=0
            while n>0:
                n,digits=divmod(n,10)
                ans+=pow(digits,2)
            return ans

        slow=n
        fast=getNext(n)
        while fast !=1 and fast != slow:
            slow=getNext(slow)
            fast=getNext(getNext(fast))
        return fast==1

题解三|数学:

如果这样做,您会发现只有一个循环:44→16→37→58→89→145→42→20→4。所有其他数字都在进入这个循环的链上,或者在进入 1 的链上。

时间复杂度:O(logn)
空间复杂度:O(1)

class Solution:
    def isHappy(self, n: int) -> bool:
        cycle={4, 16, 37, 58, 89, 145, 42, 20}

        def getNext(n):
            ans=0
            while n>0:
                n,digits=divmod(n,10)
                ans+=pow(digits,2)
            return ans

        while n!=1 and n not in cycle:
            n=getNext(n)
        return n==1

204. 计数质数

统计所有小于非负整数 n 的质数的数量。

示例 1:

输入:n = 10
输出:4
解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2:

输入:n = 0
输出:0
示例 3:

输入:n = 1
输出:0


提示:

0 <= n <= 5 * 106

题解一|暴力|超时:

注意:题意是小于,而不是小于等于。

class Solution:
    def countPrimes(self, n: int) -> int:
        if n<2:
            return 0
        count=0
        for i in range(2,n):
            flag=True
            for j in range(2,i):
                if j!=i and i%j==0: # if i%j==0:
                    flag=False
                    break
            if flag:
                count+=1
        return count

题解二|暴力优化:

class Solution:
   def countPrimes(self, n: int) -> int:
       if n<3:
           return 0
       count=1
       for i in range(3,n):
           if i%2 == 0: # 排除偶数,使用if i^1==0:有可以
               continue
           flag=True
           for j in range(3,int(i**0.5)+1,2): # 因为排除偶数,加2会更快。
               if i%j==0:
                   flag=False
                   break
           if flag:
               count+=1
       return count

题解三|厄拉多塞筛法:

https://leetcode-cn.com/problems/count-primes/solution/ji-shu-zhi-shu-bao-li-fa-ji-you-hua-shai-fa-ji-you/

思路:

选中数字2,并排除2的倍数;
选中数字3,并排除3的倍数;
选中数字5,并排除5的倍数;
...
class Solution:
    def countPrimes(self, n: int) -> int:
        count=0
        sign=[True]*n
        for i in range(2,n):
            if sign[i]:
                count+=1
                for j in range(i+i,n,i):
                    sign[j]=False
        return count

326. 3的幂

链接:https://leetcode-cn.com/problems/power-of-three/

给定一个整数,写一个函数来判断它是否是 3 的幂次方。

示例 1:

输入: 27
输出: true
示例 2:

输入: 0
输出: false
示例 3:

输入: 9
输出: true
示例 4:

输入: 45
输出: false
进阶:
你能不使用循环或者递归来完成本题吗?

题解一|循环:

时间复杂度:O(logb(n)),我们的例子中是 O(logn),除数是用对数表示的。
空间复杂度:O(1),没有使用额外的空间。

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n<1: # 不加这里,会在0里面陷入死循环
            return 0
        while n%3==0:
            n//=3
        return n==1

题解二|递归:

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n==1:
            return True
        if n<=0 or n%3!=0:
            return False
        n=n//3
        return self.isPowerOfThree(n)

题解三|换底公式:

class Solution:
    import math
    def isPowerOfThree(self, n: int) -> bool:
        if n<1:
            return False
        res=math.log10(n)/math.log10(3) # 不能使用math.log(),会有小数
        return True if res-int(res)==0 else False
        # return (math.log10(n) / math.log10(3))%1 == 0

412. Fizz Buzz

链接:https://leetcode-cn.com/problems/fizz-buzz/

写一个程序,输出从 1 到 n 数字的字符串表示。

1. 如果 n 是3的倍数,输出“Fizz”;

2. 如果 n 是5的倍数,输出“Buzz”;

3.如果 n 同时是3和5的倍数,输出 “FizzBuzz”。

示例:

n = 15,

返回:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

题解一:

class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        res=[]
        for i in range(1,n+1):
            if i%3==0 and i%5==0:
                res.append('FizzBuzz')
            elif i%3==0:
                res.append('Fizz')
            elif i%5==0:
                res.append('Buzz')
            else:
                res.append(str(i))
        return res

题解二|递归:

class Solution:
    def __init__(self):
        self.res=[]

    def fizzBuzz(self, n: int) -> List[str]:
        if not n:
            self.res.reverse()
            return self.res
        if n%3==0 and n%5==0:
            self.res.append('FizzBuzz')
        elif n%3==0:
            self.res.append('Fizz')
        elif n%5==0:
            self.res.append('Buzz')
        else:
            self.res.append(str(n))
        return self.fizzBuzz(n-1)

题解三|hash:

class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        hash={3:'Fizz',5:'Buzz'}
        res=[]
        for i in range(1,n+1):
            tmp=''
            for key in hash.keys():
                if i%key==0:
                    tmp+=hash[key]
            if not tmp:
                tmp=str(i)
            res.append(tmp)
        return res

1502. 判断能否形成等差数列

链接:https://leetcode-cn.com/problems/can-make-arithmetic-progression-from-sequence/

给你一个数字数组 arr 。

如果一个数列中,任意相邻两项的差总等于同一个常数,那么这个数列就称为 等差数列 。

如果可以重新排列数组形成等差数列,请返回 true ;否则,返回 false 。

示例 1:

输入:arr = [3,5,1]
输出:true
解释:对数组重新排序得到 [1,3,5] 或者 [5,3,1] ,任意相邻两项的差分别为 2 或 -2 ,可以形成等差数列。
示例 2:

输入:arr = [1,2,4]
输出:false
解释:无法通过重新排序得到等差数列。

提示:

2 <= arr.length <= 1000
-10^6 <= arr[i] <= 10^6

题解一|模拟:

时间复杂度:O(nlogn)。排序的时间代价为 O(nlogn),遍历序列的时间代价是 O(n),故渐进时间复杂度为 O(nlogn+n)=O(nlogn)。
空间复杂度:O(logn)。快速排序中使用的栈空间期望是 O(logn)。

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        arr.sort()
        for i in range(1,len(arr)-1):
            if arr[i]*2 != arr[i-1]+arr[i+1]:
                return False
        return True

1447. 最简分数

链接:https://leetcode-cn.com/problems/simplified-fractions/

给你一个整数 n ,请你返回所有 0 到 1 之间(不包括 0 和 1)满足分母小于等于  n 的 最简 分数 。分数可以以 任意 顺序返回。

示例 1:

输入:n = 2
输出:["1/2"]
解释:"1/2" 是唯一一个分母小于等于 2 的最简分数。
示例 2:

输入:n = 3
输出:["1/2","1/3","2/3"]
示例 3:

输入:n = 4
输出:["1/2","1/3","1/4","2/3","3/4"]
解释:"2/4" 不是最简分数,因为它可以化简为 "1/2" 。
示例 4:

输入:n = 1
输出:[]


提示:

1 <= n <= 100

题解一:

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        def gcd(x,y):
            while y:
                x,y=y,x%y
            return x

        res=[]
        tmp=set()
        for i in range(2,n+1):
            for j in range(1,i):
                c=gcd(i,j)
                a,b=j//c,i//c
                if (a,b) in tmp:
                    continue
                tmp.add((a,b))
                res.append(str(a)+'/'+str(b))
        return res