每天一道算法题（python）

目前的工作关于数据分类和图像识别，基础的算法题也是越来越生疏，在此记录时刻提醒自己是个菜鸟
题目一：冒泡排序

def bubble_sort(alist): for j in range(len(alist)-1,0,-1):# j表示每次遍历需要比较的次数，是逐渐减小的for i in range(j):if alist[i] > alist[i+1]:alist[i], alist[i+1] = alist[i+1], alist[i]
li = [54,26,93,17,77,31,44,55,20]
bubble_sort(li)
print(li)

题目二：选择排序

def selection_sort(alist):n = len(alist)# 需要进行n-1次选择操作for i in range(n-1):# 记录最小位置min_index = i# 从i+1位置到末尾选择出最小数据（找出索引）for j in range(i+1, n):if alist[j] < alist[min_index]:min_index = j# 如果选择出的数据不在正确位置，进行交换if min_index != i:#（数据交换）alist[i], alist[min_index] = alist[min_index], alist[i]alist = [54,226,93,17,77,31,44,55,20]
selection_sort(alist)
print(alist)

题目三：快速排序

def quick_sort(alist, start, end):# 递归的退出条件
if start >= end:return# 设定起始元素为要寻找位置的基准元素
mid = alist[start]# low为序列左边的由左向右移动的游标
low = start# high为序列右边的由右向左移动的游标
high = endwhile low < high:# 如果low与high未重合，high指向的元素不比基准元素小，则high向左移动while low < high and alist[high] >= mid:high -= 1# 将high指向的元素放到low的位置上alist[low] = alist[high]# 如果low与high未重合，low指向的元素比基准元素小，则low向右移动while low < high and alist[low] < mid:low += 1# 将low指向的元素放到high的位置上alist[high] = alist[low]# 退出循环后，low与high重合，此时所指位置为基准元素的正确位置
# 将基准元素放到该位置
alist[low] = mid# 对基准元素左边的子序列进行快速排序
quick_sort(alist, start, low-1)# 对基准元素右边的子序列进行快速排序
quick_sort(alist, low+1, end)alist = [54,26,93,17,77,31,44,55,20] quick_sort(alist,0,len(alist)-1)
print(alist)

题目四：互满数
如果有两个数，每个数的所有约数（除它本身以外）的和正好等于对方，则称这两个数互满数，求出3000内所有的互满数

def Sum(n):sum=0for i in range(1,n):if n%i==0:sum+=ireturn sum
print ("互满数为：")
for j in range(1,3000):k=Sum(j)if k>j and Sum(k)==j:print (j,"和",k)

题目五：无序表查找
最好情况是在第一个位置就找到了，此为O(1)；最坏情况在最后一个位置才找到，此为O(n)；所以平均查找次数为(n+1)/2。最终时间复杂度为O(n)

def sequential_search(lis, key):length = len(lis)for i in range(length):if lis[i] == key:return ielse:return Falseif __name__ == '__main__':LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]result = sequential_search(LIST, 123)print(result)

题目六：针对有序查找表的二分查找算法
时间复杂度O(log(n)）

def binary_search(lis, key):low = 0high = len(lis) - 1time = 0while low < high:time += 1mid = int((low + high) / 2)if key < lis[mid]:high = mid - 1elif key > lis[mid]:low = mid + 1else:# 打印折半的次数print("times: %s" % time)return midprint("times: %s" % time)return Falseif __name__ == '__main__':LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]#有序表result = binary_search(LIST, 99)print(result)

题目七：
抓了a,b,c,d四名犯罪嫌疑人，其中有一人是小偷，审讯中：
a说我不是小偷；
b说c是小偷；
c说小偷肯定是d；
d说c胡说！
其中有三个人说的是实话，一个人说的是假话，请编程推断谁是小偷（用穷举法和逻辑表达式）

def thief_is():for thief in ('a', 'b', 'c', 'd'):sum = ('a' != thief) + (thief == 'c') + \(thief == 'd') + (thief != 'd')if sum == 3:print("thief is %s"%thief)thief_is()

题目八：
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

#method1
def twosum(nums, target):l = len(nums)for i in range(l-1):for j in range(i+1, l):if nums[i]+nums[j] == target:return [i, j]#method2
def twosum(nums, target):l = len(nums)for i in range(l):another = target - nums[i]if another in nums:j = nums.index(another)if i==j:continueelse:return [i,j]]

