力扣python100题

❶ 14. 最长公共前缀（python）

更多精彩内容，请关注 【力扣简单题】 。

难度：★☆☆☆☆
类型：字符串

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

这道题目很简单，逐一比较各个字符串，出现不同字符则跳出，详情可见注释。

如有疑问或建议，欢迎评论区留言~

❷ 力扣236单周赛题目分享

共有 n 名小伙伴一起做游戏。小伙伴们围成一圈，按 顺时针顺序 从 1 到 n 编号。确切地说，从第 i 名小伙伴顺时针移动一位会到达第 (i+1. 名小伙伴的位置，其中 1 <= i < n ，从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。

游戏遵循如下规则：

从第 1 名小伙伴所在位置 开始 。
沿着顺时针方向数 k 名小伙伴，计数时需要 包含 起始时的那位小伙伴。逐个绕圈进行计数，一些小伙伴可能会被数过不止一次。
你数到的最后一名小伙伴需要离开圈子，并视作输掉游戏。
如果圈子中仍然有不止一名小伙伴，从刚刚输掉的小伙伴的 顺时针下一位 小伙伴 开始，回到步骤 2 继续执行。
否则，圈子中最后一名小伙伴赢得游戏。
给你参与游戏的小伙伴总数 n ，和一个整数 k ，返回游戏的获胜者。

示例 1：

输入：n = 5, k = 2

输出：3

解释：
游戏运行步骤如下：

示例 2：

输入：n = 6, k = 5

输出：1

解释：
小伙伴离开圈子的顺序：5、4、6、2、3 。小伙伴 1 是游戏的获胜者。

这是一道标准的约瑟夫环问题，类似的题目很多，比如剑指offer中有一道小朋友们的游戏与此题就如出一辙。大家找个链表画下题目就迎刃而解了，类似斐波那契数列一样，了解公式直接解题。

给你一个长度为. n. 的. 3 跑道道路. ，它总共包含. n + 1. 个. 点. ，编号为. 0. 到. n. 。一只青蛙从. 0. 号点第二条跑道. 出发. ，它想要跳到点. n. 处。然而道路上可能有一些障碍。

给你一个长度为 n + 1. 的数组. obstacles. ，其中. obstacles[i]. （取值范围从 0 到 3）表示在点 i. 处的. obstacles[i]. 跑道上有一个障碍。如果. obstacles[i] == 0. ，那么点. i. 处没有障碍。任何一个点的三条跑道中. 最多有一个. 障碍。

比方说，如果. obstacles[2] == 1. ，那么说明在点 2 处跑道 1 有障碍。
这只青蛙从点 i. 跳到点 i + 1. 且跑道不变的前提是点 i + 1. 的同一跑道上没有障碍。为了躲避障碍，这只青蛙也可以在. 同一个. 点处. 侧跳. 到 另外一条. 跑道（这两条跑道可以不相邻），但前提是跳过去的跑道该点处没有障碍。

比方说，这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。
这只青蛙从点 0 处跑道 2. 出发，并想到达点 n. 处的 任一跑道 ，请你返回 最少侧跳次数. 。

注意：点 0. 处和点 n. 处的任一跑道都不会有障碍。

示例 1：

输入：obstacles = [0,1,2,3,0]

输出：2

解释：最优方案如上图箭头所示。总共有 2 次侧跳（红色箭头）。

注意，这只青蛙只有当侧跳时才可以跳过障碍（如上图点 2 处所示）。

示例 2：

输入：obstacles = [0,1,1,3,3,0]

输出：0

解释：跑道 2 没有任何障碍，所以不需要任何侧跳。

示例 3：

输入：obstacles = [0,2,1,0,3,0]

输出：2

解释：最优方案如上图所示。总共有 2 次侧跳。

我的个人博客： https://qingfengpython.cn

力扣解题合集： https://github.com/BreezePython/AlgorithmMarkdown

❸ 813. 最大平均值和的分组（Python）

难度：★★★☆☆
类型：数组
方法：动态规划

力扣链接请移步 本题传送门
更多力扣中等题的解决方案请移步 力扣中等题目录

我们将给定的数组 A 分成 K 个相邻的非空子数组 ，我们的分数由每个子数组内的平均值的总和构成。计算我们所能得到的最大分数是多少。

注意我们必须使用 A 数组中的每一个数进行分组，并且分数不一定需要是整数。

示例:
输入:
A = [9,1,2,3,9]
K = 3
输出: 20
解释:
A 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20.
我们也可以把 A 分成[9, 1], [2], [3, 9].
这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.
说明:

1 <= A.length <= 100.
1 <= A[i] <= 10000.
1 <= K <= A.length.
答案误差在 10^-6 内被视为是正确的。

数组问题常用动态规划来解决。动态规划的精髓在于，把一个难以解决的大问题转化为若干个可以通过有限次重复解决的简单问题。接下来从动态规划的几个要素进行介绍：

【数组定义】
我们定义一个二维数组dp，维度为输入数组A的维度×K，dp[i][k]表示数组A[:i+1]被分成k+1组时，可以得到的最大分数（各组平均值的和）。这里尤其需要注意python下标和它代表的变量的物理含义之间正好相差1的。

【初始状态】
我们可以很快得知的信息是，如果数组只被分为一组的情况。因此可以先把k=0的一列填好。这一列各个位置dp[i][0]的填充规则，就是A[:i]的均值。

【递推公式】
我们以分组数k和下标i递增的方式，构造嵌套循环。这里还需要留意一个情况，就是填充dp[i][k]时，需要考虑到获得当前位置的各种情况的分组，因此借助一个中间下标变量j，范围从0到i，也就是说，我们把数组A[:i+1]从下标j砍成了两半，因此当前位置处的值可以填充为：

dp[i][k] = max(dp[i][k], dp[j][k-1]+average(j+1, i+1))

这里average是一个函数，用来计算A[i:j]子数组的均值。这里把i和j+1的原因是我们定义dp数组的物理意义决定的。

有了这个递推公式，就可以迭代进行计算了，
注意k的范围是从1到K，因为k=0的一列已经算好了；
i的范围是从k到len(A)，因为组的个数不能比数组中数字的个数还要多；
j的范围是小于i，因为必须要保证可以把A[:i+1]分开。

【最后结果】

最终范围dp[-1][-1]也就是最后计算出的值，就可以代表题目所要求的结果。

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步 力扣中等题解析

❹ 984. 不含AAA或BBB的字符串（Python）

难度：★★★☆☆
类型：字符串
方法：逻辑

力扣链接请移步 本题传送门
更多力扣中等题的解决方案请移步 力扣中等题目录

给定两个整数 A 和 B，返回任意字符串 S，要求满足：

S 的长度为 A + B，且正好包含 A 个 'a' 字母与 B 个 'b' 字母；
子串 'aaa' 没有出现在 S 中；
子串 'bbb' 没有出现在 S 中。

示例 1：

输入：A = 1, B = 2
输出："abb"
解释："abb", "bab" 和 "bba" 都是正确答案。

示例 2：

输入：A = 4, B = 1
输出："aabaa"

提示：

0 <= A <= 100
0 <= B <= 100
对于给定的 A 和 B，保证存在满足要求的 S。

题目很好理解，构建一个“a”的数量为A，“b”的数量为B的字符串，并且不要出现“AAA”或“BBB”。

这个题官网题解还是比较好的，每写一个字符，都要做下面的判断：

如果连续出现两个相同字符了，则下一个字符一定要相反；

否则，写数量更多的字符。

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步 力扣中等题解析

❺ 478. 在圆内随机生成点（Python）

难度：★★☆☆☆
类型：几何
方法：拒绝采样

力扣链接请移步 本题传送门
更多力扣中等题的解决方案请移步 力扣中等题目录

给定圆的半径和圆心的 x、y 坐标，写一个在圆中产生均匀随机点的函数 randPoint 。

说明:

输入值和输出值都将是浮点数。
圆的半径和圆心的 x、y 坐标将作为参数传递给类的构造函数。
圆周上的点也认为是在圆中。
randPoint 返回一个包含随机点的x坐标和y坐标的大小为2的数组。
示例 1：

输入:
["Solution","randPoint","randPoint","randPoint"]
[[1,0,0],[],[],[]]
输出: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]
示例 2：

