此类型的题目,没有固定的模式,只能看自己的经验
其中每道题都存在一种暴力解法,如果实在没有更好的解法,可以尝试暴力解法。面试中如果暂时想不出题解,一定要尝试使用暴力解法得到答案
给你一个未排序的整数数组 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
}
给定一个 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++
}
}
给定一个包含 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
}
给定一个 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
}
}
}
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
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
}
原文:https://www.cnblogs.com/xnzone/p/14325297.html