leetcode Golang刷题记录 数组篇

题单来源：有没有人一起从零开始刷力扣 – 力扣（LeetCode）

数组的遍历

485

func findMaxConsecutiveOnes(nums []int) int {
	inumber := 0
	max := 0
	for _, v := range nums {
		if v == 1 {
			inumber++
		} else {
			inumber = 0
		}
		if inumber > max {
			max = inumber
		}
	}
	return max
}

495

思路很简单了，计算前后之差，然后如果差大于就+上后面的，小于就累加一下就行了

func findPoisonedDuration(timeSeries []int, duration int) int {
	sumtime := 0
	for i := 0; i < len(timeSeries); i++ {
		if i == len(timeSeries)-1 {
			sumtime += duration
			break
		}
		if timeSeries[i+1]-timeSeries[i] > duration {
			sumtime += duration
		} else {
			sumtime += timeSeries[i+1] - timeSeries[i]
		}

	}
	return sumtime
}

运行时间挑战最慢，笑死饿了

414

思路：列表去重后然后排序，直接返回第三个和第二个就行了

func thirdMax(nums []int) int {
	nums = SliceRemoveDuplicates(nums)
	less := func(i, j int) bool {
		return nums[i] > nums[j]
	}
	sort.Slice(nums, less)
	if len(nums) < 3 {
		return nums[0]
	} else {
		return nums[2]
	}

}

func SliceRemoveDuplicates(slice []int) []int {
	sort.Ints(slice)
	i := 0
	var j int
	for {
		if i >= len(slice)-1 {
			break
		}
		for j = i + 1; j < len(slice) && slice[i] == slice[j]; j++ {
		}
		slice = append(slice[:i+1], slice[j:]...)
		i++
	}
	return slice
}

鉴定为屎山

628

func maximumProduct(nums []int) int {
	sort.Ints(nums)
	return max(nums[0]*nums[1]*nums[len(nums)-1], nums[len(nums)-1]*nums[len(nums)-2]*nums[len(nums)-3])

}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

统计数组中的元素

645

func findErrorNums(nums []int) []int {
	ans := make([]int, 2)
	sort.Ints(nums)
	pre := 0
	for _, v := range nums {
		if v == pre {
			ans[0] = v
		} else if v-pre > 1 {
			ans[1] = pre + 1
		}
		pre = v
	}
	n := len(nums)
	if nums[n-1] != n {
		ans[1] = n
	}
	return ans
}

697

声明 maxLen：记录某个最多出现的数多次；min: 记录某个数maxLen次时，从第1次出到最后一次出现所用的最小距离；numMap：一个Map，key为某个出现过的唯一的数，值为一个Slice，下标为0用于记录当前数出现的次，下标为1用于记录第一次在nums出现的下标，下标为2用于记录最后次在nums出现的下标；
遍历numMap, 如果出现的次数小maxLen则直接跳过；否则用值的下标2对应的值（当前数最后一次出现的次的下标） – 下标1对应的值（当前数第一次出现的次的下标）+1，即两个位置之间的距离，如果该距离小于其它相同次数的距离min=该距离；
最终返回min。

func findShortestSubArray(nums []int) int {
	maxLen, min := 0, 0
	numMap := make(map[int][]int)
	for k, v := range nums {
		if _, ok := numMap[v]; !ok {
			numMap[v] = make([]int, 3)
			numMap[v][1] = k
		}
		numMap[v][0] += 1
		numMap[v][2] = k
		if maxLen < numMap[v][0] {
			maxLen = numMap[v][0]
		}
	}

	for _, v := range numMap {
		if v[0] < maxLen {
			continue
		}

		l := v[2] - v[1] + 1
		if min == 0 || min > l {
			min = l
		}

	}
	return min
}

448

本想着先去重然后再索引，奈何golang没有自带的这些功能，自己写了两个导致直接超时了。。。炒了一个

func findDisappearedNumbers(nums []int) []int {
  var res []int
    length := len(nums)
    for _, num := range nums {
        index := (num-1) % length
        nums[index] += length
    }
    for index, num := range nums {
        if num <= length {
            res = append(res, index+1)
        }
    }
    return res
}

442

直接hash表拿下就行了，一次过

