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

本文主要是介绍秋招突击——算法练习——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

相关文章

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

Qt使用QSqlDatabase连接MySQL实现增删改查功能

《Qt使用QSqlDatabase连接MySQL实现增删改查功能》这篇文章主要为大家详细介绍了Qt如何使用QSqlDatabase连接MySQL实现增删改查功能,文中的示例代码讲解详细,感兴趣的小伙伴... 目录一、创建数据表二、连接mysql数据库三、封装成一个完整的轻量级 ORM 风格类3.1 表结构

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库:CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文

golang版本升级如何实现

《golang版本升级如何实现》:本文主要介绍golang版本升级如何实现问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录golanwww.chinasem.cng版本升级linux上golang版本升级删除golang旧版本安装golang最新版本总结gola

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具