刷题记录

• 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))