秋招突击——算法练习——8/26——图论——200-岛屿数量、994-腐烂的橘子、207-课程表、208-实现Trie

2024-08-28 18:04
文章标签 算法 实现 数量 200 图论 练习 秋招 26 课程表 突击 trie 994 橘子 腐烂 岛屿 208 207

本文主要是介绍秋招突击——算法练习——8/26——图论——200-岛屿数量、994-腐烂的橘子、207-课程表、208-实现Trie，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

    • 引言
    • 正文
      • 200-岛屿数量
        • 个人实现
      • 994、腐烂的橘子
        • 个人实现
        • 参考实现
      • 207、课程表
        • 个人实现
        • 参考实现
      • 208、实现Trie前缀树
        • 个人实现
        • 参考实现
    • 总结

引言

正文

200-岛屿数量

题目链接
在这里插入图片描述

个人实现
  • 我靠，这道题居然是腾讯一面的类似题，那道题是计算最大的岛屿面积，如果当时没做出来，现在得哭死！好在做出来了！
  • 这道题单纯使用回溯实现的，然后修改一下地图的坐标就行了！但是修改了原来的地图坐标，这样做效果并不好，但是不这样做，又必须得复制一个原来的数组，这样不行！
class Solution {public int[][] DIRECT = {{0,1},{0,-1},{1,0},{-1,0}};public void dfs(int x,int y,char[][] grid){if(grid[x][y] == '0' || grid[x][y] == '2') return;else grid[x][y] = '2';// 遍历对应的四个方向int m = grid.length;int n = grid[0].length;for(int[] dir:DIRECT){if(x + dir[0] < m && y + dir[1] < n && x + dir[0] >= 0  && y + dir[1] >= 0)dfs(x + dir[0],y + dir[1],grid);}}public int numIslands(char[][] grid) {int count = 0;  for(int i = 0;i < grid.length;i ++){for(int j = 0;j < grid[0].length;j ++){if(grid[i][j] == '1' ) {dfs(i,j,grid);count ++;}}}return count;}
}

在这里插入图片描述

994、腐烂的橘子

  • 题目链接
    在这里插入图片描述
    注意
  • 不会存在空图的情况
个人实现

思路分析

  • 首先不能让所有橘子都变坏，就返回-1，如果不会错，笔试的话，直接返回-1即可。具体见下图，可以看到通过了88个样例。这个技巧在华师大的预推免的笔试中已经见过了，很难受！这个技巧得敏感一点！

在这里插入图片描述

  • 正常思路还是使用BFS进行遍历，知道遍历不了，应为通过BFS的遍历方式和橘子腐烂的方式更像。
class Solution {public int[][] DIRECTION = {{0,1},{0,-1},{1,0},{-1,0}};public int orangesRotting(int[][] grid) {Queue<int[]> q = new ArrayDeque<>();Queue<int[]> q2 = new ArrayDeque<>();int res = 0;// 如果弹出栈的橘子是好橘子，跳过，如果是坏橘子，执行入站for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] == 2) {// 入栈开始烂橘子int count = 0;q.offer(new int[] { i, j });while (!q.isEmpty()) {int[] curNode = q.poll();int x = curNode[0];int y = curNode[1];for (int[] dir : DIRECTION) {// 遍历四个可以扩展的方向if (x + dir[0] >= 0 && x + dir[0] < grid.length &&y + dir[1] >= 0 && y + dir[1] < grid[0].length) {// 遍历到好橘子，先改变状态，然后直接入站        if (grid[x + dir[0]][y + dir[1]] == 1) {grid[x + dir[0]][y + dir[1]] = 2;q2.offer(new int[] { x + dir[0], y + dir[1] });}}}// 这里需要交换对应的节点if(q.isEmpty() && !q2.isEmpty()){Queue<int[]> temp = q;q = q2;q2 = temp;count ++;}}res = Math.max(res,count ++);}}}for (int i = 0; i < grid.length; i++) for (int j = 0; j < grid[0].length; j++)if(grid[i][j] == 1) return -1; return res;}
}

在这里插入图片描述
总结

