前缀和
LC 303. Range Sum Query - Immutable 区域和检索 - 数组不可变
https://leetcode.com/problems/range-sum-query-immutable/
type NumArray struct {
sums []int
}
func Constructor(nums []int) NumArray {
sums := make([]int, len(nums))
sums[0] = nums[0]
for i := 1; i < len(nums); i++ {
sums[i] = sums[i-1] + nums[i]
}
return NumArray{sums}
}
func (this *NumArray) SumRange(left int, right int) int {
if left == 0 {
return this.sums[right]
}
return this.sums[right] - this.sums[left-1]
}
/**
* Your NumArray object will be instantiated and called as such:
* obj := Constructor(nums);
* param_1 := obj.SumRange(left,right);
*/
LC 304. Range Sum Query 2D - Immutable 二维区域和检索 - 矩阵不可变
https://leetcode.com/problems/range-sum-query-2d-immutable/
type NumMatrix struct {
sums [][]int
}
func Constructor(matrix [][]int) NumMatrix {
sums := make([][]int, len(matrix)+1)
sums[0] = make([]int, len(matrix[0])+1)
for i := range matrix {
sums[i+1] = make([]int, len(matrix[0])+1)
for j := range matrix[i] {
sums[i+1][j+1] = sums[i+1][j] + matrix[i][j]
}
}
// fmt.Println(sums)
for i := range matrix {
for j := range matrix[i] {
sums[i+1][j+1] += sums[i][j+1]
}
}
// for i := range sums {
// for j := range sums[i] {
// fmt.Printf("%2d ", sums[i][j])
// }
// fmt.Println()
// }
return NumMatrix { sums }
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
return this.sums[row2+1][col2+1] - this.sums[row1][col2+1] - this.sums[row2+1][col1] + this.sums[row1][col1]
}
/**
* Your NumMatrix object will be instantiated and called as such:
* obj := Constructor(matrix);
* param_1 := obj.SumRegion(row1,col1,row2,col2);
*/
双指针数组
LC 88. Merge Sorted Array 合并两个有序数组
https://leetcode.com/problems/merge-sorted-array/
func merge(nums1 []int, m int, nums2 []int, n int) {
i, j := m-1, n-1
p := m+n-1
for i >= 0 && j >= 0 {
if nums1[i] >= nums2[j] {
nums1[p] = nums1[i]
p--
i--
} else {
nums1[p] = nums2[j]
p--
j--
}
}
for i >= 0 {
nums1[p] = nums1[i]
p--
i--
}
for j >= 0 {
nums1[p] = nums2[j]
p--
j--
}
}
LC 977. Squares of a Sorted Array 有序数组的平方
https://leetcode.com/problems/squares-of-a-sorted-array/description/
待复习
func sortedSquares(nums []int) []int {
n := len(nums)
i, j := 0, n-1
result := make([]int, n)
p := n-1
for i <= j {
a := nums[i] * nums[i]
b := nums[j] * nums[j]
if a >= b {
result[p] = a
p--
i++
} else {
result[p] = b
p--
j--
}
}
return result
}
LC 360. 有序转化数组 [Premium]
https://leetcode.com/problems/sort-transformed-array/description/
未完成
LC 1329. 将矩阵按对角线排序
https://leetcode.com/problems/sort-the-matrix-diagonally/description/
待复习
func diagonalSort(mat [][]int) [][]int {
m, n := len(mat), len(mat[0])
diagonals := make(map[int][]int, m+n-1)
for i := range mat {
for j, v := range mat[i] {
diagonals[j-i] = append(diagonals[j-i], v)
}
}
for _, v := range diagonals {
sort.Slice(v, func(i, j int) bool {
return v[i] >= v[j]
})
}
for i := range mat {
for j := range mat[i] {
v := diagonals[j-i][len(diagonals[j-i])-1]
diagonals[j-i] = diagonals[j-i][:len(diagonals[j-i])-1]
mat[i][j] = v
}
}
return mat
}
LC 1260. 二维网格迁移
https://leetcode.com/problems/shift-2d-grid/
func shiftGrid(grid [][]int, k int) [][]int {
m, n := len(grid), len(grid[0])
total := m*n
all := make([]int, total)
for i := range grid {
for j, v := range grid[i] {
all[(i*n+j+k) % total] = v
}
}
for i := range grid {
for j := range grid[i] {
grid[i][j] = all[i*n+j]
}
}
return grid
}
不引入额外空间做法
待复习
func shiftGrid(grid [][]int, k int) [][]int {
m, n := len(grid), len(grid[0])
k = k % (m*n)
reverse(grid, 0, m*n-1)
reverse(grid, 0,k-1)
reverse(grid, k, m*n-1)
return grid
}
func reverse(grid [][]int, start, end int) {
i, j := start, end
for i < j {
a := get(grid, i)
b := get(grid, j)
set(grid, j, a)
set(grid, i, b)
i++
j--
}
}
func set(grid [][]int, index int, newValue int) {
n := len(grid[0])
i, j := index / n, index % n
grid[i][j] = newValue
}
func get(grid [][]int, index int) int {
n := len(grid[0])
i, j := index / n, index % n
return grid[i][j]
}