LeetCode 算法之路
最近，希望做一系列的文章，来记录刷算法的过程。
目前，主要是根据 LeetCode 上 https://leetcode-cn.com/circle/article/48kq9d/ 这一帖子的模块进行刷题。
内容呢，主要是帖子内楼主的总结以及个人的一些体会，和自认为较典型题目的算法思路。
数组篇 - 1
数组的遍历与统计
知识点
遍历一个数组。
遍历数组时记录数组中的最值，最值数量固定时通过相应个数的辅助变量。
题目
T485 最大连续 1 的个数
描述：给定一个二进制数组， 计算其中最大连续1的个数。
解答：
对数组进行一次遍历，记录连续出现 1 的个数，遇上不是 1 的时候同已有最大长度进行比较；
需要注意最后一位的比较不能丢失。
func findMaxConsecutiveOnes(nums []int) int {
ans := 0
nums = append(nums, 0)
idx, sum := 0, 0
for idx < len(nums) {
if nums[idx] == 1 {
sum++
} else {
if ans < sum {
ans = sum
}
sum = 0
}
idx++
}
return ans
}T414 第三大的数
描述：返回非空数组第三大的数，不存在就返回数组中最大的数。
解答：
其实，通过 Partition 可以以 O(n) 的时间复杂度得到无序数组中第 k 大的数。
这里，通过设置三个辅助变量来记录最值，可以多次遍历也可以单次遍历；
就是测试用例里有 -1<<31，需要注意一下，我这里其实偷懒了。
func thirdMax(nums []int) int {
fMax, sMax, tMax := -(2 << 31), -(2 << 31), -(2 << 31)
for _, v := range nums {
if v > fMax {
tMax = sMax
sMax = fMax
fMax = v
}
if v > sMax && v < fMax {
tMax = sMax
sMax = v
}
if v > tMax && v < sMax {
tMax = v
}
}
if tMax != -(2 << 31) {
return tMax
}
return fMax
}统计数组中的元素
知识点
统计元素出现的个数：
- 如果元素的范围较小且非负，用数组来记录更加优雅；
- 否则需要使用 map。
统计数组元素出现的最左和最右位置，使用额外的数组或映射记录，自左向右扫描为最左、自右向左扫描为最右；
如果是单个元素，且数组排序可以使用二分法来迅速定位。
统计元素是否出现、重复出现：
- 直接统计元素个数，需要额外的辅助空间；
- 观察是否给出额外条件且没有使用上，比如元素范围、元素排序等；
- 如果空间复杂度要求较高，需要使用 inplace 的想法，一般考虑 nums[i] == i 的操作。
若排序得到的结果选多余题目需要的，考虑简化时间复杂度，不使用排序。
题目
T645 错误的集合
描述：集合 S 包含了 1 - n 的整数，内有一个元素丢失和一个元素重复，找到他们。
解答：
借助原地的算法可以通过修改原数组的方式，比如将 nums[i] 同 nums[nums[i]] 交换，得到空间复杂度为 O(1) 的解法。
借助位运算，同原始的 1 - n 数进行异或，转换成一个出现三次、一个出现一次、其他出现两次的情况；
同样可以得到空间复杂度为 O(1) 的解法，详情见 LeetCode 136。
这里使用一个 mark 数组来作为 map：
func findErrorNums(nums []int) []int {
mark := make([]int, len(nums)+1)
for _, v := range nums {
mark[v]++
}
var rep, mis int
for i := 1; i < len(mark); i++ {
if mark[i] == 2 {
rep = i
}
if mark[i] == 0 {
mis = i
}
}
return []int{rep, mis}
}T697 数组的度
描述：数组的度是数组任一元素出现频数的最大值，找到度相同的最短连续子数组。
解答：
明显的，度相同的最短连续子数组就是那个元素的最左和最右内的连续子数组，因此我们需要保存下来左右索引；
不过我当时的代码不是特别优美，但大致是这个意思，主要需要能够明确该如何做：
func findShortestSubArray(nums []int) int {
type attr struct {
hPos int
tPos int
times int
}
m := make(map[int]*attr)
for i := 0; i < len(nums); i++ {
if _, ok := m[nums[i]]; !ok {
m[nums[i]] = &attr{-1, -1, 0}
}
if m[nums[i]].hPos == -1 {
m[nums[i]].hPos = i
}
m[nums[i]].times++
}
for i := len(nums)-1; i >= 0; i-- {
if m[nums[i]].tPos == -1 {
m[nums[i]].tPos = i
}
}
tMax := 0
for _, v := range m {
if tMax < v.times {
tMax = v.times
}
}
lMin := len(nums)
for _, v := range m {
if v.times == tMax && lMin > v.tPos-v.hPos+1 {
lMin = v.tPos - v.hPos + 1
}
}
return lMin
}T448 找到所有数组中消失的数字
描述：指定值范围的整型数组，其中某些元素出现两次，某些出现一次，找到没有出现的数。
解法：
典型的以原地改变数组为思路的题目，实现空间复杂度 O(1)，如果有这个要求那一般考虑原地的思路；
具体方法就是令索引 i 存储值为 i 的元素，再看哪些位上存储的不是 i：
func findDisappearedNumbers(nums []int) []int {
for i := 0; i < len(nums); i++ {
for nums[i] != i+1 && nums[i] != nums[nums[i]-1] {
nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
}
}
ans := make([]int, 0)
for i := 0; i < len(nums); i++ {
if nums[i] != i+1 {
ans = append(ans, i+1)
}
}
return ans
}有疑问加站长微信联系（非本文作者）
