java算法题每日多道九

2024-03-26 19:12
文章标签 java 算法 每日 多道

本文主要是介绍java算法题每日多道九,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

530. 二叉搜索树的最小绝对差

题目

给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值

差值是一个正数,其数值等于两值之差的绝对值。

答案

class Solution {int res;TreeNode pre;public int getMinimumDifference(TreeNode root) {res = Integer.MAX_VALUE;pre = null;deal(root);return res;}void deal(TreeNode root){if(root==null){return;}deal(root.left);//左中右if(pre!=null){res = Math.min(res,root.val-pre.val);}pre = root;deal(root.right);}
}








230. 二叉搜索树中第K小的元素

题目

给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。

答案

class Solution {int count;int res;public int kthSmallest(TreeNode root, int k) {count = 0;res = 0;deal(root,k);return res;}void deal(TreeNode root,int k){if(root==null){return;}deal(root.left,k);//左根右count++;if(count==k){res = root.val;return;}deal(root.right,k);}
}








98. 验证二叉搜索树

题目

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

  • 节点的左

    子树

    只包含

    小于

    当前节点的数。

  • 节点的右子树只包含 大于 当前节点的数。

  • 所有左子树和右子树自身必须也是二叉搜索树。

答案

class Solution {public boolean isValidBST(TreeNode root) {return deal(root,Long.MIN_VALUE,Long.MAX_VALUE);//用long防止溢出}boolean deal(TreeNode root,long min,long max){if(root==null){return true;}if(root.val<=min || root.val>=max){//=return false;}boolean left = deal(root.left,min,root.val);boolean right = deal(root.right,root.val,max);return left && right;}
}class Solution {TreeNode pre;boolean flag;public boolean isValidBST(TreeNode root) {flag = true;deal(root);return flag;}void deal(TreeNode root){if(root==null){return;}deal(root.left);//左根右if(pre!=null && root.val<=pre.val){flag = false;return;}pre = root;//注意deal(root.right);}
}








200. 岛屿数量

题目

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。

示例 1:

输入:grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]
]
输出:1

示例 2:

输入:grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]
]
输出:3

答案

class Solution {int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};int m,n;public int numIslands(char[][] grid) {m = grid.length;n = grid[0].length;int res = 0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]=='1'){res++;deal(grid,i,j);//防止重复计算}}}return res;}void deal(char[][] grid,int i,int j){if(i<0 || i>=m || j<0 || j>=n || grid[i][j]=='0'){return;}grid[i][j] = '0';for(int[] dir : dirs){deal(grid,i+dir[0],j+dir[1]);}}
}








130. 被围绕的区域

题目

给你一个 m x n 的矩阵 board ,由若干字符 'X''O' ,找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O''X' 填充。

输入:board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出:[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释:被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。

示例 2:

输入:board = [["X"]]
输出:[["X"]]

答案

class Solution {int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};int m,n;public void solve(char[][] board) {m = board.length;n = board[0].length;for(int i=0;i<m;i++){deal(board,i,0);deal(board,i,n-1);}for(int j=0;j<n;j++){deal(board,0,j);deal(board,m-1,j);}for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(board[i][j]=='A'){board[i][j] = 'O';}else if(board[i][j]=='O'){board[i][j] = 'X';}}}}void deal(char[][] board,int i,int j){if(i<0 || i>=m || j<0 || j>=n || board[i][j]!='O'){return;}board[i][j] = 'A';for(int[] dir : dirs){deal(board,i+dir[0],j+dir[1]);}}
}








133. 克隆图

题目

给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。

图中的每个节点都包含它的值 valint) 和其邻居的列表(list[Node])。

class Node {public int val;public List<Node> neighbors;
}

答案

class Solution {Map<Node,Node> map = new HashMap();public Node cloneGraph(Node node) {if(node==null){return null;}if(map.containsKey(node)){return map.get(node);}Node newNode = new Node(node.val,new ArrayList());map.put(node,newNode);for(Node curr : node.neighbors){newNode.neighbors.add(cloneGraph(curr));}return newNode;}
}








207. 课程表

题目

你这个学期必须选修 numCourses 门课程,记为 0numCourses - 1

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai必须 先学习课程 bi

  • 例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1

请你判断是否可能完成所有课程的学习?如果可以,返回 true ;否则,返回 false

答案

class Solution {List<List<Integer>> list;int[] visited;boolean flag = true;public boolean canFinish(int numCourses, int[][] prerequisites) {list = new ArrayList();for(int i=0;i<numCourses;i++){list.add(new ArrayList());}visited = new int[numCourses];for(int[] info : prerequisites){list.get(info[1]).add(info[0]);}for(int i=0;i<numCourses && flag;i++){if(visited[i]==0){deal(i);}}return flag;}void deal(int i){visited[i] = 1;for(int num : list.get(i)){if(visited[num]==0){deal(num);if(!flag){return;}}else if(visited[num]==1){flag = false;return;}}visited[i] = 2;}
}








