最近在跟着B站的视频(aHR0cHM6Ly93d3cuYmlsaWJpbGkuY29tL3ZpZGVvL0JWMW5xNHkxazdCNA==)学习,完整看完了,记的所有笔记,这些题目也可灵活多变,你可以思考,如何去使用C、JAVA、GO等语言实现,记得留在评论区,一起学习,共同成长。
题目1:水仙花数
水仙花数(Narcissistic number)也被称为超完全数字不变数(pluperfect digital invariant, PPDI)、自恋数、自幂数、阿姆斯壮数或阿姆斯特朗数(Armstrong number),水仙花数是指一个 3 位数,它的每个位上的数字的 3次幂之和等于它本身。例如:1^3 + 5^3+ 3^3 = 153。
for i in range(100, 1000): i1 = i // 100 # 取百位数字 123//100=1 i2 = i // 10 % 10 # 取十位数字 123//10=12 12%10=2 i3 = i % 10 # 取个位数字 123%10=3 if i1 ** 3 + i2 ** 3 + i3 ** 3 == i: print(f"{i}是水仙花数") # 153 是水仙花数 # 370 是水仙花数 # 371 是水仙花数 # 407 是水仙花数
题目2:四叶玫瑰数
四叶玫瑰数是4位数的自幂数。自幂数是指一个 n 位数,它的每个位上的数字的 n 次幂之和等于它本身。(例如:当n为3时,有1^3 + 5^3 + 3^3 = 153,153即是n为3时的一个自幂数,3位数的自幂数被称为水仙花数)。
for i in range(1000,10000): i1 = i // 1000 # 取千位数字 1234//1000=1 i2 = i // 100 % 10 # 取百位数字 1234//100=12 12%10=2 i3 = i // 10 % 10 # 取十位数字 1234//10=123 123%10=3 i4 = i % 10 # 取个位数字 1234%10=4 # print(i,i1,i2,i3,i4) if i1 ** 4 + i2 ** 4 + i3 ** 4 + i4 ** 4 == i: print(f'{i}是四叶玫瑰数') # 1634 是四叶玫瑰数 # 8208 是四叶玫瑰数 # 9474 是四叶玫瑰数
题目3:逆序输出字符串
# 写法1:切片方式str = input("请输入字符串")print(str[::-1])# 写法2:循环转换str = input("请输入字符串")list = []for x in range(len(str) -1,-1,-1): list.append(str[x])print(''.join(list))
题目4:猜数字小游戏
需求分析:
- 随机生成一个100以内的整数,共有10次机会
- 开始游戏,输入猜测的数字
- 如果猜小了,提示猜小了
- 如果猜大了,提示猜大了
- 猜对了,提示猜对了,并且结束游戏
- 10次机会用完还没猜对,提示游戏结束,没有猜到。
import random as rdnumber = rd.randint(0,100)for i in range(10): choice = int(input("请输入你要猜测的数字:")) if choice > number: print("你猜大了") elif choice < number: print("你猜小了") else: print("你猜对了,真棒!") print(f'你一共用了{i + 1}次机会') break print(f'还剩{9 - i}次机会')else: print('游戏结束,你没有猜到')
题目5:百鸡百钱
需求分析:
- 公鸡每只5元,母鸡每只3元,小鸡3只一元,现要求用100元钱买100只鸡(三种类型的鸡都要买),问公鸡、母鸡、小鸡各买几只?
- 数学:
- 设公鸡买了x只,母鸡买了y只,小鸡买了z只
- x+y+z= 100
5x+3y+z/3 = 100
算法思路
- 以公鸡为突破点,公鸡5元一只,100元最多只能买20只,
- 由于三种鸡都要买,所以公鸡数一定是小于20的。
- 母鸡每只3元,100全拿来买母鸡,最多也不能超过33只
- 设公鸡数为x,母鸡数为y,小鸡z只
- 只要满足5x+3y+z/3=100 和 x+y+z==100 就可以输出此种组合的结果.
count = 0for x in range(1,20): for y in range(1,33): z = 100 - x -y if z > 0 and 5 * x + 3 * y + z / 3 == 100: count += 1 print("="*60) print(f'第{count}种买法,公鸡买了{x}只,母鸡买了{y}只,小鸡买了{z}只') # == == == == == == == == == == == == == == == == == == == == == == == == == == == == == == # 第1种买法,公鸡买了4只,母鸡买了18只,小鸡买了78只 # == == == == == == == == == == == == == == == == == == == == == == == == == == == == == == # 第2种买法,公鸡买了8只,母鸡买了11只,小鸡买了81只 # == == == == == == == == == == == == == == == == == == == == == == == == == == == == == == # 第3种买法,公鸡买了12只,母鸡买了4只,小鸡买了84只
题目6:闰年问题升级版
输入年月日,输出该日期是否是闰年,并且输出该日期是此年份的第几天
闰年判断条件:
- 能被4整除,并且不能被100整除
- 能被400整除
- 两个条件满足任意一个就为闰年
算法思路
- 接收用户输入的年月日,创建保存12个月份天数的列表
- 根据年份判断是否是闰年,如果是把二月份设为29天,否则把二月份设为28天
- 根据月份和日期统计是当年的第几天
year = int(input("请输入年份"))month = int(input("请输入月份"))day = int(input("请输入日期"))date_list = [31,29,31,30,31,30,31,31,30,31,30,31]count_day = dayif year % 4 == 0 and year % 100 !=0 or year % 400 == 0: print(f'{year}年是闰年') date_list[1]=29else: print(f'{year}年是平年') date_list[1]=28for i in range(month-1): count_day += date_list[i]print(f'{year}年{month}月{day}日是当年的第{count_day}天')
题目7:猴子吃桃问题
需求分析:
猴子第一天摘下若干个桃子,当即吃了一半,还不过瘾,又多吃了一个。
第二天早上又将剩下的桃子吃掉一半,又多吃了一个。
以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时,见只剩下一个桃子了。
求原来它一共摘了多少个桃子。
这题得倒着推。第10天还没吃,就剩1个,说明第9天吃完一半再吃1个还剩1个。
假设第9天还没吃之前有桃子p个
可得:p/2 - 1 = 1,得出第九天的桃子数p=4。
以此类推,即可算出第一天摘了多少桃子.
算法思路
- 第10天还没吃之前的桃子数量初始化p=1
- 从9至1循环9次,根据上述公式反推为p=(p+1)*2可得
- 第1天还没吃之前的桃子数量
p = 1print(f'第10天还剩下{p}个桃子')for i in range(9,0,-1): p = (p + 1) * 2 print(f'第{i}天还剩下{p}个桃子')print(f'第一天一共摘了{p}个桃子')# 第10天还剩下1个桃子# 第9天还剩下4个桃子# 第8天还剩下10个桃子# 第7天还剩下22个桃子# 第6天还剩下46个桃子# 第5天还剩下94个桃子# 第4天还剩下190个桃子# 第3天还剩下382个桃子# 第2天还剩下766个桃子# 第1天还剩下1534个桃子# 第一天一共摘了1534个桃子
题目8:冒泡排序
冒泡排序算法由来
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”
从前到后(即从下标较小的元素开始) 依次比较相邻元素的值,若发现比后一个值大则交换位置,使值较大的元素逐渐从前移向后部。
假设有一个列表 [29 ,12 ,19 ,37 ,14] 想升序
第一轮
- 比较 29 > 12 交换位置
- [12,29,19,37,14]
- 比较 29 > 19 交换位置
- [12,19,29,37,14]
- 比较 29 > 37 不大于 不交换,列表同上
- 比较 37 > 14 交换位置
- [12,19,29,14,37]
第二轮
- 比较 12 > 19 不大于 不交换,列表同上
- 比较 19 > 29 不大于 不交换,列表同上
- 比较 29 > 14 交换位置
- [12,19,14,29,37]
第三轮
- 比较 12 > 19 不大于 不交换,列表同上
- 比较 19 > 14 交换位置
- [12,14,19,29,37]
第四轮
- 比较 12 > 14 不大于 不交换,列表同上
- 完成
- [12,14,19,29,37]
import numpy as nppop_list = np.random.randint(100,size=6)# pop_list = [82,15,15,41,37,31]# pop_list = [29,12,19,37,14]count = len(pop_list)print('没排序之前的列表',pop_list)for i in range(count-1): for j in range(count-i-1): if pop_list[j] > pop_list[j + 1]: # 如果要降序就是改成 < 号 pop_list[j],pop_list[j+1] = pop_list[j+1],pop_list[j]print('排好序的列表为',pop_list)# 排好序的列表为 [15, 15, 31, 37, 41, 82]# 排好序的列表为 [12, 14, 19, 29, 37]
题目9:二分查找法
二分法是一种效率比较高的搜索方法
回忆之前做过的猜数字的小游戏,预先给定一个小于100的正整数x,让你猜,猜测过程中给予大小判断的提示,问你怎样快速地猜出来? 我们之前做的游戏给定的是10次机会,如果我们学会二分查找法以后,不管数字是多少,最多只需要7次就能猜到数字
二分查找法
首先先猜50,如果猜对了,结束;如果猜大了,往小的方向猜,再猜25;如果猜小了,往大的方向猜,再猜75;...每猜测1次就去掉一半的数,这样我们就可以逐步逼近预先给定的数字.这种思想就是二分法。
二分法适用情况
- 必须是有序的序列。
- 对数据量大小有要求。
- 数据量太小不适合二分查找,与直接遍历相比效率提升不明显。
- 数据量太大也不适合用二分查找,因为数组需要连续的存储空间,若数据量太大,往往找不到存储如此大规模数据的连续内存空间
算法思路
- 假设有一个有序列表
- [5,7,11,22,27,33,39,52,58] 请问数字11是否在此列表中,如果在它的索引值为多少?
- 首先我们取有序列表的中间位置 27 和 11 进行比较 我们发现 11 是小于 27 的
- 所以我们排除 27 右边的数字
- [5,7,11,22,27(排除了右边的),33,39,52,58]
- 接着我们取 [5,7,11,22] 位置中间的 7 和 11 比较 发现 11 是大于 7 的 所以我们排除 7 左边的数字
- 最后我们取 11到22 的中间位置
- 刚好到了11 这时候就可以返回 11 的索引值了,如果没有找到就提示不存在
第一种 纯算法的方式
arr_list = [5,7,11,22,27,33,39,52,58]number = 11count = 0left = 0right = len(arr_list)-1while left<=right: middle = (left+right)//2 count += 1 if number > arr_list[middle]: left = middle +1 elif number < arr_list[middle]: right = middle - 1 else: print(f'数字{number}已找到,索引值为{middle}') breakelse: print(f'数字{number}没有找到')print(f'一共用了{count}次查找') 数字11已找到,索引值为2 一共用了3次查找
第二种 递归函数的方式
arr_list = [5,7,11,22,27,33,39,52,58]def binary_search(number,left,right): if left <= right: middle = (left + right) // 2 if number < arr_list[middle]: right = middle - 1 elif number > arr_list[middle]: left = middle + 1 else: return middle return binary_search(number,left,right) else: return -1print(binary_search(11,0,len(arr_list)-1))
题目10:选择排序
基本思想:从未排序的序列中找到一个最小的元素,放到第一位,再从剩余未排序的序列中找到最小的元素,放到第二位,依此类推,直到所有元素都排序完毕
- 若列表 [6,8,3,5,9,10,7,2,4,1]
- 先找到 1 最小 调换
- [1, 8, 3, 5, 9, 10, 7, 2, 4, 6]
- 接着是 2 最小 调换
- [1, 2, 3, 5, 9, 10, 7, 8, 4, 6]
- 接着是 3 最小 位置不变
- 接着是 4 最小 调换
- [1, 2, 3, 4, 9, 10, 7, 8, 5, 6]
- 接着是 5 最小 调换
- [1, 2, 3, 4, 5, 10, 7, 8, 9, 6]
- 接着是 6 最小 调换
- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
- 接着是 7 最小 位置不变
- 接着是 8 最小 位置不变
- 接着是 9 最小 位置不变
- 接着是 10 最小 位置不变
import random as rdsec_list = [rd.randint(1,100) for i in range(8)]# sec_list = [91,30,93,98,26,98,20,90]length = len(sec_list)print(f'未排序的列表为:{sec_list}')for i in range(length -1): min_index = i for j in range(i + 1,length): if sec_list[min_index] > sec_list[j]: min_index = j sec_list[min_index],sec_list[i] = sec_list[i],sec_list[min_index] print(f'第{i+1}轮排好序是:{sec_list}')print(f'最终排好序的列表为:{sec_list}')# 未排序的列表为:[91, 30, 93, 98, 26, 98, 20, 90]# 第1轮排好序是:[20, 30, 93, 98, 26, 98, 91, 90]# 第2轮排好序是:[20, 26, 93, 98, 30, 98, 91, 90]# 第3轮排好序是:[20, 26, 30, 98, 93, 98, 91, 90]# 第4轮排好序是:[20, 26, 30, 90, 93, 98, 91, 98]# 第5轮排好序是:[20, 26, 30, 90, 91, 98, 93, 98]# 第6轮排好序是:[20, 26, 30, 90, 91, 93, 98, 98]# 第7轮排好序是:[20, 26, 30, 90, 91, 93, 98, 98]# 最终排好序的列表为:[20, 26, 30, 90, 91, 93, 98, 98]
题目11:剪刀石头布
游戏开始,初始状态下用户和电脑都有100分,赢一局+10分,输一局-10分。当用户为0分时,游戏结束,提示游戏结束,比赛输了,当用户为200分时,游戏结束,提示游戏结束,赢得比赛、每轮比赛都输出当前的分数
1代表剪刀 2代表石头 3代表布
import random as rdprint('=' * 60)print(' ' * 20, '剪刀石头布游戏')print('1代表剪刀 2代表石头 3代表布')game_info = {1: "剪刀", 2: "石头", 3: "布"}score = 100while True: robots_choice = rd.randint(1, 3) user_choice = input("请出拳") if user_choice not in '123': print('出拳错误,请重新出拳') continue user_choice = int(user_choice) print('*' * 60) print(f'电脑出{game_info[robots_choice]}') print(f'你出{game_info[user_choice]}') print('*' * 60) if user_choice == 1 and robots_choice == 3 or user_choice == 2 \ and robots_choice == 1 or user_choice == 3 and robots_choice == 2: score += 10 print(f'你赢得本轮游戏,当前分数为{score}') elif user_choice == robots_choice: print(f'本轮游戏平局,当前分数为{score}') else: score -= 10 print(f'你输了本轮游戏,当前分数{score}') if score >= 200: print('游戏结束,你赢得比赛') break elif score <= 0: print('游戏结束,你输了') break
题目12:快乐数
在给定的数字下,该数字所有数位(digits)的平方和,得到的新数再次求所有数位的平方和,如此重复进行,最终结果必定为1
比如数字:19
- 1 1 = 1 9 9 = 81 = 1 + 81 = 82
- 8 8 = 64 2 2 = 4 = 64 + 4 = 68
- 6 6 = 36 8 8 = 64 = 36 + 64 = 100
- 1 + 0 + 0 = 1
def sum_square(n): sum = 0 for i in str(n): sum += int(i) ** 2 return sumlist1 = []n = int(input('请输入数字:'))while sum_square(n) not in list1: n = sum_square(n) list1.append(n)if n == 1: print('是快乐数')else: print('不是快乐数')
题目13:猜年龄(一)
- 小明带两个妹妹参加元宵灯会。别人问她们多大了,她们调皮地说:“我们俩的年龄之积是年龄之和的6倍“。
- 小明又补充说:“她们可不是双胞胎,年龄差肯定也不超过8岁啊。“
- 请你写出:小明的较小的妹妹的年龄。
for i in range(1,100): for j in range(1,i): if i*j == 6*(i+j) and i-j<8: print(i,j)# 15 10
题目14:猜年龄(二)
美国数学家维纳(N.Wiener)智力早熟,11岁就上了大学。
他曾在1935~1936年应邀来中国清华大学讲学。
一次,他参加某个重要会议,年轻的脸孔引人注目。于是有人询问他的年龄,
他回答说:“我年龄的立方是个4位数。我年龄的4次方是个6位数。
这10个数字正好包含了从0到9这10个数字,每个都恰好出现1次。“
请你推算一下,他当时到底有多年轻
for i in range(10,30): i3 = str(i ** 3) i4 = str(i ** 4) if len(i3) == 4 and len(i4) == 6: if len(set(i3+i4)) == 10: print(i) print(i3 + i4)# 18# 5832104976
题目15:split算法实现
- split是python字符串内置的一个非常有用的方法它可以将一个字符串通过分隔符切成我们想要的列表比如现在我们有个字符串
- life-is-short-you-need-python
- 每一个单词之间使用横杆进行分割,当我们去调用字符串split的方法之后传入我们的分隔符横杆 - 那我们就会得到一个列表列表里面每个元素其实就是通过分隔符切出来的子字符串
- 那这个算法该怎么样去实现呢?python内置的split方法是通过C语言实现的,我们今天去写一个函数,去实现和split相同的功能
- 我们先来讲下算法该怎么样去实现这个算法需要我们对字符串进行迭代,我们先去定义一个初始化的指针,因为我们切片的时候需要从哪一个开始的位置进行切,所以我们先要初始化一个指针
- 我们可以定义一个指针变量,默认值为0,紧接着我们开始对字符串进行迭代,当碰到第一个分隔符的时候,我们是不是会获取到当前分隔符的索引,那这个时候,我们就把初始的指针开始到分隔符结束对字符串进行切片
- 因为我们字符串是遵守左闭右开的,你的结束索引写的是分隔符的索引,所以只会切到life,我们并把它添加到列表里面,紧接着添加完之后呢,我们需要把初始化的指针修改一下位置,修改到哪个地方呢?修改到我们第一次碰到的分隔符的下一个位置
- 也就是i,紧接着继续进行迭代,迭代之后发现第二个分隔符,是不是还有一个分隔符的索引,这个时候我们继续向字符串进行切片,切片的开始位置是你的i这个位置的指针,结束的位置是第二个 - 的指针,那遵循左闭右开,所以我们is这个单词,也可以添加进列表
- 就这样一直到最后呢,当我们去迭代到最后一个字符n的时候,发现后面是没有横杆分隔符了,这个时候我们需要进行处理一下,需要进行去判断一下,如果我们迭代到的字符是最后一个字符,那么我们进行切片的时候,就应该从哪个地方切呢?
- 从p开始 ,如果切到n,我们只能取到pytho,少切一个n,所以到n + 1的位置,好,知道这个流程我们就用代码去实现这个算法
def split_s(string, sep="", num=0): split_words = [] last_index = 0 count = 0 for index, char in enumerate(string): if count == num and num > 0: split_words.append(string[last_index:len(string)]) break if char == sep: split_words.append(string[last_index:index]) last_index = index + 1 count += 1 elif index + 1 == len(string): split_words.append(string[last_index:index + 1]) return split_wordsprint(split_s("life-is-short-you-need-python",'-'))# ['life', 'is', 'short', 'you', 'need', 'python']print(split_s("life-is-short-you-need-python",'-',2))# ['life', 'is', 'short-you-need-python']
题目16:大衍数列
中国古代文献中,曾记载过“大衍数列”,主要用于解释中国传统文化中的太极衍生原理
它的前几项是:0、2、4、8、12、18、24、32、40、50...
其规律是:偶数项,是序号平方再除2,奇数项,是序号平方减1再除2。
打印大衍数列的前100项
for x in range(1,101): if x % 2 == 0: # 偶数 a = int((x ** 2) / 2) else: # 奇数 a = int((x ** 2 - 1) / 2) print(a)# 0# 2# 4# 8# 12# 18# 24# 32# 40# 50
题目17:单词分析
- 小蓝正在学习一门神奇的语言,这门语言中的单词都是由小写英文字母组成,有些单词很长,远远超过正常英文单词的长度。小蓝学了很长时间也记不住一些单词,他准备不再完全记忆这些单词,而是根据单词中哪个字母出现得最多来分辨单词
- 现在,请你帮助小蓝,给了一个单词后,帮助他找到出现最多的字母和这个字母出现的次数
- 其实就是让你输入一段字符串后,得到当前字符串出现最多的字母和它的次数
- 输入:HelloWorld
- 输出:
- l
- 3
- 我们可以对当前的字符串进行循环迭代,然后把字符串当前每个字符当作key值,把它存到字典里面,如果当前key在字典里面,我们就让它加一,如果不在那我们就让它的次数初始化为1,最终我们再从字典找到次数最多的key值和value值
def analyse_words(words): word_dict = {} for i in words: if i in word_dict: word_dict[i] += 1 else: word_dict[i] = 1 max_key = max(word_dict,key=word_dict.get) print(max_key) print(word_dict[max_key]) # l # 3analyse_words('helloworld')
题目18:利用栈打印菱形
输入边长n,打印对应边长的菱形
分析:
- 打印几行
- 每一行打印几个空格,几个星星
- 前几行打印之前加入到栈,利用栈的后进先出原则打印后几行的内容
def diamond(n): stack = [] for i in range(1, 2 * n): if i <= n: p_str = ' ' * (n - i) + '*' * (2 * i - 1) if i != n: stack.append(p_str) print(p_str) else: print(stack.pop())diamond(5)# 为了区分我把空格换成了点# ....*# ...***# ..*****# .*******# *********# .*******# ..*****# ...***# ....*
题目19:深入理解递归函数
什么是递归函数?
递归函数就是一个函数在它的函数体内调用它自身。执行递归函数将反复调用其自身,每调用一次就进入新的一层。
递归函数必须有结束条件。
设计递归函数三要素:
- 明确你这个函数想要干什么
- 寻找递归结束条件
- 找出函数的等价关系式
def p(n): if n == 0: return print('递归前->',n) p(n-1) print('递归后->',n)p(5)# 递归前-> 5# 递归前-> 4# 递归前-> 3# 递归前-> 2# 递归前-> 1# 递归后-> 1# 递归后-> 2# 递归后-> 3# 递归后-> 4# 递归后-> 5
题目20:斐波那契递归函数
斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:
1、1、2、3、5、8、13、21、34、...
这个数列,前两项都是数字1,从第三项开始,每一项数字是前两项数字之和
关系表达式【f(n) = f(n-1)+f(n-2)】
def fib(n): if n<=2: return 1 return fib(n-1)+fib(n-2)print(fib(10)) # 55print(fib(2)) # 1
递归与栈的关系
递归函数原理:每一次调用都会把当前调用压入到栈里,最后按照后进先出的原则,不停返回返回
由递归程序的执行过程,我们得知递归程序的调用是一层层向下的,而返回过程则恰好相反,一层层向上。
换个说法:最先一次的函数调用在最后返回,而最后一次的函数调用则是最先返回。这就跟栈的“后进先出”次序是一样的。因此,在实现递归调用的时候,通常就会使用栈来保存每一次调用的现场数据:
- 当一个函数被调用的时候,系统会把调用时的现场数据压入到系统调用栈,压入栈的现场数据称为栈帧。
- 当函数返回时,要从调用栈的栈顶取得返回地址,恢复现场,弹出栈帧,按地址返回。
题目21:三个数取最大数
己知数字a,b,c分别为10,6,18
找出a,b,c中最大的数字(不借助函数以及列表等方式)
我们知道函数max可以直接获取到最大值,或者可以把数字添加到列表里,通过排序也能获取到最大数字,我们单纯使用if分支来实现
a, b, c = 10, 6, 18if a > b: max_num = aelse: max_num = bif max_num < c: max_num = cprint(max_num) # 18
题目22:因子之和“完数”
什么是因子?
因子就是所有可以整除这个数的数字,包括1但不包括这个数自身。比如8的因子有1,2,4
什么是完数?
一个数如果恰好等于它的因子之和,这个数就称为“完数”,打印输出1000以内的完数,例如6=1+2+3,6就是“完数
def factor_sum(n): s_sum = 0 for i in range(1, n): if n % i == 0: s_sum += i return s_sumfor j in range(1, 1000): if j == factor_sum(j): print(j) # 6 # 28 # 496
题目23:递归阶乘求和
一个正整数的阶乘(factorial)是所有小于及等于该数的正整数之积,并且0的阶乘为1
如5!=1*2*3*4*5计算1!+2!+3!+4!+5!+…+10!关系表达式【f(n) = n*f(n-1)】
def factor(n): if n < 2: return 1 return n * factor(n - 1)s_sum = 0for i in range(1, 11): s_sum += factor(i)print(s_sum) # 4037913
题目24:有效的括号
给定一个只包括'(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合
- 左括号必须以正确的顺序闭合
- 空字符串可被认为是有效字符串
示例 1:
输入:"()"
输出:True
示例 2:
输入:"()[]{}"
输出:True
示例 3:
输入:"(]"
输出:False
示例 4:
输入:"([)]"
输出:False
解法一:字符串替换法
在字符串中找成对的()、[]、{},找到后替换成空
使用while循环,不停判断是否存在成对的小括号中括号大括号,如果存在就使用replace替换成空
直到无法再替换的时候,再判断下当前的字符串是否为空,如果为空说明字符串是有效的,如果不为空说明字符串是无效的
def valid_str(string): if len(string) % 2 == 1: return False while '()' in string or '[]' in string or '{}' in string: string = string.replace('()', '') string = string.replace('[]', '') string = string.replace('{}', '') return string == ''print(valid_str('()')) # Trueprint(valid_str('()[]{}')) # Trueprint(valid_str('()[]{[()]}')) # Trueprint(valid_str('()[]{[(}]}')) # False
解法二:利用栈的后进先出原则
先去定义一个空栈,对当前栈进行循环遍历,遇到左括号我们就把当前的左括号添加到栈里面,遇到右括号,我们就和栈顶元素进行比对
看它们是不是成对的括号,如果是,就把当前的元素出栈,直到字符串遍历结束之后,我们再来看下字符串是不是空的,如果是空的说明字符串是有效的,如果不为空说明字符串是无效的
def valid_str(string): if len(string) % 2 == 1: return False stack = [] char_dict = { ')': '(', '}': '{', ']': '[' } for char in string: if char in char_dict: # 右括号 if not stack or char_dict[char] != stack.pop(): return False else: # 左括号 stack.append(char) return not stackprint(valid_str('(){}[({[]})]')) # Trueprint(valid_str('(){}[({[)})]')) # Falseprint(valid_str('')) # True
题目25:回文数的两种解法
回文数是指正序(从左向右)和倒序(从右向左)都是一样的整数。例如,1221是回文,而1222不是。
解法一:通过逆转字符串进行比对
def is_palindrome(x): if x < 0 or x > 0 and x % 10 == 0: return False str_x = str(x) return str_x == str_x[::-1]print(is_palindrome(121)) # Trueprint(is_palindrome(120)) # False
解法二:反转一半数字和前半部分的数字进行比较
流程
- 对于整数x,后半部分reverted
- 每次循环x%10拿到末尾数字
- 然后x/10去除末尾的数字
- 循环结束条件x<=reverted
数字长度(奇数)
12321
数字长度(偶数)
1221
def is_palindrome(x): if x < 0 or x > 0 and x % 10 == 0: return False reverted = 0 while x > reverted: # 我们看下 1221 # 第一次循环我们需要把末尾数字1取出来 第二次取末尾数字2 我们需要把21变成12 reverted = reverted * 10 + x % 10 # 把x的末尾数字删除掉 x //= 10 return x == reverted or x == reverted // 10print(is_palindrome(1221)) # Trueprint(is_palindrome(1223)) # Falseprint(is_palindrome(123321)) # True
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件!
如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
白云城资源网 Copyright www.dyhadc.com