知识补充

浅拷贝与深拷贝：

浅拷贝只复制指向某个对象的指针，而不复制对象本身，新旧对象还是共享同一块内存。但深拷贝会另外创造一个一模一样的对象，新对象跟原对象不共享内存，修改新对象不会改到原对象。
三、赋值和浅拷贝的区别
当我们把一个对象赋值给一个新的变量时，赋的其实是该对象的在栈中的地址，而不是堆中的数据。也就是两个对象指向的是同一个存储空间，无论哪个对象发生改变，其实都是改变的存储空间的内容，因此，两个对象是联动的。
浅拷贝是按位拷贝对象，它会创建一个新对象，这个对象有着原始对象属性值的一份精确拷贝。如果属性是基本类型，拷贝的就是基本类型的值；如果属性是内存地址（引用类型），拷贝的就是内存地址 ，因此如果其中一个对象改变了这个地址，就会影响到另一个对象。即默认拷贝构造函数只是对对象进行浅拷贝复制(逐个成员依次拷贝)，即只复制对象空间而不复制资源。

浅拷贝不管数据多复杂，只会拷贝一层。
https://www.cnblogs.com/blaomao/p/7239203.html

python中调用的类函数类成员记得加上self.
此外，类函数必须有一个成员变量self（静态函数出外）

补码：正数的补码与原码相同。负数的补码等于其原码的符号位不变，数值部分的各位取反，然后整个数加1。
反码：正数的反码与其原码相同；负数的反码是对其原码逐位取反，但符号位除外

python中首先明确一点就是二进制没有位数的概念，所以也就无法获得负数真实表示方法

n = -3
n = n & 0xffffffff #n=4294967293
bin(n)#查看二进制形式：'0b11111111111111111111111111111101'

获得的最终结果python会认为是一个正数（因为没有位数的概念，所以首位的1并不代表符号位），那么获得

0b11111111111111111111111111111101

只是形式上和-3的补码相同。
python中，对于负数，无论是右移操作，还是n&（n-1）操作，都会陷入死循环。
所以利用上述这个小技巧，将负数的影响用于0xffffffff相与变为python认为的正数（与机器中的补码相同）。
链接：https://www.nowcoder.com/questionTerminal/8ee967e43c2c4ec193b040ea7fbb10b8?answerType=1&f=discussion
来源：牛客网

如何将整数转化成二进制：

• 采用 python 自带了方法 bin 函数，比如 bin(12345) 回返回字符串 '0b11000000111001', 这个时候在把0b去掉即可:

  bin(12345).replace('0b','')
  '11000000111001'

• 也可以采用字符串的 format 方法来获取二进制：

  "{0:b}".format(12345)
  '11000000111001'

元组

tup1=(1)
tup2=(1,)
print(tup1, tup2)
>>>
1 (1,)

显然，定义元组时，如果单元素不加逗号会造成系统认为括号为运算符，所以tup1为int而不是tuple

函数补充

string 中的count函数可以返回特定字符串在string中出现的次数
关键在于矩阵是有序的,在python中tuple就是二维的，可以通过下表访问，并len(array)长度便是行
math.pow(x,y) x^y
math.floor 下舍整数
math.ceil 上舍整数

enumerate():

该函数在字面上是枚举、列举的意思，用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中，可同时得到数据对象的值及对应的索引值。如对于下面的例子:

collections中deque的使用：

from collections import deque
双端队列。可两侧访问：
deque1.maxlen 最大长度 如果制定了，那么添加元素时，如果超过你maxlen，旧元素会被删除。
deque1.append() deque1.appendleft()一个默认右侧一个左侧添加元素
deque1.extend() deque1.extendleft()添加列表
deque1.pop() deque.popleft() 出队列
count() clear() remove() insert(index,x) reverse()翻转
copy浅拷贝

list.reverse 列表翻转。
s.join(ite) 添加字符串
s[::-1]可以实现字符串的逆向输出

如何保留两位小数：

math : round(x[,n]):x为数字，n为保留小数点后的位数，但是如果3.5那么输出的结果为3.5而不是3.50
那么如何让其输出3.50呢？
这样可以：
'%.2f'%x

name属性

一个模块被另一个程序第一次引入时，其主程序将运行。如果我们想在模块被引入时，模块中的某一程序块不执行，我们可以用name属性来使该程序块仅在该模块自身运行时执行。

#!/usr/bin/python3
# Filename: using_name.py

if __name__ == '__main__':
   print('程序自身在运行')
else:
   print('我来自另一模块')

$ python using_name.py
程序自身在运行

$ python
>>> import using_name
我来自另一模块
>>>

python 栈

listNode的实操，list的逆序输出的3方法

list1=[1,2,34,5]
list1[::-1]                #切片
list(list1.reverse())    #list自带的reverse，直接逆向输出
list(reversed(list))    #利用reversed，但需要列表化

list的压栈出栈用法

append、pop均默认最后一个元素
一般讲list当做C++中的栈，append，pop可以当做进栈出栈

二叉树

二叉树-前中后序