func findDuplicates(nums []int) []int {
	var m = make(map[int]int)
	var res []int
	for _, v := range nums {
		if _, ok := m[v]; ok {
			res = append(res, v)
		} else {
			m[v] = 1
		}
	}
	return res

}

41

假设数组1-n，然后遍历两次寻找位置就行了

func firstMissingPositive(nums []int) int {
	lens := len(nums)
	for i := 0; i < lens; i++ {
		for nums[i]-1 >= 0 && nums[i]-1 < lens && nums[i] != nums[nums[i]-1] {
			temp := nums[nums[i]-1]
			nums[nums[i]-1] = nums[i]
			nums[i] = temp
		}
	}
	for i := 0; i < lens; i++ {
		if nums[i] != i+1 {
			return i + 1
		}
	}
	return lens + 1
}

我是废物

274

这题描述什么jb，反正就是先排序，然后让citations[i]>=h满足就行了

func hIndex(citations []int) int {
	sort.Ints(citations)
	for i := 0; i < len(citations); i++ {
		h := len(citations) - i
		if citations[i] >= h {
			return h
		}
	}
	return 0
}

数组的改变、移动

453

func minMoves(nums []int) int {
	sum := 0
	minnum := min(nums)
	for _, v := range nums {
		sum += v - minnum
	}
	return sum
}

func min(nums []int) int {
	minnum := nums[0]
	for _, v := range nums {
		if v < minnum {
			minnum = v
		}
	}
	return minnum
}

665

管他用不用该数字，直接判断是否是递减数列就完了

func checkPossibility(nums []int) bool {
	count := 0
	for i := 1; i < len(nums); i++ {
		if nums[i] < nums[i-1] {
			count++
			if count > 1 {
				return false
			}
			if i-2 >= 0 && nums[i] < nums[i-2] {
				nums[i] = nums[i-1]
			}
		}
	}
	return true
}

283

简单的排序方法

func moveZeroes(nums []int) []int {
	var i, j int
	for i < len(nums) {
		if nums[i] != 0 {
			nums[i], nums[j] = nums[j], nums[i]
			j++
		}
		i++
	}
	return nums
}

二维数组及滚动数组

118

杨辉三角，梦回高中

func generate(numRows int) [][]int {
	result := make([][]int, numRows)
	for i := 0; i < numRows; i++ {
		result[i] = make([]int, i+1)
		result[i][0] = 1
		result[i][i] = 1
		for j := 1; j < i; j++ {
			result[i][j] = result[i-1][j-1] + result[i-1][j]
		}
	}
	return result

}

119

func getRow(rowIndex int) []int {
	res := make([]int, rowIndex+1)
	res[0] = 1
	for i := 1; i <= rowIndex; i++ {
		for j := i; j >= 1; j-- {
			res[j] += res[j-1]
		}
	}
	return res
}

661

卷积，手撸个getavg就行了

func imageSmoother(img [][]int) [][]int {
	var res [][]int
	for i := 0; i < len(img); i++ {
		var tmp []int
		for j := 0; j < len(img[i]); j++ {
			tmp = append(tmp, getAvg(img, i, j))
		}
		res = append(res, tmp)
	}
	return res
}

func getAvg(img [][]int, i, j int) int {
	var sum, count int
	for m := i - 1; m <= i+1; m++ {
		for n := j - 1; n <= j+1; n++ {
			if m < 0 || m >= len(img) || n < 0 || n >= len(img[i]) {
				continue
			}
			sum += img[m][n]
			count++
		}
	}
	return sum / count
}

598

给定好范围直接乘就完了

func maxCount(m int, n int, ops [][]int) int {
	if len(ops) == 0 {
		return m * n
	}
	minx := ops[0][0]
	miny := ops[0][1]
	for _, v := range ops {
		if v[0] < minx {
			minx = v[0]
		}
		if v[1] < miny {
			miny = v[1]
		}
	}
	return minx * miny

}

419

遍历，判断x，y，然后放置’X’即可

func countBattleships(board [][]byte) int {
	var count int
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[i]); j++ {
			if board[i][j] == 'X' {
				if i > 0 && board[i-1][j] == 'X' {
					continue
				}
				if j > 0 && board[i][j-1] == 'X' {
					continue
				}
				count++
			}
		}
	}
	return count
}