输入:
["Solution","randPoint","randPoint","randPoint"]
[[10,5,-7.5],[],[],[]]
输出: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]
输入语法说明：

输入是两个列表：调用成员函数名和调用的参数。Solution 的构造函数有三个参数，圆的半径、圆心的 x 坐标、圆心的 y 坐标。randPoint 没有参数。输入参数是一个列表，即使参数为空，也会输入一个 [] 空列表。

我们在以圆心为中心，以二倍半径为边长的正方形内部进行随机选点，当点落在圆内或者圆上时，满足条件，返回该点。

我们可以把上面的直角坐标变换为极坐标，随机的选取角度和半径，生成的点一定在圆上或者圆内。这里需要注意，由于在平面维度是均匀采样的，生成随机半径时需要对结果开方。

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步 力扣中等题解析

❻ Python挑战100题（14~20）

题目：给你个小写英文字符串a和一个非负数b(0<=b<26), 将a中的每个小写字符替换成字母表中比它大b的字母。这里将字母表的z和a相连，如果超过了z就回到了a。
例如a="cagy", b=3,
则输出 ：fdjb
提示： ord('a') = 97, ord('b') = 98, chr(97) = a
参考答案：

题目：给你一个字符串a和一个正整数n,判断a中是否存在长度为n的回文子串。如果存在，则输出YES，否则输出NO。
回文串的定义： 记串str逆序之后的字符串是str1，若str=str1,则称str是回文串，如"abcba".
参考答案：