  • 这里只能过一半，并不能过所有的样例，因为存在多个烂橘子，然后同时开始腐坏周围的橘子的情况，所以这里就不能抓住一个烂橘子，然后进行遍历，应该是先加上所有的烂橘子，然后所有烂橘子每次都想外扩展一圈，知道没有好橘子了，然后在遍历一下，但是面试的时候可能已经挂了，这里已经没时间了，直接看的样例吧！
参考实现
  • 这里先遍历一次，然后计算一下好橘子和烂橘子的数量，同时将所有的烂橘子加入到一个列表中，然后每一分钟，将所有烂橘子的周围的好橘子都变烂，然后加入到列表中，直到列表为空！
  • 具体实现如下，这里还是自己在原来的代码上修改的！
class Solution {public int[][] DIRECTION = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };public int orangesRotting(int[][] grid) {Queue<int[]> q = new ArrayDeque<>();int freshNum = 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] == 1)freshNum++;if (grid[i][j] == 2)q.offer(new int[] { i, j });}}int orangeNum = q.size() + freshNum;if(orangeNum == 0)  return 0;int count = -1;while (!q.isEmpty()) {count ++;int n = q.size();for (int i = 0; i < n; i++) {int[] curNode = q.poll();int x = curNode[0];int y = curNode[1];for (int[] dir : DIRECTION) {// 遍历四个可以扩展的方向if (x + dir[0] >= 0 && x + dir[0] < grid.length &&y + dir[1] >= 0 && y + dir[1] < grid[0].length) {// 遍历到好橘子，先改变状态，然后直接入站if (grid[x + dir[0]][y + dir[1]] == 1) {grid[x + dir[0]][y + dir[1]] = 2;freshNum --;q.offer(new int[] { x + dir[0], y + dir[1] });}}}}}if(freshNum != 0) return -1;return count;}
}

在这里插入图片描述

207、课程表

  • 题目链接
    在这里插入图片描述
个人实现

思路分析

  • 前缀课程这个想到了并查集，但是这个是检测是否成环的，这个有点忘记了，成环我记得有一个特定的算法，想想看！
  • 使用并查集，然后进行判定，父节点是否是自己！

在这里插入图片描述

上述两种情况并不好进行鉴别，这里应该修改一下，如果是初始状态，就默认是-1，然后如果是其他节点，就不是-1，看看行不行！

class Solution {int[] f;boolean flag = false;public int find(int idx){if(f[idx] == idx ){flag = true;return idx;}if(f[idx] == -1){return idx;}else{return find(f[idx]);}}public void union(int a,int b){// a节点是子节点，b节点是父节点// 找到对应的父亲节点int fa = find(a);int fb = find(b);if(fa == fb)    {flag = true;}// 设置对应的父亲节点f[fb] = fa;}public boolean canFinish(int numCourses, int[][] prerequisites) {// 创建并初始化父节点的数组f = new int[numCourses];for(int i = 0;i < numCourses;i ++) f[i] = -1;// 绑定父亲节点之间的关系for(int[] pre:prerequisites)    union(pre[0],pre[1]);// 这里要判定一下，是否没一门课都有自己的前导课程if(flag)    return false;return true;}
}

在这里插入图片描述
在这里插入图片描述

  • 确实没有环，但是插入3的关系时，还是出了问题，如果按照我这样写，3的先导课程已经插入过了，下次插入，会找到的祖先相同，直接返回false

又修改了一下，这里仅仅区分原始的单个节点成环状态，如果某个节点匹配到自己，就是实际上成环，直接退出

具体如下

class Solution {int[] f;public int find(int idx){if(f[idx] == -1 || f[idx] == idx){return idx;}else{return find(f[idx]);}}public void union(int a,int b){// a节点是子节点，b节点是父节点// 找到对应的父亲节点int fa = find(a);int fb = find(b);// 设置对应的父亲节点f[fb] = fa;}public boolean canFinish(int numCourses, int[][] prerequisites) {// 创建并初始化父节点的数组f = new int[numCourses];for(int i = 0;i < numCourses;i ++) f[i] = -1;// 绑定父亲节点之间的关系for(int[] pre:prerequisites)    union(pre[0],pre[1]);// 这里要判定一下，是否没一门课都有自己的前导课程for(int i = 0 ;i < numCourses;i ++) if(f[i] == i)   return false;return true;}
}

在这里插入图片描述
在这里插入图片描述
上述算法不行的，因为会出现一个问题，就是一个节点会有多个父节点，但是使用并查集，只能保存一个父节点，所以还是只能想到DFS或者BFS，但是不想这样做，没有任何意义！

参考实现

无向图成环——染色原理-三色

有向图求拓扑排序的问题——这是一个模版题

  • 遍历所有入度为零的点，对应子节点入度减一，入度为零加入队列，不能遍历完所有节点，就是有环

下图是针对成环的度数操作
在这里插入图片描述
下图是针对不成环的操作
在这里插入图片描述

class Solution {public boolean canFinish(int n, int[][] prerequisites) {// 创建邻接表，并进行赋值List<List<Integer>> grid = new ArrayList<>();int[] inNum = new int[n + 1];for(int i = 0;i <= n;i ++)  grid.add(new ArrayList<>());for(int[] edge: prerequisites){grid.get(edge[0]).add(edge[1]);inNum[edge[1]] ++;}// 遍历所有的节点，找到所有入度为零的点，加入队列进行遍历Queue<Integer> q = new ArrayDeque<>();for(int i = 0;i < n;i ++) if(inNum[i] == 0)q.offer(i);// 然后遍历队列中的点，并将其子节点的入度减一int visitedNum = q.size();while(!q.isEmpty()){int curNode = q.poll();// 遍历当前节点的所有后继子节点，并进行访问for(int i :grid.get(curNode)){inNum[i] --;if(inNum[i] == 0)   {q.offer(i);visitedNum ++;}}} if(visitedNum == n) return true;return false;}
}

在这里插入图片描述
总结