210. 课程表 II

题目

现在你总共有 numCourses 门课需要选,记为 0numCourses - 1。给你一个数组 prerequisites ,其中 prerequisites[i] = [ai, bi] ,表示在选修课程 ai必须 先选修 bi

  • 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示:[0,1]

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序,你只要返回 任意一种 就可以了。如果不可能完成所有课程,返回 一个空数组

答案

class Solution {List<List<Integer>> list;int[] visit;boolean flag = true;int res[];int index;public int[] findOrder(int numCourses, int[][] prerequisites) {list = new ArrayList();for(int i=0;i<numCourses;i++){list.add(new ArrayList());}visit = new int[numCourses];res = new int[numCourses];index = numCourses - 1;for(int[] info : prerequisites){list.get(info[1]).add(info[0]);}for(int i=0;i<numCourses && flag;i++){if(visit[i]==0){deal(i);}}if(!flag){return new int[0];}return res;}void deal(int i){visit[i] = 1;for(int num : list.get(i)){if(visit[num]==0){deal(num);if(!flag){return;}}else if(visit[num]==1){flag = false;return;}}visit[i] = 2;res[index--] = i;}
}








这篇关于java算法题每日多道九的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/849560

相关文章

Spring Security常见问题及解决方案

《SpringSecurity常见问题及解决方案》SpringSecurity是Spring生态的安全框架,提供认证、授权及攻击防护,支持JWT、OAuth2集成,适用于保护Spring应用,需配置... 目录Spring Security 简介Spring Security 核心概念1. ​Securit

SpringBoot+EasyPOI轻松实现Excel和Word导出PDF

《SpringBoot+EasyPOI轻松实现Excel和Word导出PDF》在企业级开发中,将Excel和Word文档导出为PDF是常见需求,本文将结合​​EasyPOI和​​Aspose系列工具实... 目录一、环境准备与依赖配置1.1 方案选型1.2 依赖配置(商业库方案)二、Excel 导出 PDF

SpringBoot改造MCP服务器的详细说明(StreamableHTTP 类型)

《SpringBoot改造MCP服务器的详细说明(StreamableHTTP类型)》本文介绍了SpringBoot如何实现MCPStreamableHTTP服务器,并且使用CherryStudio... 目录SpringBoot改造MCP服务器(StreamableHTTP)1 项目说明2 使用说明2.1

spring中的@MapperScan注解属性解析

《spring中的@MapperScan注解属性解析》@MapperScan是Spring集成MyBatis时自动扫描Mapper接口的注解,简化配置并支持多数据源,通过属性控制扫描路径和过滤条件,利... 目录一、核心功能与作用二、注解属性解析三、底层实现原理四、使用场景与最佳实践五、注意事项与常见问题六

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

Java中Arrays类和Collections类常用方法示例详解

《Java中Arrays类和Collections类常用方法示例详解》本文总结了Java中Arrays和Collections类的常用方法,涵盖数组填充、排序、搜索、复制、列表转换等操作,帮助开发者高... 目录Arrays.fill()相关用法Arrays.toString()Arrays.sort()A

Spring Boot Maven 插件如何构建可执行 JAR 的核心配置

《SpringBootMaven插件如何构建可执行JAR的核心配置》SpringBoot核心Maven插件,用于生成可执行JAR/WAR,内置服务器简化部署,支持热部署、多环境配置及依赖管理... 目录前言一、插件的核心功能与目标1.1 插件的定位1.2 插件的 Goals(目标)1.3 插件定位1.4 核

如何使用Lombok进行spring 注入

《如何使用Lombok进行spring注入》本文介绍如何用Lombok简化Spring注入,推荐优先使用setter注入,通过注解自动生成getter/setter及构造器,减少冗余代码,提升开发效... Lombok为了开发环境简化代码,好处不用多说。spring 注入方式为2种,构造器注入和setter

使用zip4j实现Java中的ZIP文件加密压缩的操作方法

《使用zip4j实现Java中的ZIP文件加密压缩的操作方法》本文介绍如何通过Maven集成zip4j1.3.2库创建带密码保护的ZIP文件,涵盖依赖配置、代码示例及加密原理,确保数据安全性,感兴趣的... 目录1. zip4j库介绍和版本1.1 zip4j库概述1.2 zip4j的版本演变1.3 zip4

Java堆转储文件之1.6G大文件处理完整指南

《Java堆转储文件之1.6G大文件处理完整指南》堆转储文件是优化、分析内存消耗的重要工具,:本文主要介绍Java堆转储文件之1.6G大文件处理的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言文件为什么这么大?如何处理这个文件?分析文件内容(推荐)删除文件(如果不需要)查看错误来源如何避