文章目录
- 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. 实现 Trie (前缀树)
- 4.1 题目链接
- 4.2 题目描述
- 4.3 解题代码
- 4.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 解题思路
- 使用广度优先搜索来解决问题。
- 广度优先搜索的核心思路为哈希+队列。
2、腐烂的橘子
2.1 题目链接
点击跳转到题目位置
2.2 题目描述
在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一:
- 值 0 代表空单元格;
- 值 1 代表新鲜橘子;
- 值 2 代表腐烂的橘子。
每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1 。
提示:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 10
- grid[i][j] 仅为 0、1 或 2
2.3 解题代码
class Solution {int[][] dir = {{-1, 0},{1, 0},{0, -1},{0, 1},};public int orangesRotting(int[][] grid) {Queue<Integer> q = new LinkedList<Integer>();int m = grid.length;int n = grid[0].length;int num = 0;int res = 0;for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){if(grid[i][j] == 1){num++;}if(grid[i][j] == 2){q.offer(i * 100 + j);}}}if(num == 0){return 0;}while(!q.isEmpty()){int len = q.size();System.out.println(len);res++;for(int i = 0; i < len; ++i){int curr = q.peek();q.poll();int x = curr / 100;int y = curr % 100;for(int k = 0; k < 4; ++k){int tx = dir[k][0] + x;int ty = dir[k][1] + y;if(tx < 0 || tx >= m || ty < 0 || ty >= n){continue;} if(grid[tx][ty] == 1){grid[tx][ty] = 2;q.offer(tx * 100 + ty);num--;if(num == 0){System.out.println("ggggggg");break;}}}if(num == 0){break;} }if(num == 0){break;} }return num == 0 ? res : -1;}
}
2.4 解题思路
- 用广度优先搜索模拟橘子腐坏的过程。
- 哈希+队列,直到橘子完全腐坏或者橘子无法被腐坏跳出循环。
3. 课程表
3.1 题目链接
点击跳转到题目位置
3.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] 中的所有课程对 互不相同
3.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;}
}
3.4 解题思路
- 使用拓扑排序来解决问题
- 每次将度为0的结点放入队列中,每次从队首取点,并且numCourses–。如果最后图中存在环的话,则numCourses则不为0。
4. 实现 Trie (前缀树)
4.1 题目链接
点击跳转到题目位置
4.2 题目描述
Trie(发音类似 “try”)或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补全和拼写检查。
请你实现 Trie 类:
- Trie() 初始化前缀树对象。
- void insert(String word) 向前缀树中插入字符串 word 。
- boolean search(String word) 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false 。
- boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false 。
提示:
- 1 <= word.length, prefix.length <= 2000
- word 和 prefix 仅由小写英文字母组成
- insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次
4.3 解题代码
class TrieNode{TrieNode[] next;boolean end;TrieNode(){next = new TrieNode[26];end = false;}
}class Trie {TrieNode root;public Trie() {root = new TrieNode();}public void insert(String word) {TrieNode now = root;for(int i = 0; i < word.length(); ++i){int child = word.charAt(i) - 'a';if(now.next[child] == null){now.next[child] = new TrieNode();}now = now.next[child];}now.end = true;}public boolean search(String word) {TrieNode now = root;for(int i = 0; i < word.length(); ++i){int child = word.charAt(i) - 'a';if(now.next[child] == null){return false;}now = now.next[child]; }return now.end;}public boolean startsWith(String prefix) {TrieNode now = root;for(int i = 0; i < prefix.length(); ++i){int child = prefix.charAt(i) - 'a';if(now.next[child] == null){return false;}now = now.next[child]; }return true;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/
4.4 解题思路
- 字典树经典题型,套用模板即可。