今天是LeetCode专题的第34篇文章，刚好接下来的题目比较简单，很多和之前的做法类似。所以我们今天出一个合集，一口气做完接下来的57、59和60这三题。
再次申明一下，为了节约篇幅，保证文章的质量，我跳过了LeetCode当中所有的Easy以及少量没什么营养的Medium和Hard的问题。Easy的问题都不是很难，即使是新手一般来说也不需要看题解，仔细想想也应该能搞定。所以就不占用篇幅了，如果大家有比较感兴趣的Easy问题，可以在下方的小程序处给我留言。
LeetCode 57 插入区间
题是57题Insert Interval，插入区间。题意会给定一组区间和一个单独的区间，要求将这个单独的区间插入区间集合，如果有两个区间存在交叉的情况，需要将它们合并，要求合并之后的终结果。从题意上来看，基本上和我们上一篇文章讲的区间合并问题完全一样。不同的是，在这题当中给定的这一组区间都是天然有序的，我们不需要对它进行排序。
区间已经有序了，剩下的就很简单了，我们只需要进行插入即可。区间插入的判断条件还是和之前一样，如果A区间的左端点在B区间左端点左侧，那么只要A区间的右侧端点在B区间左端点的右侧即可。所以这题基本上没有难度，就是一道裸题，我也不明白为什么官方给定的难度是Hard。
我们直接放出代码：
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
ret = []
# l, r记录待插入区间
l, r = newInterval
# 记录待插入区间是否完成插入
flag = False
for x, y in intervals:
# x, y记录当前区间
# 如果当前区间在待插入区间左侧，那么将当前区间插入答案
if y < l:
ret.append([x, y])
# 如果当前区间在待插入区间右侧，那么将两个区间都插入答案
elif r < x:
if not flag:
flag = True
ret.append([l, r])
ret.append([x, y])
# 否则，说明当前区间与待插入区间可以合并
# 更新待插入区间的范围
else:
l, r = min(l, x), max(r, y)
# 如果后还没有完成插入，说明待插入区间大于所有区间
# 手动插入，防止遗漏
if not flag:
ret.append([l, r])
return ret
只要理解了区间合并的条件，这题真的没有难度。
LeetCode 59 螺旋矩阵II
前不久我们刚出过螺旋矩阵I的题解，在螺旋矩阵I当中，我们给定了一个矩阵让我们螺旋形去遍历它。这题则相反，给定我们矩阵的长和宽，让我们生成一个这样的螺旋矩阵。
我们来看下样例：
在这题当中，我们使用54题的思路也完全可以解出来，但是这题更加简单了一些。由于是让我们构造一个矩阵，那么我们其实没有必要维护每个方向的边界了。只要出现出界或者是遇到了已经填好的数字那么就说明应该转向了。某种程度上来说，这题应该是I，之前的54题应该是II，因为这题更简单一些。
如果对54题解法不熟悉的同学，可以点击下方的传送门，学习一下方向数组的使用方法。
LeetCode54 螺旋矩阵，题目不重要，重要的是这个技巧
由于我们不需要维护每个方向的边界，并且移动的步数是固定的，更重要的是，转向每次多只会发生一次，所以这个流程非常简单，我们直接来看代码即可。
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
# 初始化答案
ret = [[ for _ in range(n)] for _ in range(n)]
# 初始化方向数组
fx = [[, 1], [1, ], [, -1], [-1, ]]
# 初始化方向以及起始点
dt =
x, y = ,
# n*n的方阵，一共需要填入n*n个数字
for i in range(n*n):
ret[x][y] = i+1
# 移动的下一个位置
x_, y_ = x+fx[dt][], y+fx[dt][1]
# 如果发生超界或者是遇到的数字大于0，说明需要转向
if x_ < or x_ >= n or y_ < or y_ >= n or ret[x_][y_] > :
dt = (dt + 1) % 4
# 转向之后的位置
x, y = x+fx[dt][], y+fx[dt][1]
return ret
LeetCode 60 第K个排列
这题是一个排列组合问题，给定一个整数n，它代表[1,2,3,...,n]这n个元素的序列。然后还有一个整数K，要求这n个元素从小到大第K个排列。
这题其实蛮有意思，我觉得可以上hard，但遗憾的是它有一个讨巧的办法，大概也许是这样，所以才被降级成Medium的吧。这个讨巧的办法应该蛮容易想到的，很明显，由于n个数字是确定的，所以小的排列一定是[1,2,3,...,n]。而我们之前做过一道LeetCode31题，它求的是给定一个排列，然后生成字典序比它大刚好一位的下一个排列。
既然如此，我们可以重复使用这个算法K-1次，就得到了答案了。对于做过31题的同学而言，这题毫无难度。如果对于31题解法不熟悉的同学可以点击下方传送门，回去复习一下。
LeetCode 31：递归、回溯、八皇后、全排列一篇文章全讲清楚
但其实可以不用这么麻烦，因为Python当中有自带的排列组合的工具库，我们可以直接调用，只用5行代码就可以搞定。
class Solution:
# 引入包
from itertools import permutations
def getPermutation(self, n: int, k: int) -> str:
# 由于后返回的结果要是string
# 生成['1','2','3',...,'n']的序列用来计算下一个排列
base = [str(i) for i in range(1, n+1)]
# 调用permutations会得到一个按顺序计算排列的生成器
perms = permutations(base, n)
for i in range(k):
# 我们调用k-1次next就能获得答案了
ret = next(perms)
return ''.join(ret)
class Solution:
def getPermutation(self, n: int, k: int) -> str:
frac = [1 for _ in range(n+1)]
# 生成一个序列存放所有的元素
nums = [i for i in range(1, n+1)]
# 计算每一位的种类数
for i in range(1, n):
frac[i] = i * frac[i-1]
ret = ''
k -= 1
for i in range(n-1, -1, -1):
# 计算第i位的数字是当前第几大的数
cur = k // frac[i]
# 放完之后取模，表示去除掉之前的所有情况数
k %= frac[i]
# 求出当前元素之后，需要从序列当中移除
ret += str(nums[cur])
nums.remove(nums[cur])
return ret
