leetcode漫漫求索路……🛣，进行日常算法训练，就当强身健体了😢，燥起来吧...... ## 从排序数组中删除重复项
原题链接https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/21/
题解：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
1 | 给定数组 nums = [1,1,2], |
示例 2:
1 | 给定 nums = [0,0,1,1,1,2,2,3,3,4], |
这道题目很简单，关键词有三个：排序数组，原地删除，返回新数组长度
1 | class Solution: |
买卖股票的最佳时机
原题链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
题意：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
1 | 输入: [7,1,5,3,6,4] |
示例 2:
1 | 输入: [7,6,4,3,1] |
分析
题目中要求最多允许完成一次交易，并且得到最大的收益，这是一个很明显的动态规划问题，我们可以将问题进行拆解，会发现在整个输入序列中，相邻元素之间如果后者大于前者则存在收益；否则没有收益，并且我们要的是最大的收益，那么就需要比较当前这一步的收益和之前得到的所以之间取大值，即
$$
profit=max(profit,sale-buy)
$$
$profit$为获得的收益，$sale$为卖出交个，$buy$为买入价格，由于限制了单次交易，那么买入的价格应该选择最低的价格，而卖出应该选择比上次的收益更大的价格，代码如下代码
1 | class Solution(object): |
买卖股票最佳时机 II
原题链接：https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/22/
题意：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
1 | 输入: [7,1,5,3,6,4] |
示例 2:
1 | 输入: [1,2,3,4,5] |
示例 3:
1 | 输入: [7,6,4,3,1] |
- 分析：根据题意，求解的是累计总收益，实际上在leetcode中有一个类似的求解收益的问题是，求解的是单次投资的最大收益，那个使用动态规划的思路求解,也就是上面那道题，说到本题目，有两种思路。
- 方法一：直接根据题意和例子进行分析，遍历价格列表，假设初始价格为a，也就是prices[0]=a，当前价格如果大于初始价格并且大于当前的下一个价格，则认为是卖出点，获得收益；如果当前价格小于初始价格，那么对初始价格进行更新，更新为当前的价格
- 方法二：利用加法交换律，D-A=(D-C)+(C-B)+(B-A)，这样思考的话就不用具体考虑当前价格和初始价格的关系，只管比较当前价格和前一个价格之间的关系，如果当前价格大于之前一个的价格，则获得收益，使用迭代的方法，遍历到价格列表最后就可获得总收益
- 代码：将两种方法的写在了一个代码段之中，并使用注释隔开
1 | class Solution: |
最佳买卖股票时机含冷冻期
原题链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/comments/
题解：
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例
1 | 输入: [1,2,3,0,2] |
分析
整个购买过程包含买入，卖出和冷冻，可以创建三个数组分别表示在第i天时候对应的是买入，卖出和冷冻状态下的收益状况buy,sale,cold
- 第i天为买入状态下的收益情况buy[i]
- 前一天不持有股票，也就是为冷冻状态，那么今天买入得到的收益为cold[i-1]-pirces[i]
- 前一天持有股票，那么肯定前一天为买入状态，那么今天买入得到的收益为buy[i-1]
- 取两种情况下的最大收益情况为今天买入的收益状况
- 第i天为卖出状态下的收益情况sale[i]
- 前一天不持有股票，也就是前一天股票就是卖出状态，那么今天的卖出收益为sale[i-1]
- 前一天持有股票，那么前一天为买入状态，由此，今天的卖出收益为buy[i-1]+prices[i]
- 第i天为冷冻状态下的收益情况cold[i]
- 前一天刚卖出，今天冷冻的收益为sale[i-1]
- 前一天就已经冷冻，今天的冷冻收益为cold[i-1]
最终得到的最大收益，最后一天的状况应该是卖出
- 第i天为买入状态下的收益情况buy[i]
代码
1 | class Solution(object): |
Nim游戏
题目：
你和你的朋友，两个人一起玩 Nim游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。
你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。
示例
1
2
3
4输入: 4
输出: false
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。分析
这是一个easy级别的题目，轮流拿掉1-3个，每次都是最优解而不是随便拿的，通过示例的分析，将二人每那一次作为一组，在一组中，买这时候对应着最少2个石头，最多6个石头，每次都是最优解，因此先拿的人肯定是要拿最少的石子，而第二个人要想胜利必须拿更多的石子，由此可以得出，只要组中的石子是4的倍数，那么肯定是先手的人输，推广到整个n中同样如此。
1
2
3
4
5
6
7class Solution:
def canWinNim(self, n):
"""
:type n: int
:rtype: bool
"""
return False if n%4==0 else True
旋转数组
原题链接：https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/23/
题解：给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
1
2
3
4
5
6输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]示例 2:
1
2
3
4
5输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]说明:
- 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
- 要求使用空间复杂度为 O(1) 的原地算法。
分析：
这个题目很简单，右侧移动k步，如果移动的步数和数组的长度相等，那么得到的数组和原来的数组相等。可以对k于数组长度进行取余计算，数组实际移动的步数就是取余之后的结果。
- 方法1：一次移动一个，数组左侧进行插入insert，右侧进行删除del，每次都把数组的最后一个移动0位置，删除新数组的最后一个元素
- 方法2：使用切片移动，利用extend命令，如果取余结果为m，那么把数组的前length-m个元素添加到数组的后面构成新数组，之后删除新数组的前length-m个元素
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution:
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
if k<=0:
return
length=len(nums)
step=k%length
## 方法1：
# 后面元素向前移动，一个一个移动，移动之后删除最后一个元素
# for i in range(step):
# nums.insert(0,nums[-1])
# del nums[-1]
## 方法2
# 使用元素切片，把前面的整体移动到后面之后删除前面部分
nums.extend(nums[:length-step])
del nums[:length-step]
整数反转
题意
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。解析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution:
def reverse(self, x: int) -> int:
if x==0: return 0
str_x=str(x)
flage=1
if str_x[0]=="-":
flage=-1
str_x=str_x[1:]
reverse=str_x[::-1]
if reverse[0]=="0":
reverse=reverse[1:]
if int(reverse) > 2**31-1:
return 0
else:
return int(reverse)*flage很简单的题目，主要考虑一些注意点就行
- 给的x是0，直接返回
- 给的x是负数，使用flage来控制
- 给的x能被10整除，也就是个位是0，反转之后要把0去掉
- 控制输出数据的范围，只控制正数就可以了
正则表达式匹配
题意
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false解析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32class Solution:
def isMatch(self, s: str, p: str) -> bool:
# 这个终止条件不能忘，否则对于给定的p就是空的情况，不出现错误
if not p: return not s
self.cache={}
self.search(s,p)
return self.cache[(s,p)]
def search(self,s,p):
# 终止条件，如果p空，s也是空的能匹配，否则不能匹配
if not p: return not s
# 从缓存查询
if (s, p) in self.cache:
return self.cache[(s, p)]
# 第一个字符是否匹配，如果不匹配，如果后面是"*"还有的救，
first_char_match=len(s)>0 and (p[0] in {s[0],"."})
if len(p)>=2 and p[1]=="*":
# 开始是一个字符，后面跟一个*
# 对前面字符匹配0次，直接跳过，这时候s不变，p变成p[2:]
cond1=self.search(s,p[2:])
# *对前面字符匹配多次，这时候考虑s[1]已经在first的时候匹配过了，因此从s[1:]开始匹配，p不变
cond2=first_char_match and self.search(s[1:],p)
res= cond1 or cond2
else:
# 处理的是"."的情况，"."对应着任意任意字符，继续匹配，只有一种情况
cond=first_char_match and self.search(s[1:],p[1:])
res=cond
# 把结果存入缓存
self.cache[(s,p)]=res
return res
字符串转换整数 (atoi)
题意
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：
本题中的空白字符只包括空格字符 ' ' 。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42"
输出: 42
示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。解析
1
2
3class Solution:
def myAtoi(self, s: str) -> int:
return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)最好的办法就是正则匹配
1
2
3
4
5
6
7
8
9
10
11
12^：匹配字符串开头
[\+\-]：代表一个+字符或-字符
?：前面一个字符可有可无
\d：一个数字
+：前面一个字符的一个或多个
\D：一个非数字字符
*：前面一个字符的0个或多个
作者：QQqun902025048
链接：https://leetcode-cn.com/problems/string-to-integer-atoi/solution/python-1xing-zheng-ze-biao-da-shi-by-knifezhu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。max(min(数字, 2**31 - 1), -2**31)用来防止结果越界
存在重复
原题链接：https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/24/
题意：给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
示例 1:
1
2输入: [1,2,3,1]
输出: true示例 2:
1
2输入: [1,2,3,4]
输出: false示例 3:
1
2输入: [1,1,1,3,3,4,3,2,4,2]
输出: true分析：这道题真的太太太简单了，感觉是考察元组的性质，元组内部元素只能出现一次，根据这个特性直接写出代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution:
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
## 一步到位，直接比较元组的长度和原始列表长度，如果相等，则没有重复元素，返回False，否则返回True
# return not len(set(nums))==len(nums)
## 麻烦一些，思路大体一致
new=set()
for i in nums:
if i in new:
return True
new.add(i)
return False
只出现一次的数字
原题：https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/25/
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
1
2输入: [2,2,1]
输出: 1示例 2:
1
2输入: [4,1,2,1,2]
输出: 4分析：很简单，也是两种方法。
- 只有一个数出现一次，其余都出现了两次，可以利用元组的性质，进行求解，该方法更好理解
- 使用按照位进行异或运算，因为除了出现一次的其余的全部出现两次，所以出现两次的元素进行异或运算最后都会变为0，只有出现一次的会保留下来，也就是所求的结果
代码
1 | class Solution: |
两个数组的交集 II
原题链接：https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/26/
题意：给定两个数组，编写一个函数来计算它们的交集。
示例 1:
1
2输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]示例 2:
1
2输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]说明：
- 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
- 我们可以不考虑输出结果的顺序。
分析：要求不用考虑输出结果的顺序，那么直接求在两个数组中的元素
代码：两种思路：
- 直接按照题意，找出长度较短的数组，查看内部元素是否在长数组中，时间复杂度$n^2$
- 使用字典的方式，存储一个数组中的值以及对应出现的次数，之后另一个数组查看是否在该字典中，如果存在，字典中该key对应的value减去1。时间复杂度$nlog(n)$
- 利用字典形式，将nums1和num2都出现的次数都存储在字典中，字典的value为列表形式，时间复杂度为$log(n)$
1 | class Solution: |
加一
原题链接：https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/27/
题意：给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:
1
2
3输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。示例 2:
1
2
3输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。分析：两种思路
直接在数组上进行操作，进行输入数组原地修改，空间复杂度$O(1)$时间复杂度$O(n)$，更优选择
把数组转换成数字，进行+1操作之后再转换回去，空间O2，时间On
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution:
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
##方法1 直接按照加法法则从后向前移动,
length=len(digits)
count=1
for idx in range(-1,-length-1,-1):
s=digits[idx]+count
cur,res=s%10,s//10
count=res
digits[idx]=cur
if count:
digits.insert(0,1)
return digits
## 方法2
## 把数组转换成字符串
# ori=int(''.join(str(i) for i in digits))
# ori+=1
# out=str(ori)
# return list(int(i) for i in out)
移动零
原题链接：https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/28/
题意：给定一个数组
nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。示例:
1
2输入: [0,1,0,3,12]
输出: [1,3,12,0,0]说明:
- 必须在原数组上操作，不能拷贝额外的数组。
- 尽量减少操作次数。
分析：遍历整个数组，遍历的次数为数组的长度，当遇到为0时，append一个0，并且删除当前值，并且继续从当前值遍历
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution:
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
'''
count表示遍历的次数，index代表数组的索引，如果不添加遍历次数的限制，会出现死循环情况
'''
idx=0
count=0
while count<len(nums):
if nums[idx]==0:
nums.append(0)
del nums[idx]
else:
idx+=1
count+=1
两数之和
原题链接：https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/29/
题意：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
1
2
3
4给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]分析：两数之和为target，可以认为一个为a，另一个为target-a
- 使用哈希的方式，假设当前值为cur，key为(target-cur)，对应的value为idx
代码：
1 | class Solution: |
三数之和
题意
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]解析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
ans = list()
# 枚举 a
for first in range(n):
# 需要和上一次枚举的数不相同
if first > 0 and nums[first] == nums[first - 1]:
continue
# c 对应的指针初始指向数组的最右端
third = n - 1
target = -nums[first]
# 枚举 b
for second in range(first + 1, n):
# 需要和上一次枚举的数不相同
if second > first + 1 and nums[second] == nums[second - 1]:
continue
# 需要保证 b 的指针在 c 的指针的左侧
while second < third and nums[second] + nums[third] > target:
third -= 1
# 如果指针重合，随着 b 后续的增加
# 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if second == third:
break
if nums[second] + nums[third] == target:
ans.append([nums[first], nums[second], nums[third]])
return ans直接按照题意去做，先做序列进行排序，参考两个数之和的思路，先枚举第一个数，剩下的两个数之和就是第一个数的相反数，因为题意上有条件，不重复的三元组，如果使用两数之和的思路没办法控制这个条件，这里使用前后指针的方式实现。
两数相加
题解：给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例：
1 | 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) |
- 分析：该题一目了然，使用链表的形式模拟了十进制加法运算。根节点代表低位，next代表了高位，直至给定的两个链表全部加完，即next为none。
1 | # Definition for singly-linked list. |
最小栈
题意
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) – 将元素 x 推入栈中。
- pop() – 删除栈顶的元素。
- top() – 获取栈顶元素。
- getMin() – 检索栈中的最小元素。
示例
1
2
3
4
5
6
7
8MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.分析
这道题目考察的堆栈的理解，对于堆栈结构使用的是先进后出的策略，类似于摞盘子，先放的盘子是在最下面，后方的盘子在最上面，取盘子的时候先取的都是最后放的，
push操作
将元素压入栈中，也就是为栈append一个元素
pop操作
删除栈顶的元素，也就是对栈进行pop操作，删除最后添加的元素
top
获取栈顶匀速，也就是返回栈中最后添加的元素
getMin
获取栈的最小元素，并且是在常数时间内，也就是不能说那个min()的方式，因为这种方式的时间复杂度为$O(n)$，题目要求的是$O(1)$，基于此，可以创建一个临时数组只用来存储最小的元素，当进行getMin操作的时候，返回该临时数组的最后一个元素
代码
1 | class MinStack: |
Note
这里有一个要注意的地方，实际上对于使用数组结构模拟栈的结构形式，有两种实现方式
insert,del
对于push操作，使用insert(0,x)进行，也就是新元素插入数组的顶部
对于pop操作，删除的是最近添加的元素，使用del data[0]
Apped,pop
对于push操作，使用append(X)，将新元素添加到数组的尾部
对于pop操作，直接使用data.pop()
比较这两种方法，对于第一种的insert+del的方式，元素压入和删除元素，数组中的其他元素都要顺序后移或前移一位，而第二中的append+pop的方式则不会这样，因此在操作时间上，第二种方法是更优的。对于数组结构，都要优先使用尾部添加或删除的方式。
3的幂
题意
给定一个整数，写一个函数来判断它是否是 3 的幂次方。
示例
示例 1:
1
2输入: 27
输出: true示例 2:
1
2输入: 0
输出: false示例 3:
1
2输入: 9
输出: true示例 4:
1
2输入: 45
输出: false进阶：
你能不使用循环或者递归来完成本题吗？分析
递归方法
简单易行，每次当前数字和3取余
代码
1 | class Solution: |
二叉树的坡度
题意
给定一个二叉树，计算整个树的坡度。
一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
整个树的坡度就是其所有节点的坡度之和。
示例:
1
2
3
4
5
6
7
8
9
10输入:
1
/ \
2 3
输出: 1
解释:
结点的坡度 2 : 0
结点的坡度 3 : 0
结点的坡度 1 : |2-3| = 1
树的坡度 : 0 + 0 + 1 = 1注意:
- 任何子树的结点的和不会超过32位整数的范围。
- 坡度的值不会超过32位整数的范围。
分析
根据每个节点的坡度的定义，对于某个节点当前节点和左右子树之和为
left+right+root.val，依次为递归的返回式，进行后续遍历1
2
3
4
5def find_sum(root):
left=find_sum(root.left)
right=find_sum(root.right)
out+=abs(left-right)
return root.val+left+right通过该遍历得到每个节点计算得到的
left-right之和，得到的out即为所求，因此，整个代码可以为1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def findTilt(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.out = 0
def find_sum(root):
if not root: return 0
left = find_sum(root.left)
right = find_sum(root.right)
# 计算坡度，左右节点相减
self.out += abs(left - right)
# 返回以当前的节点为根节点的所有节点之和,进入下一步的递归
# root.val + left + right构成一个完成的节点
return root.val + left + right
find_sum(root)
return self.out
寻找两个有序数组的中位数
原题链接 https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
题意
给定两个大小为 m 和 n 的有序数组
nums1和nums2。请你找出这两个有序数组的中位数，**并且要求算法的时间复杂度为 O(log(m + n))**。
你可以假设
nums1和nums2不会同时为空。示例
示例 1:
1
2
3
4nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0示例 2:
1
2
3
4nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5分析
先说中位数的定义
對於有限的數集，可以通過把所有觀察值高低排序後找出正中間的一個作爲中位數。如果觀察值有偶數個，則中位數不唯一，通常取最中間的兩個數值的平均數作爲中位數。
由此可以看到，对于中位数，针对数组长度的奇偶数不同而计算方法不同
代码
1 | class Solution: |
复原ip地址
原题链接：https://leetcode-cn.com/explore/interview/card/bytedance/242/string/1044/
题意
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例
1
2输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]分析
本体考察的是图搜索算法，分为广度优先搜索和深度优先搜索
对于ip的格式
- ip分为4断格式，每段之间数字为0–255之间的数字
- 数字不能以0开头，除了0本身
对于该判断可以得到条件函数
1
2
3
4def isvalid(s):
if str(int(s))==s and 0<=int(s)<=255:
return True
return False对于每个字段之间，可能的数字数量为为1，2，3，将符合条件字符串分段存储，如果最后将给定的字符串分割完毕并且满足条件的分段字符串为4段，可以得到满足条件的一个分割ip地址，使用递归的方式进行依次调用查找函数。
代码
- 递归方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36class Solution:
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
# 边界条件，大于12个或者小于4个无法构成有效ip地址
if len(s) > 12 or len(s)<4:
return []
res = []
dfs(s, [], res)
return res
def isvalid(s):
if 0<=int(s)<=255 and str(int(s))==s:
return True
return False
def dfs(s, path, res):
# 剪枝条件，如果剩余的有效的ip字符段数量无法满足最大的字符数量条件退出该条路径
if len(s) > (4 - len(path)) * 3 or len(s)<4-len(path):
return
# 如果s被查找完毕并且找的ip字符段数量满足收敛条件，添加到res中
if not s and len(path) == 4:
res.append('.'.join(path))
return
# 每个ip字段有可能为1，2，3个
for i in range(1, 4):
# 判断剩余的s是否满足条件
if i > len(s):
continue
# 是否满足ip格式
if isvalid(s[:i]):
# 如果满足条件，path中存储满足条件的字符段并重复调用寻找函数path+[s[:i]]
# 寻找区间缩小为剩余的字符串s[:i]
dfs(s[i:],path+[s[:i]],res)
- 对于递归的方式，由于需要重复对函数本身进行调用，因此容易造成内存溢出，将递归的方式修改成迭代方式，更加直白，类似于暴力搜索的方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution:
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
def isvalid(s):
if s and 0<=int(s)<=255 and str(int(s))==s:
return True
return False
res=[]
for i in range(1,4):
f1=s[:i]
if not isvalid(f1):
continue
for j in range(i+1,i+4):
f2=s[i:j]
if not isvalid(f2):
continue
for k in range(j+1,j+4):
f3,f4=s[j:k],s[k:]
if not isvalid(f3) or not isvalid(f4):
continue
res+=[f1+'.'+f2+'.'+f3+'.'+f4]
return res
反转字符串的单词
链接：https://leetcode-cn.com/explore/interview/card/bytedance/242/string/1011/
题意
给定一个字符串，逐个翻转字符串中的每个单词。
示例
1
2输入: "the sky is blue",
输出: "blue is sky the".说明
- 无空格字符构成一个单词。
- 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
- 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
进阶: 请选用C语言的用户尝试使用 O(1) 空间复杂度的原地解法。
分析
对于python来说，直接进行字符串分割，然后反转列表输出字符串
代码
1 | class Solution(object): |
搜索旋转排序数组
题意
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组
[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回
-1。你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例
1
2
3
4
5输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1分析
时间复杂度是$O(\log n)$首先想到的就是二分查找法，对于该题目，由于涉及两个查找，首先是对单调递增区间的查找，之后是在单调区间内的查找
对于单调递增权健的查找
实际上就是找到两个单调区间的临界点，该临近点的右侧是单调递增区间并且，该临界点大于右侧区间的所有点，该临界点的左侧也是单调递增区间，同样，该临界点也大于左侧的区间内的左右点，使用二分查找的方式确定该临界点，确定右侧的单调区间，设置left,right对应右侧单调区间的起始索引，
- 如果中值大于右侧的值，那么右侧区间在在中值的更右侧，此时left=mid+1
- 如果中值小于右侧的值，那么该中值的位置位于右侧的单调区间内，此时，right=mid
找到单调区间之后可以使用标准的二分查找方式确定目标值的索引
代码
1 | class Solution: |
第k个排列
题意
给出集合
[1,2,3,…,*n*]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123""132""213""231""312""321"
给定 n 和 k，返回第 k 个排列。
说明：
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
示例 1:
1 | 输入: n = 3, k = 3 |
示例 2:
1 | 输入: n = 4, k = 9 |
分析
参考https://cloud.tencent.com/developer/article/1335755
本题目考察的也是一种回溯法，但是直接使用递归的方法计算全排列然后再拿到全排列数组中的第k个元素会存在超时的问题，对于得到字符串全排列的方法为
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution:
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
s=''.join(str(i) for i in list(range(1,n+1)))
# 迭代方法
self.res=[s]
def Permutation(ss):
res=[]
if len(ss) <= 1:
return ss
for i in range(len(ss)):
# 使用map和lambda函数
# 递归的计算ss[:i] + ss[i+1:]
for n in map(lambda x:ss[i] + x, Permutation(ss[:i] + ss[i+1:])):
res.append(n)
return res
self.res=Permutation(s)
return self.res[k-1]对于递归的方法计算复杂度是在是太高，可以稍微修改一下为
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution:
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
s=''.join(str(i) for i in list(range(1,n+1)))
def helper(ss, res, path):
if not ss:
# 如果ss为空，那么将前面得到的path存入到res中
res.append(path)
else:
for i in range(len(ss)):
# 将当前字符串添加入path中，并递归计算剩余的元素
helper(ss[:i] + ss[i+1:], res, path + ss[i])
self.res=[]
helper(s, self.res, '')
return self.res[k-1]上面两个是基于先计算字符串的全排列然后再返回所有全排列的第k-1个元素的思路，这两种方法都会存在运算超时的问题，肯定是有问题的。
重新分析，
对于n个数字，范围是1-9，那么全排列的可能性为n!
加入给定n=4，那么数字为1234，并且要求的k是得到的所有排列从小到大排列之后的第k个元素
- 1开头+(2,3,4)全排列
- 2开头+(1,3,4)全排列
- 。。。
- 12开头+(3,4全排列)
- 13开头+(2,4)全排列
可以逐位计算得到最终的字符串
第一位元素对应着(k/(n-1)!)，第二位对应着(k%(n-1)!)/(n-2)!，以此类推
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39class Solution:
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
# n个数字存在n!全排列
# 每个数字开头，存在(n-1)!种全排列
nums = list(range(1, n+1))
if k == 1:
return "".join(str(i) for i in nums)
fact = 1
# 对于第一个个字开头的情况存在着n-1种全排列
for i in range(2, n):
fact *= i
_round = n - 1
# 求的是第k个元素，对于列表中对应着k-1的索引
k -= 1
Res = []
# 找到排列中的n个元素
# 对于每个元素，根据k的值进行计算
# 第一个元素，对应着(n-1)!种全排列可能，使用int(k/(n-1)!)得到第一位的元素对应的nums中的位置
# 第二个元素，对应着(n-2)!种全排列可能，使用int(k/(n-2)!)得到第二位元素对应的nums中的位置
# 由此，一次类推，逐渐求出每位的元素
while _round >= 0:
index = int(k / fact)
# 对k取余，得到下一位对应的排列可能的数量
k %= fact
# 当前位元素在nums中的位置，并删除nums中的这个元素
Res.append(nums[index])
nums.remove(nums[index])
# 如果还有下一位要进行计算，那么对fact进行更新，上一位存在(n-1)!种可能
# 那么下一位存在(n-2)!种可能
if _round > 0:
fact /= _round
_round -= 1
return "".join(str(i) for i in Res)
朋友圈
原题链接 https://leetcode-cn.com/explore/interview/card/bytedance/243/array-and-sorting/1036/
题意
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
示例
1
2
3
4
5
6
7输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。1
2
3
4
5
6输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。注意
- N 在[1,200]的范围内。
- 对于所有学生，有M[i][i] = 1。
- 如果有M[i][j] = 1，则有M[j][i] = 1。
分析
对于本题来说，有三种解体方法，
- DFS
- BFS
- 查并集
对于这种搜索的问题，要优先考虑图搜索的相关算法，在图搜索中包含深度优先搜索DFS，广度优先搜索BFS。
广度优先搜索
BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。
BFS属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。1
2
3
4
5算法流程：
1.首先将根节点放入队列中。
2.从队列中取出第一个节点，并检验它是否为目标。如果找到目标，则结束搜寻并回传结果。否则将它所有 尚未检验过的直接子节点加入队列中。
3. 若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
重复步骤2。深度优先搜索
它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。
1
2
3
4算法流程
1.访问顶点v；
2.依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
3.若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶 点均被访问过为止。
在图论中，能使用BFS的一般也能使用DFS。
- DFS代码
对于本题目，一共存在n个人，使用深度优先搜索的方法，首先设置一个状态列表，从每个节点出发，如果这个节点不再状态列表内，那么查找该人的朋友圈，关于该人朋友圈的查找方法为，如果这个人不在已经状态列表中，并且这个人和查找的节点的人存在朋友关系，那么把这个人加入到状态信息中并且继续查找这个人对饮的朋友信息。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution:
def findCircleNum(self, M):
"""
:type M: List[List[int]]
:rtype: int
"""
cnt, N = 0, len(M)
vset = set()
def dfs(n):
for x in range(N):
if M[n][x] and x not in vset:
vset.add(x)
dfs(x)
for x in range(N):
if x not in vset:
cnt += 1
dfs(x)
return cnt- BFS代码
如果是广度优先搜索的方法，需要借助一个队列来协助，遍历
（1）可以先找到一个人，把这个人的所有朋友都入队。
（2）然后依次出队，把朋友的朋友都入队，已经入过队列的，则不再入队。
（3）直到不再有朋友入队，而且已经出队完成，说明现在已经组成了一个朋友圈。
（4）然后把剩下的没被分到朋友圈里面的，同学，再次入队，进行下一个朋友圈的计算，依次循环直到结束。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32class Solution:
def findCircleNum(self, M):
"""
:type M: List[List[int]]
:rtype: int
"""
cnt, N = 0, len(M)
vset = set()
# bfs搜索算法
def bfs(n):
# 将该人添加到队列中
q = [n]
while q:
# 依次出队，第一次出队的是节点本身
# 找到和该节点满足朋友关系的人之后再找这些朋友的朋友
n = q.pop(0)
# 找到该节点人对应的所有朋友，
# 将朋友关系的添加到队列中，此外在将此添加到状态列表中
for x in range(N):
# 如果满足朋友关系但是该人已经在状态列表中，那么这个人不再入队列
# 目的是剪枝去重，如果a和bc都是朋友关系，那么不再查找bc之间的关系
if M[n][x] and x not in vset:
vset.add(x)
q.append(x)
for x in range(N):
if x not in vset:
cnt += 1
# 对该人进行bfs搜索
bfs(x)
return cnt- 查并集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution:
def findCircleNum(self, M):
"""
:type M: List[List[int]]
:rtype: int
"""
N = len(M)
# 假设每个人是相互独立的
f = list(range(N))
def find(x):
while f[x] != x:
x = f[x]
return x
for x in range(N):
# 向前搜索
for y in range(x + 1, N):
# 如果满足朋友关系
if M[x][y]:
# 满足朋友关系的话，将f中的x的节点的值进行更新
# 更新为与其为朋友关系的人值
# 更新之后，如果是一个朋友圈的，那么在f中的值是相同的
f[find(x)] = find(y)
return sum(f[x] == x for x in range(N))
回文数
题意
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶:
你能不将整数转为字符串来解决这个问题吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。求解
1
2
3
4
5
6class Solution:
def isPalindrome(self, x: int) -> bool:
if x==0: return True
if x%10==0 or x<0: return False
strx=str(x)
return strx==strx[::-1]非常简单，直接转换成字符串判断。另外，对特殊情况建议单独处理，避免浪费算力，实际上前面两个if条件如果去掉也能正常运行，但是测试会变慢不少。
最长回文子串
题意：
给定一个字符串
s，找到s中最长的回文子串。你可以假设s的最大长度为 1000。示例 1：
1
2
3输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。示例 2：
1
2输入: "cbbd"
输出: "bb"分析
- 暴力搜索
这是一道经典题目，直接暴力搜索肯定可以完成，遍历整个字符串，以当前位置为中心进行前后查找，判断前后位置对应的字符是否相等，直到找到不相同的字符，跳出循环；此外还要判断当前位置的字符和前后位置的字符是否为连续相同的字符，直到遍历完整个字符串，时间复杂度为$O(n^3)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if not s or len(s)==1: return s
l = len(s)
max_length = 0
palindromic = ''
for i in range(l):
x = 1
# 以当前点为中心前后寻找
while (i - x) >= 0 and (i + x) < l:
if s[i + x] == s[i - x]:
x += 1
else:
break
# 找到不满足条件的点之后当前已经进行了x+1操作，当前步减去1
x -= 1
# 更新长度和返回的回文子串
if 2 * x + 1 > max_length:
max_length = 2 * x + 1
palindromic = s[i - x:i + x + 1]
# 有可能相邻两位相同，这个时候要进行要进行特殊移动，前移动也行后移动也行的
# 例如字符串为abbc，如果当前位对应着第一个b，那么前后分别为ba，不满足上面的条件，
# 上面的方法可以提取奇数个相同的相邻数字
# 使用下面的条件判定，一直找到不同的数字，对于偶数个相同的相邻数字使用下面的方法提取
x = 0
if i + 1 < l:
while (i - x) >= 0 and (i + 1 + x) < l:
# 当前为为i，右侧为i+1+x,左侧为x
if s[i + 1 + x] == s[i - x]:
x += 1
else:
break
x -= 1
#
if 2 * x + 2 > max_length:
max_length = 2 * x + 2
palindromic = s[i - x:i + x + 2]
if palindromic == '':
palindromic = s[0]
return palindromic更直白的暴力求解，直接穷举给定字符中所有的长度大于2 的子串，并根据回文子串的定义，进行回文验证。整个复杂度是$,O(n^3)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27class Solution:
# 暴力匹配（超时）
def longestPalindrome(self, s: str) -> str:
# 特判
size = len(s)
if size < 2:
return s
max_len = 1
res = s[0]
# 枚举所有长度大于等于 2 的子串
for i in range(size - 1):
for j in range(i + 1, size):
if j - i + 1 > max_len and self.__valid(s, i, j):
max_len = j - i + 1
res = s[i:j + 1]
return res
def __valid(self, s, left, right):
# 验证子串 s[left, right] 是否为回文串
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True动态规划求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34class Solution:
def longestPalindrome(self, s: str) -> str:
size = len(s)
if size < 2:
return s
# 生成dp图，dp[i][j]表示s[i:j+1]是否为回文子串，如果是就是True,否则就是False
dp = [[False for _ in range(size)] for _ in range(size)]
max_len = 1
start = 0
# 对角线为true，实际上对角元素没什么含义，表示s[i]==s[i]，单个字符串肯定是回文的
for i in range(size):
dp[i][i] = True
# 这一步很关键，哪一个迭代在先哪一个在先在后
for j in range(1, size):
for i in range(0, j):
## 状态转移方程 d[i][j]= (s[i]==s[j]) and dp[i+1][j-1]
if s[i] == s[j]:
# 边界条件，[i + 1, j - 1]不构成区间，也就是j-1-i-1+1<2，此时dp[i+1][j-1]必然是回文的
if j - i < 3:
dp[i][j] = True
else:
dp[i][j] = dp[i + 1][j - 1]
else:
dp[i][j] = False
if dp[i][j]:
cur_len = j - i + 1
if cur_len > max_len:
max_len = cur_len
start = i
return s[start:start + max_len]中心扩散
和暴力的穷举类似，但是 更加巧妙，一次遍历，遍历到的位置假设为回文子串的中心位置，由中心位置想前后进行扩散，并判断是否是一个回文子串，此外，题目要的最长的回文子串，那么比找到的再短的串就不看了，随着迭代的进行，index每移动一步，观察区间都[i-max_len:i+1]，这不是相对中心位置i为对称的一个区间，这一步不好理解，因为不是从整个序列的中间开始找的，所以，遍历的索引index不太可能是窗口的中心位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution:
def longestPalindrome(self, s: str) -> str:
if not s: return ""
length = len(s)
if length == 1 or s == s[::-1]: return s
max_len,start = 1,0
for i in range(1, length):
# 观察区间的长度可能是偶数或者奇数，两个情况分别处理
# 向右边扩散位置为1，向左边扩散位置是max_len，
even = s[i-max_len:i+1]
odd = s[i-max_len-1:i+1]
print("env,odd",even,odd,max_len,i)
if i - max_len - 1 >= 0 and odd == odd[::-1]:
start = i - max_len - 1
# 如果是奇数，下次index移动，中心位置是个字符，整个观察区间增大2
max_len += 2
continue
if i - max_len >= 0 and even == even[::-1]:
start = i - max_len
# 如果是偶数，中心位置是两个字符之间的间隙，因此下次index移动，观察区间只增加1
max_len += 1
continue
return s[start:start + max_len]Manacher算法
代码
Manacher 实现
1 | class Solution(object): |
无重复字符的最长子串
题意
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。解析
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# k 子串的结束位置
# res 子串的长度
# c_dict 存储字符串的索引和对应的值
k, res, c_dict = -1, 0, {}
for i, c in enumerate(s):
# 字符c在字典中,且上次出现的下标大于当前长度的起始下标，这一步在记录当前的最长无重复子串
if c in c_dict and c_dict[c] > k:
k = c_dict[c]
else:
res = max(res, i-k) # 字符C不在字典中，更新res, 保持res是遍历到当前的最大的值
c_dict[c] = i
return res在迭代的过程中，记录字符和对应的位置，如果遇到了重复的字符出现，兵器出现重复的这个字符比上一次停止的位置靠后，那么就会更新新的结束标志K。这里面的条件
c_dict[c] > k，很重要，如果去掉这个条件，对于tmmzuxt这种类似的数据，当遇到重复字符m的时候，这个时候会更新k的值为1，随着迭代的进行，遇到重复的字符t的时候k又被更新成了0，这个显然是错误的，因为这个时候子串的结束位置显然应该比之前的1更大才对。
m个苹果n个盒子
这是一个经典的算法题，本题的前提假设是，苹果是相同的，盒子是相同的，并且允许有的盒子空置，问有多少种分法
迭代方法
如果苹果数量>=盒子的数量，以有盒子为空为分界，有两种情况
- 至少一个盒子为空，那么find(m,n-1)
- 没有盒子为空，那么先在所有的盒子里各放置一个苹果，这个不会影响分配结果，将剩余的苹果分配给这m个盒子，那么find(m-n,n)
如果苹果的数量<盒子的数量
肯定至少会有一些盒子是空的，又因为盒子的相同的，那么先去掉一些盒子(n-m)，并不会影响分配方案，也就是将这些苹果分配给剩下的这些盒子，那么对应find(m,m)
边界条件
- 当剩下的盒子数量为1时，不管剩下多少盒子，剩下的这些苹果必须全部放在这个盒子里面，也就是对应着1中分配方案
- 当剩下的苹果数量为0时，这个时候已经没有苹果了，也是一种分配方案
1 | def find(m,n): |
m个苹果n个人
本题是上一个题目”m个苹果n个盒子”的升级版。
苹果相同，人是不同的，并且允许有的人拿不到苹果，问多少种分法
分析
假设存在m个苹果，n个人来分，先给一个人拿一个苹果，那么剩下的m-1个苹果，由剩下的人来分，剩下了可能是n个人，也可能是n-1个人；直到剩下的苹果全部分完，在递归过程中，每次当前的人分的一个苹果，在查看剩下的m-1个苹果别的分配情况，苹果分完之后，
1 | def nums(m,n): |
宝石与石头[E]
题意：
给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此”a”和”A”是不同类型的石头。
示例 1:
1 | 输入: J = "aA", S = "aAAbbbb" |
- 示例 2:
1 | 输入: J = "z", S = "ZZ" |
注意:
S 和 J 最多含有50个字母。
J 中的字符不重复。解析
这道题很简单，两个序列，求一个序列中某些字符出现的次数
1 | class Solution: |
三种方法基本一致，方法2算是原生实现，没有调用count的方法，此外，由于给了条件J的字符不重复，因此这里没有进行J=set(J)的处理。
Z字形变换
题意：
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：
1 | L C I R |
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”LCIRETOESIIGEDHN”。
请你实现这个将字符串进行指定行数变换的函数：
1 | string convert(string s, int numRows); |
示例 1:
1 | 输入: s = "LEETCODEISHIRING", numRows = 3 |
示例 2:
1 | 输入: s = "LEETCODEISHIRING", numRows = 4 |
解析
1
2
3
4
5
6
7
8
9
10class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows < 2: return s
res = ["" for _ in range(numRows)]
i, flag = 0, -1
for c in s:
res[i] += c
if i == 0 or i == numRows - 1: flag = -flag
i += flag
return "".join(res)设置一个指针flage，按照给定的题意，生成n行，对每行的数据，按照z字形生成，数据会先向下在向上进行，转折点是行的索引为上下的两个点，也就是索引为0或者索引为n-1的时候。
手写经典算法
积分图/avgpooling/maxpooling
在计算机视觉领域中，如果要对一幅图像使用不同的方框滤波器重复卷积的时候，可以先计算区域求和表。区域求和表是指一定区域内所有像素的值的和，计算方法如下。
$$
s(i, j)=\sum_{k=0}^{i} \sum_{l=0}^{j} f(k, l)
$$
$f(k,l)$表示图像中点$(i,j)$对应的值。在实际计算的时候一般是利用递归的方法去计算
$$
s(i, j)=s(i-1, j)+s(i, j-1)-s(i-1, j-1)+f(i, j)
$$
在这里$s(i,j)$通常被称作积分图，也就是点$(i,j)$到左上角区域的所有元素的和。
积分图计算代码实现
1
def
手写公式
给定图像，尺寸为w,h,c，使用尺寸为k的方形滤波器以步长为s进行滤波，计算滤波之后的图像
1
