Python学习之线性数据结构(二)

print(end=' ') end=表示语句结束后加入的东西

print(sep='') sep 表示间隔符 1 2 2 3 这个间隔的空格就是间隔符

print(1,2,sep=' ',end='') #打印数字1和2 间隔符为空格‘ ’ #以 结尾

分析一下菱形 *

 *
***
 *

思路一 前置空格

行号 星号 前置空格 后置空格 1 1 3 6 2 3 2 4 3 5 1 2 4 7 0 0 5 5 1 2 6 3 2 4 7 1 3 6 n=7 char ='*' lead=' ' for i in range(-3,4): spaces=-i if i<0 else i # 等价于上面的if print(spaces * lead,end ='') print((7 - 2 * spaces) * char)

面试问你求素数的本质是，如果素数规模很大，你该如何考虑算法。

Python 内存管理

面试题： 1. 变量无须事先声明，也不需要指定类型，这是动态语言的特性 2. 变量只是一个标识符，指向一个对象，而这个对象被创建在内存"堆"中 3. Python编程中一般无须关心变量的存亡，一般也不用关心内存的管理 4. python使用引用计数记录所有对象的引用数。当对象引用数变为0，它就可以被 垃圾回收GC

#列表

X=[] 新建的空列表来说[],地址交给了x,引用计数为1

import sys sys.getrefcount(x) 函数调用自动加1，用完减一 。这函数是计算引用次数的 输出2

y=x sys.getrefcount(x) 此时输出3

sys.getrefcount([]) 这个应该输出几？ 输出1 如何解释输出1 ？ 这个写法表示新对象，肯定计数为1 实际[]引用计数0，调用完之后，适当的时候，gc清理它

a=1 #字符常量，数值或字符串等，他们是常量，常量处理不同，常量一旦创建不允许 修改，因此没有必要在内存中保留很多份

随机数模块：

元组tuple： 元组和列表有什么区别呢？列表是可增、可减，元组一旦创建则不能改变

列表 可变数据类型
元组 不可变数据类型

元组的初始化： t1= 1，2 这个属于封装 也属于元组 t2 =(1,2) 这个之间声明了是元组 (): 空元组 tuple(): 类加括号，表示空元组

t3=()
t4=tuple()
t3 == t4 会返回 True  
  解释器对不可变的tuple类型，做了优化

t4=(1,2,[3,4])  元组也是容器

t5=(5) 这个不是创建元组，这个就是单纯的数值5，因为不知道这个()是想
    增加优先级，还是创建元组。所有就同一按照是定义数值了来理解
t5=(5，)：后面加一个逗号，才算定义元组

t5=tuple([1,3,5])
t6=tuple(range(5)) tuple()里面要写可迭代对象

元组的使用：

1.索引 
  t6[0] 为 0  索引也是不允许越界
  t6[10]=10 不允许修改元素，这样写是错误的

2.元组没有，增删改得方法。一旦元组创建好将不允许改变。

t7=([1]) *5  因为没加逗号所以不是元组，这个就相当于 
        t7 = [1] *5  这就是列表能修改   
t7[1]=100 是可以的。 
        输出为[1,100,1,1,1]

t8 =([1],) *5   这个才是元组
  输出为t8=([1],[1],[1],[1],[1])
t8[1]=200 可以这样修改吗？ 不能修改，因为是元组
t8[1][0]=300 这个可以修改吗? 不是地址的能修改
  这个是可以的，修改的是元组中列表的元素是OK的，因为元组存放列表的地址
    元组所说的不能改变是，元素一旦定义好了是不能改变的，可以间接的通过地址可以修改的

t9=(1,2,[111,222])

元组的查询同列表一样的

1.学会利用索引技巧填充值
2.连续开辟一段很大的内存空间

newlist=[None] *len(nums) #必须要有，一般来说append效率也不错。 #但是，如果需要大空间列表，那么一次次append从 #原理来讲不如一次性开辟够 index=-1

while nums: m=max(nums) print(m) nums.remove(m) newlist[index]=m #利用索引填充值的技巧 index-=1

字符串： 一个个字符组成的有序的序列，是字符的集合 使用单引号、双引号、三引号引住的字符序列 字符串是不可变对象，是字面常量

Python3起，字符串都是Unicode类型

初始化： r:取消所有转义字符 打印 \ 用\\ 写长语句的时候用三引号 ''' adsad asd '''

python 中没有提供其他语言都有的char类型，只有str类型
字符串一旦创建就是字面常量了，不能进行修改了

字符串拼接： 使用加法 + 就能对两个字符串进行连接 1.'a' +'b' 这个会输出什么？ a+b并不是变成了ab,他的意思是我会生成一个全新 的字符串'ab'，这个字符串依旧是字面常量.

