面试经典150题——图

devtools/2025/2/5 17:28:38/

文章目录

  • 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 解题思路
  • 6、课程表 II
    • 6.1 题目链接
    • 6.2 题目描述
    • 6.3 解题代码
    • 6.4 解题思路

1、岛屿数量

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] 的值为 ‘0’ 或 ‘1’

1.3 解题代码

class Solution {int[][] dir = {{-1, 0},{1, 0},{0, 1},{0, -1},};public int numIslands(char[][] grid) {Map<Integer, Integer> hash = new HashMap<Integer, Integer>(); int m = grid.length;int n = grid[0].length;int ret = 0;Queue<Integer> q = new LinkedList();for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){if(grid[i][j] == '1' && !hash.containsKey(500 * i + j)){q.offer(500 * i + j);hash.put(500 * i + j, 1);++ret;}while(!q.isEmpty()){int num = q.peek();q.poll();int x = num / 500;int y = num % 500;for(int k = 0; k < 4; ++k){int tx = x + dir[k][0];int ty = y + dir[k][1];if(tx < 0 || tx >= m || ty < 0 || ty >= n || grid[tx][ty] == '0'){continue;}if(!hash.containsKey(tx * 500 + ty)){hash.put(tx * 500 + ty, 1);q.offer(tx * 500 + ty);}}}}}return ret;}
}

1.4 解题思路

  1. 使用广度优先搜索来解决问题。
  2. 广度优先搜索的核心思路为哈希+队列。

2、被围绕的区域

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ 组成，捕获 所有 被围绕的区域：

  • **连接：**一个单元格与水平或垂直方向上相邻的单元格连接。
  • 区域：连接所有 ‘O’ 的单元格来形成一个区域。
  • **围绕：**如果您可以用 ‘X’ 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 ‘X’ 单元格围绕。

通过 原地 将输入矩阵中的所有 ‘O’ 替换为 ‘X’ 来 捕获被围绕的区域。你不需要返回任何值。

提示：

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] 为 ‘X’ 或 ‘O’

2.3 解题代码

class Solution {int[][] dir = {{-1, 0},{1, 0},{0, -1},{0, 1},};Map<Integer, Integer> hash = new HashMap<Integer, Integer>();void bfs(char[][] board, int startX, int startY, int m, int n){Queue<Integer> q = new LinkedList();q.offer(startX * 500 + startY);hash.put(startX * 500 + startY, 1);while(!q.isEmpty()){int num = q.peek();q.poll();int x = num / 500;int y = num % 500;for(int k = 0; k < 4; ++k){int tx = x + dir[k][0];int ty = y + dir[k][1];if(tx < 0 || tx >= m || ty < 0 || ty >= n || board[tx][ty] == 'X'){continue;}if(!hash.containsKey(tx * 500 + ty)){hash.put(tx * 500 + ty, 1);q.offer(tx * 500 + ty);}}}}public void solve(char[][] board) {int m = board.length;int n = board[0].length;for(int i = 0; i < m; ++i){if(board[i][0] == 'O' && !hash.containsKey(i * 500 + 0)){bfs(board, i, 0, m, n);}if(board[i][n - 1] == 'O' && !hash.containsKey(i * 500 + n - 1)){bfs(board, i, n - 1, m, n);}}for(int j = 0; j < n; ++j){if(board[0][j] == 'O' && !hash.containsKey(0 * 500 + j)){bfs(board, 0, j, m, n);}if(board[m - 1][j] == 'O' && !hash.containsKey((m - 1) * 500 + j)){bfs(board, m - 1, j, m, n);}}for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){if(board[i][j] == 'O' && !hash.containsKey(i * 500 + j)){board[i][j] = 'X';}}}}
}

2.4 解题思路

  1. 广度优先搜索，首先先从地图边缘开始进行广搜，将所有与地图边缘连接且字符为’O’的点用哈希表标注起来
  2. 之后遍历地图，对所有字符为‘O’，并且哈希表中不存在的点转化成‘X’。

3、克隆图

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）
在这里插入图片描述
测试用例格式：

简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

提示：

  • 这张图中的节点数在 [0, 100] 之间。
  • 1 <= Node.val <= 100
  • 每个节点值 Node.val 都是唯一的，
  • 图中没有重复的边，也没有自环。
  • 图是连通图，你可以从给定节点访问到所有节点。

3.3 解题代码

/*
// Definition for a Node.
class Node {public int val;public List<Node> neighbors;public Node() {val = 0;neighbors = new ArrayList<Node>();}public Node(int _val) {val = _val;neighbors = new ArrayList<Node>();}public Node(int _val, ArrayList<Node> _neighbors) {val = _val;neighbors = _neighbors;}
}
*/class Solution {Map<Node, Node> hash = new HashMap<Node, Node>();public Node cloneGraph(Node node) {if(node == null){return null;}if(!hash.containsKey(node)){Node newNode = new Node(node.val);hash.put(node, newNode);for(int i = 0; i < node.neighbors.size(); ++i){newNode.neighbors.add(cloneGraph(node.neighbors.get(i)));}}return hash.get(node);}
}

