代码随想录
由于本人参加了代码随想录的 python 组打卡，那么文章笔记的记录会偏向于记录 python 语言
Day 1
1、数组理论基础
- 数组是 上的相同类型数据的集合。
- 数组可以方便的 。
举个字符数组的例子，如图所示：
需要注意的两点是：
- 数组 的。
- 数组 的
正是因为 数组在内存空间的地址是连续的，
所以我们在 元素的时候，就难免
例如：删除下标为 3 的 元素，需要对下标为3的元素后面的所有元素都要做移动操作，如图所示：
数组的元素是不能删的，只能覆盖。
要是可以删，留个空位出来？那计算机内部怎么按照下标来找对应的元素？
那么二维数组直接上图：
那么二维数组在内存的空间地址是连续的么？
不同编程语言的内存管理是不一样的，以C++为例，在C++中二维数组是连续分布的。
我们来做一个实验，C++ 测试代码如下：
void test_arr() {
int array[2][3] = {
{0, 1, 2},
{3, 4, 5}
};
cout << &array[0][0] << " " << &array[0][1] << " " << &array[0][2] << endl;
cout << &array[1][0] << " " << &array[1][1] << " " << &array[1][2] << endl;
}
int main() {
test_arr();
}测试地址为：
0x7ffee4065820 0x7ffee4065824 0x7ffee4065828
0x7ffee406582c 0x7ffee4065830 0x7ffee4065834注意地址为16进制，可以看出二维数组地址是连续一条线的。
Ps : 0x7ffee4065820 与 0x7ffee4065824 差了一个4，就是4个字节，
因为这是一个 int 型的数组，所以两个相邻数组元素地址差4个字节。
0x7ffee4065828 与 0x7ffee406582c 也是差了4个字节，在16进制里 8 + 4 = c，c 就是12。
如图：
Ps : 相当于把一个二维的数组拉直了一样，先存了第一行，
然后第一行的最后一个元素紧接着第二行的第一个元素，这样就存成了一条连续的地址
这种可以叫做是 。（ 同理列优先存储的方式就是先第一列然后第二列... ）
2、704.二分查找
本节题目
给定一个 n 个元素有序的（升序）整型数组
nums和一个目标值target，写一个函数搜索
nums中的target，如果 。
示例 1 ：
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4示例 2 ：
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1tips :
你可以假设
nums中的所有元素是不重复的。n 将在 [1, 10000] 之间。
nums的每个元素都将在 [-9999, 9999]之间。
查找算法
查找：在一些数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程。
列表查找（ 线性表查找 ）：从列表中查找指定元素
- 输入：列表、待查找元素值
- 输出：元素下标（ 未找到元素时一般返回
None或者 -1 ）
内置列表查找函数 :
index()
顺序查找
: 也叫线性查找，从列表第一个元素开始，
顺序进行搜索，直到找到元素或搜索到列表的最后一个元素位置
时间复杂度：
O(n)
代码实现：
def linear_search(li,val):
"""
:param li: 传入要查找的序列
:param val: 传入要查找的值
:return: 找到返回查找到的值的索引，没找到返回None
"""
for ind,v in enumerate(li):
if v == val:
return ind
else:
return None二分查找
: 又叫折半查找，从 的初始候选区
li[0:n]开始，通过对待查找的值与候选区的中间值
mid的比较，可以使候选区减少一半。
- 时间复杂度：
O(log n)- 空间复杂度：
O(1)
图解算法逻辑：
- 例如 要在这个有序的 1- 9 的列表查找元素 3 的位置
- 首先初始化 :
left = 0andright = len(li)-1
- 根据
left和right算出mid mid = (left + right) // 2
- 上一步判断
mid > 3 - 则待查找的元素在
mid左侧 ， 修改right在mid左一位
- 根据新的
left和right重新计算mid
- 这次
mid小于待查找的元素，所以说明待查找的元素在mid右侧 - 修改
left为mid的右一位
最后重新计算
mid时 ， 满足了循环退出条件mid == 待查找元素(val)此时
mid的值就是要查找的元素的下标值，return mid 即可
代码实现：
def binary_search(li, val):
"""
:param li: 传入要查找的序列
:param val: 传入要查找的值
:return: 返回查找到的值的索引
"""
left = 0
right = len(li) - 1
while left <= right: # 候选区有值
# 候选区就是 left在左，right在右，然后夹着的中间的区域
mid = (left + right) // 2
if li[mid] == val:
return mid # 找到了返回查找元素的索引
elif li[mid] > val: # 待查找的值在mid左侧
right = mid - 1
else: # li[mid] < val 待查找的值在mid右侧
left = mid + 1
else: # 没找到return None
return None二分法的区间定义
二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。
例如到底是
while(left < right)还是while(left <= right)，到底是
right = middle呢，还是要right = middle - 1呢？
- 写二分法，区间的定义一般为两种，左闭右闭即
[left, right]，或者左闭右开即[left, right)。
：
我们定义 target 是在一个在左闭右闭的区间里，也就是 [left, right] （这个很重要非常重要）。
Ps : 其实上面图解的那种情况就是左闭右闭的写法
注意点：
while (left <= right)要使用<=，因为left == right是有意义的，所以使用<=
if (nums[middle] > target)right要赋值为middle - 1，因为当前这个nums[middle]一定不是
target，那么接下来要查找的左区间结束下标位置就是middle - 1
（左闭右闭）题目代码：
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1 # 定义target在左闭右闭的区间里，[left, right]
while left <= right:
middle = left + (right - left) // 2
if nums[middle] > target:
right = middle - 1 # target在左区间，所以[left, middle - 1]
elif nums[middle] < target:
left = middle + 1 # target在右区间，所以[middle + 1, right]
else:
return middle # 数组中找到目标值，直接返回下标
return -1 # 未找到目标值- ：
定义 target 是在一个在 左闭右开 的区间里，也就是
[left, right)，那么二分法的边界处理方式则截然不同。
注意点：
while (left < right)，这里使用<,因为left == right在区间[left, right)是没有意义的
- 比如给定一个区间
[1,1), 左闭取1，右开不取1，那么这个区间定义没有意义，根本没有值- 比如给定一个区间是
[1,2), 也就是上面的(left < right),1<2, 这样有意义，可以取 1
if (nums[middle] > target)right更新为middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以
right更新为middle，即：下一个查询区间不会去比较
nums[middle]
（左闭右开）题目代码：
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) # 定义target在左闭右开的区间里，即：[left, right)
while left < right: # 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
middle = left + (right - left) // 2
if nums[middle] > target:
right = middle # target 在左区间，在[left, middle)中
elif nums[middle] < target:
left = middle + 1 # target 在右区间，在[middle + 1, right)中
else:
return middle # 数组中找到目标值，直接返回下标
return -1 # 未找到目标值题目通过记录：
3、27.移除元素
本节题目
对应力扣题目链接：https://leetcode.cn/problems/remove-element/description/
给你一个数组 nums 和一个值 val，你需要 移除所有数值等于 val 的元素，
并 。
不要使用额外的数组空间，你必须仅使用
O(1)额外空间并 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5,
并且 nums 中的前五个元素为 0, 1, 3, 0, 4, 你不需要考虑数组中超出新长度后面的元素。
思路
多余的元素，删掉不就得了?
（ 虽然说我们 py 人有列表可以用，列表直接删掉指定元素它就会自动调整好位置 ）
但是为了学习的角度，我们当成我们只能用数组，而数组为什么不能直接删？
要知道 。
暴力解法
这个题目暴力的解法就是两层 for 循环，
- 一个for循环遍历数组元素
- 第二个for循环更新数组。
删除过程如下：
暴力解法的时间复杂度是
O(n^2)，这道题目暴力解法在 leetcode 上是可以过的。
暴力解法 - 代码如下：
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i, l = 0, len(nums)
while i < l:
if nums[i] == val: # 找到等于目标值的节点
for j in range(i+1, l): # 移除该元素，并将后面元素向前平移
nums[j - 1] = nums[j]
l -= 1
i -= 1
i += 1
return l双指针法
双指针法（快慢指针法）： 。
定义快慢指针：
- 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
- 慢指针：指向更新 新数组下标的位置
删除过程如下：
双指针 - 代码如下：
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
# 快慢指针
fast = 0 # 快指针
slow = 0 # 慢指针
size = len(nums)
while fast < size: # 不加等于是因为，a = size 时，nums[a] 会越界
# slow 用来收集不等于 val 的值，如果 fast 对应值不等于 val，则把它与 slow 替换
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow题目通过记录：
4、977.有序数组的平方
本节题目
对应力扣题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/description/
给你一个按 的整数数组 nums，
返回 每个数字的平方 组成的新数组，要求也按 。
示例 1：
- 输入：nums =
[-4,-1,0,3,10]- 输出：
[0,1,9,16,100]- 解释：平方后，数组变为
[16,1,0,9,100]，排序后，数组变为[0,1,9,16,100]示例 2：
- 输入：nums =
[-7,-3,2,3,11]- 输出：
[4,9,9,49,121]
Ps : 由给出的示例
nums可见，序列其实就是单调递增的，但负数比正数小，但是负数经过平方后不一定比正数小 ...
暴力排序
最直观的想法，莫过于：每个数平方之后，排个序，代码如下：
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
for i in range(len(nums)):
nums[i] *= nums[i]
nums.sort()
return nums这个时间复杂度是
O(n + nlogn)， 可以说是O(nlogn)的时间复杂度，但为了和下面双指针法算法时间复杂度有鲜明对比，记为
O(n + nlog n)。
双指针法
思想：
数组其实是有序的， 只不过负数平方之后可能成为最大数了。
那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
此时可以考虑双指针法了，
i指向 (左侧) 起始位置，j指向 (右侧) 终止位置。定义一个新数组
result，和 原 ( A ) 数组一样的大小，让k指向result数组终止位置。
如果
A[i] * A[i] < A[j] * A[j]说明两边都平方，右边的平方后更大，
所以把右边平方后的值放到
result数组 索引为k的位置上，且k--那么
result[k--] = A[j] * A[j];。类似地
A[i] * A[i] >= A[j] * A[j]那么result[k--] = A[i] * A[i];。如动画所示：
双指针 - 代码如下：
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
l, r, i = 0, len(nums)-1, len(nums)-1
res = [float('inf')] * len(nums) # 需要提前定义列表，存放结果
while l <= r:
if nums[l] ** 2 < nums[r] ** 2: # 左右边界进行对比，找出最大值
res[i] = nums[r] ** 2
r -= 1 # 右指针往左移动
else:
res[i] = nums[l] ** 2
l += 1 # 左指针往右移动
i -= 1 # 存放结果的指针需要往前平移一位
return resps :
float('inf')是生成一个 的数
此时的时间复杂度为
O(n)，相对于暴力排序的解法O(n + nlog n)还是提升不少的。
题目通过记录：
Day 2
1、209.长度最小的子数组
本节题目
对应力扣题目链接 ：https://leetcode.cn/problems/minimum-size-subarray-sum/description/
给定一个含有
n个正整数的数组和一个正整数s，找出该数组中满足其和
≥ s的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回
0。
示例：
- 输入：s = 7, nums = [2,3,1,2,4,3]
- 输出：2
- 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
提示：
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
暴力解法
这道题目暴力解法当然是 两个for循环，然后不断的寻找符合条件的子序列，
- 解释：
- 外层 for 循环控制起始位置
- 内层 for 循环控制终止位置
- 这样把全部情况遍历出来，然后找出符合条件的那个
- 但注意题目的提示 ：
1 <= nums.length <= 10^5- 我感觉 py 人都别考虑这个了，一看就得超时 ....
时间复杂度很明显是
O(n^2)。
这里给出代码，但肯定超时的，可以了解一下逻辑：
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
l = len(nums)
min_len = float('inf') # min_len 初始化为无穷大
for i in range(l): # 控制起始位置
cur_sum = 0
for j in range(i, l): # 控制终止位置
cur_sum += nums[j]
if cur_sum >= s:
min_len = min(min_len, j - i + 1) # 比较 min_len 与 当前长度
break
return min_len if min_len != float('inf') else 0ps :
float('inf')是 生成一个 的数 , 这样第一次min(min_len, j - i + 1)它比任何数小
滑动窗口
接下来就开始介绍数组操作中另一个重要的方法： 。
所谓滑动窗口， 。
在暴力解法中，是一个 for 循环控制起始位置，一个 for 循环控制终止位置，
用两个 for 循环 完成了一个不断搜索区间的过程。
那么滑动窗口如何用一个 for 循环来完成这个操作呢 ?
首先要思考 如果用一个 for 循环，那么应该表示 滑动窗口的 。
如果只用一个for循环来表示 滑动窗口的 起始位置，那么如何遍历剩下的终止位置？
此时难免再次陷入 暴力解法的怪圈 。
所以 只用一个 for 循环，那么这个循环的索引， 。
既然 for 循环是控制终止位置了，那么起始位置怎么控制呢？？
以题目中的示例来举例，s=7， 数组是 2，3，1，2，4，3，来看一下查找的过程：
最后找到
[4，3]是最短距离 。其实从动画中可以发现滑动窗口也可以理解为双指针法的一种！
只不过这种解法更像是一个窗口的移动，所以叫做滑动窗口更适合一些。
实现滑动窗口，主要确定如下三点：
- 窗口内是什么？
- 如何移动窗口的起始位置？
- 如何移动窗口的结束位置？
确定问题答案：
窗口就是 。
窗口的起始位置如何移动：如果当前**** ，窗口就要向前移动了（也就是该缩小了）。
窗口的结束位置如何移动：窗口的结束位置就是 ，也就是 for 循环里的索引。
可以发现 :
滑动窗口的精妙之处在于 ，
。从而将
O(n^2)暴力解法降为O(n)。
滑动窗口 - 代码如下 :
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
l = len(nums) # 数组nums长度
left = 0 # 起始位置
right = 0 # 终止位置
min_len = float('inf') # 最小长度 ，初始化为无穷大，后续有任何比它小的都会更新
cur_sum = 0 #当前的累加值
while right < l: # 当终止位置小于nums的长度就一直循环遍历终止位置
cur_sum += nums[right]
while cur_sum >= s: # 当前累加值大于目标值
# 若当前长度是更小的则更新min_len
min_len = min(min_len, right - left + 1)
# 在改变起始位置之前，不要忘了减掉当前起始位置的值
cur_sum -= nums[left]
# 改变起始位置，缩小窗口大小
left += 1
# 遍历终止位置
right += 1
return min_len if min_len != float('inf') else 0题目通过记录：
2、59.螺旋矩阵II
本节题目
对应力扣题目链接：https://leetcode.cn/problems/spiral-matrix-ii/description/
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例 1 :
输入: n = 3
输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
示例 2：
输入：n = 1 输出：[[1]]
提示：
1 <= n <= 20
题解
这道题目可以说在面试中出现频率较高的题目，
本题并不涉及到什么算法，就是 过程，但却十分考察对代码的掌控能力。
要如何画出这个螺旋排列的正方形矩阵呢？
还记得前面的 中有类似的思想，在这种多次循环中我们要坚持
也就是我们需要在一开始就想清楚那个循环过程，
模拟顺时针画矩阵的过程:
- 填充上行从左到右
- 填充右列从上到下
- 填充下行从右到左
- 填充左列从下到上
由外向内一圈一圈这么画下去。
可以发现这里的边界条件非常多，在一个循环中，如此多的边界条件，
如果不按照固定规则来遍历，那就是 一进循环深似海，从此offer是路人 。
那么如果按照 的区间定义来画一圈的话就是：
这里每一种颜色，代表一条边，我们遍历的长度，
可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。
但是还有一个 关键的点 需要注意：
比如像上图那样，就是
n = 3的情况 ，那么画出了一个3 * 3的正方形矩阵在画完圈之后，内部会还有一个位置是空缺的，也就是 当
当 n 为 偶数的时候则不会有那个空缺，画完圈则已经填满
像
n = 3的情况 ，就画出了一圈，然后空了一个我们可以很容易的知道一个问题的答案 ：
其实就是
n // 2圈
代码如下：
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
# 先生成一个 n x n 的空白正方形矩阵 matrix
matrix = [[0 for j in range(n)] for i in range(n)]
start_x = 0 # 画圈起始位置的横坐标
start_y = 0 # 画圈起始位置的纵坐标
cur_num = 1 # 当前填充的数值
offset = 1 # 当前这圈的终止位置偏移量
for i in range(n//2):
# 画 n // 2 圈
# 上边界，从左到右画圈
# 那么x不变，y向右走
for j in range(start_y,n-offset):
# range的左开右闭
# 那么下标范围就是 0 - (n-1)
matrix[start_x][j] = cur_num
# 填充一次后改变填充的数值
cur_num += 1
# 右边界，从上到下画圈
# 那么y不变，x向下走
for j in range(start_x,n-offset):
matrix[j][n-offset] = cur_num
# 填充一次后改变填充的数值
cur_num += 1
# 下边界，从右到左画圈
# 那么x不变，y向左走
for j in range(n-offset,start_y,-1):
matrix[n-offset][j] = cur_num
# 填充一次后改变填充的数值
cur_num += 1
# 左边界 ， 从下到上画圈
# 那么y不变，x向上走
for j in range(n-offset,start_x,-1):
matrix[j][start_y] = cur_num
# 填充一次后改变填充的数值
cur_num += 1
# 画完一圈后改变起始位置
start_x += 1
start_y += 1
# 改变偏移量
offset += 1
# 全部画完后判断 n 的奇偶
if n % 2 != 0:
matrix[start_x][start_y] = cur_num
return matrix题目通过记录：
3、58. 区间和
本节题目
本题为代码随想录后续扩充题目 ， 非力扣题目
给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。
- 输入描述 :
第一行输入为整数数组
Array的长度n，接下来n行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间，直至文件结束。
- 输出描述：
输出每个指定区间内元素的总和。
- 输入示例：
5
1
2
3
4
5
0 1
1 3- 输出示例：
3
9- 提示信息：
数据范围：
0 < n <= 100000暴力思路
首先来看本题，我们最直观的想法是什么？
那就是给一个区间，然后 把这个区间的和都累加一遍不就得了，是一道简单得不能再简单的题目。
虽然知道肯定会
TLE, 但是还是写一下暴力的代码：
# 数组长度 n
n = int(input())
# 数组
arr = []
# 构建数组
for i in range(n):
arr.append(int(input()))
# print(arr)
# 接下来是 q 次询问，每次询问给出左区间L 和 右区间R
# 需要输出区间 [L,R] 的 和
# 但是这道题没有询问 q 的输入，那么我们只能不断的接收输入，并且结合try-except
while True:
try:
l,r = map(int,input().split())
print(sum(arr[l:r + 1]))
except:
# 接收不到输入报错的时候退出这个死循环
break示例运行结果：
示例数据量太少，通过完全没有问题，但是提交看看：
没有悬念的
TLE, 因为它这个算法一直在做重复的事情，当数据一大时间就爆炸了...
来举一个极端的例子，如果我查询
m次，每次查询的范围都是从0到n - 1也就是
m次 询问，每次都是0 n-1,l永远是0，r永远是n-1这就很暴漏出这个算法的问题了，每次都是同一个区间的和，但是每次都重新计算
那么该算法的时间复杂度是
O(n * m)
前缀和
接下来我们来引入 前缀和，看看 前缀和 如何解决这个问题。
前缀和的思想是 : 。
( 有点动态规划的味道 ~ ~ )
前缀和 在涉及计算区间和的问题时非常有用 ！
前缀和的思路其实很简单，举个例子很容易就懂了。
例如，我们要统计
vec[i]这个数组上的区间和。我们先做累加，即
p[i]表示 下标0到i的vec[i]累加 之和。如图：
如果，我们想统计，在
vec数组上 下标2到下标5之间的累加和，那是不是就用
p[5] - p[1]就可以了。为什么呢 ？
这不就是我们要求的 下标 2 到下标 5 之间的累加和吗。
再如下图所示：
p[5] - p[1]就是上面的红色的区间部分
而 p 数组是我们之前就计算好的累加和，
所以后面每次求区间和的之后 我们只需要
O(1)的操作。
： 如果我们要求 区间下标
[2, 5]的区间和，那么应该是
p[5] - p[1]，而不是p[5] - p[2]如果说还记得 高中数学的数列方面的知识的话， 应该记得有一个公式
就是 ：
S n-m = Sn - Sm-1这就是上面的思想 （Sn是前n项的和 ）
代码实现：
# 数组长度 n
n = int(input())
# 数组
arr = []
# 构建数组
for i in range(n):
arr.append(int(input()))
# print(arr)
# 构建前缀和数组
sum_arr = [0 for i in range(n)]
sum_arr[0] = arr[0]
for i in range(1,n):
# 下标为0在前面初始化好，然后从1开始
sum_arr[i] = sum_arr[i-1] + arr[i]
# print(sum_arr)
# 接下来是 q 次询问，每次询问给出左区间L 和 右区间R
# 需要输出区间 [L,R] 的 和
# 但是这道题没有询问 q 的输入，那么我们只能不断的接收输入，并且结合try-except
while True:
try:
l,r = map(int,input().split())
if l==0:
print(sum_arr[r])
else:
print(sum_arr[r] - sum_arr[l-1])
except:
# 接收不到输入报错的时候退出这个死循环
break题目通过记录：
4、44.开发商购买土地
本节题目
本题为代码随想录后续扩充题目 ， 非力扣题目
【题目描述】
在一个城市区域内，被划分成了
n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。
现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。
然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，
而且每个子区域都必须包含一个或多个区块。
为了确保公平竞争，你需要找到一种分配方式，
。
注意：区块不可再分。
【输入描述】
第一行输入两个正整数，代表 n 和 m。
接下来的 n 行，每行输出 m 个正整数。
输出描述
请输出一个整数，代表两个子区域内土地总价值之间的最小差距。
【输入示例】
3 3
1 2 3
2 1 3
1 2 3【输出示例】
0【提示信息】
如果将区域按照如下方式划分：
1 2 | 3
2 1 | 3
1 2 | 3
两个子区域内土地总价值之间的最小差距可以达到 0。
数据范围：
1 <= n, m <= 100；
n 和 m 不同时为 1。思路
本题不同于
58.区间和, 这个变成二维的数据了，如果这个想要暴力求解的话， 应该是n^3的时间复杂度暴力的话即 ： 一个 for 枚举分割线， 嵌套 两个 for 去累加区间里的和。
虽然说，本题数据变成了二维的数据，但是因为是用 来分割，并非求
所以用不到 这么高级 ， 仔细研读题目可以发现，其实就是一个
思路就是：如果对
sum( 某一行 )作为该行的值，那么就变成了一个一维的数据，同理 如果对
sum( 某一列 )作为该列的值，那么也变成了一个一维的，这样的就实现了降维从而可以退化到前面我们 的思路
分别求出 行的前缀和 ＆ 列的前缀和 后 就可以遍历分割线的位置，
然后收集全部 土地总价值之间的差距 ，然后取里面的最小值就是答案
代码实现：
# import pprint
# 第一行输入两个正整数，n和m
n, m = map(int, input().split())
matrix = []
# 构建题目中输入的 n * m 的矩阵
for i in range(n):
cur_row = [*map(int, input().split())]
matrix.append(cur_row)
# pprint.pprint(matrix)
# 按行构建前缀和数组
sum_row = [0 for i in range(n)]
sum_row[0] = sum(matrix[0]) # 初始化第一个值为第一行的和
for i in range(1, n):
sum_row[i] = sum(matrix[i]) + sum_row[i - 1]
# print(sum_row)
# 按列构建前缀和
sum_col = [0 for i in range(m)]
sum_col[0] = sum([row[0] for row in matrix])
for i in range(1, m):
sum_col[i] = sum([row[i] for row in matrix]) + sum_col[i - 1]
# print(sum_col)
result = [] # 用于存储两土地之差的
# 按行分割的话，两土地之差有
for i in range(n - 1):
result.append(abs(sum_row[i] - (sum_row[n - 1] - sum_row[i])))
# 按列分割的话，两土地之差有
for i in range(m - 1):
result.append(abs(sum_col[i] - (sum_col[m - 1] - sum_col[i])))
print(min(result))- 题目通过记录：
Day 3
1、链表理论基础
关于链表， 你该了解这些 ！
什么是链表？
链表是一种通过指针串联在一起的线性结构，
每一个节点由两部分组成，一个是 一个是 （存放指向下一个节点的指针），
最后一个节点的指针域指向
null( 空指针的意思）。链表的入口节点 称为链表的头结点也就是
head。如图所示 ：
链表的类型
- 单链表
刚刚说的 ， 上图 ， 就是单链表
- 双链表
单链表中的指针域只能指向节点的下一个节点
next。双链表：每一个节点有两个指针域，一个指向下一个节点
next，一个指向上一个节点prev。双链表 既可以 向前查询 也可以 向后查询。
如图所示：
- 循环链表
循环链表，顾名思义，就是链表首尾相连。
循环链表可以用来解决
约瑟夫环问题。如图所示：
链表的存储方式
了解完链表的类型，再来说一说链表在内存中的存储方式。
数组 是在内存中是连续分布的，但是链表 在内存中可 。
： 很多人会有一个误解 ，
python的 原生数据结构list可以随意的增加元素，它不像
c的 数组那样， 需要更大的空间就需要定义，就会让人感觉 它内部是不是 链表 实现的 ？
其实不是，
Python列表本质上是一个 。这意味着列表在内存中是以 的存储空间来存储元素的，
并且还有个关键点，它
这就有下列优势：由于内存连续，通过索引访问元素非常高效，时间复杂度为
O(1)。而且与静态数组不同，列表的大小可以动态变化。
而且 ， 我们可以由此知道， 拿
python的列表 来做大量的增删时间复杂度是
O(n), 而 链表做增删的时间复杂度是O(1)。
链表是通过指针域的指针链接在内存中各个节点。
所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，
分配机制取决于操作系统的内存管理。
如图所示：
这个链表起始节点为 2， 终止节点为 7， 各个节点分布在内存的不同地址空间上，通过指针串联在一起。
链表的定义
关于链表的定义，很多同学经常会忘记
这是也是因为平时在刷
leetcode的时候，链表的节点都默认定义好了，直接用就行了所以 没有注意到链表的节点是如何定义的。
而在面试的时候，一旦要自己手写链表，就写的错漏百出。
代码随想录上的
C/C++定义链表节点方式，如下所示：
// 单链表
struct ListNode {
int val; // 节点上存储的元素
ListNode *next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};python 的定义链表节点的方式，如下所示：
class ListNode:
def __init__(self, val, next=None):
self.val = val # 节点上存储的元素 # 数据域
self.next = next # 指向下一个节点的指针 # 指针域链表的操作
Ps : 下列链表的操作的
python代码基于这个链表的定义：
class Node:
def __init__(self,item):
self.item = item # 数据域
self.next = None # 指针域- 链表的创建
用链表的数据结构来存储已有的数据
- 1. 头插法
在头指针
head的位置一个一个插入的方式来创建链表
假如说已有的链表如下：
可以看到 头指针
head现在 指向一个
如果要继续执行下一步头插法操作的话，就应该
"""----非可运行代码，仅为演示部分代码---"""
cur_node = Node(element) # 为当前遍历到的元素创建新节点
然后首先 新创建的这个节点需要
然后再 指向刚刚新插入的节点
头插法的
python代码如下 ：
def create_linklist_head(li):
# 传入一个列表li，使用头插法创建一个数据相同的链表
head = Node(li[0]) # 创建一个头节点，传入列表的第一个元素
for element in li[1:]:
# 遍历列表第二个及其后面的元素，使用头插法创建链表
cur_node = Node(element) # 为当前遍历到的元素创建新节点
cur_node.next = head # 先把新节点的 next 指向 head
head = cur_node # 然后再更新 head 为刚刚插入的节点
return head # 返回头节点- 2. 尾插法
在尾指针
tail的位置一个一个插入的方式创建链表
那么这种方式就需要两个指针
- 头指针：最后需要
return head， 需要靠 头指针来找到整个链表的数据- 尾指针 ：需要尾指针指定最后一个节点在哪，用于插入新的节点
然后后续过程也跟前面类似，注意顺序就好了，尾节点的
next先链接上，再更新tail
尾插法
python代码如下 ：
def create_linklist_tail(li):
# 传入一个列表li，使用尾插法创建一个数据相同的链表
head = tail = Node(li[0]) # 一开始初始化头节点和尾节点都是li[0]
for element in li[1:]: # 遍历li[1:]
cur_node = Node(element) # 为当前遍历到的元素创建新节点
tail.next = cur_node # 先让尾节点的next指向cur_node
tail = cur_node # 然后更新新的尾节点为刚刚插入的节点
return head # 返回头节点知道了头插法和尾插法，下面再提供一个简易的打印链表的方式来查看一下两个方式创建的链表怎么样：
# 打印链表
def print_linklist(head):
# 传入一个链表的头节点，根据这个节点遍历打印这个链表
count = 1
while head:
if head.next != None:
print(head.item,"-->",end=" ")
if count % 6 == 0: # 计数，每一行打印六个后再换行
print()
else:
print(head.item,end=" ")
head = head.next
count += 1
print()除函数定义外，演示代码如下：
# 头插法
lk = create_linklist_head([1,5,4,2,6])
print_linklist(lk)
# 尾插法
lk2 = create_linklist_tail([1,5,4,2,6])
print_linklist(lk2)运行效果：
可以见到 ： 头插法创建的链表是 的，尾插法创建的链表是 的
- 链表的插入
前面是从无到有创建一个链表，那如果已经有了一个链表，需要插入一个元素到特定位置怎么办？
关键还是要注意操作的顺序 :
- 为新插入的元素创建一个节点
- 把新节点链接到链表正确的位置
- 再把
cur_node链接到新插入的节点
：每次这些顺序问题只要注意 就行了
比如前面的 第三步 ， 如果放到前面的话 ，
cur_node的next先链接到新插入的节点，那么
cur_node节点后面的节点都会消失，游离在内存里，最后被清理掉 ...
链表的插入
python代码实现：
# 链表的插入
def lk_insert(lk,pos,ele):
"""
:param lk: 要插入的链表
:param pos: 要插入的位序（下标；索引）
:param ele: 要插入的元素
:return: lk
"""
if pos == 0:
# 为要插入的元素，创建一个节点
p = Node(ele)
p.next = lk
lk = p
return lk
# 为要插入的元素，创建一个节点
p = Node(ele)
count = 0 # 位序计数
cur_node = lk # 当前遍历到的节点，初始化为 head
# 需要遍历到要插入的位置的前一个节点 即 pos-1
while cur_node:
# 当前没遍历到Null就可以一直往下走
if count == pos - 1:
break
cur_node = cur_node.next
count += 1
else:
# 这里不是通过 break 退出的
# 就是没找到那个位置
print("pos out of range")
return lk
# 找到位置就可以执行插入操作
p.next = cur_node.next
cur_node.next = p
del cur_node
return lk测试代码：
# 尾插法
lk2 = create_linklist_tail([1,2,6])
print_linklist(lk2)
# 链表插入
lk2 = lk_insert(lk2,2,99) # 1. 插入99到下标为2的位置
print_linklist(lk2) # 打印
lk2 = lk_insert(lk2,4,88) # 2. 插入88到最后一个位置
print_linklist(lk2) # 打印
lk2 = lk_insert(lk2,0,33) # 3.插入33到第一个位置
print_linklist(lk2) # 打印
lk2 = lk_insert(lk2,99,100) # 4. 插入到没有的pos
print_linklist(lk2)运行效果：
- 链表的删除
给定一个链表，删除特定位置的元素
还是注意操作顺序就可以，关键点就是
- 找到要删除的节点
del_node和 要删除的节点的前一个节点cur_node- 先把
cur_node的next链接到del_node的next- 然后
del_node其实就不在这个链表了，可以认为是已经被删除了，但也可以del del_node
链表的删除
python代码实现：
# 链表删除
def lk_delete(lk,pos):
"""
:param lk: 要删除的链表
:param pos: 要删除的位序
:return: lk
"""
# 如果要删除的是第一个节点
if pos == 0:
lk = lk.next
return lk
# 位序计数
count = 0
# 遍历游标
cur_node = lk # 初始化为头节点
# 遍历游标找到要插入的位置的前一个位置 ， 也就是 pos - 1
while cur_node:
# 当没到Null就可以一直往下遍历
if count == pos - 1:
break
cur_node = cur_node.next
count += 1
else:
# 正常退出就是没找到
print("pos out of range")
return lk
# 执行删除操作
del_node = cur_node.next # 先记住被删除的节点
cur_node.next = del_node.next
del del_node
del cur_node
return lk测试代码：
# 尾插法
lk2 = create_linklist_tail([1,2,6,5,4])
print_linklist(lk2)
# 链表删除
lk2 = lk_delete(lk2,2) # 1. 删除下标为 2 的节点
print_linklist(lk2) # 打印
lk2 = lk_delete(lk2,3) # 2. 删除最后一个节点
print_linklist(lk2) # 打印
lk2 = lk_delete(lk2,0) # 3.删除第一个节点
print_linklist(lk2) # 打印
lk2 = lk_delete(lk2,999) # 4. 传入没有的pos
print_linklist(lk2) # 打印运行效果：
2、203.移除链表元素
本节题目
对应力扣链接：https://leetcode.cn/problems/remove-linked-list-elements/description/
题意：删除链表中等于给定值
val的所有节点。
示例 1： 输入：head = [1,2,6,3,4,5,6] , val = 6 输出：[1,2,3,4,5]
示例 2： 输入：head = [], val = 1 输出：[]
示例 3： 输入：head = [7,7,7,7], val = 7 输出：[]
思路
这里以链表
1 4 2 4来举例，移除元素4
如果使用 C/C++ 编程语言的话，不要忘了还要从内存中删除这两个移除的节点， 清理节点内存之后如图：
- 当然如果使用
java，python的话就不用手动管理内存了。
还要说明一下，就算使用
C++来做leetcode，如果移除一个节点之后，没有手动在内存中删除这个节点，
leetcode依然也是可以通过的，只不过，内存使用的空间大一些而已，但建议依然要养成手动清理内存的习惯。
这种情况下的移除操作，就是让节点
next指针直接指向下下一个节点就可以了那么因为单链表的特殊性，只能指向下一个节点，
刚刚删除的是链表的中第二个，和第四个节点，
那么
这里就涉及如下链表操作的两种方式 ：
- 直接使用原来的链表来进行删除操作。
- 设置一个虚拟头结点在进行删除操作。
- 第一种操作：直接使用原来的链表来进行移除。
移除头结点和移除其他节点的操作是不一样的，
因为链表的其他节点都是通过前一个节点来移除当前节点，而 。
所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，
这样就从链表中移除了一个头结点。
c++依然别忘将原头结点从内存中删掉。
这样移除了一个头结点，是不是发现，
在单链表中移除头结点 和 移除其他节点的操作方式是不一样，
其实在写代码的时候也会发现，需要 。
那么就到第二种操作的好处了
- 第二种操作：设计一个虚拟头节点
这样原链表的所有节点就都可以按照统一的方式进行移除了。
来看看如何设置一个虚拟头。依然还是在这个链表中，移除元素1。
这样每个结点都有一个 ，这样的话所有的节点的操作就都可以统一了
最后呢在题目中，return 头结点的时候，
别忘了
return dummyNode->next;， 这才是新的头结点因为
return head这种情况，你是不是没想到可能删除的节点有可能是 head ？？
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
# 创建一个虚拟头节点
dummy_node = ListNode()
# 虚拟头节点挂在 head 前面
dummy_node.next = head
# 遍历游标节点
cur_node = dummy_node # 初始化为最前面的虚拟头节点
while cur_node:
while cur_node.next != None and cur_node.next.val == val:
# 如果cur_node 的下一个节点的值就是val的话
# 循环地不断删除到不是val为止
# 删除操作
cur_node.next = cur_node.next.next
cur_node = cur_node.next # 向下遍历
# dummy_node.next 才是头节点
# 因为删除的节点也可能是 head
return dummy_node.next- 题目通过记录
3、707.设计链表
本节题目
对应力扣题目链接：https://leetcode.cn/problems/design-linked-list/description/
题意：
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，
则不会插入节点。如果 index 小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
题解
总结题意：
这道题目设计链表的五个接口：
- 获取链表第 index 个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第 index 个节点前面插入一个节点
- 删除链表的第 index 个节点
可以说这五个接口，已经覆盖了链表的常见操作，是练习链表操作非常好的一道题目
只要练熟了这道题，基本上就可以算掌握了链表的基本操作
链表操作的两种方式 :
- 直接使用原来的链表来进行操作。
- 设置一个虚拟头结点在进行操作。
只给出虚拟头节点的代码，因为这是很好的方式统一了很多操作：
代码如下：
# 单链表法 - 设计链表
# 定义链表节点类
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 定义链表类
class MyLinkedList:
def __init__(self):
# 虚拟头节点
self.dummy_head = ListNode()
self.size = 0
# 获取链表 第 index 个节点的数值
# 注意 index 从 0 开始算
def get(self, index):
# index 的合法性
if index < 0 or index >= self.size:
return -1 # 不合法
# 初始化为首元结点，因为如果index是0的话直接就是首元结点的值了
cur = self.dummy_head.next
for i in range(index):
cur = cur.next
return cur.val
# 在链表的最前面插入一个节点
def addAtHead(self, val):
# 这样先执行等号右边再执行左边也不会丢失链表，也是正确的顺序
self.dummy_head.next = ListNode(val=val, next=self.dummy_head.next)
self.size += 1
# 在链表的最后面插入一个节点
def addAtTail(self, val):
cur = self.dummy_head
while cur.next:
# 当cur.next不为Null一直遍历，最后一个节点的next为Null
cur = cur.next
# 新创建的节点的next默认为Null
cur.next = ListNode(val)
self.size += 1
# 在链表的第 index 个节点前面插入一个节点
def addAtIndex(self, index, val):
# index 的合法性
# 注意这里的 index > self.size 和其它地方不同，
# 这里index=self.size是可以插到最后一位的，不算非法
if index < 0 or index > self.size:
return
cur = self.dummy_head
for i in range(index):
cur = cur.next
# 这样找到的cur就是下标为 index-1 的节点
cur.next = ListNode(val=val,next=cur.next)
self.size += 1
# 删除链表的 第 index 个节点
def deleteAtIndex(self,index):
# index 的合法性
if index < 0 or index >= self.size:
return
cur = self.dummy_head
for i in range(index):
cur = cur.next
# 这样找到的cur就是下标为 index-1 的节点
cur.next = cur.next.next
self.size -= 1- 题目通过记录：
4、206.反转链表
本节题目
对应力扣题目链接：https://leetcode.cn/problems/reverse-linked-list/description/
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2 ：
输入：head = [1,2]
输出：[2,1]
示例 3 ：
输入：head = []
输出：[]
思路
如果再定义一个新的链表，实现链表元素的反转，那就简单太多了，并且这是对内存空间的浪费！
其实只需要改变链表的
next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表如图所示 :
那么看看动画演示是怎么反转的
首先定义一个
cur指针，指向头结点，再定义一个pre指针，初始化为null。首先要把
cur.next节点用tmp指针保存一下 ,否则接下来如果改变
cur的next反转指向pre那么则会导致链表丢失然后反转指向
cur.next = pre然后先移动
pre再移动cur，否则找不到cur现在指向的节点了也就是 先
pre = cur然后cur = tem
代码如下 ：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 初始化cur为head
cur = head
# 初始化pre为None
pre = None
while cur:
# cur指到None才结束循环
# 先保存cur的next，不然cur反转指针的时候会丢失链表
tmp = cur.next
cur.next = pre # 反转
# 先移动pre 再移动cur
pre = cur
cur = tmp
return pre- 题目通过记录
Day 4
1、24.两两交换链表中的节点
本节题目
对应力扣题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/description/
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
思路
这道题目正常 就行了 ， 然后使用 会方便很多
接下来就是交换相邻两个元素了，
此时
初始时，
cur指向虚拟头结点，然后进行如下三步 ：
记得要在 保存
tmp1, 否则而且要在 保存
tmp2，否则
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 虚拟头节点
dummy_head = ListNode(next=head)
# cur 初始化为虚拟头节点
cur = dummy_head
# 向后遍历
while cur.next != None and cur.next.next != None:
# 以第一步来注释说明
tmp1 = cur.next # 1.先保存首元结点和cur下一个位置的下一个节点
tmp2 = cur.next.next.next # 防止链表丢失
cur.next = cur.next.next # 2.cur指向下下个
cur.next.next = tmp1 # 3. 第二个节点再指回首元结点
tmp1.next = tmp2 # 之前的首元结点再指向第三个节点，完成第一步反转
cur = tmp1 # cur向后走
return dummy_head.next- 题目通过记录：
2、19. 删除链表的倒数第 N 个结点
本节题目
对应力扣题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
快慢指针
双指针的经典应用，如果要删除倒数第
n个节点，让fast移动n步，然后让
fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。思路是这样，但要注意一些细节：
- 首先推荐使用虚拟头结点
dummy_head之前也说过了，在这种删除操作，虚拟头节点可以统一操作 - 定义
fast和slow节点初始化为虚拟头节点
fast首先走n + 1步 ，因为只有这样同时移动的时候
slow才能指向 （方便做删除操作）如图：
fast和slow同时移动，直到fast指向末尾，如图 ：( 图片中有错别词：应该将 “只到” 改为 “直到” )
- 删除
slow指向的下一个节点，如图：
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
# 因为要走n+1步，先改变n
n += 1
# 虚拟头节点
dummy_head = ListNode(next=head)
# 初始化快慢指针都是虚拟头节点
fast = slow = dummy_head
# 快指针走 n+1 步 然后后续快慢指针一起走，这样距离就是 n+1
# 最后slow就会在倒数第 n 个节点的前一个节点，就可以执行删除操作
while n!= 0 and fast != None:
fast = fast.next
n -= 1
# 出来的话，要不就是正常走了n+1，要不就是没走完就走到头了
# 判断是哪种情况？？ **略写**
while fast != None:
fast = fast.next
slow = slow.next
# 执行删除操作
slow.next = slow.next.next
return dummy_head.next- 题目通过记录：
3、面试题 02.07. 链表相交
对应力扣题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回
null。
思路
简单来说，就是求两个链表交点节点的 。但是要注意，交点不是数值相等，而是 。
看如下两个链表，目前
curA指向链表A的头结点，curB指向链表B的头结点：
我们求出两个链表的长度，并求出两个链表长度的差值，
然后让
curA移动到，和curB末尾对齐的位置，如图：
此时我们就可以比较
curA和curB是否相同，如果不相同，同时向后移动
curA和curB，如果遇到
curA == curB，则找到交点。否则循环退出返回空指针。
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
lenA, lenB = 0, 0
# 遍历游标
cur = headA
# 求链表A的长度
while cur:
cur = cur.next
lenA += 1
cur = headB
# 求链表B的长度
while cur:
cur = cur.next
lenB += 1
curA,curB = headA,headB
if lenA > lenB: # 让curB为最长链表的头，lenB为其长度
curA,curB = curB,curA
lenA,lenB = lenB,lenA
for _ in range(lenB - lenA):
# 让curA和curB在同一个起点上
# 操作：curB移动(两个链表差值)个步数
curB = curB.next
while curA:
# 遍历curA 和 curB , 遇到相同则直接返回
if curA == curB: # 这样的条件判断的是内存地址
# 内存地址相同才算同一个节点
return curA
else:
curA = curA.next
curB = curB.next
return None- 题目通过记录：
4、142. 环形链表 II
本节题目
对应力扣题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/
给定一个链表的头节点
head，返回链表开始入环的第一个节点。 如果链表无环，则返回null。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数
pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果
pos是-1，则在该链表中没有环。注意：
pos不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
思路
这道题目，不仅考察对链表的操作，而且还需要一些数学运算。
主要考察两知识点：
- 判断链表是否环
- 如果有环，如何找到这个环的入口
- 判断链表是否有环
可以使用快慢指针法，分别定义
fast和slow指针，从头结点出发，
fast指针每次移动两个节点，slow指针每次移动一个节点，如果
fast和slow指针在途中相遇 ，说明这个链表有环。
❓ 为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢
首先第一点：
fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。
那又正如刚刚所说，如果有环的话，就不能是在环中永远的恰好错开吗？
先明确一下，
fast的速度是一次两步，slow的速度是一次一步，那么相对速度就是一次一步在普遍的情况下，
fast就是这样一步一步的接近slow, 然后最终都会演变成下图：
上图那样，各自再走一步就相遇了 ...
动画如下：
- 如果有环，如何找到这个环的入口
此时已经可以判断链表是否有环了，那么接下来要找这个环的入口了。
假设 从头结点到环形入口节点 的节点数为
x。 环形入口节点到fast指针与slow指针相遇节点节点数为
y。 从相遇节点 再到环形入口节点节点数为z。 如图所示：
那么相遇时：
slow指针走过的节点数为:x + y，
fast指针走过的节点数：x + y + n (y + z)，
n为fast指针在环内走了n圈才遇到slow指针，
(y+z)为 一圈内节点的个数A。
因为
fast指针是一步走两个节点，slow指针一步走一个节点，所以
fast指针走过的节点数 =slow指针走过的节点数 × 2：也就是 ：
(x + y) * 2 = x + y + n (y + z)两边消掉一个
(x+y):x + y = n (y + z)因为要找环形的入口，那么要求的是
x，因为x表示 头结点到 环形入口节点的的距离。所以要求
x，将x单独放在左面：x = n (y + z) - y,再从
n(y+z)中提出一个(y+z)来，整理公式之后为如下公式：x = (n - 1) (y + z) + z注意这里
n一定是大于等于1的，因为fast指针至少要多走一圈才能相遇slow指针。
这个公式说明什么呢 ？
先拿 n 为 1 的情况来举例，意味着
fast指针在环形里转了一圈之后，就遇到了slow指针了。当 n 为 1 的时候，公式就化解为
x = z，这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点，
那么当这两个指针相遇的时候就是 环形入口的节点 。
也就是在相遇节点处，定义一个指针
index1，在头结点处定一个指针index2。让
index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。动画如下：
那么 n 如果大于 1 是什么情况呢，就是
fast指针在环形转n圈之后才遇到slow指针。其实这种情况和 n 为 1 的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，
只不过，
index1指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
# fast 和 slow 都初始化为 head
fast = slow = head
# 都遍历向后走，fast两步，slow一步
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
# 两个指针相遇，移动一个指针回去head那
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
# 这里再相遇的位置就是环入口
return slow
return None补充
在推理过程中，可能会有一个疑问就是：
为什么第一次在环中相遇，
slow的步数是x+y( 如下图所示位置 )而不是
x + 若干环的长度 + y呢？
首先
slow进环的时候，fast一定是先进环来了。如果
slow进环入口，fast也在环入口，那么把这个环展开成直线，就是如下图的样子：
可以看出如果
slow和fast同时在环入口开始走，一定会在环入口 3 相遇，
slow走了一圈，fast走了两圈。重点来了，
slow进环的时候，fast一定是在环的任意一个位置，如图 ：
那么
fast指针走到 环入口 3 的时候，已经走了k + n个节点，
slow相应的应该走了(k + n) / 2个节点。因为
k是小于n的（图中可以看出），所以(k + n) / 2一定小于n。也就是说 slow 一定没有走到环入口3，而 fast 已经到环入口3了 。
这说明什么呢？
在 slow 开始走的那一环已经和 fast 相遇了。
那有同学又说了，为什么
fast不能跳过去呢？在之前已经说过一次了，fast 相对于 slow 是一次移动一个节点，所以不可能跳过去 。
- 题目通过记录：
Day 6
1、哈希表理论基础
哈希表
首先什么是哈希表，哈希表（英文名字为
Hash table，国内也有一些算法书籍翻译为散列表，大家看到这两个名称知道都是指
hash table就可以了）。
哈希表是根据
关键码的值而直接进行访问的数据结构。
这么官方的解释可能有点懵，其实直白来讲其实数组就是一张哈希表。
哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：
那么哈希表能解决什么问题呢， 。
例如要查询一个名字是否在这所学校里。
要枚举的话时间复杂度是
O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。
我们只需要初始化把这所学校里学生的名字都存在哈希表里，
在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。
将学生姓名映射到哈希表上就涉及到了 。
哈希函数
哈希函数，把学生的姓名直接映射为哈希表上的索引，
然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。
哈希函数如下图所示，通过
hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将 ，这样就把学生名字映射为哈希表上的索引数字了。
如果
hashCode得到的数值大于 哈希表的大小了，也就是大于tableSize了，怎么办呢？
此时为了 上，我们会在再次对数值做一个 的操作，
这样我们就保证了学生姓名一定可以映射到哈希表上了。
此时问题又来了，哈希表我们刚刚说过，就是一个数组。
如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，
也 。
接下来 登场
哈希碰撞
如图所示，小李和小王都映射到了索引下标 1 的位置， 。
一般哈希碰撞有两种解决方法， 和 。
- 拉链法
刚刚小李和小王在索引 1 的位置发生了冲突， 。
这样我们就可以通过索引找到小李和小王了
（数据规模是
dataSize， 哈希表的大小为tableSize）其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，
也不会因为链表太长而在查找上浪费太多时间。
- 线性探测法
使用线性探测法，一定要保证
tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题 。
例如冲突的位置，放了小李，那么就 。
所以要求
tableSize一定要大于dataSize，要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示：
常见的三种哈希结构
当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。
- 数组
- set （ 集合 ）
- map ( 映射 )
2、242.有效的字母异位词
本节题目
对应力扣题目链接：https://leetcode.cn/problems/valid-anagram/description/
给定两个字符串
s和t，编写一个函数来判断t是否是s的 字母异位词。
是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。
思路
先看暴力的解法，两层 for 循环，同时还要记录字符是否重复出现，很明显时间复杂度是
O(n^2)。暴力的方法这里就不做介绍了，直接看一下有没有更优的方式。
哈希表基础里提到，常见三种哈希结构有：数组，集合（
set）, 映射（map）那么 ，而且这道题目中字符串只有小写字符，
那么就可以定义一个数组，来记录字符串
s里字符出现的次数。.
需要定义一个多大的数组呢，定一个数组叫做
record，大小为 26 就可以了，初始化为 0，因为 。
为了方便举例，判断一下字符串
s= "aee",t = "eae"。操作动画如下：
定义一个数组叫做
record用来上记录字符串s里字符出现的次数。需要把字符映射到数组也就是哈希表的索引下标上，
因为字符 a 到字符 z 的 ASCII 是26个连续的数值，
所以我们需要使得字符 a 映射为下标 0 ，相应的字符 z 映射为下标 25。
关于字符和 ASCII 码值，在
python里有两个函数可以互求
chr(i)：这是一个将 的字符的函数。ord(c)： 这是一个将 ****的函数
那么这种情境下，我们就可以使用
ord()求 ASCII 值那么通过 ：
ord(某个小写字母) - ord(a)这种计算方式就可以把任意输入一个小写字母都可以映射到数组的
0-25的范围内
我们就可以遍历
s字符串，然后每个字符都经过上面的运算，取到的值，数组对应下标 做
+1操作 , 这样就可以实现统计了
同样在遍历字符串
t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。
那么最后检查一下，
record数组如果 ，说明字符串 s 和 t 一定是谁多了字符或者谁少了字符，
return false。最后如果 record 数组 ，说明字符串 s 和 t 是字母异位词，
return true。
时间复杂度为
O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为O(1)。
代码如下：
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# record 数组记录统计结果
record = [0] * 26
# 遍历字符串s 做+1操作
for i in s:
record[ord(i) - ord('a')] += 1
# 遍历字符串 t 做-1操作
for j in t:
record[ord(j)-ord('a')] -= 1
# 检查record数组
for i in record:
if i != 0:
return False
else:
return True- 题目通过记录：
补充
对于
python来说，还有一些非常有用的内置模块可以作为这道题的其他解法
defaultdict
Python 中的
defaultdict是一个非常好用的工具，它属于collections模块，是dict类的一个子类
❓ 什么是
defaultdict在普通的字典中，如果尝试访问一个不存在的键，会抛出
KeyError。而
defaultdict可以自动为不存在的键提供一个默认值，这个默认值的类型在创建
defaultdict时就需要指定。这样就避免了在使用字典时频繁地检查键是否存在，让代码更加简洁高效。
导入
collections模块中的defaultdict类：
from collections import defaultdict创建
defaultdict对象 :创建时 。
比如你想让 默认值是整数 0 ，就可以传入
int函数，因为int()不带参数时会返回 0 ：
dd = defaultdict(int)此时
dd就是一个默认值为 0 的defaultdict对象。
如果你想让 ，可以传入
list函数：
dd = defaultdict(list)使用
defaultdict和普通字典很像，可以直接通过键来访问值，如果键不存在，就会自动使用默认值。先看看 默认值为 0 的例子：
dd = defaultdict(int)
print(dd['a']) # 输出0，因为 'a' 这个键不存在，自动使用默认值0
dd['b'] = 5
print(dd['b']) # 输出5再看 默认值为空列表 的例子：
dd = defaultdict(list)
dd['a'].append(1)
dd['a'].append(2)
print(dd['a']) # 输出[1, 2]
print(dd['b']) # 输出[]，因为 'b' 这个键不存在，自动使用默认值空列表本题代码如下：
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
from collections import defaultdict
s_dict = defaultdict(int)
t_dict = defaultdict(int)
for x in s:
s_dict[x] += 1
for x in t:
t_dict[x] += 1
return s_dict == t_dict
defaultdict还有一个很好的应用，就是可以用在图的数据结构上：下面我随机数随机构建一个图：
graph = defaultdict(set)
for i in range(10): # 第几个节点
for _ in range(3): # 这个节点随机增加三个连接
graph[i].add(random.randint(1,10))
print(graph)运行结果：
defaultdict(<class 'set'>, {0: {1, 6, 9}, 1: {3, 4, 7}, 2: {1, 10, 4}, 3: {8, 4, 5}, 4: {8, 2, 4}, 5: {8, 3, 7}, 6: {9, 5, 7}, 7: {2, 6, 7}, 8: {8, 10, 5}, 9: {9, 6, 1}})这就生成了一幅
有向图：比如
0: {1, 6, 9}即 0 号节点的出度为 3 ，分别指向 {1, 6, 9} ...
Counter
Python 中的
Counter也是collections模块里的一个非常实用的类，它主要
❓ 什么是
Counter
Counter是一个字典子类，专门用于统计元素出现的次数。它可以对任意可哈希的对象进行计数，比如字符串、数字、元组等。
它会以元素为键，以元素出现的次数为值，创建一个计数器对象，方便我们快速统计和操作数据。
- 导入
collections模块中的Counter类：
from collections import Counter
- 创建
Counter对象有多种方式可以创建
Counter对象
- 直接传入可迭代对象 ：比如列表、字符串等
c = Counter(['red', 'blue', 'red', 'green', 'blue', 'blue'])
print(c)
# 输出 Counter({'blue': 3, 'red': 2, 'green': 1})c = Counter("gallahad")
print(c)
# 输出 Counter({'a': 3, 'l': 2, 'g': 1, 'h': 1, 'd': 1})- 传入一个字典：字典的键是元素，值是元素出现的次数
c = Counter({'red': 4, 'blue': 2})
print(c)
# 输出 Counter({'red': 4, 'blue': 2})- 使用关键字参数：参数名是元素，参数值是元素出现的次数
c = Counter(cats=4, dogs=8)
print(c)
# 输出 Counter({'dogs': 8, 'cats': 4})
Counter对象的常用方法
- 更新计数：使用
update()方法可以对计数器进行更新
c = Counter(['red', 'blue'])
c.update(['blue', 'yellow'])
print(c)
# 输出Counter({'blue': 2, 'red': 1, 'yellow': 1})如果更新的对象是字典，会将字典中的键值对作为元素和出现次数进行更新。
获取出现次数最多的元素：使用
most_common()方法，可以指定返回出现次数最多的前 n 个元素及其出现次数
c = Counter(['red', 'blue', 'red', 'green', 'blue', 'blue'])
print(c.most_common(1)) # 输出[('blue', 3)]
print(c.most_common(2)) # 输出[('blue', 3), ('red', 2)]如果不指定参数，则返回所有元素按出现次数从多到少排序的列表。
- 计数器的运算：可以对两个
Counter对象进行加、减等运算
c1 = Counter(['red', 'blue'])
c2 = Counter(['blue', 'yellow'])
print(c1 + c2) # 输出Counter({'blue': 2, 'red': 1, 'yellow': 1})
print(c1 - c2) # 输出Counter({'red': 1})减法运算会自动去除结果中出现次数为 0 或 负数 的元素。
- 实际应用场景
假设你有一个文本文件，想统计文件中每个单词出现的次数，就可以用
Counter来轻松实现：
from collections import Counter
with open('example.txt', 'r') as file:
words = file.read().split()
# word_counts = Counter(words)
word_counts = Counter()
for i in words:
word_counts.update(Counter(i))
print(word_counts)本题代码如下：
class Solution(object):
def isAnagram(self, s: str, t: str) -> bool:
from collections import Counter
a_count = Counter(s)
b_count = Counter(t)
return a_count == b_count3、349.两个数组的交集
本节题目
对应力扣题目链接：https://leetcode.cn/problems/intersection-of-two-arrays/description/
给定两个数组
nums1和nums2，返回 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
思路
这道题目，主要要学会使用一种哈希数据结构：
unordered_set，这个数据结构可以解决很多类似的问题。
注意题目特意说明：输出结果中的每个元素一定是唯一的，
也就是说输出的结果的 的， 同时可以
这道题用暴力的解法时间复杂度是
O(n^2)，那来看看使用哈希法进一步优化。但是要注意，使用数组来做哈希的题目，是因为题目都限制了数值的大小
而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。
而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。
需要提及的是，在
C++中提供了如下三种可用的数据结构：
- std::set
- std::multiset
- std::unordered_set
std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表，使用
unordered_set读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择
unordered_set。
我们使用
python的话，就可以使用提供的set这个数据结构，它也是可以去重但不要忘记 力扣的
return需要返回的是中括号的列表形式，最后记得转过来
思路如图所示：
代码如下：
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
# 使用默认字典数据结构
# 不需要判定字典有没有这个
from collections import defaultdict
result = set() # set去重
dd1 = defaultdict(int)
for i in nums1:
dd1[i] = 1 # 有这个数的标注为一就可以了
for i in nums2:
if i in dd1:
result.add(i)
del dd1[i]
return list(result)- 题目通过记录：
补充
那有同学可能问了，遇到哈希问题我直接都用
set不就得了，用什么数组啊。直接使用
set不仅占用空间比数组大，而且速度要比数组慢，
set把数值映射到key上都要做hash计算的。不要小瞧 这个耗时，在数据量大的情况，差距是很明显的。
同时我们可以利用
python的一些集合运算符很简洁的提交这道题代码如下：
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return list(set(nums1) & set(nums2))仅仅一行代码就完成了这道题 ！
顺便梳理一下有哪些集合的运算符：
- 交集 (
&)： 返回两个集合的交集。
set1 = {1, 2, 3}
set2 = {2, 3, 4}
print(set1 & set2) # 输出 {2, 3}- 并集 (
|)：返回两个集合的并集。
set1 = {1, 2, 3}
set2 = {2, 3, 4}
print(set1 | set2) # 输出 {1, 2, 3, 4}- 差集 (
-)：返回一个集合中存在而另一个集合中不存在的元素。
set1 = {1, 2, 3}
set2 = {2, 3, 4}
print(set1 - set2) # 输出 {1}
print(set2 - set1) # 输出 {4}- 对称差集 (
^)： 返回两个集合中不同时存在的元素。
set1 = {1, 2, 3}
set2 = {2, 3, 4}
print(set1 ^ set2) # 输出 {1, 4}4、202.快乐数
本节题目
对应力扣题目链接：https://leetcode.cn/problems/happy-number/description/
编写一个算法来判断一个数
n是不是快乐数。「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果
n是 快乐数 就返回true；不是，则返回false。
思路
这道题目看上去貌似一道数学问题，其实并不是！
题目中说了会 无限循环，那么也就是说 求和的过程中，sum可能会重复出现，这对解题很重要！
正如前面
哈希表理论基础所说 :
所以这道题目使用哈希法，来判断这个
sum是否重复出现，如果重复了就是
return false， 否则一直找到sum为 1 为止。判断
sum是否重复出现就可以使用unordered_set，也就是python的 原生set。还有一个难点就是求和的过程，如果对取数值各个数位上的操作不熟悉的话，也会比较艰难
代码如下：
class Solution:
def isHappy(self, n: int) -> bool:
# 记录每次 sum 的结果，如果sum重复出现就可以 return false 了
record = set()
while True:
n = self.get_sum(n)
if n == 1:
return True
# 如果中间结果重复出现，说明进入死循环了，这个数不是快乐数
if n in record:
return False
else:
record.add(n)
def get_sum(self,n):
# 求 n 的各个数位的平方的和
new_sum = 0
while n:
# n 为商，r为余数
n, r = divmod(n, 10)
new_sum += r ** 2
return new_sum- 题目通过记录：
5、1.两数之和
本节题目
给定一个整数数组
nums和一个整数目标值target，请你在该数组中找出 和为目标值
target的那 两个 整数，并 返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
思路
很明显暴力的解法是两层 for 循环查找，时间复杂度是
O(n^2)。
再强调一下：
本题呢，就需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，
某元素是否遍历过，也就是 是否出现在这个集合。那么我们就应该想到使用哈希法了。
同时，本题不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，
需要使用
key:value的结构，key存元素，val存下标，那么map正合适也就是我们可以使用
python的dict字典存储结构为
{key：数据元素，value：数组元素对应的下标}过程如下：
代码如下：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 有一个哈希表存放遍历过的元素
record = dict()
# 遍历 nums 数组
for idx,val in enumerate(nums):
# 需要在哈希表里查找的对象
s = target - val
if s in record:
return [record[s],idx]
# 记录下遍历过的 (遍历过的值:它的下标)
record[val] = idx
else:
return []- 题目通过记录：
Day 7
1、454.四数相加II
本节题目
给你四个整数数组
nums1、nums2、nums3和nums4，数组长度都是n，请你计算有多少个元组
(i, j, k, l)能满足：
0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
思路
本题这个题目一看感觉和
0015.三数之和，0018.四数之和差不多 ， 其实差很多。本题是使用 的经典题目 ， 而
0015.三数之和，0018.四数之和并不合适使用 哈希法因为 那两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的，很有多细节需要处理。
而这道题目是 ，只要找到
A[i] + B[j] + C[k] + D[l] = 0就可以 ，不用考虑有重复的四个元素相加等于 0 的情况，所以相对于那两题，还是简单了不少 ！
代码如下：
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
from collections import defaultdict
record = defaultdict(int)
res = 0 # 需要返回的结果值
# 遍历出 a + b 存进哈希结构map (字典dict)
# 结构是 (a+b的和的值:a+b这个值出现的次数)
for a in nums1:
for b in nums2:
# 默认字典的好处，第一次遍历到不用创建键，
# 后面遍历到也可以直接加，这样可以统一操作了
record[a+b] += 1
# print(record)
# 遍历出 c + d 然后 target = 0 - (c+d) ,在哈希表中找target
# 找到一次加一次对应value
for c in nums3:
for d in nums4:
target = 0-(c+d)
if target in record:
# 找到加对应value，而不是加一
res += record[target]
return res- 题目通过记录：
2、383.赎金信
本节题目
对应力扣题目链接：https://leetcode.cn/problems/ransom-note/description/
给你两个字符串：
ransomNote和magazine，判断ransomNote能不能由magazine里面的字符构成。如果可以，返回
true；否则返回false。
magazine中的每个字符只能在ransomNote中使用一次。
思路
这道题和
242.有效的字母异位词很像 ，242相当于 求 字符串 a 和 字符串 b 是否可以相互组成，而这道题目是求 字符串 a 能否组成 字符串 b ， 而不用管 字符串 b 能不能组成 字符串 a
本题判断第一个字符串
ransom能不能由第二个字符串magazines里面的字符构成，但是这里需要注意两点 :
第一点 “为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，
组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。
第二点 “ 你可以假设两个字符串均只含有小写字母。” 说明只有小写字母，这一点很重要
代码如下：
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
# 先遍历 magazine 里面出现的字符去哈希表里
# 这个跟字符异位词不同的是，字符异位词是一一对应了，最后要求哈希表全为0
# 而这个只需要magazine里面含有就可以了，也就是哈希表最后只要全大于等于0就对
from collections import defaultdict
record = defaultdict(int)
for i in magazine:
# magazine 加一操作
record[i] += 1
# 遍历ransomNote进行减一操作
for j in ransomNote:
record[j] -= 1
for val in record.values():
if val < 0:
return False
else:
return True- 题目通过记录：
3、15.三数之和
本节题目
给你一个整数数组
nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足
i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为
0且不重复的三元组。注意： 答案中不可以包含重复的三元组。
思路
- 哈希法（不推荐）
两层for循环就可以确定 两个数值，可以使用哈希法来确定 第三个数
0-(a+b)或者0 - (a + c)是否在 数组里出现过，其实这个思路是正确的，
但是我们有一个非常棘手的问题，就是题目中说的 。
把符合条件的三元组放进vector中，然后再 ，这样是非常费时的，
很容易超时，也是这道题目通过率如此之低的根源所在。
去重的过程不好处理，有很多小细节，如果在面试中很难想到位。
时间复杂度可以做到
O(n^2)，但还是比较费时的，因为不好做剪枝操作。
- 双指针法（推荐）
动画效果如下：
拿这个
nums数组来举例，首先将 ，然后有一层for循环，i从下标 0 的地方开始，同时定一个下标
left定义在i+1的位置上，定义下标right在数组结尾的位置上。依然还是在数组中找到
a,b,c使得a + b +c =0，我们这里相当于
a = nums[i]，b = nums[left]，c = nums[right]。
接下来
如果
nums[i] + nums[left] + nums[right] > 0就说明 ，因为数组是排序后了，所以
right下标就应该向左移动，这样才能让三数之和小一些。
同理如果
nums[i] + nums[left] + nums[right] < 0说明 ，
left就向右移动，才能让三数之和大一些，直到left与right相遇为止。
代码如下：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 收集结果集的列表
result = []
# 对传入的nums进行排序
nums.sort()
# 遍历 i
for i in range(len(nums)):
# 如果一个数就大于0就没必要往后走了，剪枝操作
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
# i 的去重在这里完成
continue
# 初始化 left 和 right
left = i + 1 # left 是 i 右边一位
right = len(nums) - 1 # right 是 nums 的最后一位开始
while (right > left): # 不能相等，相等就不是三元组了
target = 0 - nums[i]
if nums[left] + nums[right] == target:
# 这就是一组结果集
result.append([nums[i], nums[left], nums[right]])
# left 和 right 的去重
# 注意要在收集至少一个结果后进行
while left < right and nums[left + 1] == nums[left]:
left += 1
while right > left and nums[right - 1] == nums[right]:
right -= 1
# 确保 left 和 right 的下一个位置都不会导致重复结果后
# 进行同时向下一步遍历
left += 1
right -= 1
elif nums[left] + nums[right] > target:
# 大了的话，right向下走
right -= 1
else: # nums[left] + nums[right] < target
# 小了的话，left 往后走
left += 1
return result- 题目通过记录：
去重的思考
说到去重，其实主要考虑 三个数的去重。
a, b ,c, 对应的就是nums[i]，nums[left]，nums[right]
- a 的去重
a 如果重复了怎么办，a是
nums里遍历的元素，那么应该直接跳过去。但这里有一个问题，是判断
nums[i]与nums[i + 1]是否相同，还是判断
nums[i]与nums[i-1]是否相同。有同学可能想，这不都一样吗。 其实不一样！
都是和
nums[i]进行比较，是比较它的前一个，还是比较它的后一个。
如果我们的写法是 这样：
if nums[i] == nums[i + 1]: # 去重操作
continue那我们就把 三元组中出现重复元素的情况直接 pass 掉了。 例如
{-1, -1 ,2}这组数据，当遍历到第一个 -1 的时候，判断 下一个也是 -1，那这组数据就 pass了。
我们要做的是 ，
但 ！
所以这里是有两个重复的维度。
那么应该这么写：
if nums[i] == nums[i - 1]: # 去重操作
continue这么写就是当前使用
nums[i]，我们判断前一位是不是一样的元素，再看 {-1, -1 ,2} 这组数据，当遍历到 第一个 -1 的时候，只要前一位没有-1，
那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里。
这是一个非常细节的思考过程。
- b 和 c 的去重
在收集到一组结果集后，我们可以对
b,c进行去重因为本组遍历的
i是不变的，如果收集到一组满足条件的结果的话任意变
b,c其中一个，都会导致和前面那组三元组是完全一样的
if nums[left] + nums[right] == target:
# 这就是一组结果集
result.append([nums[i], nums[left], nums[right]])
# left 和 right 的去重
# 注意要在收集至少一个结果后进行
while left < right and nums[left + 1] == nums[left]:
left += 1
while right > left and nums[right - 1] == nums[right]:
right -= 14、18.四数之和
本节题目
给你一个由
n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且
[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target你可以按 返回答案 。
思路
四数之和，和
15.三数之和是一个思路 ， 都是使用 ，基本解法就是在
15.三数之和的基础上再套一层for循环
但是有一些细节需要注意，
例如：不要判断
num[k] > target就返回了，三数之和 可以通过num[i] > 0就返回了，是因为
0已经是确定是数了， 四数之和这道题目的target是任意值。比如 ：数组是
[-4, -3, -2, -1]，target是-10，不能因为
-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成
nums[i] > target and (nums[i] >=0 or target >= 0)就可以了。
- 解法对比：
15.三数之和的双指针解法是一层for循环num[i]为确定值，然后循环内有
left和right下标作为双指针，找到num[i] + num[left] + num[right]== target
18.四数之和的双指针解法是两层for循环nums[k]+nums[i]为确定值，依然是循环内有
left和right下标作为双指针，找出
nums[k] + nums[i] + nums[left] + nums[right] == target的情况，
三数之和的时间复杂度是
O(n^2), 四数之和的时间复杂度是O(n^3)。
那么一样道理，五数之和、六数之和等等都采用这种解法。
对于
15.三数之和双指针法就是将原本暴力O(n^3)，降为O(n^2)的解法，四数之和的双指针解法就是将原本暴力
O(n^4)的解法，降为O(n^3)的解法。
代码如下：
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
# 收集结果集的列表
result = []
# 对传入的nums进行排序
nums.sort()
for k in range(len(nums)):
# 一级剪枝
if (nums[k] > 0 or target > 0) and nums[k] > target:
break
# k 去重
if k > 0 and nums[k] == nums[k-1]:
continue
for i in range(k+1,len(nums)):
# 二级剪枝
if (nums[k] + nums[i] > 0 or target > 0) and nums[k] + nums[i] > target:
break
# i 去重
if i > k+1 and nums[i] == nums[i-1]:
continue
# 下面就是三数之和中的双指针的逻辑
# 初始化left 和 right
left = i + 1
right = len(nums) - 1
while left < right:
if nums[k] + nums[i] + nums[left] + nums[right] == target:
# 符合条件就加入结果集
result.append([nums[k],nums[i],nums[left],nums[right]])
# 加入结果集后要做双指针的去重
while left + 1 < right and nums[left] == nums[left+1]:
left += 1
while right - 1 > left and nums[right] == nums[right-1]:
right -= 1
# 去重后同时向内走一步
left += 1
right -= 1
elif nums[k] + nums[i] + nums[left] + nums[right] > target:
# 大了的话 ，right就向内收
right -= 1
else: # nums[k] + nums[i] + nums[left] + nums[right] < target
# 小了的话，left向内收
left += 1
return result- 题目通过记录：
Day 8
1、344.反转字符串
本节题目
对应力扣题目链接：https://leetcode.cn/problems/reverse-string/description/
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组
s的形式给出。不要给另外的数组分配额外的空间，
你必须 原地修改输入数组 、使用
O(1)的空间复杂度解决这一问题。