《LeetCode热题100》笔记&题解&思路&技巧&优化_Part_5
- 😍😍😍 相知
- 🙌🙌🙌 相识
- 😢😢😢 开始刷题
- 图论
- 🟡1. 岛屿数量
- 🟡2. 腐烂的橘子（待定）
- 🟡3. 课程表(待定)
- 🟡4. 实现Trie (前缀树)
😍😍😍 相知
刷题不要一上来就直接干，先看题，明白题说的什么意思，然后想一下用什么现成的算法和数据结构可以快速解决，如果还是无从下手，建议先去看视频，不要直接翻评论或官方代码实现，看完视频，自己在idea中模拟敲几遍代码，如果跑通了，先别急着上leetcode黏贴，而是再回顾一下要点，然后确定自己完全懂了后，在leetcode中手敲，注意是手敲下来！！！ 目前我就是采用的这种方法，虽然慢，但是可以维持一周忘不掉它，如果要想长期不忘，只能隔段时间就review一下了，就算是大牛，知道方法，长时间不碰，也不可能保证一次到位把代码敲完一遍过！！！
🙌🙌🙌 相识
刷LeetCode热题100的想法有几个原因：
-
流行度高：LeetCode是一个广受欢迎的在线刷题平台，拥有大量用户和活跃的讨论社区。因此，热门题目通常代表了大多数人认为重要的题目或者面试中常见的题目。
-
面试备战：LeetCode上的题目往往和面试题目有很大的重合度。刷LeetCode热题100可以帮助你熟悉常见的面试题型和解题思路，提高应对面试的能力。
-
广泛的覆盖：热题100覆盖了各种难度级别的题目，包括简单、中等和困难。通过解答这些题目，可以提高自己的算法和编程能力，并扩展自己的知识面。
-
反馈和讨论：由于热题100是根据用户的反馈和讨论度排名的，因此这些题目往往有大量的解题思路和讨论可以参考。你可以从其他人的解题过程中学习到很多知识和技巧。
😢😢😢 开始刷题
图论
🟡1. 岛屿数量
题目链接：https://leetcode.cn/problems/number-of-islands/description/?envType=study-plan-v2&envId=top-100-liked
class Solution {
private int [][] ref = new int[][] {{1,0},{-1,0},{0,-1},{0,1}};
public int numIslands(char[][] grid) {
int sum = 0;
if(grid.length==0||grid[0].length==0)return 0;
boolean[][] flag = new boolean[grid.length][grid[0].length];
for(int i = 0;i<grid.length;i++){
for(int j = 0;j<grid[i].length;j++){
if(!flag[i][j] && grid[i][j]=='1'){
dfs(grid,flag,i,j);
sum++;
}
}
}
return sum;
}
private void dfs(char[][] grid,boolean[][] flag,int a,int b){
for(int i = 0;i<4;i++){
int na = a + ref[i][0];
int nb = b + ref[i][1];
if(na<0||na>=grid.length||nb<0||nb>=grid[0].length) continue;
if(!flag[na][nb]&&grid[na][nb]=='1'){
flag[na][nb] = true;
dfs(grid,flag,na,nb);
}
}
}
}
🟡2. 腐烂的橘子（待定）
题目链接：https://leetcode.cn/problems/rotting-oranges/description/?envType=study-plan-v2&envId=top-100-liked
class Solution {
public int orangesRotting(int[][] grid) {
if(grid.length<=0||grid[0].length<=0)return 0;
boolean oneflag = false;
boolean twoflag = false;
for(int i = 0;i<grid.length;i++){
for(int j = 0;j<grid[i].length;j++){
if(grid[i][j]==1)oneflag =true;
else if(grid[i][j]==2 )twoflag =true;
}
}
if(oneflag==false)return 0;
if(twoflag==false)return -1;
//solve
for(int i = 0;i<grid.length;i++){
for(int j = 0;j<grid[i].length;j++){
if(grid[i][j]==2){
dfs(grid,i,j,2);
}
}
}
int min = Integer.MIN_VALUE;
for(int i = 0;i<grid.length;i++){
for(int j = 0;j<grid[i].length;j++){
if(grid[i][j]==1) return -1;
if(grid[i][j]!=0) min = Math.max(min,grid[i][j]);
}
}
return min-2;
}
private void dfs (int[][] grid,int i,int j,int level){
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length ) return;
if (grid[i][j] != 1 && grid[i][j] < level) { // 只有新鲜橘子或者传播路径比当前路径长的橘子，才继续进行传播。
return;
}
grid[i][j] = level; // 将传染路径的长度存到grid[i][j]中
level++;
dfs(grid,i - 1, j, level);
dfs(grid,i + 1, j, level);
dfs(grid,i, j - 1, level);
dfs(grid,i, j + 1, level);
}
}
🟡3. 课程表(待定)
题目链接：https://leetcode.cn/problems/course-schedule/description/?envType=study-plan-v2&envId=top-100-liked
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if(prerequisites.length<=1)return true;
int [] task = new int[numCourses];
for(int i = 0;i<prerequisites.length;i++){
task[prerequisites[i][0]]++;
}
boolean[] removed = new boolean[prerequisites.length];
int removenum = 0;
while(removenum < prerequisites.length){
int currRemove = 0;// 本轮移除的元素数量
for(int i =0;i<prerequisites.length;i++){
if(removed[i]) continue;
if(task[prerequisites[i][1]]==0){
task[prerequisites[i][0]]--;
removed[i] = true;
currRemove++;
}
}
if (currRemove == 0) return false;// 如果一轮跑下来一个元素都没移除，则没必要进行下一轮
removenum += currRemove;
}
return true;
}
}
🟡4. 实现Trie (前缀树)
题目链接：https://leetcode.cn/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-100-liked
class TrieNode{
public boolean isWord;
public TrieNode [] children;
public TrieNode(){
isWord = false;
children = new TrieNode[26];
}
}
class Trie {
private TrieNode trienode;
public Trie() {
trienode = new TrieNode();
}
public void insert(String word) {
TrieNode temp = trienode;
for(int i = 0;i<word.length();i++){
if(temp.children[word.charAt(i)-'a']==null)
temp.children[word.charAt(i)-'a'] = new TrieNode();
temp = temp.children[word.charAt(i)-'a'];
}
temp.isWord = true;
}
public boolean search(String word) {
TrieNode temp = trienode;
for(int i = 0;i<word.length();i++){
temp = temp.children[word.charAt(i)-'a'];
if(temp==null)return false;
}
return temp.isWord;
}
public boolean startsWith(String prefix) {
TrieNode temp = trienode;
for(int i = 0;i<prefix.length();i++){
temp = temp.children[prefix.charAt(i)-'a'];
if(temp==null)return false;
}
return true;
}
}