2.用join 方法也可以，拼接两个字符串。
  ‘aaa’.join()  ‘aaa’这个字符串调用这个join()方法

  ‘a’.join(‘bbb’)，这个的意思是， 用‘aaa’这个字符串来拼接
    join('bbb') join函数里可迭代对象的值。这里能迭代出‘bbb’三个
    元素来.
    这个会输出 'bababa' 输出一个join里的b,后面会拼接一个join前的a
    这个生产的是一个全新的字符串

  list('abc') 什么意思？ 
    遍历'abc'中的这三个元素，并且放到列表中。会这样输出
      ['a','b','b']
  tuple('abc') 元组也是这样的
      ('a','b','b')

  join(),函数的拼接，是在元素之间的拼接。 这个相当于是在字符串之间加
  分隔符。 
  join(),函数本身不能拼接非字符串类型，这是它的问题。
    可以写为 ' '.join(map(str,range(5))) 用一下map函数

字符查找： x.index(‘1’): 找1 是不是在这个字符串中，找到则返回1 的下标index

y='1234'
y.index('123')  能找到并返回索引0  这个是找 子串

2.x='1\n2\n3\n'
  x.conut('2') 输出1 找字符串中‘2’出现的次数

  x.conut(r'\n') 这样一写，\n 就不代表转义字符了，这个\n就是两个字符了
    这里会输出6

  只要是这种动不动进行遍历的，数据规模大的时候一般都不用，效率比较低
    count 能不用就不用，字符串的count个数问是题相当难的算法题
      'abcabc' 单独知道个数不够，还要知道出现在哪里了，所以才难
    index 少用  

3.find 方法介绍 也是找字符串子串 推荐使用find方法找子串
  s3='abcabc'
  s3.find('c')  这里会输出 2 
    默认从左开始搜索，找到第一个'c'，并返回他的索引
  
  s3.rfinf('c') 这里输出5
    默认从右开始搜索，找到第一个'c'，并返回他的索引
  find系方法，找不到，不会像index方法一样返回异常。find找不到就返回负数  
    我们一般用find的返回值 是不是大于等于0 >=0。大于等于0说明找到了

  find 也可以指定子区间 
    s4='www.magedu.edu'
    s4.find('edu',4,9) , s4.rfind('edu')  这个区间也是前包后不包
        -1                 11 
      先划定子区间，在子区间内找字符串
      带r是从右开始找
4.时间复杂度：
  find index count 方法都是O(n)
  随着字符串数据规模的增加，而效率下降

字符串的分割 1. a='1,2,3,a,b,c' a.split() split 立即返回一个列表,找到分隔符切断 这样写会输出['1','2','3','a','b','c']

a.split('3')  以'3'分割,‘3’所在的位置进行分割，把‘3’删除
      ['1,2',',a,b,c']

   b='\n\t\r\n a\nb\tc\t\n' #空格、换行符、tab，统称为空白字符space
   b.split() #缺省值来分割，开头结尾切一刀，不会多出空串。
         切割行为是：尽可能长的空白字符

   b.split('\n') 以/n分割。指定了切割符，你说切什么就切什么

   b.rsplit('\n') 从右向左开始切

   最大切割数：
   b.split('\n',2)  指定切割次数是两次

   b.splitlines() 切成多行

   d.partition(',') #立即返回三元组(part1,sep,part2) 相当于切一刀
   d.rpartition(',') 从字符串右侧开始切

字符串替换函数 replace() d='a+b+c' d.replace('+','-'，2) 2表示替换两次 输出为 'a-b-c' 把减号(-)替换为+ 。这个生成的是全新字符串。 python 中的字符串替换不是就地修改，而是生成一个全新的字符串 不支持模式匹配和替换，以后使用re

e='a***b***c***d***e***f***g'
e.replace('**', '*') ，此时e替换后会输出什么呢？
  a**b**c**d**e**f**g 会减少一个*

字符串的移除 b='\n\t\r\n a\nb\t \nc\r\n' b.strip() 移除了什么？ 会输出 'a\nb\t \nc' 这个字符串 括号里什么都不写把两端的空白字符都拿掉

b.strip('\n')  只移除了两端的指定的字符\n
  \t\r\n a\nb\t   \nc\r

b.strip('\t \nc\r')  两端拿掉字符集，跟字符的顺序无关

字符串首尾字符判断： a='1,2,3,a,b,c' a.startswitch('1') 这个字符串是用‘1’开头吗？ a.endswitch('c') 这个字符串是用‘1’结尾吗？ 这两个函数效率还是比较高的 a.startswitch('1'，2) 从下标2开始查询 前包后不包

