面试经典150题——矩阵

embedded/2025/1/7 19:30:34/

文章目录

  • 1、有效的数独
    • 1.1 题目链接
    • 1.2 题目描述
    • 1.3 解题代码
    • 1.4 解题思路
  • 2、螺旋矩阵
    • 2.1 题目链接
    • 2.2 题目描述
    • 2.3 解题代码
    • 2.4 解题思路
  • 3、旋转图像
    • 3.1 题目链接
    • 3.2 题目描述
    • 3.3 解题代码
    • 3.4 解题思路
  • 4、矩阵置零
    • 4.1 题目链接
    • 4.2 题目描述
    • 4.3 解题代码
    • 4.4 解题思路
  • 5、生命游戏
    • 5.1 题目链接
    • 5.2 题目描述
    • 5.3 解题代码
    • 5.4 解题思路


1、有效的数独

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)

注意:

  • 一个有效的数独(部分已被填充)不一定是可解的。
  • 只需要根据以上规则,验证已经填入的数字是否有效即可。
  • 空白格用 ‘.’ 表示。

提示:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字(1-9)或者 ‘.’

1.3 解题代码

class Solution {boolean judgeRow(char[][] board, int row){int[] hash = new int[10];for(int i = 0; i < 9; ++i){if(board[row][i] == '.'){continue;}int num = board[row][i] - '0';if(hash[num] == 1){return false;}hash[num] = 1;}return true;}boolean judgeCol(char[][] board, int col){int[] hash = new int[10];for(int i = 0; i < 9; ++i){if(board[i][col] == '.'){continue;}int num = board[i][col] - '0';if(hash[num] == 1){return false;}hash[num] = 1;}return true;}boolean judgeBoard(char[][] board, int row, int col){int[] hash = new int[10];for(int i = 0; i < 3; ++i){for(int j = 0; j < 3; ++j){if(board[row + i][col + j] == '.'){continue;}int num = board[row + i][col + j] - '0';if(hash[num] == 1){return false;}hash[num] = 1;}}return true;}public boolean isValidSudoku(char[][] board) {for(int i = 0; i < 9; ++i){if(judgeCol(board, i) == false || judgeRow(board, i) == false){return false;}}for(int i = 0; i < 9; i += 3){for(int j = 0; j < 9; j += 3){if(judgeBoard(board, i , j) == false){return false;}}}return true;}
}

1.4 解题思路

  1. 哈希表判断一行,一列或者一个九宫格中是否有相同的数字即可。
  2. 判断一行就是行值固定,列数9列;判断一列就是列值固定,行数9列;判断九宫格就是九宫格左上角固定,从左往右三列,从上往下三行。

2、螺旋矩阵

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • loo-100 <= matrix[i][j] <= 100

2.3 解题代码

class Solution {int[][] dir = {{0, 1},{1, 0},{0, -1},{-1, 0},};public List<Integer> spiralOrder(int[][] matrix) {int m = matrix.length;int n = matrix[0].length;int[][] hash = new int[m][n];List<Integer> ret = new ArrayList<Integer>();int i = 0;int row = 0;int col = 0;int flag = 0;while(i < m * n){hash[row][col] = 1;ret.add(matrix[row][col]);int next_row = row + dir[flag][0]; int next_col = col + dir[flag][1];if(next_row < 0 || next_row >= m || next_col < 0 || next_col >= n || hash[next_row][next_col] == 1){flag = (flag + 1) % 4;} row += dir[flag][0];col += dir[flag][1];++i;}return ret;}
}

2.4 解题思路

  1. 四方向遍历,用数组来表示从左往右,从上往下,从右往左,从下往上。
  2. 用(flag + 1) % 4 来进行控制状态的变化。
  3. 之后遍历二维矩阵m * n次即可。

3、旋转图像

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

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

你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

3.3 解题代码

3.4 解题思路

4、矩阵置零

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

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

提示:

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -231 <= matrix[i][j] <= 231 - 1

4.3 解题代码

class Solution {public void setZeroes(int[][] matrix) {int m = matrix.length;int n = matrix[0].length;int[] row = new int[m];int[] line = new int[n];for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){if(matrix[i][j] == 0){row[i] = 1;line[j] = 1;}}}for(int i = 0; i < m; ++i){if(row[i] == 1){for(int j = 0; j < n; ++j){matrix[i][j] = 0;}}}for(int i = 0; i < n; ++i){if(line[i] == 1){for(int j = 0; j < m; ++j){matrix[j][i] = 0;}}}}
}

