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
}