1. LeetCode-数组和字符串

1.数组简介

1.1 集合、列表和数组

集合

集合定义：由一个或多个确定的元素所构成的整体。

集合的特性：

首先，集合里的元素类型不一定相同。你可以将商品看作一个集合，也可以将整个商店看作一个集合，这个商店中有人或者其他物品也没有关系。
其次，集合里的元素没有顺序。我们不会这样讲：我想要集合中的第三个元素，因为集合是没有顺序的。
事实上，这样的集合并不直接存在于编程语言中。然而，实际编程语言中的很多数据结构，就是在集合的基础上添加了一些规则形成的。

列表

列表（又称线性列表）的定义为：是一种数据项构成的有限序列，即按照一定的线性顺序，排列而成的数据项的集合。

在编程语言中，列表最常见的表现形式有数组和链表，而我们熟悉的栈和队列则是两种特殊类型的列表。除此之外，向列表中添加、删除元素的具体实现方式会根据编程语言的不同而有所区分。

数组

数组是列表的实现方式，它具有列表的特征，同时也具有自己的一些特征。然而，在具体的编程语言中，数组这个数据结构的实现方式具有一定差别。比如 C++ 和 Java 中，数组中的元素类型必须保持一致，而 Python 中则可以不同。Python 中的数组叫做 list，具有更多的高级功能。

那么如何从宏观上区分列表和数组呢？这里有一个重要的概念：索引。

首先，数组会用一些名为索引的数字来标识每项数据在数组中的位置，且在大多数编程语言中，索引是从 0 算起的。我们可以根据数组中的索引，快速访问数组中的元素。

而列表中没有索引，这是数组与列表最大的不同点。

其次，数组中的元素在内存中是连续存储的，且每个元素占用相同大小的内存。

相反，列表中的元素在内存中可能彼此相邻，也可能不相邻。比如列表的另一种实现方式——链表，它的元素在内存中则不一定是连续的。

1.2 数组的操作

读取元素

读取数组中的元素，是通过访问索引的方式来读取的，索引一般从 0 开始。在计算机中，内存可以看成一些已经排列好的格子，每个格子对应一个内存地址。一般情况下，数据会分散地存储在不同的格子中。而对于数组，计算机会在内存中为其申请一段连续的空间，并且会记下索引为 0 处的内存地址。我们知道，计算内存地址这个过程是很快的，而我们一旦知道了内存地址就可以立即访问到该元素，因此它的时间复杂度是常数级别，为 O(1)。

查找元素

