理论基础
数组是非常基础的数据结构，在面试中，考察数组的题目一般在思维上都不难，主要是考察对代码的掌控能力。也就是说，想法很简单，但实现起来可能就不是那么回事了
首先要知道数组在内存中的存储方式，这样才能真正理解数组相关的面试题，数组是存放在连续内存空间上的相同类型数据的集合
数组可以方便的通过下标索引的方式获取到下标所对应的数据，需要两点注意的是
- 数组下标都是从0开始的。
- 数组内存空间的地址是连续的
正是因为数组的在内存空间的地址是连续的，所以在删除或者增添元素的时候，就难免要移动其他元素的地址
二分查找
704. 二分查找 - 力扣（LeetCode）
给定一个升序的整数数组和一个目标值，返回数组中目标值的下标，若没有返回-1
思路一：遍历数组
1
2
3
4
5
6
7
8
|
func search(nums []int, target int) int {
for i, v := range nums {
if v == target {
return i
}
}
return -1
}
|
思路二：二分查找，定义初始区间索引为给定数组索引；比较区间的中间值和目标值的大小，若区间中间值小于目标值，说明目标值在区间中间值右半部分，调整区间左索引为中间索引+1；若区间中间值大于目标值，说明目标值在区间中间值左半部分，调整区间右索引为中间索引-1；若区间中间值等于目标值，返回中间值索引
注意：
- 调整区间索引时要设为中间索引的前一个或后一个
- 使用二分查找的数组要是有序的
- 求中间索引时为了防止求和后整数溢出，可以用left+(right-left)/2，即先求出区间元素个数的一半，再从左边界前进该个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
func search(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right { // 当left = right时[left, right]依然有效
mid := left + (right - left) / 2 // 获得区间中间索引
if nums[midIdx] == target {
return midIdx // 找到目标值
} else if nums[midIdx] < target {
left = midIdx + 1 // 目标值在右区间
} else { // nums[midIdx] > target
right = midIdx - 1 // 目标值在左区间
}
}
return -1
}
|
搜索插入位置
35. 搜索插入位置 - 力扣（LeetCode）
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引，如果目标值不存在于数组中，返回它将会被按顺序插入的位置，必须使用时间复杂度为 O(log n) 的算法
只要看到面试题里给出的数组是有序数组，都可以想一想是否可以使用二分法，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的
二分查找若直到左区间大于右区间仍未找到目标值，则看最后左区间等于右区间时的元素值，若最后的中间值大于目标值，则返回该中间值下标，否则返回该中间值下一元素下标
简化：若二分查找结束没找到目标值，直接返回区间右边界加一；因为若最后的中间值小于目标值，说明目标值在右半区间，目标值要插入到最后中间值的后面一个，而此时只调整了左边界，右边界没动，还指向最后的中间值；若最后的中间值大于目标值，说明目标值在左半区间，目标值要插入到最后的中间值位置，此时右边界被移到最后中间值的前一个元素，右边界再加一刚好是最后的中间值位置；若最后的中间值等于目标值，则插入到最后的中间值位置或后面一个都可以
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
func searchInsert(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right - left) / 2
if nums[mid] == target {
return mid
} else if nums[mid] < target {
left = mid + 1 // 目标值在右半区间
} else {
right = mid - 1 // 目标值在左半区间
}
}
return right + 1 // 返回插入位置
}
|
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
给定一个递增数组和目标值 ，找出给定目标值在数组中的开始位置和结束位置，如果数组中不存在目标值，返回 [-1, -1]，必须设计并实现时间复杂度为 O(log 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
24
25
26
27
|
func searchRange(nums []int, target int) []int {
left, right := 0, len(nums)-1
resLeft, resRight := 0, 0
for left <= right {
mid := left + (right - left) / 2
if nums[mid] == target {
for i := mid; i < len(nums); i++ { // 从目标值向右遍历
if nums[i] != target {
break
}
resRight = i // 更新右边界
}
for i := mid; i >= 0; i-- { // 从目标值向左遍历
if nums[i] != target {
break
}
resLeft = i // 更新左边界
}
return []int{resLeft, resRight}
} else if nums[mid] > target {
right = mid - 1 // 目标值在左区间
} else {
left = mid + 1 // 目标值在右区间
}
}
return []int{-1, -1}
}
|
思路二：分别用两个二分查找左右边界；在找左边界的二分查找中找到目标值后需要判断目标值的上一个元素是否与目标值不同，若不同或已经是数组的第一个元素则说明此中间值是左边界，否则继续更新右边界向左半区间查找；同理，在找右边界的二分查找中找到目标值后需要判断目标值的下一个元素是否与目标值不同，若不同或已经是数组最后一个元素则说明此中间值是右边界，否则继续更新左边界向右半区间查找
注意：在遇到目标值但判断后不是边界后需要更新边界
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
|
func searchRange(nums []int, target int) []int {
left := searchLeft(nums, target)
right := searchRight(nums, target)
return []int{left, right}
}
func searchLeft(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target { // 找到目标值
if mid == 0 || nums[mid-1] != target {
return mid
} else { // 不是第一个目标值
right = mid - 1 // 向左搜索更新右边界
}
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1 // 没找到左边界
}
func searchRight(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target { // 找到目标值
if mid == len(nums)-1 || nums[mid+1] != target {
return mid
} else { // 不是最后一个目标值
left = mid + 1 // 向右搜索更新左边界
}
} else if nums[mid] > target {
right = mid - 1
} else {
left = mid + 1
}
}
return -1 // 没找到右边界
}
|
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
x 的平方根
69. x 的平方根 - 力扣（LeetCode）
给你一个非负整数 ，返回算术平方根，结果只保留整数部分，舍去小数部分
一个数x的算术平方根一定在0~x/2，升序数组，考虑使用二分查找法找到目标元素
在二分查找过程中有三种情况
- 如果这个整数的平方等于输入整数，那么我们就找到了这个整数；
- 如果这个整数的平方大于输入整数，那么这个整数肯定不是我们要找的那个数；
- 如果这个整数的平方小于输入整数，那么这个整数可能是我们要找的那个数 (算术平方根为小数时只保留整数)。
若算术平方根是小数，则最后一轮循环中，mid是第一个大于x/mid的值，所以在左区间寻找，执行right = mid -1 ，此时right < left，结束循环，right就是只保留整数的算术平方根
注意：
- 若使用
mid == x/mid判断，则2/0会报错，进入循环前判断是否给定整数为0和1，此外，左边界应初始化为0，不能初始化为0；若左区间初始化为0，给定整数为2，由于右边界初始化为x/2，mid会算出0，x/0报错；左右边界可初始化为[0,x]或[1,x/2]，[0,x]相比[1,x/2]刚开始会多判断一次
- 若直接使用
mid*mid == x判断，乘数可能会发生整数溢出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
func mySqrt(x int) int {
left, right := 0, x
if x <= 1 {
return x
}
for left <= right {
mid := left + (right-left)/2
if mid == x/mid {
return mid
} else if mid < x/mid {
left = mid + 1
} else {
right = mid - 1
}
}
return right
}
|
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
有效的完全平方数
367. 有效的完全平方数 - 力扣（LeetCode）
给给定一个正整数 。若是一个完全平方数，则返回 true ，否则返回 false ，例如16是完全平方数，因为4*4=16，14不是完全平方数，因为3.742 * 3.742 = 14，但 3.742 不是一个整数
用二分法查找给定整数的平方根，若能找到返回true，否则返回false
注意：
-
判断条件不能写mid == num/mid，只能写mid * mid == num，因为num/mid为int类型，会导致结果错误
例如：当num=5, mid=2时，mid == num/mid为true，而num并不是完全平方数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
func isPerfectSquare(num int) bool {
left, right := 1, num/2
if num <= 1 {
return true
}
for left <= right {
mid := left + (right-left)/2
if mid*mid == num {
return true
} else if mid*mid < num {
left = mid + 1
} else {
right = mid - 1
}
}
return false
}
|
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
移除元素
27. 移除元素 - 力扣（LeetCode）
给定一个数组和目标值，原地移除数组中等于目标值的元素，返回移除后数组的长度，要求不能使用额外的数组空间
思路一：暴力，外层循环遍历数组，每遇到一个目标值就在内层循环中将后面的所有元素前移一个单位；前移结束后设置下一次遍历位置为仍为当前下标，数组长度减一；若当前元素不是目标值，则下一次遍历位置为下一元素
注意：遍历结束的标志是移除后数组的长度
1
2
3
4
5
6
7
8
9
10
11
12
13
|
func removeElement(nums []int, val int) int {
size := len(nums)
for i := 0; i < size; i++ {
if nums[i] == val {
for j := i; j < len(nums)-1; j++ {
nums[j] = nums[j+1] // 元素前移一个单位
}
i-- // 下次循环仍从当前元素位置开始
size-- // 数组长度减一
}
}
return size
}
|
思路二：双指针（快慢指针），在一个循环中完成两个循环的工作；快指针寻找与目标值不同的新元素，慢指针指向要更新的下标；将快指针指向的新元素更新到前面慢指针指向的元素；当快指针遍历结束后，返回最后慢指针指向的下标即可
快慢指针都从头出发；快指针遍历数组，当快指针指向的元素与目标值不同时，将快指针指向的元素值赋给慢指针指向的元素，然后慢指针前进一步（快指针遇到与目标值不同的元素时，快慢指针同步前进）；当快指针指向的元素与目标值相同时，慢指针不动此时指向要更新的元素，快指针继续前进，快指针遇到的元素若仍与目标值相同，慢指针仍不动，快指针继续前进，直到快指针遇到与目标值不同的元素，此时快指针的指向的元素会赋给此时慢指针指向的要更新的元素，更新后慢指针前进一个单位指向下一个要更新元素
1
2
3
4
5
6
7
8
9
10
|
func removeElement(nums []int, val int) int {
slowIdx := 0
for fastIdx := 0; fastIdx < len(nums); fastIdx++ {
if nums[fastIdx] != val {
nums[slowIdx] = nums[fastIdx] // 更新元素
slowIdx++ // 慢指针前进一步
}
}
return slowIdx
}
|
删除有序数组中的重复项
26. 删除有序数组中的重复项 - 力扣（LeetCode）
给定一个递增数组，原地移除数组中重复的元素，使每个元素只出现一次，返回移除后数组的长度，要求不能使用额外的数组空间
双指针法：快指针遍历数组寻找新元素，慢指针指向要更新的元素下标，将快指针指向的元素更新到慢指针指向的元素，快指针遍历结束后，返回慢指针指向的下标
初始时将第一个元素置为目标值，快慢指针遍历从第二个元素开始，当快指针遇到新元素，更新目标值为新元素，更新慢指针指向元素的值，慢指针前进
简化：省去目标值变量，判断快指针是否遇到新元素，直接与快指针指向的前一个元素比较
1
2
3
4
5
6
7
8
9
10
|
func removeDuplicates(nums []int) int {
slowIdx := 1
for fastIdx := 1; fastIdx < len(nums); fastIdx++ {
if nums[fastIdx] != nums[fastIdx-1] { // 找到新元素
nums[slowIdx] = nums[fastIdx] // 更新慢指针指向元素
slowIdx++ // 慢指针前进
}
}
return slowIdx
}
|
移动零
283. 移动零 - 力扣（LeetCode）
给定一个数组，将数组中所有的0都移到末尾，要求其余元素顺序不变，必须在不复制数组的情况下原地对数组进行操作
暴力：遍历数组，每遇到一个0就将所有元素前移一个，同时将末尾元素置为0，时间复杂度O(n2)
双指针法：类似用快慢指针移除元素的操作，目标值为0，快指针遍历数组，慢指针标记要更新的元素，当快指针遇到非目标值说明要更新慢指针指向的目标值
由于是将0移到数组末尾，并非是完全移除，所有当快指针找到不为0的数时，将慢指针和快指针的值交换即可，这样会将非0值逐个换到前面的0所在位置
1
2
3
4
5
6
7
8
9
|
func moveZeroes(nums []int) {
slowIndex := 0
for fastIndex := 0; fastIndex < len(nums); fastIndex++ {
if nums[fastIndex] != 0 {
nums[slowIndex], nums[fastIndex] = nums[fastIndex], nums[slowIndex] // 更新慢指针指向元素
slowIndex++ // 慢指针前进
}
}
}
|
比较含退格的字符串
844. 比较含退格的字符串 - 力扣（LeetCode）
给定两个字符串，# 代表退格字符，若两者相等返回 true ，否则返回false，如果对空文本输入退格字符，文本仍为空
双指针分开版
对两个字符串分别使用双指针，得到退格后的字符串，最后直接使用==判断
注意：
- 退格就是移除前面的一个字符，当快指针发现
#且慢指针不是第一个元素，则慢指针后退一个，且统计有效元素数减二，当快指针发现#但慢指针是第一个元素，则慢指针不动，统计有效元素数减一（仅移除该退格符）
- 简化：不用专门的变量去统计有效数组长度，直接使用最后慢指针指向的下标作为数组长度，同时，由于最后返回的是左闭右开数组转换的字符串，所以在快指针遇到退格符且慢指针不在首时，慢指针退后一个，表示有效数组长度即可，若快指针遇到退格符且慢指针在首，则不对慢指针做任何操作，因为此时慢指针指向下标为0，已经表示了有效数组长度为0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
func backspaceCompare(s string, t string) bool {
if getString(s) == getString(t) {
return true
}
return false
}
func getString(s string) string {
slowIdx := 0
runeS := []rune(s)
for fasrIdx := range runeS {
if runeS[fasrIdx] != '#' {
runeS[slowIdx] = runeS[fasrIdx] // 更新慢指针指向值
slowIdx++ // 慢指针前进
} else if slowIdx != 0 {
slowIdx--
}
}
return string(runeS[:slowIdx]) // 返回更新后的数组
}
|
- 时间复杂度：O(n+m)
- 空间复杂度：O(n+m)
双指针合并版
一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。
具体地，我们定义 skip 表示当前待删除的字符的数量。每次我们遍历到一个字符：
这样，我们定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完字符串为止
注意：
具体代码可以去看力扣官方题解
有序数组的平方
977. 有序数组的平方 - 力扣（LeetCode）
给定一个非递减的整数数组，要求返回每个数字的平方组成的新数组，新数组也要非递减
考虑到原数组中有负数，原数组元素逐个直接平方后可能会出现递减数组
思路一：暴力，逐个元素平方，然后对元素排序
1
2
3
4
5
6
7
|
func sortedSquares(nums []int) []int {
for i := range nums {
nums[i] = nums[i] * nums[i]
}
sort.Ints(nums)
return nums
}
|
- 时间复杂度：O(n + nlogn) = O(nlogn)；但为了和下面双指针法算法时间复杂度有鲜明对比，记为 O(n + nlogn)
思路二：双指针，省去排序操作；两个指针分别指向给定数组的首尾，由于给定数组是递增的，所以平方后的大值一定在两端；开辟一个结果数组，每次比较首尾两个指针指向元素平方后的值，大值存入结果数组的末尾，大值指针移动，小值指针不变等待下次比较，重复上述步骤直到俩指针错位，返回结果数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
func sortedSquares(nums []int) []int {
leftIdx, rightIdx := 0, len(nums)-1
res := make([]int, len(nums))
resIdx := len(res) - 1
for leftIdx <= rightIdx {
if nums[leftIdx]*nums[leftIdx] > nums[rightIdx]*nums[rightIdx] {
res[resIdx] = nums[leftIdx] * nums[leftIdx]
leftIdx++ // 左指针移动一个单位
} else {
res[resIdx] = nums[rightIdx] * nums[rightIdx]
rightIdx-- // 右指针移动一个单位
}
resIdx-- // 结果集指针移动一个单位
}
return res
}
|
长度最小的子数组
209. 长度最小的子数组 - 力扣（LeetCode）
给定一个整数数组和一个目标值 ，找出数组中一个连续子数组，要求其总和要大于等于目标值，且长度要最小，若能找到则返回长度，若找不到返回0
暴力：一个for循环定滑动窗口的起始位置，一个for循环定滑动窗口的终止位置，用两个for循环完成一个不断搜索区间的过程，会超时
双指针（滑动窗口）：用一个for循环和一个内层while循环来不断调节子数组的起始位置和终止位置，从而得出结果；for循环控制子数组终止位置；while循环控制起始位置；若当前窗口值大于等于目标值，则统计长度，起始位置后移一个单位，直到当前窗口值小于目标值退出while循环，进入下一次for循环，终止位置更新，重复上述步骤，直至终止位置到给定数组末尾
注意：结果初始化为给定数组长度加一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
func minSubArrayLen(target int, nums []int) int {
left := 0
sum := 0
res := len(nums) + 1
for right := range nums {
sum += nums[right]
for sum >= target {
length := right - left + 1 // 子数组长度
if length < res {
res = length
}
sum -= nums[left] // 更新子数组和
left++ // 更新起始位置
}
}
if res == len(nums)+1 {
return 0 // 没有符合条件的子数组
}
return res
}
|
不要以为for里放一个while就以为是O(n2)，时间复杂度主要是看每一个元素被操作的次数，每个元素在滑动窗口进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)
水果成篮
904. 水果成篮 - 力扣（LeetCode）
给定一个数组，找至多包含两种元素的最长子串，返回其长度
最小滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最小长度。
1
2
3
4
5
6
|
while j < len(nums):
判断[i, j]是否满足条件
while 满足条件：
不断更新结果(注意在while内更新！)
i += 1 （最大程度的压缩左边界，使得滑窗尽可能的小）
j += 1
|
最大滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最大长度。
1
2
3
4
5
6
|
while j < len(nums):
判断[i, j]是否满足条件
while 不满足条件：
i += 1 （最保守的压缩左边界，一旦满足条件了就退出压缩左边界的过程，使得滑窗尽可能的大）
不断更新结果（注意在while外更新！）
j += 1
|
最小滑窗是在迭代右移左边界的过程中更新结果，而最大滑窗是在迭代右移右边界的过程中更新结果。
判断滑动窗口内是否满足题设条件有两种选择：
- 遍历这个滑窗来判断是否满足需要，总时间会退化为O(N2)
- 选择字典，用空间换时间，总时间为O(N).
用哈希表存储窗口内的数以及出现的次数，若出现的数多于两个，则说明不满足条件；每次将 right 移动一个位置，并将 fruits[right] 加入哈希表。如果此时哈希表不满足要求（即哈希表中出现超过两个键值对），那么需要不断移动 left，并将 fruits[left] 在哈希表中的值减一，当值减少到 0 时，需要将对应的键值对从哈希表中移除，直到哈希表满足要求为止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
func totalFruit(fruits []int) int {
left := 0
res := 0
countMap := make(map[int]int)
for right := range fruits {
countMap[fruits[right]]++
for len(countMap) > 2 { // 不满足条件
countMap[fruits[left]]-- // 更新哈希表
if countMap[fruits[left]] == 0 {
delete(countMap, fruits[left]) // 删除出现次数为0的元素
}
left++ // 左边界后移
}
res = max(res, right-left+1) // 更新窗口最大长度
}
return res
}
|
最小覆盖子串
76. 最小覆盖子串 - 力扣（LeetCode）
给定两个字符串，返回第一个字符串中涵盖第二个字符串中所有字符的最小子串，重复字符也必须在子串中出现至少同样次数，如果不存在则返回空字符串
用哈希表存储第二个字符串的字符以及出现的次数，其值也表示字符串t中对应字符未出现在子串中的次数；用一个变量统计子串中应出现的字符个数；若查询哈希表得知对应字符出现在哈希表，则在更新哈希表之前检查哈希值是否大于0，若大于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
|
func minWindow(s string, t string) string {
left := 0
res := ""
count := len(t)
countMap := make(map[byte]int)
for i := 0; i < len(t); i++ {
countMap[t[i]]++ // 哈希存储t
}
for right := 0; right < len(s); right++ {
if _, ok := countMap[s[right]]; ok { // 右边界字符出现在哈希表中
if countMap[s[right]] > 0 { // 右边界字符在子串中出现次数不够
count-- // 更新子串中应出现的字符个数
}
countMap[s[right]] -= 1 // 更新哈希表
}
for count == 0 { // 满足条件
if len(res) == 0 || right-left+1 < len(res) {
res = s[left : right+1] // 更新结果
}
if _, ok := countMap[s[left]]; ok { // 左边界字符出现在哈希表中
if countMap[s[left]] == 0 {
count++ // 更新子串中应出现的字符个数
}
countMap[s[left]] += 1 // 更新哈希表
}
left++ // 左边界移动
}
}
return res
}
|
- 时间复杂度：O(n)，其中 n 是字符串 s 的长度
- 空间复杂度：O(m)，其中 m 是字符串 t 的长度
螺旋矩阵 II
59. 螺旋矩阵 II - 力扣（LeetCode）
给定一个正整数 n ，生成一个正方形矩阵，顺时针螺旋排列包含 1 到 n^2 所有元素
本题不涉及具体的算法，就是模拟过程，但却十分考察对代码的掌控能力
注意：
- 先用给定n除以2求出循环次数，也就是需要转几圈，若给定n为奇数，最后中间会剩一个元素，若给定n为偶数，中间不会剩元素
- 不断循环直至循环次数为0，每次循环就是一圈，完成四个边的填充，填充时遵循左闭右开的规则，每次转完一圈要更新每个边要填充的元素个数、每圈起始的横纵坐标和本圈目前填充到的横纵坐标
- 每填充一个元素，元素值就加一
- 由于循环中会递减n和循环次数，所以最后判断奇偶可以用元素值（循环结束后是n2）
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
|
func generateMatrix(n int) [][]int {
matrix := make([][]int, n)
for i := range matrix {
matrix[i] = make([]int, n)
}
count := 1 // 元素值
loop := n / 2 // 循环次数
startRow, startCol := 0, 0 // 控制起始位置
eleCount := n // 标记每圈每个边要填充的元素个数
for ; loop > 0; loop-- {
curRow, curCol := startRow, startCol
eleCount--
for ; curCol < eleCount; curCol++ {
matrix[curRow][curCol] = count // 从左到右填充排
count++
}
for ; curRow < eleCount; curRow++ {
matrix[curRow][curCol] = count // 从上到下填充列
count++
}
for ; curCol > startCol; curCol-- {
matrix[curRow][curCol] = count // 从右到左填充排
count++
}
for ; curRow > startRow; curRow-- {
matrix[curRow][curCol] = count // 从下到上填充列
count++
}
startRow++ // 更新每圈起始位置的排数
startCol++ // 更新每圈起始位置的列数
}
if n%2 == 1 {
matrix[startRow][startCol] = count
}
return matrix
}
|
螺旋矩阵
54. 螺旋矩阵 - 力扣（LeetCode）
给定一个 m 行 n 列的矩阵 matrix ，按照顺时针螺旋顺序返回矩阵中的所有元素
注意：
- 矩阵中元素不一定是从1开始的，不能用最大元素来计算循环次数，要用元素数来计算循环次数
- 每遍历完一圈查看一次结果集是否满足条件，若满足直接返回，因为是长方形时，有可能结果集已满足但循环次数还有
- 从右往左和从左往右遍历时要用偏移量控制
- 若矩阵只有一列，则直接从上往下遍历后返回，因为不构成一圈，也不能通过最后的中间遍历
- 若矩阵只有一排，则直接从左往右遍历后返回，因为最后一个元素作为四个边的哪个都不会被遍历，也会导致最后的中间遍历索引越界
- 最后剩下的中间元素，可以是一排也可能是一列，可以用总排/列数减去已遍历的排/列数来判断
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
46
47
48
49
50
51
52
|
func spiralOrder(matrix [][]int) []int {
row, col := len(matrix), len(matrix[0]) // 矩阵的最大行数和列数
res := make([]int, 0)
if col == 1 { // 只有一列
for i := range matrix {
res = append(res, matrix[i][0])
}
return res
}
if row == 1 { // 只有一列
for i := range matrix[0] {
res = append(res, matrix[0][i])
}
return res
}
count := row * col // 矩阵中元素个数
n := math.Sqrt(float64(count)) // 求元素个数的平方根
loop := int(n / 2) // 圈数（取整）
curX, curY := 0, 0 // 当前遍历到的位置
offset := 1 // 偏移量（前闭后开）
for loop > 0 { // 按圈遍历
for ; curY < col-offset; curY++ { // 从左到右遍历（该行最后一个不遍历）
res = append(res, matrix[curX][curY])
}
for ; curX < row-offset; curX++ { // 从上到下（最后一个不遍历）
res = append(res, matrix[curX][curY])
}
for ; curY >= offset; curY-- { // 从右到左（最后一个不遍历）
res = append(res, matrix[curX][curY])
}
for ; curX >= offset; curX-- { // 从下到上（最后一个不遍历）
res = append(res, matrix[curX][curY])
}
loop-- // 更新圈数
offset++ // 更新偏移量
curX++ // 更新下一次起始排数
curY++ // 更新下一次起始列数
if len(res) == count {
return res
}
}
if row-2*(offset-1) == 1 {
for ; len(res) != count; curY++ {
res = append(res, matrix[curX][curY]) // 遍历中间一排
}
} else if col-2*(offset-1) == 1 {
for ; len(res) != count; curX++ {
res = append(res, matrix[curX][curY]) // 遍历中间一列
}
}
return res
}
|
简化：loop的计算和中间值的判断
本题的loop计算与59.螺旋矩阵II算法略微差异，因为存在rows和columns两个维度，loop取min(rows, columns) / 2
中间值的判断：若min(rows, columns)为偶数，则矩阵中间不会剩下值；若min(rows, columns)为奇数，则矩阵中间会剩下一个行或列；判断是行还是列，要看矩阵行数和列数的大小，如果行数大于列数，则中间剩下列，反之中间剩下行
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
|
func spiralOrder(matrix [][]int) []int {
row, col := len(matrix), len(matrix[0]) // 矩阵的最大行数和列数
res := make([]int, 0)
loop := min(row, col) / 2 // 圈数（取整）
curX, curY := 0, 0 // 当前遍历到的位置
offset := 1 // 偏移量（前闭后开）
for loop > 0 { // 按圈遍历
for ; curY < col-offset; curY++ { // 从左到右遍历（该行最后一个不遍历）
res = append(res, matrix[curX][curY])
}
for ; curX < row-offset; curX++ { // 从上到下（最后一个不遍历）
res = append(res, matrix[curX][curY])
}
for ; curY >= offset; curY-- { // 从右到左（最后一个不遍历）
res = append(res, matrix[curX][curY])
}
for ; curX >= offset; curX-- { // 从下到上（最后一个不遍历）
res = append(res, matrix[curX][curY])
}
loop-- // 更新圈数
offset++ // 更新偏移量
curX++ // 更新下一次起始排数
curY++ // 更新下一次起始列数
}
if min(row, col)%2 == 1 { // 奇数=>中间有剩余
if row > col { // 排数>列数=>剩余一列
for ; curX <= row-offset; curX++ { // 遍历中间一列(包括最后一个未被遍历的元素)
res = append(res, matrix[curX][curY])
}
} else { // 剩余一排
for ; curY <= col-offset; curY++ { // 遍历中间一排(包括最后一个未被遍历的元素)
res = append(res, matrix[curX][curY])
}
}
}
return res
}
|
螺旋遍历二维数组
LCR 146. 螺旋遍历二维数组 - 力扣（LeetCode）
本题与上一题基本相同，唯一区别是本题数组可能为空
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
|
func spiralArray(array [][]int) []int {
if len(array) == 0 {
return []int{}
}
row, col := len(array), len(array[0])
res := make([]int, 0)
loop := min(row, col) / 2
curX, curY := 0, 0
offset := 1
for loop > 0 {
for ; curY < col-offset; curY++ {
res = append(res, array[curX][curY])
}
for ; curX < row-offset; curX++ {
res = append(res, array[curX][curY])
}
for ; curY >= offset; curY-- {
res = append(res, array[curX][curY])
}
for ; curX >= offset; curX-- {
res = append(res, array[curX][curY])
}
curX++
curY++
offset++
loop--
}
if min(row, col)%2 == 1 {
if row > col {
for ; curX <= row-offset; curX++ {
res = append(res, array[curX][curY])
}
} else {
for ; curY <= col-offset; curY++ {
res = append(res, array[curX][curY])
}
}
}
return res
}
|