题目：给你两个时间st和et(00:00:00<=st <= et<=23:59:59), 请你给出这两个时间间隔的秒数。
如：st="00:00:00", et="00:00:10", 则输出10.
参考答案：
方法一：切片

方法二：time模块

题目：给你一个时间t（t是一个字典，共有六个字符串key(year,month,day,hour,minute,second),值为每个值为数字组成的字符串，
如t={'year':񟭍','month':Ə','day':ཚ','hour':ཌ','minute':ཀྵ','second':ƈ'}
请将其按照以下格式输出， 格式:XXXX-XX-XX XX:XX:XX。如上例应该输出： 2013-09-30 16:45:02。
参考答案：
方法一：利用datetime模块

方法二：一行

题目：给你一个整数组成的列表L，按照下列条件输出：
若L是升序排列的,则输出"UP";
若L是降序排列的,则输出"DOWN";
若L无序，则输出"WRONG"。
参考答案：

题目：一个环形的公路上有n个加油站，编号为0,1,2,...n-1,
每个加油站加油都有一个上限，保存在列表limit中，即limit[i]为第i个加油站加油的上限，
而从第i个加油站开车开到第(i+1)%n个加油站需要cost[i]升油,cost为一个列表。
现在有一辆开始时没有油的车，要从一个加油站出发绕这个公路跑一圈回到起点。
给你整数n，列表limit和列表cost,你来判断能否完成任务。
如果能够完成任务，输出起始的加油站编号，如果有多个,输出编号最小的。
如果不能完成任务，输出-1。
参考答案：
构造新的limit和cost并遍历,来源 http://www.pythontip.com/coding/report_detail/3195/

题目：给你一个整数列表L,判断L中是否存在相同的数字，
若存在，输出YES，否则输出NO。
参考答案：

❼ 977. 有序数组的平方（Python）

更多精彩内容，请关注 【力扣简单题】 。

难度：★☆☆☆☆
类型：数组

给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

提示
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。

示例 1
输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]

示例 2
输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]

我们对输入数组中每个元素进行平方，然后对结果进行数组进行排序即可。

（参考官方解答）

我们可以使用两个指针分别读取数组的非负部分与负数部分 —— 指针 i 反向读取负数部分，指针 j 正向读取非负数部分。

那么，现在我们就在使用两个指针分别读取两个递增的数组了（按元素的平方排序）。接下来，我们可以使用双指针的技巧合并这两个数组。

如有疑问或建议，欢迎评论区留言~

❽ Python求数学题 1到100包括100 能被3整除和被5整除余1的所有数之和 用for

for i in range (1,101): print i, if i%3==0 and i%5==0: print 'A*B', elif i%3==0: print 'A', elif i%5==0: print 'B', print

❾ 求大神帮忙做道Python题。

menu = {'蒜泥黄瓜':6,'花生米':6,'青椒炒肉':28,'西红柿鸡蛋':18,'红烧肉':38,'烤鱼':30,'手撕鸡':45,'海带排骨':35,'白菜':12,'三鲜汤':15}
def order(*dish):
s = 0
for i in dish:
s += menu[i]
return s
m = order('蒜泥黄瓜','花生米','青椒炒肉','西红柿鸡蛋')
print(f'结账: {m}元')

程序缩进如图所示

❿ 力扣每日一题：102.二叉树的层序遍历 深度优先与广度优先双解！

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

对于二叉树的层序遍历，一般都是使用BFS配合队列完成解题。

二叉树的前、中、后 顺序遍历，一般最简单的是使用深度优先，但层序遍历也可以通过DFS来解题。

麻烦一些的就是我们需要在DFS层级遍历的时候，根据当前深度进行保存，这里由于返回列表，所以
使用defaultdict来构造特殊的Hash表更为快捷。由于字典的key值为深度，是存在默认排序的，
所以递归返程回放回即可。

下面来分别看看一下两种解题...

我的个人博客： https://qingfengpython.cn

力扣解题合集： https://github.com/BreezePython/AlgorithmMarkdown