刷题记录
1.python输入输出
总结了笔试过程中经常需要用到的输入输出方式：
- 字符串的拆分方法
string对象的split方法，不允许有多个分隔符
函数re.split()，允许为分隔符指定多个正则表达式
str.split(字符串切片)\str.find(查找字符)\str.strip(去除首尾指定字符)
#1.单个分隔符
line2=line.split()#只能分割一种符号，默认为空格，可指定‘，’
print(line2) #['asdf fjdk', ' afed, fjek,asdf, foo']
#2.多个分隔符
import re
line = 'asdf fjdk; afed, fjek,asdf, foo'
line1=re.split(r'[;,\s]\s*', line)#调用方式[]中为分隔符
print(line1) #['asdf', 'fjdk', 'afed', 'fjek', 'asdf', 'foo']
#一行键盘输入
#1.知道输入的个数 推荐
n,k,m=map(int,input().split())
#2.输入转为列表，int,str 推荐
line=list(map(int,input().split()))
print(line)
#3.读入一维矩阵(也是列表，，，
arr = input("") #输入一个一维数组，每个数之间使空格隔开
num = [int(n) for n in arr.split()] #将输入每个数以空格键隔开做成数组
print(num) #打印数组
#处理多行输入
#4.读入二维矩阵适用于n*n矩阵
n = int(input()) #输入二维数组的行数和列数
m = [[0]*n]*n #初始化二维数组
for i in range(n):
#m[i] = input().split(" ") #输入二维数组，同行数字用空格分隔，不同行则用回车换行
m[i] = list(map(int,input().split(" "))) #输入二维数组，同行数字用空格分隔，不同行则用回车换行
print(m) #打印二维数组
#5.读入二维矩阵适用于n*任意列矩阵，缺点是必须要知道有多少行的输入
n=int(input())
m=[]
for i in range(n):
m.append(list(map(int,input().split(" "))))
#m.append(list(map(float,input().split(" "))))
print(m) #输入二维数组，同行数字用空格分隔，不同行则用回车换行print(m)
#6.读取多行输入，不知道多少行，但肯定是以换行符结束，输出是一维列表形式
import sys
s = []
for line in iter(input, ''):
s.append(line.replace(',',''))
print(s)
7.不指定行数 输入多行数据 返回二维list（最实用） 推荐
#不指定输入的行数，但是必须以最后下一行只输入空格或者什么都不输入为结束
#import sys
mx = []
while True:
#m = sys.stdin.readline().strip()
m = input().strip() #若是多输入，strip()默认是以空格分隔，返回一个包含多个字符串的list。
if m == '':
break
#m = list(m.split()) #字符串格式
m=list(map(int,m.split())) #int格式
mx.append(m)
print(mx)
2.排序算法
#猪猪教我的排序算法
#1.冒泡排序（两两比较，交换位置）:外循环遍历所有数，内循环是逐渐找到最大的放后面，所以每次内循环的次数会降低
def bubble(nums):
for i in range(len(nums)):
for j in range(1,len(nums)-i):
if nums[j-1]>nums[j]:
nums[j-1],nums[j] = nums[j],nums[j-1]
return nums
#2.选择排序（选择基准）:每次外循环，都是以当前index为基准，在内循环里与index后的数进行比较交换
def selection(nums):
for i in range(len(nums)):
index=i
for j in range(i,len(nums)):
if nums[j]<nums[index]:
index = j
nums[index],nums[i]=nums[i],nums[index]
return nums
#3.插入排序：外循环即遍历除第一次基准数外的所有数，接下来，将当前tmp与前面已排数组相比，逐个往前倒序遍历比较，小的在前面
def insertion(nums):
for i in range(1,len(nums)):
tmp=nums[i]
for j in range(i-1,-1,-1):
if nums[j] > tmp:
nums[j],nums[j+1] = nums[j+1], nums[j]
return nums
#4.快速排序：左右分区，进行递归。
def quicksort(nums,left,right):
if left >= right:return nums
temp=left
i=left
j=right
while i<j:
while i<j and nums[j]>nums[temp]:
j -= 1
while i<j and nums[i]<=nums[temp]:
i += 1
nums[i],nums[j] = nums[j],nums[i]
nums[temp],nums[j]= nums[j],nums[temp]
quicksort(nums,left,j-1)
quicksort(nums,j+1,right)
return nums
#5.计数排序：
def countsort(nums):
if not nums:return ''
min_nums=min(nums)
max_nums=max(nums)
length=max_nums-min_nums+1
tmp=[0]*length
for num in nums:
tmp[num-min_nums] +=1
index=0
for i in range(length):
while tmp[i] != 0:
nums[index] = i+min_nums
tmp[i] -=1
index +=1
return nums
#6.shell排序:复杂度无法分析
def shellsort(nums):
h=0
while h<len(nums)/2:
h = h*2+1
while h>=1:
for i in range(h,len(nums)):
for j in range(i-h,-1,-h):
if nums[j] >nums[j+h]:
nums[j],nums[j+h]=nums[j+h],nums[j]
else:
break
h=h//2
return nums
#7.归并排序
def mergesort(nums,left,right):
#两路归并函数
def merge(nums, left, right):
mid=(left+right)//2
i=left
j=mid+1
index=left
res=[0]*len(nums)
while i<=mid and j<=right:
if nums[i]<=nums[j]:
res[index]=nums[i]
i +=1
else:
res[index]=nums[j]
j +=1
index += 1
while i<=mid:
res[index]=nums[i]
index +=1
i +=1
while j<=right:
res[index]=nums[j]
index +=1
j +=1
for i in range(left,right+1):
nums[i]=res[i]
return nums
#递归结束条件
if left >= right :
return nums
#分组，分子序列
mid=(left+right)//2
mergesort(nums,left,mid)
mergesort(nums,mid+1,right)
#调用函数归并
merge(nums,left,right)
return nums
#调用方法
if __name__ == "__main__":
nums = [4, 6, 1, 3, 6, 9, 1, 2]
#a=quicksort(nums,0,len(nums)-1)
a = mergesort(nums,0,len(nums)-1)
print(a)
3.字符串的全排列
#有重复字符串的排列组合
def permutation(s: str):
ans_all = []
s = sorted(s)
def dfs(s, ans):
if not s: ans_all.append(ans)
i = 0
while i < len(s):
dfs(s[0:i] + s[i + 1:], ans + s[i])
while i + 1 < len(s) and s[i] == s[i + 1]: i += 1
i += 1
dfs(s, '')
return ans_all
s = "qqe"
print(permutation(s))
#无重复字符串的排列组合
def permutation(s: str):
if len(s) == 0:
return []
def back(cur, res): # 第一个参数代表当前的组合，第二个参数代表待选的元素
if len(res) == 0: # 回溯跳出的条件，如果没有元素可以选择了，则将cur组成字符串然后压入结果集
result.append(''.join(cur))
return
for idx, charater in enumerate(res): # 如果res不为空
cur.append(charater)
back(cur, res[:idx] + res[idx + 1:]) # 回溯
cur.pop()
result = []
back([], list(s))
return result
s = "qwe"
print(permutation(s))
4.三数之和
中级算法：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
def threesum(nums):
nums.sort() #先进行排序
res=[]
if len(nums)<3:return []
i=0
for i in range(len(nums)-2):
if i>0 and nums[i]==nums[i-1]:#如果有重复的，跳过，i+1
continue
left,right=i+1,len(nums)-1 #定义左右指针
while left<right:
if nums[i]+nums[left]+nums[right]<0: #小于0说明，left需要增加
left +=1
elif nums[i]+nums[left]+nums[right]>0:#大于0，right需要减小
right -=1
else:
res.append([nums[i],nums[left],nums[right]]) #把结果加入res
#指针去重
while left<right and nums[right]==nums[right-1]:right -=1
while left<right and nums[left]==nums[left+1]:left +=1
left += 1
right -= 1
return res
nums = [-2,0,1,1,2] #[-2,0,0,2,2]
print(threesum(nums)
5.无重复字符的最长子串
中级算法：给定一个字符串 s ，请你找出其中不含有重复字符的最长子串 的长度。
def lengthOfLongestSubstring(s):
if not s:return 0
left=0
lookup=set()
maxlen=curlen=0
n=len(s)
for i in range(n):
curlen +=1 #遍历字符串，子串的个数
while s[i] in lookup: #如果当前是s[i]已经存在字串中，
lookup.remove(s[left]) #把第一个是字符舍弃，窗口往前移动。
left +=1 #子串的起始位置+1
curlen -=1 #保持窗口长度
if curlen>maxlen:
maxlen=curlen #更新maxlen
lookup.add(s[i]) #加入该s[i]
return maxlen
#用字典：依次遍历i之后的数，不重复则加入字典，重复则跳出，并记录当前子串的长度
# if not s:
# print(0)
# else:
# dict1={}
# a=[]
# for i in range(len(s)):
# dict1[s[i]]=i
# for j in range(i+1,len(s)):
# if s[j] not in dict1:
# dict1[s[j]]=j
# else:
# break
# a.append(len(list(dict1.keys())))
# dict1 = {}
# print(max(a))
6.字典的使用dict
#求字符串中重复次数最少的字母
s="wwssefefcsfc"
dict1={} #创建字典
for i in s:
if i not in dict1:
dict1[i]=1
else:
dict1[i] +=1
print(dict1)#打印字典
print(list(dict1.values()))#打印字典的值
print(list(dict1.keys()))#打印字典的键
print(list(dict1.items()))#打印字典的键-值对
print(sorted(dict1.keys()))#打印排序后的键
print(list(sorted(dict1.values())))#打印排序后的值
for i in sorted(dict1.keys()):
if dict1[i] ==list(sorted(dict1.values()))[0]:
print(i) #重复次数最少的键
7. 验证是否回文子串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
def huiwen(s):
new=s.lower() #字母都转为小写、、大写s.upper()
res = ''.join([x for x in new if x.isalpha() or x.isdigit()]) #过滤其余符号，只有数字和字母添进res中
left=0
right=len(res)-1
while left<=right:
if res[left]!=res[right]:
return False
break
left +=1
right -=1
return True
s="A man, a plan, a canal: Panama"
print(huiwen(s))