q54 螺旋矩阵
题解
以一层层的方式去遍历每一行和每一列，每一行或者每一列的最后一个元素就是下一列或者下一行的开始。因为题目中的矩阵边长不一定相等，所以最后会多出来一行或者一列，另外处理即可。
func spiralOrder(matrix [][]int) []int {
if len(matrix) == 0 {
return []int{}
}
res := make([]int, 0)
top, bottom, left, right := 0, len(matrix) - 1, 0, len(matrix[0]) - 1
// 以环的方式遍历，每行或者列的最后一个元素就是后一列或者行的开始
for top < bottom && left < right {
for i := left; i < right; i++ {
res = append(res, matrix[top][i])
}
for i := top; i < bottom; i++ {
res = append(res, matrix[i][right])
}
for i := right; i > left; i-- {
res = append(res, matrix[bottom][i])
}
for i := bottom; i > top; i-- {
res = append(res, matrix[i][left])
}
right--
top++
bottom--
left++
}
// 多出一行
if top == bottom {
for i := left; i <= right; i++ {
res = append(res, matrix[top][i])
}
// 多出一列
} else if left == right {
for i := top; i <= bottom; i++ {
res = append(res, matrix[i][left])
}
}
return res
}
q73 矩阵置零
题解
用一个哈希表来标记值为0的坐标，然后遍历哈希表，将同行和同列的元素置为0 。
type Point struct {
x int
y int
}
func setZeroes(matrix [][]int) {
m, n := len(matrix), len(matrix[0])
hashTable := make(map[Point]bool)
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if matrix[i][j] == 0 && hashTable[Point{i, j}] == false {
hashTable[Point{i, j}] = true
}
}
}
for key, _ := range hashTable {
// 同列变为0
for i := 0; i < m; i++ {
matrix[i][key.y] = 0
}
// 同行变为0
for i := 0; i < n; i++ {
matrix[key.x][i] = 0
}
}
}
q78 子集
题解
该题可以使用dfs和bfs两种方法来解决。
dfs:
func subsets(nums []int) [][]int {
res = make([][]int, 0)
dfs(nums, 0, nil)
return res
}
func dfs(nums []int, path int, prefix []int) {
if path >= len(nums) {
dst := make([]int, len(prefix))
copy(dst, prefix)
res = append(res, dst)
return
}
dfs(nums, path + 1, append(prefix, nums[path]))
dfs(nums, path + 1, prefix)
}
bfs:
func subsets1(nums []int) [][]int {
res := make([][]int, 0)
path := make([]int, 0)
var bfs func(int)
bfs = func(start int) {
if start > len(nums) {
return
}
tmp := make([]int, len(path))
copy(tmp, path)
res = append(res, tmp)
for i := start; i < len(nums); i++ {
path = append(path, nums[i])
bfs(i + 1)
path = path[:len(path) - 1]
}
}
bfs(0)
return res
}
q384 打乱数组
题解
这道题最难的部分就是怎么去打乱数组，策略是这样的：循环n次，每次将随机获得的数组元素与数组的最后一个元素交换。
type Solution struct {
nums []int
reNums []int
}
func Constructor(nums []int) Solution {
return Solution{nums: nums, reNums: append([]int{}, nums...)}
}
func (this *Solution) Reset() []int {
return this.reNums
}
func (this *Solution) Shuffle() []int {
for n := len(this.nums); n > 0; n-- {
randIndex := rand2.Intn(n)
this.nums[n - 1], this.nums[randIndex] = this.nums[randIndex], this.nums[n - 1]
}
return this.nums
}
q581 最短连续无序子数组
题解
首先要确定子数组的边界，我们设为begin和end。其实begin的就是比最小值大的最后一个数的下标，而end实际上就是比最大值小的最后一个元素的下标。举个例子就很好理解：{1, 2, 5, 4, 3, 6, 7} , 在这个例子中，比最大值小的最后一个数字其实是3，因为数组遍历到3的时候，此时的最大值是5，所以3是最后一个比最大值小的数，在后面的遍历中，都是更新最大值。那么找左边界也是一样的道理。
func findUnsortedSubarray(nums []int) int {
n := len(nums)
min, max := nums[n - 1], nums[0]
begin, end := -1, -1
for i := 0; i < n; i++ {
if nums[i] >= max {
max = nums[i]
} else {
end = i
}
if nums[n - i - 1] <= min {
min = nums[n - i - 1]
} else {
begin = n - i - 1
}
}
// 特判
if end == -1 {
return 0
}
return end - begin + 1
}
q945 使用数组唯一的最小增量
题解
首先将数组排序，然后遍历数组，如果当前元素小于等于它前一个元素，那么就将它变为前面一个数+1 。
func minIncrementForUnique(nums []int) int {
sort.Ints(nums)
move := 0
for i := 1; i < len(nums); i++ {
if nums[i] <= nums[i - 1] {
prev := nums[i]
nums[i] = nums[i - 1] + 1
move += nums[i] - prev
}
}
return move
}