二维数组
2022-02-04 本文已影响0人
Eden0503
[TOC]
创建m*n的二维数组
func construct_array(rowNum, colNow int) [][]int {
arr := make([][]int, rowNum)
for i := 0; i < len(arr); i++ {
arr[i] = make([]int, colNow)
}
return arr
}
创建 m*n的，数值为-1的二维数组
func construct_array(rowNum, colNow int) [][]int {
arr := make([][]int, rowNum)
for i := 0; i < rowNum; i++ {
arr[i] = make([]int, colNow)
for j := 0; j < colNow; j++ {
arr[i][j] = -1
}
}
return arr
}
删除二维数组中的i+1行
intervals = append(intervals[:i+1], intervals[i+2:]...) // 删除了i+1这一行
74. 搜索二维矩阵（中等/二分查找）
//======= 方法一： 对矩阵的第一列的元素二分查找，找到最后一个不大于目标值的元素，然后在该元素所在行中二分查找目标值是否存在。
func searchMatrix(matrix [][]int, target int) bool {
rows, _ := len(matrix), len(matrix[0])
//最后一个不大于目标值的元素所在的行
tempRows := sort.Search(rows, func(i int) bool {
return matrix[i][0] > target
}) - 1 // 尤其要注意，这里有一个减一操作
if tempRows < 0 {
return false
}
return searchTgt(matrix[tempRows], target)
}
// 二分查找最基础的模板
func searchTgt(array []int, target int) bool {
lenArr := len(array)
left, right := 0, lenArr-1
for left <= right {
middle := (left + right) / 2
if array[middle] == target {
return true
}
if array[middle] > target {
right = middle - 1
} else {
left = middle + 1
}
}
return false
}
// 方法二：若将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，我们可以在该数组上二分找到目标元素。
func searchMatrix(matrix [][]int, target int) bool {
rows, cols := len(matrix), len(matrix[0])
left, right := 0, rows*cols-1
for left <= right {
midd := (left + right) / 2
tempValue := matrix[midd/cols][midd%cols] // 这里很关键的一次转化
if tempValue == target {
return true
}
if tempValue > target {
right = midd - 1
} else {
left = midd + 1
}
}
return false
}
54. 螺旋矩阵（中等）
// 方法一：利用dir是右-》下-》左-》上 来进行旋转
func spiralOrder(matrix [][]int) []int {
rows, cols := len(matrix), len(matrix[0])
visited := make([][]bool, rows)
for i := 0; i < rows; i++ {
visited[i] = make([]bool, cols)
}
total := rows * cols
order := make([]int, total)
dir := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}} // 这里方向修改为右-》下-》左-》上，符合螺旋矩阵的转圈路径
directionIndex := 0
row, col := 0, 0
order[0] = matrix[row][col]
visited[row][col] = true
for i := 1; i < total; i++ {
nextRow, nextColumn := row+dir[directionIndex][0], col+dir[directionIndex][1]
if nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= cols || visited[nextRow][nextColumn] {
directionIndex = (directionIndex + 1) % 4 // 这里是用来转方向的，这种方向转
}
row += dir[directionIndex][0]
col += dir[directionIndex][1]
order[i] = matrix[row][col]
visited[row][col] = true
}
return order
}
// 方法二：按照右-》下-》左-》上的方向进行旋转
func spiralOrder(matrix [][]int) []int {
rows, cols := len(matrix), len(matrix[0])
left, right := 0, cols-1
top, bottom := 0, rows-1
totalElem := rows * cols
res := make([]int, 0)
for totalElem > 0 { // 这里是为了循环再绕着走哦
// 下述操作其实是绕着外层走一圈
for i := left; i <= right && totalElem > 0; i++ { // left to right.
res = append(res, matrix[top][i])
totalElem--
}
top++
for i := top; i <= bottom && totalElem > 0; i++ { // top to bottom.
res = append(res, matrix[i][right])
totalElem--
}
right--
for i := right; i >= left && totalElem > 0; i-- { // right to left.
res = append(res, matrix[bottom][i])
totalElem--
}
bottom--
for i := bottom; i >= top && totalElem > 0; i-- { // bottom to top.
res = append(res, matrix[i][left])
totalElem--
}
left++
}
return res
}
59. 螺旋矩阵 II（中等）
// 方法一：利用dir是右-》下-》左-》上 来进行旋转
func generateMatrix1(n int) [][]int {
totalElem := n * n
// 初始化一个n*n的二维数组
res := make([][]int, n)
for i := 0; i < n; i++ {
res[i] = make([]int, n)
}
dir := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}} // 这里方向修改为右-》下-》左-》上，符合螺旋矩阵的转圈路径
row, col := 0, 0
res[row][col] = 1
directionIndex := 0
for i := 2; i <= totalElem; i++ {
nextRow, nextColumn := row+dir[directionIndex][0], col+dir[directionIndex][1]
if nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= n || res[nextRow][nextColumn] != 0 {
directionIndex = (directionIndex + 1) % 4 // 这里是用来转方向的，这种方向转
}
row += dir[directionIndex][0]
col += dir[directionIndex][1]
res[row][col] = i
}
return res
}
// 方法二：按照右-》下-》左-》上的方向进行旋转
func generateMatrix(n int) [][]int {
totalElem := n * n
left, right := 0, n-1
top, bottom := 0, n-1
// 初始化一个n*n的二维数组
res := make([][]int, n)
for i := 0; i < n; i++ {
res[i] = make([]int, n)
}
num := 1
for num <= totalElem {
for i := left; i <= right; i++ { // left to right.
res[top][i] = num
num++
}
top++
for i := top; i <= bottom; i++ { // top to bottom.
res[i][right] = num
num++
}
right--
for i := right; i >= left; i-- { // right to left.
res[bottom][i] = num
num++
}
bottom--
for i := bottom; i >= top; i-- { // bottom to top.
res[i][left] = num
num++
}
left++
}
return res
}