a.split(',').pop().upper() + 'd'
  会输出'Cd' 一定要明白函数返回的类型

字符串的格式化： python这里print中输出换为了 % 1 "%d" %(i) C语言风格的输出 print("%d * %d = %d" %(3,4,12) ) %()百分号后面是一个元组，不能为 列表 2 print("My name is %(name)s, I am %(age)d" %{'age':20,'name':'mi'} ) %{}： 这里百分号后面是一个字典，根据小括号里的字符串，去字典中对应。 通过名字来找就跟顺序就无关了

3. age=20 name='Tom'
  f'{age} {name}' 差值字符串输出
  上面这些都是C风格的输出  
   %% ： 两个%，会输出一个%

4. 进制的问题
  %X ：十六进制输出
  %o  : 八进制输出

5. fommat 函数推荐使用
  位置或者关键字对应
  print("{0} {1} {2} {a} {b}".format(1,2,3,a=100,b=200))     
    a和b想输出，是靠名称找值，必须按照顺序写，因为是元组，大括号里面的是元组的下标，表示输出谁.
      a和b 按照名称对应，其余的按照顺序对应

  print( "{}".format( (1,22) ) )这里会输出 (1，22) 这是一个元组 

  print("{0[1]}-----{0}".format{(1,22)})
    这个0[1],会输出22 第0个元素，是元组，1，表示元组下标为0的值

  print("{}+++++{}".format{ *(1,22) }) 
    输出 '1++++22' 通过*号把这个变为了format(1,22)这是常用的

    class A:
       def __init__(self):
          self.x=5
          self.y=6

      t=A() 
      print("{} {}".format(t.x,t.y))  输出5 和6 不推荐

  import datetime
  d1 =datetime.datetime.now()
  
  print("{}".format(d1))  获取当前时间  
    2023-02-02 08:40:49.836858
    如何单独获取年、月、日？

    "{:%Y %y %M %m}".format(d1)  
      大写Y 输出2023 小写y输出23
      %M: 分钟 %m:月份 %d:日 %H：小时 %S:秒

    print("{:Y/%m/%d %H:%M:%S}".format(d1))
      输出：2023/02/02 09:03:17

编码与解码： 1.字节序列： bytes叫做字节序列 bytearray 也叫做字节序列，但是可变

这两个主要用于，编码和解码当中。

  "abc".endconde() str=>bytes 从字符串序列到字节序列
    b'abc' b说明是bytes类型，这个类型不可变

  bytes和bytearray这两个字节序列要转换为 str字符串 
  decode() 解码，把二进制码，变为字符串 默认解码 utf-8

  python 3 中字符串使用的是unicode

  在内存中，数据都是0和1，无差别的。当你指定某些字节，赋予数据类型的时候。这些数值就有了不同的理解。字符串类型，数值就要去找编码表了

  Cpython，C语言中字符串尾部都有结束符，就是null字符，长度多1


  中文  是双字节编码  
    gb2312 是大陆创建的编码表。gb指的是国家标准 国标。
      gb2312问题在于收录的太少了。之后出现了gbk.
    windows使用的内部就是gbk。 所谓gbk就是双字节系统，兼容
    ASCII

  unicode  iso 国际组织。需要兼容ASCLL。
    完成双字节把全世界已知字符装进去
    unicode 的问题在于始终用两个字节，描述ASCII 这样一个字节的
    也用了两个字节，浪费空间

  gbk和这个unicode 编码有映射关系的  

str 在字符的世界中，是有编码的，要查编码表
bytes 在字节的世界里，只有一个个字节，没有编码

互联网时代，传输数据，字节。为了解决单字符也传输两个字节的问题
为了适应网络传输，和为了能把全世界的文字收录在内，诞生了一种适合于网络
传输的编码方式  叫做 utf 。
  utf-8 变字长的编码1-6个字节表示。他能兼容所有字符
  ascii 单字节：中文字符绝大多数落在3个字节上 
  一些特殊符号需要4个字节
压缩，字符的压缩比非常大

字节序列：存在形式是二进制 bytes 不可变字节序列 bytearray 是可变字节数组

初始化：
  b1=bytes()  print(b1) 会输出 b'' 表示空字节，不可变类型，一但定义
                            不可修改
  b2 = b''                          
  b3 = bytes(5)
  b3 = b'\x00\x00\x00\x00\x00'   
  b4 = bytes('abc','utf-8')
  b4 = b'abc'
  b4 = 'abc'.encode('gbk')  
    对于ascii 码来说utf8 和gbk 得到的二进制是一样的 
  b6 = bytes(range(10)) 参数可以是可迭代对象
  b6 = bytes(range(0x30,0x3a))
    print(bytes(range(65, 91)))
    输出 b'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    bytes(range(65, 91，2)) 表示间隔为2

