python刷题记录
2021/7/26 12:06:00
本文主要是介绍python刷题记录,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
刷题记录
- 1.python输入输出
- 2.排序算法
- 3.字符串的全排列
- 4.三数之和
- 5.无重复字符的最长子串
- 6.字典的使用dict
- 7. 验证是否回文子串
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))
这篇关于python刷题记录的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-14Python编程入门指南
- 2024-11-13Python基础教程
- 2024-11-12Python编程基础指南
- 2024-11-12Python基础编程教程
- 2024-11-08Python编程基础与实践示例
- 2024-11-07Python编程基础指南
- 2024-11-06Python编程基础入门指南
- 2024-11-06怎么使用python 计算两个GPS的距离功能-icode9专业技术文章分享
- 2024-11-06Python 基础编程入门教程
- 2024-11-05Python编程基础:变量与类型