3.4 解题思路

  1. 递归求解即可，题目与之前的138. 随机链表的复制一致。

4、除法求值

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

**注意：**输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

**注意：**未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。

提示：

  • 1 <= equations.length <= 20
  • equations[i].length == 2
  • 1 <= Ai.length, Bi.length <= 5
  • values.length == equations.length
  • 0.0 < values[i] <= 20.0
  • 1 <= queries.length <= 20
  • queries[i].length == 2
  • 1 <= Cj.length, Dj.length <= 5
  • Ai, Bi, Cj, Dj 由小写英文字母与数字组成

4.3 解题代码

class Solution {Map<String, Integer> hash = new HashMap<String, Integer>();int find(List<Integer> pre, List<Double> weight, int x){if(x != pre.get(x)){int origin = pre.get(x);pre.set(x, find(pre, weight, pre.get(x))); weight.set(x, weight.get(x) * weight.get(origin));}return pre.get(x);}void union(List<Integer> pre, List<Double> weight, double value, int x, int y){int index1 = find(pre, weight, x);int index2 = find(pre, weight, y);if(index1 != index2){pre.set(index1, index2);weight.set(index1, weight.get(y) * value / weight.get(x)); }}public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {int equationsSize = equations.size();int queriesSize = queries.size();double[] res = new double[queriesSize];int id = 0;List<Integer> pre = new ArrayList<>();List<Double> weight = new ArrayList<Double>();for(int i = 0; i < equationsSize; ++i){String str1 = equations.get(i).get(0);String str2 = equations.get(i).get(1);if(!hash.containsKey(str1)){hash.put(str1, id);pre.add(id);weight.add(1.0d);id++;        }if(!hash.containsKey(str2)){hash.put(str2, id);pre.add(id);weight.add(1.0);id++;}union(pre, weight, values[i], hash.get(str1), hash.get(str2));}for(int i = 0; i < queriesSize; ++i){String str1 = queries.get(i).get(0);String str2 = queries.get(i).get(1);if(!hash.containsKey(str1) || !hash.containsKey(str2)){res[i] = -1.0;continue;}Integer id1 = hash.get(str1);Integer id2 = hash.get(str2);if(find(pre, weight, id1) != find(pre, weight, id2)){res[i] = -1.0d;continue;}double value1 = weight.get(id1);double value2 = weight.get(id2);res[i] = value1 / value2;}return res;}
}

4.4 解题思路

  1. 使用并查集解决问题。

5、课程表

5.1 题目链接

点击跳转到题目位置

5.2 题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

提示：

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[i] 中的所有课程对 互不相同

5.3 解题代码

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {List<List<Integer>> edge = new ArrayList<>();for (int i = 0; i < numCourses; ++i) {edge.add(new ArrayList<>());}int[] deg = new int[numCourses];int n = prerequisites.length;for(int i = 0; i < n; ++i){int x = prerequisites[i][0];int y = prerequisites[i][1];deg[x]++;edge.get(y).add(x);}Queue<Integer> q = new LinkedList<Integer>();for(int i = 0; i < numCourses; ++i){if(deg[i] == 0){q.offer(i);}}while(!q.isEmpty()){int x = q.peek();q.poll();numCourses--;for(int i = 0; i < edge.get(x).size(); ++i){int num = edge.get(x).get(i);deg[num]--;if(deg[num] == 0){q.offer(num);}}}return numCourses == 0;}
}

5.4 解题思路

  1. 使用拓扑排序来解决问题
  2. 每次将度为0的结点放入队列中，每次从队首取点，并且numCourses–。如果最后图中存在环的话，则numCourses则不为0。

6、课程表 II

6.1 题目链接

点击跳转到题目位置

6.2 题目描述

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

  • 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

提示：

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • ai != bi
    所有[ai, bi] 互不相同

6.3 解题代码

class Solution {public int[] findOrder(int numCourses, int[][] prerequisites) {int[] res = new int[numCourses];int k = 0;List<List<Integer>> edge = new ArrayList<>();for (int i = 0; i < numCourses; ++i) {edge.add(new ArrayList<>());}int[] deg = new int[numCourses];int n = prerequisites.length;for(int i = 0; i < n; ++i){int x = prerequisites[i][0];int y = prerequisites[i][1];deg[x]++;edge.get(y).add(x);}Queue<Integer> q = new LinkedList<Integer>();for(int i = 0; i < numCourses; ++i){if(deg[i] == 0){q.offer(i);}}while(!q.isEmpty()){int x = q.peek();res[k++] = x;q.poll();numCourses--;for(int i = 0; i < edge.get(x).size(); ++i){int num = edge.get(x).get(i);deg[num]--;if(deg[num] == 0){q.offer(num);}}}if(numCourses == 0){return res;}return new int[0];}
}

