首页 > 编程语言 > 详细

LeetCode 系列-数组与矩阵

时间:2021-01-25 16:14:53      阅读:15      评论:0      收藏:0      [点我收藏+]

解题要点

此类型的题目,没有固定的模式,只能看自己的经验

其中每道题都存在一种暴力解法,如果实在没有更好的解法,可以尝试暴力解法。面试中如果暂时想不出题解,一定要尝试使用暴力解法得到答案

题目摘要

41 First Missing Positive

LeetCode/力扣

给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。

输入:nums = [1,2,0]
输出:3

输入:nums = [3,4,-1,1]
输出:2

题解

func firstMissingPositive(nums []int) int {
    helper := make([]int, len(nums)+1)
    for _, h := range helper {
        h = 1
    }
    for _, num := range nums {
        if num > len(nums) || num <= 0 {
            continue
        }
        helper[num] = 0
    }
    for i := range helper {
        if helper[i] == 1 {
            return i
        }
    }
    return len(nums) + 1
}

48 Rotate Image

LeetCode/力扣

给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度

给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵,使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

题解 分层旋转,每次旋转交换4个数,用一个中间变量保存其中一个数就可以,一层旋转完了再往里层循环,直到层数大于n/2,需要注意判断特殊情况

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

54 Spiral Matrix

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

题解 可以按层来输出,每一层输出上,右,下,左四个方向,输出完之后,上,左加一,右,下减一,如此循环直到上大于下或左大于右

技术分享图片

func spiralOrder(matrix [][]int) []int {
    m := len(matrix)
    if m <= 0 {
        return []int{}
    }
    n := len(matrix[0])
    res := make([]int,0)
    u,d,l,r := 0,m-1,0,n-1
    for u <= d && l <= r {
        for i := l; i <= r; i++ {
            res = append(res, matrix[u][i])
        }
        for i := u+1;i<=d;i++ {
            res = append(res, matrix[i][r])
        }
        if u < d && l < r {
            for i := r - 1; i > l; i--{
                res = append(res, matrix[d][i])
            }
            for i := d; i > u; i-- {
                res = append(res, matrix[i][l])
            }
        }
        u++
        l++
        d--
        r--
    }
    return res
}

73 Set Matrix Zeroes

LeetCode/力扣

给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。

输入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

题解 用map保存需要变换的行或列,如果行或列不为0,将map设为0就可以了,但是这样空间复杂度为O(m+n),最优解法的空间复杂度为O(1),时间复杂度为O(mxn)。其实类似于54题,在数组内保存需要的结果就可以了

func setZeroes(matrix [][]int)  {
    isCol := false
    r := len(matrix)
    c := len(matrix[0])
    
    for i := 0; i < r; i++ {
        if matrix[i][0] == 0 {
            isCol = true
        }
        for j := 1; j < c; j++ {
            if matrix[i][j] == 0 {
                matrix[0][j] = 0
                matrix[i][0] = 0
            }
        }
    }
    
    for i := 1; i < r; i++ {
        for j := 1; j < c; j++ {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
    }
    
    if matrix[0][0] == 0 {
        for j := 0; j < c; j++ {
            matrix[0][j] = 0
        }
    }
    
    if isCol {
        for i := 0; i < r; i++ {
            matrix[i][0] = 0
        }
    }
    
}

LeetCode/力扣

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

board =
[
  [‘A‘,‘B‘,‘C‘,‘E‘],
  [‘S‘,‘F‘,‘C‘,‘S‘],
  [‘A‘,‘D‘,‘E‘,‘E‘]
]

给定 word = "ABCCED", 返回 true 给定 word = "SEE", 返回 true 给定 word = "ABCB", 返回 false

题解 其实这道题涉及到广度优先搜索(BFS),如果当前满足条件,调用周围其他节点,需要用一个字段表明是否已经被访问过了

func exist(board [][]byte, word string) bool {
    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[i]); j++ {
            if helper(i,j, board, word, 0) {
                return true
            }
        }
    }
    return false
}

func helper(x, y int, board [][]byte, word string, idx int) bool {
    if x < 0 || y < 0 || x >= len(board) || y >= len(board[0]) || board[x][y] != word[idx] {
        return false
    }
    if idx == len(word) - 1 {
        return true
    }
    c := board[x][y]
    board[x][y] = ‘0‘

    check := helper(x-1, y, board, word, idx+1) || helper(x, y-1, board, word, idx+1) || helper(x+1, y, board, word, idx+1) || helper(x, y+1, board, word, idx +1)
    board[x][y] = c
    return check
}

技术分享图片

LeetCode 系列-数组与矩阵

原文:https://www.cnblogs.com/xnzone/p/14325297.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!