  • 这类图论的题目，这些基础的定理想起来了，就是会做，没想起来，只能硬做，没什么办法，具体需要考虑的因素也就只有出度、入度，然后成环也就是不同的情况而已！

208、实现Trie前缀树

  • 题目链接
    在这里插入图片描述
    注意
  • 这个会不会有多个字符串插入？会的
  • startwith是判定是否为前缀
  • search是找是否存在对应的字符串
个人实现

思路分析

  • 如果只有一个search，使用一个map就能够简单实现，找得到就是true，找不到就是false。或者说使用一个set也是完全可以的。
  • 现在如果只有一个startwith，就需要建造一个类似霍夫曼匹配树的东西，具体见下图。
    • 但是这个链表，太费空间了，想想每一个节点都要有对应的指针的往下才行，不过先实现一下，能通过就行！

在这里插入图片描述

个人实现

class Trie {class Node{char v;Map<Character,Node> map;Node(char c){v = c;map = new HashMap<>();}void put(Node next){map.put(next.v,next);}}Set<String> set;Map<Character,Node> sourMap;public Trie() {sourMap = new HashMap<>();set = new HashSet<>();}public void insert(String word) {set.add(word);// 先找到第一个字母对应的链表的位置char curChar = word.charAt(0);Node curNode;if(sourMap.containsKey(curChar)){// 包含当前节点curNode = sourMap.get(curChar);}else{// 不包含当前节点curNode  = new Node(curChar);sourMap.put(curChar,curNode);}// 构造对应的链表节点 for(int i = 1;i < word.length();i ++){char nextChar = word.charAt(i);// 判断当前的curNode是否包含了对应的节点的Node nextNode = null;if(!curNode.map.containsKey(nextChar)){nextNode = new Node(nextChar);curNode.put(nextNode);}else{nextNode = curNode.map.get(nextChar);}curNode = nextNode;}}public boolean search(String word) {return set.contains(word);}public boolean startsWith(String prefix) {char curChar = prefix.charAt(0);if(!sourMap.containsKey(curChar))   return false;Node curNode = sourMap.get(curChar);for(int i = 1;i < prefix.length();i ++){char nextChar = prefix.charAt(i);// 判断当前的curNode是否包含了对应的节点的if(!curNode.map.containsKey(nextChar)){return false;}curNode = curNode.map.get(nextChar);}return true;}
}

总结

  • 靠，我都惊讶了，一次过了，逻辑没啥问题！难得！
  • 总觉得我实现的不够光彩，还是有很多的问题，空间复杂度太高了，真的爆炸！
参考实现
  • 基本的思路还是一样的，不过增加了一个叶子节点的boolean状态值，判定是否存在对应的以叶子节点为结尾的序列是否存在。
  • 这里是使用数组来保存对应的后继节点的，然后默认是26个小写字母，所以会使用对应的字符串序列进行表示！
class Trie {class Node{boolean isExist;Node[] son;Node(){isExist = false;son = new Node[26];}}Node root;public Trie() {root = new Node();}public void insert(String word) {Node curNode = root;for(char x:word.toCharArray()){int idx = x - 'a';if(curNode.son[idx] == null){curNode.son[idx] = new Node();}curNode = curNode.son[idx];}curNode.isExist = true;}public boolean search(String word) {Node curNode = root;for(char x:word.toCharArray()){int idx = x - 'a';if(curNode.son[idx] == null){return false;}curNode = curNode.son[idx];}return curNode.isExist;}public boolean startsWith(String prefix) {Node curNode = root;for(char x:prefix.toCharArray()){int idx = x - 'a';if(curNode.son[idx] == null)    return false;curNode = curNode.son[idx];}return true;}
}

在这里插入图片描述
总结

  • 这个代码效率确实更高，写起来更加简洁！

总结

  • hot100的图论基本上都过了，总体来说还是其他部分要简单，继续二刷其他题目！保证每道题都能刷个两三遍！这样笔试还有手撕就不害怕了！

这篇关于秋招突击——算法练习——8/26——图论——200-岛屿数量、994-腐烂的橘子、207-课程表、208-实现Trie的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1115495。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2