Fork me on GitHub

leetcode数组类算法精析

面试中的算法问题,有很多并不需要复杂的数据结构支撑。就是用数组,就能考察出很多东西了。其实,经典的排序问题,二分搜索等等问题,就是在数组这种最基础的结构中处理问题的,今天主要介绍leetcode中典型的数组类问题,主要介绍这类问题的一些常用解法:做好初始定义;基础算法思想应用;对撞指针;滑动窗口法等。所有题解代码采用python实现。

做好初始定义

做数组类算法问题的时候,我们常常需要定义一个变量,明确该变量的定义,并且在书写整个逻辑的时候,要不停的维护住这个变量的意义。也特别需要注意初始值和边界的问题

leetcode(283):移动零

题目描述

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

示例:

1
2
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

  • 必须在原数组上操作,不能拷贝额外的数组。
  • 尽量减少操作次数。

直观解题思路

首先遍历一遍数列,用另个数列按顺序存储所有非0的元素,在将存储的非零元素按顺序复制到原数列中,空位补0即可

paste image

直观的解题思路新建额外的数组,不符合要求,但是对于我们下面的优化算法很有起始

简单的优化

只要把数组中所有的非零元素,按顺序给数组的前段元素位赋值,剩下的全部直接赋值0。我们定义一个nums0…i表示为非0元素的数组,之后在遍历数列的时候不断维护这个定义

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
n = len(nums)
i = -1
j = 0
# nums[0....i]表示非0元素的数列,初始值i=-1
while j <= n-1:
if nums[j] != 0:
i += 1
nums[i] = nums[j]
j += 1
for k in range(i+1, n):
nums[k] = 0

相似问题

leetcode 27. 移除元素

题目描述

给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

1
2
3
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。

解题思路

定义nums[0…i]为非val的数列,遍历整个数列不断的维护这个定义

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
n = len(nums)
i = -1
# 定义nums[0...i]为非val的数列
j = 0
while j <= n-1:
if nums[j] != val:
i += 1
nums[i] = nums[j]
j += 1
return i+1

leetcode 26. 删除排序数组中的重复项

题目描述

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

1
给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。

解题思路

定义nums[0…i]为为非重复数列,遍历整个数列不断的维护这个定义

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0 or n ==1:
return n
# nums[0,i]为非重复数列
i = 0
j = i + 1
while j <= n-1:
if nums[j] != nums[i]:
# 指向同一个元素不需要赋值
if i + 1 != j:
nums[i+1] = nums[j]
i += 1
j += 1
return i + 1

leetcode 80. 删除排序数组中的重复项 II

题目描述

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

1
2
3
4
5
给定 nums = [1,1,1,2,2,3],
函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。
你不需要考虑数组中超出新长度后面的元素。

解题思路

定义nums[0…i]满足每个元素最多出现两次,初始值i=-1,遍历整个数列不断的维护这个定义

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if (n <= 2):
return n
# nums[0...i]是符合要求的,
i = 1
k = i - 1
j = i + 1
while j <= n-1:
if (nums[j] != nums[i]) or (nums[j] == nums[i] and nums[j] != nums[k]):
k = i
nums[i+1] = nums[j]
i += 1
j += 1
return i + 1

基础算法思想在leetcode中的应用

典型的排序算法思想、二分查找思想在解leetcode题目时很有用。

leetcode 75. 分类颜色

题目描述

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:

1
不能使用代码库中的排序函数来解决这道题。

示例:

1
2
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

解题思路

基数排序法

可以采用基数排序法的思想,用一个数组记录下0,1,3的次数,后重排,这个算法对数组进行了两次遍历,其实有一种只进行一次遍历的方法。

三路快速排序方法

设置三个lt, gt, i 定义:nums[0…lt] == 0, nums[lt+1…i-1] = 1, nums[gt…n-1] == 2, 遍历一遍改数列保持这个定义。

paste image

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def sortColors(self, nums):
n = len(nums)
lt = -1
gt = n
i = 0
while i < gt:
if nums[i] == 0:
lt += 1
nums[lt], nums[i] = nums[i], nums[lt]
i += 1
elif nums[i] == 2:
gt -= 1
nums[gt], nums[i] = nums[i], nums[gt]
else:
i += 1