题目九：数独
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
输入:
[
[“5”,“3”,".",".",“7”,".",".",".","."],
[“6”,".",".",“1”,“9”,“5”,".",".","."],
[".",“9”,“8”,".",".",".",".",“6”,"."],
[“8”,".",".",".",“6”,".",".",".",“3”],
[“4”,".",".",“8”,".",“3”,".",".",“1”],
[“7”,".",".",".",“2”,".",".",".",“6”],
[".",“6”,".",".",".",".",“2”,“8”,"."],
[".",".",".",“4”,“1”,“9”,".",".",“5”],
[".",".",".",".",“8”,".",".",“7”,“9”]
]
输出: true

def isValidSudoku(board):# 判断一行是否有效for i in range(9):for j in board[i]:if j != '.' and board[i].count(j) > 1:return False# 判断一列是否有效column = [k[i] for k in board]for n in column:if n != '.' and board[i].count[n] > 1:return False# 判断九宫格是否有效for i in range(3):for j in range(3):grid = [tem[j*3:(j+1)*3] for tem in board[i*3:(i+1)*3]]merge_str = grid[0] + grid[1] + grid[2]for m in merge_str:if m != '.' and merge_str.count(m) > 1:return Falsereturn True

题目十：
给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。说明：你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 :给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

#通过观察,旋转90度的效果等价于将矩阵沿着对角线对转,然后再沿着中间列对折,如下图所示(红色表示对称轴):
def rotate(matrix):length = len(matrix)for i in range(length):for j in range(i+1,length):temp = matrix[i][j]matrix[i][j] = matrix[j][i]matrix[j][i] = tempfor i in range(length):matrix[i] = matrix[i][::-1]

题目十一：贪心算法
一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。 对于给定的n(n <= 5000)和k(k <= 1000)个加油站位置，编程计算最少加油次数。

def greedy():n = 100k = 5d = [50,80,39,60,40,32]  # 表示加油站之间的距离num = 0 # 表示加油次数for i in range(k):if d[i] > n:print('no solution')# 如果距离中得到任何一个数值大于n 则无法计算return i, s = 0, 0# 利用s进行迭代while i <= k:s += d[i]if s >= n:# 当局部和大于n时则局部和更新为当前距离s = d[i]# 贪心意在令每一次加满油之后跑尽可能多的距离num += 1i += 1print(num)if __name__ == '__main__':greedy()

题目十二：ASCLL码
输入一行字符，分别统计出其中英文字母、空格、数字和其它字符的个数。

lst=list(input("请输入一行字符："))
iLetter=[]
iSpace=[]
iNumber=[]
iOther=[]
for i in lst:if ord(i) in range(65,91) or ord(i) in range(97,123):iLetter.append(i)elif i==" ":iSpace.append(" ")elif ord(i) in range(48,58):iNumber.append(i)else:iOther.append(i)
print ("英文字母个数：",len(iLetter),iLetter)
print ("空格个数:",len(iSpace))
print ("数字个数：",len(iNumber),iNumber)
print ("其它字符个数：",len(iOther),iOther)

题目十三：
一个整数，它加上100后是一个完全平方数，再加上268又是一个完全平方数，请问该数是多少？

from math import sqrt
if __name__ == "__main__":i = 1while i < 100000:#在10万以内判断a = int(sqrt(i + 100))b = int(sqrt(i + 268))if a **2 == (i + 100) and b **2 == (i + 268):print (i)i += 1

题目十四：
有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？

for i in range(1,5):for j in range(1,5):for k in range(1,5):if( i != k ) and (i != j) and (j != k):print （i,j,k）

题目十五：汉诺塔游戏

def hanoi(x, a, b, c):  # 所有的盘子从 a 移到 cif x > 0:hanoi(x-1, a, c, b)  # step1：除了下面最大的，剩余的盘子 从 a 移到 bprint('%s->%s' % (a, c))  # step2:最大的盘子从 a 移到 chanoi(x-1, b, a, c)  # step3: 把剩余的盘子 从 b 移到 chanoi(3, 'A', 'B', 'C')
#计算次数
def h(x):num = 1for i in range(x-1):num = 2*num +1print(num)
h(3)

题目十六：
有n个台阶，可以一次走上1个阶台，2个台阶，3个台阶。请问n个台阶，有几种走法。

def func(n):if n == 1:return 1elif n == 2:return 2elif n == 3:return 4return func(n - 1) + func(n - 2) + func(n - 3)
print(func(12))