假如我们对数组中包含哪些元素并不了解，只是想知道其中是否含有元素 "E"，数组会如何查找元素 `"E" 呢？

与读取元素类似，由于我们只保存了索引为 0 处的内存地址，因此在查找元素时，只需从数组开头逐步向后查找就可以了。如果数组中的某个元素为目标元素，则停止查找；否则继续搜索直到到达数组的末尾。

我们发现，最坏情况下，搜索的元素为 "R"，或者数组中不包含目标元素时，我们需要查找 n 次，n 为数组的长度，因此查找元素的时间复杂度为 O(N)，N为数组的长度。

插入元素

假如我们想在原有的数组中再插入一个元素 "S" 呢？

如果要将该元素插入到数组的末尾，只需要一步。即计算机通过数组的长度和位置计算出即将插入元素的内存地址，然后将该元素插入到指定位置即可。

然而，如果要将该元素插入到数组中的其他位置，则会有所区别，这时我们首先需要为该元素所要插入的位置腾出空间，然后进行插入操作。我们发现，如果需要频繁地对数组元素进行插入操作，会造成时间的浪费。事实上，另一种数据结构，即链表可以有效解决这个问题，我们将在另外的卡片中进行学习。

删除元素

删除元素与插入元素的操作类似，当我们删除掉数组中的某个元素后，数组中会留下空缺的位置，而数组中的元素在内存中是连续的，这就使得后面的元素需对该位置进行填补操作。

当数组的长度为 n 时，最坏情况下，我们删除第一个元素，共需要的步骤数为 1 + (n - 1) = n 步，其中，1 为删除操作，n - 1 为移动其余元素的步骤数。删除操作具有线性时间复杂度，即时间复杂度为 O(N)，N为数组的长度。

LC 寻找数组的中心索引

给你一个整数数组 nums ，请计算数组的中心下标。

数组中心下标是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回最靠近左边的那一个。如果数组不存在中心下标，返回 -1 。

解题思路

本题给出了三种情况：

中心下标左侧元素相加之和等于右侧元素相加之和，返回中心下标；
数组中只有一个数，返回中心下标==0；
数组中不满足此条件的中心下标，返回 -1；

从以上三种情况考虑，情况1和2是同种类型，所以总体是两种情况。i的范围是range(n),n=len(nums) 。另外使用列表求和sum（）函数设置左右侧总和相等的条件，嵌套使用for循环遍历的方法找出符合条件的的中心下标i。具体代码如下：

class Solution:def findMiddleIndex(self, nums: List[int]) -> int:n = len(nums)  for i in range(n):if sum(nums[:i]) == sum(nums[i+1:n]):return i# 如果遍历完整个列表都没有找到满足条件的索引，则返回-1    return -1

PS:Python中print和return的区别_python中return和print的区别-CSDN博客

LC 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

解题思路1：

‘在数组中找到目标值，并返回其索引’，如果目标值在数组内，可以使用for循环遍历，找到则返回其位置下标，如果没找到则使用对比大小的方法进行排序。

而用nums[i] >=target作为判断则完美地继承了以上算法，如果target大于nums中的所有值，则直接返回n值作为target的下标。

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:n = len(nums)for i in range(n):if nums[i] >= target:return ireturn n

解题思路2：

请注意这个提示句：“请必须使用时间复杂度为 O(log n) 的算法。”

时间复杂度为 O(logn) 的算法通常涉及到分而治之的策略，即算法通过不断将问题分解成更小的子问题来解决，每次分解后问题的规模大致变为原来的一半（或固定比例）。这种策略在二分查找、快速排序（平均情况）、归并排序等算法中都有体现。我们要用二分法来解题比较合适。

示例：二分查找

二分查找是一个典型的 O(logn) 时间复杂度的算法。在这个算法中，每次迭代都将搜索区间减半，直到找到目标值或搜索区间为空。

初始时，搜索区间是整个数组，长度为 n。
每次迭代，搜索区间被减半。
因此，迭代次数（即递归深度）是 log2n（以2为底的对数，因为每次都将区间分成两半）。
所以，二分查找的时间复杂度是 O(logn)。

# 左闭右开区间写法def lower_bound2(nums: List[int], target: int) -> int:left = 0right = len(nums)  # 左闭右开区间 [left, right)while left < right:  # 区间不为空# 循环不变量：# nums[left-1] < target# nums[right] >= targetmid = (left + right) // 2if nums[mid] < target:left = mid + 1  # 范围缩小到 [mid+1, right)else:right = mid  # 范围缩小到 [left, mid)return left  # 或者 right

LC 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

解题思路：

该题的重点在于判断列表中的列表最后一位与下一个列表的首位大小，如果大于，则合并。先用到排序函数xx.sort()将整个数组intervals排序，然后开始判断；还会用到for循环遍历以及嵌套if...else判断条件。

class Solution:  def merge(self, intervals: List[List[int]]) -> List[List[int]]:  # 直接对 intervals 进行排序，这里省略了 lambda 函数，因为 Python 的 sort 方法在  # 列表中的元素是元组或列表时，默认按照第一个元素进行排序，这符合我们的需求。  intervals.sort()  # 初始化结果列表，并直接将 intervals 的第一个区间加入其中  # 这样可以避免在循环中处理第一个区间的特殊情况  ans = [intervals[0]]  # 遍历 intervals 列表（除了第一个元素，因为它已经被加入到 ans 中了）  for s, e in intervals[1:]:  # 如果当前区间的起始位置大于 ans 中最后一个区间的结束位置，  # 则说明这两个区间不相交，直接将当前区间添加到 ans 中  if ans[-1][1] < s:  ans.append([s, e])  # 否则，说明当前区间与 ans 中的最后一个区间有重叠，  # 更新 ans 中最后一个区间的结束位置为两个区间结束位置的较大值  else:  ans[-1][1] = max(ans[-1][1], e)  # 返回合并后的区间列表  return ans

2. 二维数组

2.1 简介

二维数组是一种结构较为特殊的数组，只是将数组中的每个元素变成了一维数组。

所以二维数组的本质上仍然是一个一维数组，内部的一维数组仍然从索引 0 开始，我们可以将它看作一个矩阵，并处理矩阵的相关问题。

示例：

类似一维数组，对于一个二维数组 A = [[1, 2, 3, 4],[2, 4, 5, 6],[1, 4, 6, 8]]，计算机同样会在内存中申请一段连续的空间，并记录第一行数组的索引位置，即 A[0][0] 的内存地址，它的索引与内存地址的关系如下图所示。

注意，实际数组中的元素由于类型的不同会占用不同的字节数，因此每个方格地址之间的差值可能不为 1。

实际题目中，往往使用二维数组处理矩阵类相关问题，包括矩阵旋转、对角线遍历，以及对子矩阵的操作等。

LC 旋转矩阵

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？（答：你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。）

解题思路1：

根据以上「元素旋转公式」，考虑遍历矩阵，将各元素依次写入到旋转后的索引位置。但仍存在问题：在写入一个元素 matrix[i][j]→matrix[j][n−1−i] 后，原矩阵元素 matrix[j][n−1−i] 就会被覆盖（即丢失），而此丢失的元素就无法被写入到旋转后的索引位置了。

为解决此问题，考虑借助一个「辅助矩阵」暂存原矩阵，通过遍历辅助矩阵所有元素，将各元素填入「原矩阵」旋转后的新索引位置即可。

class Solution:def rotate(self, matrix: List[List[int]]) -> None:n = len(matrix)# 深拷贝 matrix -> tmptmp = copy.deepcopy(matrix)# 根据元素旋转公式，遍历修改原矩阵 matrix 的各元素for i in range(n):for j in range(n):matrix[j][n - 1 - i] = tmp[i][j]return matrix

如以上代码所示，遍历矩阵所有元素的时间复杂度为 O(N2) ；由于借助了一个辅助矩阵，空间复杂度为 O(N2) 。

LC 零矩阵

解题方法：数组标记

先遍历一遍矩阵，分别用数组 rows 和 column 标记待清零的行和列。

然后再遍历一遍矩阵，将 rows 和 column 中标记的行和列对应的元素清零。

class Solution:def setZeroes(self, matrix: List[List[int]]) -> None:"""Do not return anything, modify matrix in-place instead."""r,c = len(matrix),len(matrix[0])rows = set()  #set()用于存储不重复的元素集column = set() #set()用于存储不重复的元素集for i in range(r):for j in range(c):if matrix[i][j] == 0:rows.add(i)column.add(j)for i in rows:for j in range(c):matrix[i][j] = 0for j in column:for i in range(r):matrix[i][j] = 0return matrix

3. 字符串

3.1 简介

字符串是由零个或多个字符组成的有限序列。一般记为 s = a1a2...an。它是编程语言中表示文本的数据类型。

为何单独讨论字符串类型

我们知道，字符串与数组有很多相似之处，比如使用名称[下标] 来得到一个字符。那么我们为什么要单独讨论字符串呢？原因主要有：

1.字符串的基本操作对象通常是字符串整体或者其子串

例如有这样一个字符串序列：I like leetcode 现在你想把这句话反向输出，可能会变成这样：

edocteel ekil I

这是我们想要的结果吗？你可能会回答不是，因为它没有任何意义。我们通常希望单词仍然维持原来的顺序，这样反向输出之后就是：

Leetcode like I

这样的结果对于我们来讲是不是更满意呢？维持单词本身的顺序使得我们方便进行更多操作，这里的每个单词就叫做字符串的「子串」，通常，我们的操作对象更多情况下是这些子串。

2. 字符串操作比其他数据类型更复杂（例如比较、连接操作）

对于不同的编程语言，字符串的某些操作会有所不同。下面我们将从字符串的「比较」和「连接」操作两个方面分别进行讲解。

比较函数

字符串有它自己的比较函数（我们将在下面的代码中向你展示比较函数的用法）。

然而，存在这样一个问题：

我们可以用 “==” 来比较两个字符串吗？

这取决于下面这个问题的答案：

我们使用的语言是否支持运算符重载？

如果答案是 yes （例如 C++、Python）。我们可以使用 == 来比较两个字符串；
如果答案是 no （例如 Java），我们可能无法使用 == 来比较两个字符串。当我们使用 == 时，它实际上会比较这两个对象是否是同一个对象。

连接操作

对于不同的编程语言中，字符串可能是可变的，也可能是不可变的。不可变意味着一旦字符串被初始化，你就无法改变它的内容。

在某些语言（如 C ++）中，字符串是可变的。你可以像在数组中那样修改字符串。
在其他一些语言（如 Java、Python）中，字符串是不可变的。

LC 最长公共前缀

解题思路

1.len（）函数得到其长度，使用for循环遍历

2.字符串下面有下标，再嵌套一层for循环遍历

3.依次判断所有字符串的每一列是否相同。

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:n = len(strs)m = len(strs[0])if len(strs) == 0:return ''for i in range(m):c = strs[0][i]for j in range(1,n):#检查当前索引 i 是否已经超出了当前字符串 strs[j] 的长度#检查当前字符串 strs[j] 在索引 i 处的字符是否与基准字符 c 相同if i == len(strs[j]) or strs[j][i] != c:return strs[0][0:i]return strs[0]

4 双指针技巧

4.1 情景1

在上一章中，我们通过迭代数组来解决一些问题。通常，我们只需要一个指针进行迭代，即从数组中的第一个元素开始，最后一个元素结束。然而，有时我们会使用两个指针进行迭代。

以下代码可以供你参考：

def reverseString(self, s):i, j = 0, len(s) - 1while i < j:s[i], s[j] = s[j], s[i]i += 1j -= 1

LC 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

解题方法

初始化：设置两个指针l和r分别指向列表首尾元素
步骤：交换s[l]和s[r]对应元素，并更新指针位置（l+=1,r-=1），直到两个指针相遇

class Solution:def reverseString(self, s: List[str]) -> None:"""Do not return anything, modify s in-place instead."""l,r = 0,len(s)-1while l<r:s[l],s[r] = s[r],s[l]l += 1r -= 1

LC 数组拆分

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。返回该最大总和。

解题方法：

思路就是对输入的数组 nums 进行排序，然后依次求相邻的两个元素的最小值，总和就是结果。

class Solution:def arrayPairSum(self, nums: List[int]) -> int:nums.sort()res = 0n = len(nums)for i in range(0,n,2):res += min(nums[i],nums[i+1])return res

4.2 情景2

有时，我们可以使用两个不同步的指针来解决问题，即快慢指针。与情景一不同的是，两个指针的运动方向是相同的，而非相反。

让我们从一个经典问题开始：

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

如果我们没有空间复杂度上的限制，那就更容易了。我们可以初始化一个新的数组来存储答案。如果元素不等于给定的目标值，则迭代原始数组并将元素添加到新的数组中。

实际上，它相当于使用了两个指针，一个用于原始数组的迭代，另一个总是指向新数组的最后一个位置。
考虑空间限制

如果我们不使用额外的数组，只是在原数组上进行操作呢？

此时，我们就可以采用快慢指针的思想：初始化一个快指针 fast 和一个慢指针 slow，fast 每次移动一步，而 slow 只当 fast 指向的值不等于 val 时才移动一步。

def removeElement(self, nums: List[int], val: int) -> int:slow = 0n = len(nums)for fast in range(n):if nums[fast] != val:nums[slow] = nums[fast]slow += 1return slow

小结

这是你需要使用双指针技巧的另一种非常常见的情况：同时有一个慢指针和一个快指针。

解决这类问题的关键是:确定两个指针的移动策略。

与前一个场景类似，你有时可能需要在使用双指针技巧之前对数组进行排序，也可能需要运用贪心法则来决定你的运动策略。

LC 移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

解题方法：

双指针之快慢指针法,for循环遍历跳过nums中等于val的情况，且让慢指针的下标值等于快指针的下标值，计算慢指针的次数总和

class Solution:def removeElement(self, nums: List[int], val: int) -> int:n = len(nums)slow = 0for fast in range(n):if nums[fast] != val:nums[slow] = nums[fast] slow += 1return slow

LC 最大连续1的个数

给定一个二进制数组 nums ，计算其中最大连续 1 的个数。

解题方法：

先得到数组长度，然后for循环遍历，然后设定if条件：nums[i] =1 and nums[i+1] =1时，记录次数，遇到0时，次数清零，再将次数储存起来，最后max得到最大值。

个人想的笨方法：

class Solution:def findMaxConsecutiveOnes(self, nums: List[int]) -> int:n = len(nums)slow = 0m = []if max(nums) == 0:return 0for i in range(n):if nums[i] == 1 :slow += 1m.append(slow)else:slow = 0m.append(slow)return max(m)