6.4 解题思路

  1. 使用拓扑排序解题
  2. 与上一题的区别就是需要把每次队首的元素放入结果数组中，最后符合条件的输出结果数组，否则输出空数组。

http://www.ppmy.cn/devtools/156332.html

相关文章

9.7 打造你的专属智能助手：基于 GPT Builder 定制化 ChatGPT 应用全指南

9.7 打造你的专属智能助手：基于 GPT Builder 定制化 ChatGPT 应用全指南

打造你的专属智能助手：基于 GPT Builder 定制化 ChatGPT 应用全指南 引言：让 AI 更懂你 在人工智能技术飞速发展的今天，ChatGPT 已成为提升效率和解放生产力的利器。然而，通用的 ChatGPT 可能无法完全满足个性化需求，这时候 GPT Builder 应运而生。它提供了一种直观、灵活…
阅读更多...
【网站建设：HTTPS - 如何生成免费SSL证书，并自动更新】

【网站建设：HTTPS - 如何生成免费SSL证书，并自动更新】

某阿X云服务平台的证书托管服务中&#xff0c;有关于HTTPS证书获取&#xff0c;生成和自动更新的功能。但其作为一项增值服务&#xff0c;每月就要几百元 。但是这个我们可以自己写几行代码来实现&#xff0c; 证书生成更新到Nginx自动更新 假设我们有个域名wu123.cn要为域名…
阅读更多...
菜鸟之路Day09一一集合进阶(二)

菜鸟之路Day09一一集合进阶(二)

菜鸟之路Day09一一集合进阶(二) 作者&#xff1a;blue 时间&#xff1a;2025.1.27 文章目录 菜鸟之路Day09一一集合进阶(二)0.概述1.泛型1.1泛型概述1.2泛型类1.3泛型方法1.4泛型接口1.5泛型通配符 2.Set系列集合2.1遍历方式2.2HashSet2.3LinkedHashSet2.4TreeSet 0.概述 内…
阅读更多...
什么是门控循环单元？

什么是门控循环单元？

一、概念 门控循环单元&#xff08;Gated Recurrent Unit&#xff0c;GRU&#xff09;是一种改进的循环神经网络&#xff08;RNN&#xff09;&#xff0c;由Cho等人在2014年提出。GRU是LSTM的简化版本&#xff0c;通过减少门的数量和简化结构&#xff0c;保留了LSTM的长时间依赖…
阅读更多...
开源 CSS 框架 Tailwind CSS v4.0

开源 CSS 框架 Tailwind CSS v4.0

开源 CSS 框架 Tailwind CSS v4.0 于 1 月 22 日正式发布&#xff0c;除了显著提升性能、简化配置体验外&#xff0c;还增强了功能特性&#xff0c;具体如下1&#xff1a; 性能提升 采用全新的高性能引擎 Oxide&#xff0c;带来了构建速度的巨大飞跃&#xff1a; 全量构建速度…
阅读更多...
图神经网络驱动的节点分类：从理论到实践

图神经网络驱动的节点分类：从理论到实践

图神经网络驱动的节点分类：从理论到实践 1. 引言 图神经网络（Graph Neural Networks，GNN）作为处理图结构数据的强大工具，近年来在学术界和工业界都取得了显著进展。其独特的消息传递机制能够有效捕捉图数据中的复杂关系，为节点分类、链接预测、图分类等任务提供了新的解…
阅读更多...
「全网最细 + 实战源码案例」设计模式——模板方法模式

「全网最细 + 实战源码案例」设计模式——模板方法模式

核心思想 模板方法模式&#xff08;Template Method Pattern&#xff09;是一种行为型设计模式&#xff0c;定义了一个算法的骨架&#xff08;模板&#xff09;&#xff0c;将某些步骤延迟到子类中实现&#xff08;在不修改结构的情况下&#xff09;&#xff0c;以避免代码重复…
阅读更多...
新春贺岁，共赴AGI之旅

新春贺岁，共赴AGI之旅

点击蓝字 关注我们 AI TIME欢迎每一位AI爱好者的加入&#xff01; 往期精彩文章推荐 季姮教授独家文字版干货 | 面向知识渊博的大语言模型 关于AI TIME AI TIME源起于2019年&#xff0c;旨在发扬科学思辨精神&#xff0c;邀请各界人士对人工智能理论、算法和场景应用的本质问题…
阅读更多...
最新文章

Copyright @ 2022~2023