题目十七：贪婪算法
贪婪算法，又名贪心算法，对于没有快速算法的问题（NP完全问题），就只能选择近似算法，贪婪算法寻找局部最优解，并企图以这种方式获得全局最优解，它易于实现、运行速度快，是一种不错的近似算法。假如你是个小偷，商店里有很多箱子，箱子里有各种水果，有些箱子里有3种水果，有些箱子有2种…，你想尝到所有种类的水果，但你一个人力气有限，因此你必须尽量搬走最少的箱子，所以你要搬走那些箱子呢？

fruits=set(["苹果","香蕉","梨子","西瓜","草莓","橘子","荔枝","榴莲"]) #箱子以及包含的水果
box={}
box["b1"]=set(["苹果","香蕉","西瓜"])
box["b2"]=set(["草莓","橘子","榴莲"])
box["b3"]=set(["梨子","荔枝","草莓"])
box["b4"]=set(["香蕉","橘子"])
box["b5"]=set(["梨子","榴莲"])final_boxs=set() #最终选择的箱子while fruits: #直到fruits为空best_box=None  #包含了最多的未包含水果的箱子fruits_covered=set()  #包含该箱子包含的所有未包含的水果#循环迭代每个箱子，并确定它是否为最佳箱子for boxItem,fruitItem in box.items():  #box.items()返回可遍历的元组（键、值）covered=fruits & fruitItem  #计算交集if len(covered)>len(fruits_covered):  best_box=boxItemfruits_covered=coveredfruits-=fruits_coveredfinal_boxs.add(best_box)print(final_boxs)  

题目十七：print相关
画出一个菱形

n=int(input("请输入一个数字："))
for i in range(n):for m in range(n -1- i):print(" ", sep='', end='')for j in range(2*i+1):print("*",sep='',end='')print("\n",sep='', end='')
for i in range(n):for m in range(i):print(" ", sep='', end='')for j in range(2*n-2*i-1):print("*",sep='',end='')print("\n",sep='', end='')
#end函数用来定义一行输出的末尾，默认为end=’\n’ 换行符，sep函数是设置分隔符，默认为sep=’ ’ 空格。默认的意思为不写，系统默认

题目十八：非极大值抑制（NMS）
#非极大值抑制

# --------------------------------------------------------
# Fast R-CNN
# Copyright (c) 2015 Microsoft
# Licensed under The MIT License [see LICENSE for details]
# Written by Ross Girshick
# --------------------------------------------------------# python3import numpy as npdef py_nms(dets, thresh):#x1、y1、x2、y2、以及score赋值x1 = dets[:, 0]y1 = dets[:, 1]x2 = dets[:, 2]y2 = dets[:, 3]scores = dets[:, 4]#print(scores) #只有第五列的参数[1.  0.9 0.8 0.7]#每一个候选框的面积areas = (x2 - x1 + 1) * (y2 - y1 + 1)#order是按照score降序排序的order = scores.argsort()[::-1]#print(order)keep = []while order.size > 0:i = order[0]keep.append(i)#计算当前概率最大矩形框与其他矩形框的相交框的坐标，会用到numpy的broadcast机制，得到的是向量xx1 = np.maximum(x1[i], x1[order[1:]])yy1 = np.maximum(y1[i], y1[order[1:]])xx2 = np.minimum(x2[i], x2[order[1:]])yy2 = np.minimum(y2[i], y2[order[1:]])#计算相交框的面积,注意矩形框不相交时w或h算出来会是负数，用0代替w = np.maximum(0.0, xx2 - xx1 + 1)h = np.maximum(0.0, yy2 - yy1 + 1)inter = w * h#计算重叠度IOU：重叠面积/（面积1+面积2-重叠面积）ovr = inter / (areas[i] + areas[order[1:]] - inter)#找到重叠度不高于阈值的矩形框索引inds = np.where(ovr <= thresh)[0]print(order)#将order序列更新，由于前面得到的矩形框索引要比矩形框在原order序列中的索引小1，所以要把这个1加回来order = order[inds + 1]print(order)return keep#test
if __name__ == "__main__":dets = np.array([[30, 20, 230, 200, 1], [50, 50, 260, 220, 0.9],[210, 30, 420, 5, 0.8],[430, 280, 460, 360, 0.7]])thresh = 0.35keep_dets = py_nms(dets, thresh)print(keep_dets)print(dets[keep_dets])

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！