数组的旋转

189

1. 反转整个字符串
2. 反转区间为前k的子串
3. 反转区间为k到末尾的子串

func rotate(nums []int, k int) {
	n := len(nums)
	k %= n
	reverse(nums, 0, n-1)
	reverse(nums, 0, k-1)
	reverse(nums, k, n-1)
}
func reverse(nums []int, start, end int) {
	for start < end {
		nums[start], nums[end] = nums[end], nums[start]
		start++
		end--
	}
}

396

向右旋转一次，就相当于把当前结果加上整个数组的和，再减去数组大小乘以当前最后一位。

func maxRotateFunction(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	sum := 0
	f := 0
	for i := 0; i < n; i++ {
		sum += nums[i]
		f += i * nums[i]
	}
	max := f
	for i := n - 1; i > 0; i-- {
		f = f + sum - n*nums[i]
		if f > max {
			max = f
		}
	}
	return max
}

特定顺序遍历二维数组

54

之前打ctf做过螺旋的题，一样的算法，先定义上下左右，然后走螺旋写入数组就行了

func spiralOrder(matrix [][]int) []int {
	var nums []int
	if len(matrix) == 0 {
		return nums
	}
	left, right, top, bottom := 0, len(matrix[0])-1, 0, len(matrix)-1
	for left <= right && top <= bottom {
		for i := left; i <= right; i++ {
			nums = append(nums, matrix[top][i])
		}
		for i := top + 1; i <= bottom; i++ {
			nums = append(nums, matrix[i][right])
		}
		if left < right && top < bottom {
			for i := right - 1; i > left; i-- {
				nums = append(nums, matrix[bottom][i])
			}
			for i := bottom; i > top; i-- {
				nums = append(nums, matrix[i][left])
			}
		}
		left++
		right--
		top++
		bottom--
	}
	return nums

}

59

螺旋反向，一个思路，先弄个nxn的空数组，然后把数据按照螺旋方式累加进去就行了

func generateMatrix(n int) [][]int {
	var res [][]int
	for i := 0; i < n; i++ {
		res = append(res, make([]int, n))
	}
	var (
		left, right, top, bottom = 0, n - 1, 0, n - 1
		num                      = 1
	)
	for left <= right && top <= bottom {
		for i := left; i <= right; i++ {
			res[top][i] = num
			num++
		}
		for i := top + 1; i <= bottom; i++ {
			res[i][right] = num
			num++
		}
		if left < right && top < bottom {
			for i := right - 1; i > left; i-- {
				res[bottom][i] = num
				num++
			}
			for i := bottom; i > top; i-- {
				res[i][left] = num
				num++
			}
		}
		left++
		right--
		top++
		bottom--
	}
	return res
}

一次双100，乐

498

一共有 m + n - 1m+n−1 条对角线，相邻的对角线的遍历方向不同，当前遍历方向为从左下到右上，则紧挨着的下一条对角线遍历方向为从右上到左下；

设对角线从上到下的编号为 i \in [0, m + n - 2]i∈[0,m+n−2]：

当 ii 为偶数时，则第 ii 条对角线的走向是从下往上遍历；
当 ii 为奇数时，则第 ii 条对角线的走向是从上往下遍历；
当第 ii 条对角线从下往上遍历时，每次行索引减 11，列索引加 11，直到矩阵的边缘为止：

当 i < mi<m 时，则此时对角线遍历的起点位置为 (i,0)(i,0)；
当 i \ge mi≥m 时，则此时对角线遍历的起点位置为 (m - 1, i - m + 1)(m−1,i−m+1)；
当第 ii 条对角线从上往下遍历时，每次行索引加 11，列索引减 11，直到矩阵的边缘为止：

当 i < ni<n 时，则此时对角线遍历的起点位置为 (0, i)(0,i)；
当 i \ge ni≥n 时，则此时对角线遍历的起点位置为 (i - n + 1, n - 1)(i−n+1,n−1)；
根据以上观察得出的结论，我们直接模拟遍历所有的对角线即可。