leetcode 215. 数组中的第K个最大元素

题目描述

在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例 1:

1
2
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

解题思路

利用快速排序的思想,从数组 S 中随机找出一个元素 X,把数组分为两部分 Sa 和 Sb。Sa 中的元素大于等于 X,Sb 中元素小于 X。这时有两种情况:

  • Sa 中元素的个数小于 k,则 Sb 中的第 k-|Sa| 个元素即为第k大数;
  • Sa 中元素的个数大于等于 k,则返回 Sa 中的第 k 大数。时间复杂度近似为 O(n)

代码实现

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
class Solution:
# 采用快速排序方法,分成的数列左边大于右边
def findKthLargest(self, nums, k):
n = len(nums)
if (k > n):
return
index = self.quickSort(nums, 0, n-1, k)
return nums[index]
def quickSort(self, nums, l, r, k):
if l >= r:
return l
p = self.partition(nums, l, r)
if p + 1 == k:
return p
if p + 1 > k:
return self.quickSort(nums, l, p -1, k)
else:
return self.quickSort(nums, p + 1, r, k)
def partition(self, nums, l, r):
v = nums[l]
j = l
i = l + 1
while i <= r:
if nums[i] >= v:
nums[j+1],nums[i] = nums[i],nums[j+1]
j += 1
i += 1
nums[l], nums[j] = nums[j], nums[l]
return j

相似题目

leetcode 88. 合并两个有序数组

题目描述

给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

说明:

  • 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
  • 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。

示例:

1
2
3
4
5
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

解题思路

常规解题思路

其实这道题就是归并排序partition的过程(将两个有序的数列合并成一个有序数列), 直观的思路是新建一个新的数列,遍历nums1 和 nums2这两个数列,将新建的数列有序后又赋值给nums1后返回。其实还有一种方法不需要开辟新的空间

尾插法

由于nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素,所以从k=m+n-1开始,分别遍历nums1[m…0]和nums2[n…0]中选取值大的

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def merge(self, nums1, m, nums2, n):
# 尾插入法
if (n < 1):
return
if (m < 1):
nums1[0:n] = nums2[0:n]
return
k = m + n - 1
i = m - 1
j = n - 1
while k >= 0:
if (nums1[i] > nums2[j] and i >= 0) or (j < 0 and i >= 0):
nums1[k] = nums1[i]
k -= 1
i -= 1
if (nums2[j] >= nums1[i] and j >= 0) or (i < 0 and j >=0):
nums1[k] = nums2[j]
k -= 1
j -= 1

双索引技术-对撞指针

有一些leetcode题目,我们可以采用对撞指针进行求解:指针 i 和 j 分别指向数组的第一个元素和最后一个元素,然后指针 i 不断向前, 指针 j 不断递减,知道 i = j (当然具体的逻辑操作根据题目的变化而变化)

leetcode 167. 两数之和 II - 输入有序数组

题目描述

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。

说明:

  • 返回的下标值(index1 和 index2)不是从零开始的。
  • 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

示例:

1
2
3
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

暴力解法

双层遍历,时间复杂度为O(n^2),暴力解法没有充分利用原数组的性质 —— 有序,本文不采用。

当我们看到数列有序的时候,就应该想到可以用二分搜索法

二分搜索法

遍历每个nums[i], 在剩余数组中查找target-nums[i]的值,时间复杂度为O(NlogN)

paste image

有兴趣的读者可以用这种方法尝试一下,应该也是可以AC的, 本文采用对撞指针法。

对撞指针法

们首先判断首尾两项的和是不是target,如果比target小,那么我们左边(i)+1位置的数(比左边位置的数大)再和右相相加,继续判断。如果比target大,那么我们右边(j)-1位置的数(比右边位置的数小)再和左相相加,继续判断。我们通过这样不断放缩的过程,就可以在O(n)的时间复杂度内找到对应的坐标位置。

paste image

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def twoSum(self, numbers, target):
n = len(numbers)
if (n < 2):
return []
i = 0
j = n-1
while i < j:
if numbers[i] + numbers[j] == target:
return [i+1,j+1]
elif numbers[i] + numbers[j] < target:
i += 1
else:
j -= 1
return []

相似题目

