1-leetcode200. 岛屿数目
注意:×
- 蛮奇妙的做法,直接在读取到1的时候给res的值+1,然后深度优先搜索把全部相邻的陆地全部改为海洋
- 注意dfs里面的范围判定,[0, **length-1]**
- length-1
- length-1
- length-1
- public int numIslands(char[][] grid) {
- int res = 0;
- int n = grid.length;;
- int m = grid[0].length;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- if (grid[i][j] == '1'){
- res++;
- dfs(grid, i, j);
- }
- }
- }
- return res;
- }
- private void dfs(char[][] grid, int i, int j) {
- if (i<0 || i>=grid.length || j<0 || j>=grid[0].length){
- return;
- }
- if (grid[i][j] == '0'){
- return;
- }
- grid[i][j] = '0';
- dfs(grid, i+1, j);
- dfs(grid, i, j+1);
- dfs(grid, i-1, j);
- dfs(grid, i, j-1);
- }
复制代码 leetcode994. 腐烂的橘子
注意:×
- [/code] [size=5]3-leetcode207. 课程表[/size]
- 注意:××
- [list=1]
- [*]花了许多时间,注意的地方太多了
- [*]创建List<Integer>[] graph的时候,Labuladong说写代码的时候大部分都是这种连接表的格式,先创建一个LinkedList类型的数组,然后一定要注意,是graph[i] = new LinkedList<>();
- [*]第二个注意的地方是有hasVisited和onPath两种记录,onPath的记录我能明确,hasVisited的记录还需要思索一下,主要的目的就是办理重复搜索
- [/list] [code]
- boolean hasCycle = false;
- boolean[] hasVisited;
- boolean[] onPath;
- public boolean canFinish(int numCourses, int[][] prerequisites) {
- List<Integer>[] graph = buildGraph(numCourses, prerequisites);
- hasVisited = new boolean[numCourses];
- onPath = new boolean[numCourses];
- for (int i = 0; i < numCourses; i++) {
- traverse(graph, i);
- }
- return !hasCycle;
- }
- private void traverse(List<Integer>[] graph, int i) {
- if (onPath[i]){
- hasCycle = true;
- }
- if (hasCycle || hasVisited[i]){
- return;
- }
-
- hasVisited[i] = true;
-
- onPath[i] = true;
- for (Integer integer : graph[i]) {
- traverse(graph, integer);
- }
-
- onPath[i] = false;
- }
- private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
- List<Integer>[] graph = new LinkedList[numCourses];
- for (int i = 0; i < graph.length; i++) {
- graph[i] = new LinkedList<>();
- }
- for (int[] prerequisite : prerequisites) {
- int from = prerequisite[1];
- int to = prerequisite[0];
- graph[from].add(to);
- }
- return graph;
- }
复制代码 4-leetcode208. 实现 Trie (前缀树)
注意:×
- 看了题解再写,感觉照旧有点压力
- 注意isEnd的调用
- class Trie {
- class TrieNode{
- boolean isEnd;
- TrieNode[] nodes;
- public TrieNode(){
- isEnd = false;
- nodes = new TrieNode[26];
- }
- }
- private TrieNode root;
- public Trie() {
- root = new TrieNode();
- }
- public void insert(String word) {
- TrieNode node = root;
- for (char c : word.toCharArray()) {
- if (node.nodes[c-'a'] == null){
- node.nodes[c-'a'] = new TrieNode();
- }
- node = node.nodes[c-'a'];
- }
- node.isEnd = true;
- }
- public boolean search(String word) {
- TrieNode node = root;
- for (char c : word.toCharArray()) {
- if (node.nodes[c-'a'] == null){
- return false;
- }
- node = node.nodes[c-'a'];
- }
- return node.isEnd;
- }
- public boolean startsWith(String prefix) {
- TrieNode node = root;
- for (char c : prefix.toCharArray()) {
- if (node.nodes[c-'a'] == null){
- return false;
- }
- node = node.nodes[c-'a'];
- }
- return true;
- }
- }
复制代码 免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。 |