func findDiagonalOrder(mat [][]int) []int {
	var res []int
	m := len(mat)
	n := len(mat[0])
	for i := 0; i < m+n-1; i++ {
		if i%2 == 0 {
			for j := 0; j <= i; j++ {
				if j < m && i-j < n {
					res = append(res, mat[j][i-j])
				}
			}
		} else {
			for j := i; j >= 0; j-- {
				if j < m && i-j < n {
					res = append(res, mat[j][i-j])
				}
			}
		}
	}
	return res

}

二维数组变换

566

先转成一维数组，然后在给他转成目标数组

func matrixReshape(mat [][]int, r int, c int) [][]int {
	var res [][]int
	var temp []int
	for i := 0; i < len(mat); i++ {
		for j := 0; j < len(mat[i]); j++ {
			temp = append(temp, mat[i][j])
		}
	}
	if len(temp) != r*c {
		return mat
	}
	for i := 0; i < r; i++ {
		res = append(res, temp[i*c:(i+1)*c])
	}
	return res
}

48

matlab两句话的事。。。，思路就是先矩阵转置然后再矩阵镜像就行了

func rotate(matrix [][]int) {
	transpose(matrix)
	n := len(matrix)
	for i := 0; i < n; i++ {
		for j := 0; j < n/2; j++ {
			matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]
		}
	}

}

func transpose(matrix [][]int) [][]int {
	n := len(matrix)
	for i := 0; i < n; i++ {
		for j := i; j < n; j++ {
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
		}
	}
	return matrix
}

73

先找0，然后把其坐标，对应的row和col转为0就行了

func setZeroes(matrix [][]int) {
	var row, col []int
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			if matrix[i][j] == 0 {
				row = append(row, i)
				col = append(col, j)
			}
		}
	}
	for _, v := range row {
		for i := 0; i < len(matrix[v]); i++ {
			matrix[v][i] = 0
		}
	}
	for _, v := range col {
		for i := 0; i < len(matrix); i++ {
			matrix[i][v] = 0
		}
	}
}

289

// 0 -> 1 2    // 1 -> 0 3，然后解码回去，保持这个规则即可

func gameOfLife(board [][]int) {
	// 0 -> 1 2
	// 1 -> 0 3
	m := len(board)
	n := len(board[0])
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			live := 0
			for x := i - 1; x <= i+1; x++ {
				for y := j - 1; y <= j+1; y++ {
					if x >= 0 && x < m && y >= 0 && y < n && (x != i || y != j) {
						if board[x][y] == 1 || board[x][y] == 3 {
							live++
						}
					}
				}
			}
			if board[i][j] == 1 {
				if live < 2 || live > 3 {
					board[i][j] = 3
				}
			} else {
				if live == 3 {
					board[i][j] = 2
				}
			}
		}
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == 2 {
				board[i][j] = 1
			} else if board[i][j] == 3 {
				board[i][j] = 0
			}
		}
	}
}

前缀和数组

303

type NumArray struct {
	sum []int
}

func Constructor(nums []int) NumArray {
	sums := make([]int, len(nums)+1)
	for i := 0; i < len(nums); i++ {
		sums[i+1] = sums[i] + nums[i]
	}
	return NumArray{sums}
}

func (this *NumArray) SumRange(left int, right int) int {
	return this.sum[right+1] - this.sum[left]

}

304

type NumMatrix struct {
	sum [][]int
}

func Constructor(matrix [][]int) NumMatrix {
	sums := make([][]int, len(matrix)+1)
	for i := range sums {
		sums[i] = make([]int, len(matrix[0])+1)
	}
	for i := 1; i <= len(matrix); i++ {
		for j := 1; j <= len(matrix[0]); j++ {
			sums[i][j] = sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] + matrix[i-1][j-1]
		}
	}
	return NumMatrix{sums}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	return this.sum[row2+1][col2+1] - this.sum[row2+1][col1] - this.sum[row1][col2+1] + this.sum[row1][col1]
}

238

左右乘积遍历构造数组

func productExceptSelf(nums []int) []int {
	n := len(nums)
	res := make([]int, n)
	res[0] = 1
	for i := 1; i < n; i++ {
		res[i] = res[i-1] * nums[i-1]
	}
	r := 1
	for i := n - 1; i >= 0; i-- {
		res[i] = res[i] * r
		r *= nums[i]
	}
	return res

}