https://www.cnblogs.com/bigsai/p/11393609.html

重建二叉树：

中心遍历法：

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
    # write code here
        if len(pre) == 0:
            return None
        if len(pre) == 1:
            return TreeNode(pre[0])
        root = TreeNode(pre[0])
        tinL = tin[:tin.index(pre[0])]
        tinR = tin[tin.index(pre[0]) + 1:]
        root.left = self.reConstructBinaryTree(pre[1:len(tinL)+1], tinL)
        root.right = self.reConstructBinaryTree(pre[len(tinL)+1:], tinR)
        return root

二分查找：

有序
https://xxoo521.com/2019-12-24-xuan-zhuan-shu-zu/
注意：python中逻辑运算符为and not or而不是！|&。同时，注意math的floor，ceil返回的为浮点数。

斐波那契数列

循环 or 递归（会超时）
注意：青蛙跳台阶的变种
变态跳台阶：
链接：https://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387?answerType=1&f=discussion
来源：牛客
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析
设nn 级台阶有f(n)f(n) 种跳法，根据最后一次跳台阶的数目可以分解为最后一次一级，则前面需要跳n-1n−1 级，有f(n-1)f(n−1) 种跳法；最后一次跳两级，则前面需要跳n- 2n−2 级，有f(n-2)f(n−2) 种跳法。以此类推 易知，
f(n)=f(n-1)+f(n-2)+……f(0)
f(n-1)=f(n-2)+…f(0)
两式相减得，
f(n)=2f(n-1)f(n)=2f(n−1)

栈的利用

输入一个链表，反转链表后，输出新链表的表头

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if not pHead:
            return None
        list0=[]
        Node0=pHead
        while Node0:
            list0.append(Node0)
            Node0=Node0.next
        head=list0.pop()
        Node1=head
        while list0:
            Node1.next=list0.pop()
            Node1=Node1.next
        Node1.next=None                #很关键。最后出栈的是pHead，但是你原来的pHead是指向之前的第二个，也就是现在列表的倒数第二个。致使死循环
        return head

注意：链表一定要写如果链表空的返回值

搜索树，子树☆☆

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

class Solution:
    def IsameTree(self,root1,root2):
        if not root2:
            return True
        if not root1 and root2:
            return False
        if root1.val==root2.val:
            return self.IsameTree(root1.left,root2.left) and self.IsameTree(root1.right,root2.right)
        else:
            return False

    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if not pRoot2:
            return False
        if not pRoot1 and pRoot2:
            return False
        flag=False
        if pRoot1.val==pRoot2.val:
            flag=self.IsameTree(pRoot1,pRoot2)
        if not flag:
            flag=self.HasSubtree(pRoot1.left,pRoot2)
            if not flag:
                flag=self.HasSubtree(pRoot1.right,pRoot2)
        return flag

算法

深度优先-广度优先-区别：

https://blog.csdn.net/yishuige/article/details/51769997
https://blog.csdn.net/yimixgg/article/details/90023121
https://blog.csdn.net/github_38818603/article/details/81288659
二叉树DFS,BFS:
https://blog.csdn.net/mingwanganyu/article/details/72033122?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
昨晚一直在想深度优先广度优先的区别，都是一样的程序，只有栈和队列不同而已，就造成了深度和广度的区别，那么是为什么呢？
今早上灵机一闪，问题就出在栈和队列，这两者的存储机制不同的。
深度优先：
栈先进后出，假设二叉树前序遍历[w,q,,r,t,e,y,u]
w进栈，q进栈，然后是q的子树r,t。而不是w的右子树e。然后出栈便是trq。然后eyu进栈，uyew出栈。这同时使用了回溯。
广度优先：
队列先进先出，，同样的二叉树。
w进，qe进

排序方法

快排：

时间复杂度O(nlog(n))-O(n^2)

堆排

时间复杂度O(nlog(n))

归并排序

时间复杂度O(log(n))

查找

二分查找

时间复杂度O(logn)

BFPRT（线性查找算法）

深度优先、广度优先

关于python的输入输出

这个主要针对第一次笔试出现的问题，不晓得python如何循环输入输出。
首先了解python的sys模块：
stdin标准输入:
sys.stdin.readline(): return字符串，如果需要int,float类型，则需要进行强制类型转化
使用map函数进行转化。

import sys
while True:
    line=sys.stdin.readline()
    if line == '\n':
        break
    line=line.split(' ')
    print(line)

readlines

与readline对应，其读取多行，以Ctrl+D结束，返回的为列表注意列表中的每一项含有'\n'

map函数的使用：

map(func,iter)
第一个参数func以参数序列中的每一个元素调用func函数，返回包含每次func函数返回的新列表

那么：

map(int,line.split())

即可将所有转化为int

split的使用：

s.split() 如果无参数默认空格，将s分割返回一个列表
split可以有参数，s.split('\n')则是将字符串s转化为以'\n'分割而成的字符串列表
sprip()只能删除开头和结尾的特定字符，默认为空格，不能操作中间的字符