4.4 解题思路

  1. 遍历矩阵,用哈希表row和哈希表col来表示某一行或者某一列需要全部置0.
  2. 按行和列遍历矩阵,来将矩阵的一行或者一列置0。

5、生命游戏

5.1 题目链接

点击跳转到题目位置

5.2 题目描述

根据 百度百科 , 生命游戏 ,简称为 生命 ,是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板,每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态: 1 即为 活细胞 (live),或 0 即为 死细胞 (dead)。每个细胞与其八个相邻位置(水平,垂直,对角线)的细胞都遵循以下四条生存定律:

  1. 如果活细胞周围八个位置的活细胞数少于两个,则该位置活细胞死亡;
  2. 如果活细胞周围八个位置有两个或三个活细胞,则该位置活细胞仍然存活;
  3. 如果活细胞周围八个位置有超过三个活细胞,则该位置活细胞死亡;
  4. 如果死细胞周围正好有三个活细胞,则该位置死细胞复活;

下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的,其中细胞的出生和死亡是 同时 发生的。给你 m x n 网格面板 board 的当前状态,返回下一个状态。

给定当前 board 的状态,更新 board 到下一个状态。

注意 你不需要返回任何东西。

提示:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 25
  • board[i][j] 为 0 或 1

5.3 解题代码

5.4 解题思路


http://www.ppmy.cn/embedded/151683.html

相关文章

使用 `seed` 和 `system_fingerprint` 实现 OpenAI API 的确定性输出

使用 seed 和 system_fingerprint 实现 OpenAI API 的确定性输出 1. 什么是确定性输出&#xff1f;2. 使用 seed 参数实现确定性输出如何使用 seed 参数&#xff1a;示例代码&#xff1a;注意事项&#xff1a; 3. 使用 system_fingerprint 跟踪模型配置变化如何使用 system_fin…

WebApi使用 (.Net Framework版)

1 创建 使用.Net做web后端&#xff0c;推荐使用.Net Core&#xff0c;微软在此基础上做了很多适配&#xff0c;包括内置Swagger&#xff0c;可以直接启动等等。而.Net Framework版&#xff0c;需要手动配置很多内容。 如果需要调用的项目是基于.Net Framework&#xff0c;那么…

学习随记:word2vec中归一化处理的作用

答案来自ai&#xff0c;直接复用为参考&#xff1a; 向量归一化的好处 将向量进行归一化&#xff0c;使其模长为 1&#xff08;即投射到单位圆/单位球上&#xff09;&#xff0c;在许多情况下具有实际意义和计算优势。以下是归一化的主要好处和原因&#xff1a; 1. 提高数值稳…

leetcode(hot100)6、7

解题思路&#xff1a;先排序再利用双指针思想然后再去重处理。去重要 nums [i] nums [i- 1 ] 考虑-1&#xff0c;-1&#xff0c;2这种情况。 class Solution { public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end())…

【深度学习遥感应用中的“信息”】空间信息、语义信息、纹理信息、边缘信息、表层信息、深层信息...

【深度学习遥感应用中的“信息”】空间信息、语义信息、纹理信息、边缘信息、表层信息、深层信息… 【深度学习遥感应用中的“信息”】空间信息、语义信息、纹理信息、边缘信息、表层信息、深层信息… 文章目录 【深度学习遥感应用中的“信息”】空间信息、语义信息、纹理信息…

React快速上手到项目实战总篇

React核心价值与前置知识 时刻保持对知识的渴望 家人们 开学!!! 核心价值 组件化&#xff08;易开发易维护&#xff09; 数据驱动视图 &#xff1a;定义好数据和ui的显示规则 即UIf(state) 只关注业务数据修改&#xff0c;不在操作DOM 增加开发效率 使用vite创建Recat项目 …

[SMARTFORMS] 创建FORM

输入事务码SMARTFORMS进入表单开发界面&#xff0c;选中表单&#xff0c;自定义表单名称ZFS_DEMO_2025 点击"创建"按钮&#xff0c;跳转至"SAP表格设计器"页面 在"表格属性"填写表单描述、指定页格式和样式 在"表格接口"可以填写SMART…

Git的简单介绍与如何安装Git

文章目录 前言一、初始git1.git是什么2.为什么要使用git(出现的问题)3.git是如何解决问题的 二、git的安装与卸载1.centos系统2.ubuntu系统3.windows 三、搭建git本地环境1.创建git本地仓库2.配置用户信息 总结 前言 本文简单引入git的相关内容。 一、初始git 1.git是什么 g…