leetcode 125. 验证回文串

题目描述

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

说明:

1
本题中,我们将空字符串定义为有效的回文串。

示例 1:

1
2
输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:

1
2
输入: "race a car"
输出: false

解题思路

采用对撞指针

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
n = len(s)
i = 0
j = n-1
while i < j:
if s[i].isalnum() == False:
i += 1
continue
if s[j].isalnum() == False:
j -= 1
continue
if s[i].lower() != s[j].lower():
return False
i += 1
j -= 1
return True

1
isalnum()判断一个字符是否为数字或者字母,lower()字符转小写函数

leetcode 345. 反转字符串中的元音字母

题目描述

编写一个函数,以字符串作为输入,反转该字符串中的元音字母。

示例 1:

1
给定 s = "hello", 返回 "holle".

示例 2:

1
2
给定 s = "leetcode", 返回 "leotcede".
`

注意:

1
元音字母不包括 "y".

解题思路

也是采用对撞指针哦

代码实现

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
#coding=utf-8
'''
@author: wujunqi
@email: jun_qi_wu@163.com
@desc:
'''
class Solution:
def reverseVowels(self, s):
"""
:type s: str
:rtype: str
"""
ss = list(s)
aeiou = ['a', 'e', 'i', 'o', 'u', 'A','E','I','O','U']
n = len(s)
i = 0
j = n-1
while i < j:
if ss[i] not in aeiou:
i += 1
continue
if ss[j] not in aeiou:
j -= 1
continue
if (i < j):
ss[i], ss[j] = ss[j], ss[i]
i += 1
j -= 1
d = ''
return d.join(ss)

leetcode 11. 盛最多水的容器

题目描述

给定 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:

1
你不能倾斜容器,且 n 的值至少为 2。

图示

paste image

解题思路

我们在由线段长度构成的数组中使用两个指针,一个放在开始,一个置于末尾。 此外,我们会使用变量 maxareamaxarea 来持续存储到目前为止所获得的最大面积。 在每一步中,我们会找出指针所指向的两条线段形成的区域,更新 maxareamaxarea,并将指向较短线段的指针向较长线段那端移动一步。

代码实现

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
#coding=utf-8
'''
@author: wujunqi
@email: jun_qi_wu@163.com
@desc:
'''
class Solution:
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
n = len(height)
i = 0
j = n - 1
maxareamaxarea = (j - i) * min(height[i], height[j])
while i < j:
if height[i] < height[j]:
i += 1
else:
j -= 1
maxareamaxarea = max(maxareamaxarea, (j - i) * min(height[i], height[j]))
return maxareamaxarea

双索引技术-滑动窗口

一些题目用滑动窗口方法解题,可以将时间复杂度控制在O(N)级别,最重要的是定义好滑动窗口,明确它要表达的意思,当然边界和初始值非常重要

leetcode 209. 长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。

示例:

1
2
3
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

解题思路

要求是连续子数组,所以我们必须定义i,j两个指针,i向前遍历,j向后遍历,相当与一个滑块,这样所有的子数组都会在[i…j]中出现,如果nums[i..j]的和小于目标值s,那么j向后移一位,再次比较,直到大于目标值s之后,i向前移动一位,缩小数组的长度。遍历到i到数组的最末端,就算结束了,如果不存在符合条件的就返回0.

paste image

代码实现

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
#coding=utf-8
'''
@author: wujunqi
@email: jun_qi_wu@163.com
@desc:
'''
class Solution:
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if (n < 1 or sum(nums) < s):
return 0
# 维护一个滑动窗口nums[i,j], nums[i...j] < s
i = 0
j = -1
total = 0
res = n + 1
while i <= n-1:
if (j + 1 < n) and total < s:
j += 1
total += nums[j]
else:
total -= nums[i]
i += 1
if (total >= s):
res = min(res, j-i+1)
if res == n+1:
return 0
return res

总结

我们知道在准备面试的时候,刷算法题是一种捷径,特别是刷leetcode,但是不能一味的刷题,我们需要总结和思考,对于一些相似的题目我们应该多想想他们的思想,其实很多题的解题思路都是相近的。

-------------本文结束 感谢您的阅读-------------
坚持原创技术分享,您的支持将鼓励我继续创作!