类方法构建：
  b'abc'.startswitch(b'ab')   
    b'abc'这个是对象

   bytes() 这个是用类来构建一个bytes对象
   bytes.fromhex() 没有bytes 对象，用类型，方法，构建一个bytes对象
            写字符串
   bytes.fromhex('')   括号里写字符串,求16进制的表达       
   hex(9) hex函数要数字

bytearray() 可变的这个，数组，list  
  bytearray(range(65,70))
  bytearray(b'ABCDE')

字节序： abc 它在内存中怎么放呢？ 对于一个字符串来讲，我们很容易知道谁是头谁是尾。把尾部放在大地址上。 我们把尾部放在大地址上的方式称为大端模式。 尾部如果放在小地址上，称为小端模式。几乎所有的字符串都采用了大端模式 地址顺序 0 1 2 3 4 5 6 7。 大端模式容易追加字符串

字符串采用了大端模式Big endian，把尾部字符往高地址放

对于 int类型，C语言，有1字节整型，无所谓大小端
  2字节开始，都存在大小端模式了
    2个字节：0x61 62 63 整数类型，大小端问题。

如何理解字节序呢？
  字节序就是一个多字节的数据类型，在内存中的分布方式。所谓多就是超过一个字节的数据在内存中的分布方式。一般采用大端模式。
    二进制数字，最低位是尾部

int 和bytes相互转化

切片： 只要有序就可以切片，可以索引的就可以切片 线性结构： list列表 tuple元组 str字符串 bytes 字节序列 bytearry

x=list(range(10))
  会输出 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
切片语法
  x[start:stop] 索引范围 叫做切片 
  x[index] 索引
  x[1:3] 输出 [1, 2] 前包含后不包含 输出下标1到下标3的元素
    start 为0，可以不写出来。stop如果是末位也可以不写
"abc" [1:-2] 切片的结果是本类型，列表切不出来就是空列表  

x[:] :从头到尾打印 x[::] x[::1]

x[::-1] :会逆序输出 [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
x[::2] :sep=2 步长为2 会输出 [0, 2, 4, 6, 8] 间隔为2输出一次

x[::-2] 负号代表从右侧开始输出 [9, 7, 5, 3, 1]
x[2:2] : 下标2开始走，步长为2

切片的本质： x=[1,2,3,4,5] y=x[:]

x==y 吗？  x is y 吗？ 这个两个会输出什么？
id()函数会输出对象的地址
x==y 输出true 内容相同，但是地址不同

切片本质，从start到stop，做一个区间，中间间隔使用step.把取出的元素合并成了一个本类型的对象。切片之后返回的是一个全新对象，会开辟新的内存空间

数据规模大，不推荐用切片

切片赋值问题 a=list(range(5)) 输出 [0, 1, 2, 3, 4]

print(id([1, 2, 3, ]))
   print(id([4, 5, 6, 7])) 为什么这两个列表会输出一样的地址值
   该如何解释呢？
      都输出了 1419619112256 这两个地址 
            1419619112256
      因为第一行输出完以后，没有变量进行记录，所以被垃圾回收了。第二行也同理。第一行是临时的变量，运行完就回收了。因此第二行可以在这里进行使用这个内存空间
   赋值既定义 

   a=[0,1,2,3,4]
   t=list()
   t[:]=a   t会输出 [0,1,2,3,4]  问题是 t==a吗？ t is a 吗？
      t与a内容相等，地址不同

   t[1:2] = 50 会出现语法错误，切片要赋值只能使用可迭代对象进行赋值
   t[1:2] = (50,) 换成元组就可以赋值了

   t=[0,10,11,12,13,14,15,16,17,18,19]
   t[1:3]=[20] 这个的意思就是把下标 1到2 这个范围替换为20因为只有一个
      数字20.所以这两个位置变为一个位置 最后输出
      [0,20,12,13,14,15,16,17,18,19] 
      这个就是切片赋值

切片赋值好吗？ 为什么？
   确实方便，但是不够好。因为两个空，变为一个空的时候会发生挪动。一旦数据规模过大，时间复杂度会很高，程序运行效率会变差

1. 求100以内的素数，要考虑时间复杂度，面试出这题并不简单，本质是问你
   1000000，以内的素数。不能大意，要特别小心
   22分钟


杨辉三角问题：   
   第一行和第二行都是1，中间这一行等于上一层两项之和
   第几行有几个数字
   第一行和第二行是特例

i=2 cur=[1] pre=[2-1]=[[1,1]]

j=2-1=1 循环一次从0开始循环 j会=0 cur.append(pre[0]+pre[0+1])

46分钟