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 Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控

Java中读取YAML文件配置信息常见问题及解决方法

《Java中读取YAML文件配置信息常见问题及解决方法》:本文主要介绍Java中读取YAML文件配置信息常见问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 目录1 使用Spring Boot的@ConfigurationProperties2. 使用@Valu

创建Java keystore文件的完整指南及详细步骤

《创建Javakeystore文件的完整指南及详细步骤》本文详解Java中keystore的创建与配置,涵盖私钥管理、自签名与CA证书生成、SSL/TLS应用,强调安全存储及验证机制,确保通信加密和... 目录1. 秘密键(私钥)的理解与管理私钥的定义与重要性私钥的管理策略私钥的生成与存储2. 证书的创建与

浅析Spring如何控制Bean的加载顺序

《浅析Spring如何控制Bean的加载顺序》在大多数情况下,我们不需要手动控制Bean的加载顺序,因为Spring的IoC容器足够智能,但在某些特殊场景下,这种隐式的依赖关系可能不存在,下面我们就来... 目录核心原则:依赖驱动加载手动控制 Bean 加载顺序的方法方法 1:使用@DependsOn(最直

SpringBoot中如何使用Assert进行断言校验

《SpringBoot中如何使用Assert进行断言校验》Java提供了内置的assert机制,而Spring框架也提供了更强大的Assert工具类来帮助开发者进行参数校验和状态检查,下... 目录前言一、Java 原生assert简介1.1 使用方式1.2 示例代码1.3 优缺点分析二、Spring Fr

java使用protobuf-maven-plugin的插件编译proto文件详解

《java使用protobuf-maven-plugin的插件编译proto文件详解》:本文主要介绍java使用protobuf-maven-plugin的插件编译proto文件,具有很好的参考价... 目录protobuf文件作为数据传输和存储的协议主要介绍在Java使用maven编译proto文件的插件

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

Javaee多线程之进程和线程之间的区别和联系(最新整理)

《Javaee多线程之进程和线程之间的区别和联系(最新整理)》进程是资源分配单位,线程是调度执行单位,共享资源更高效,创建线程五种方式:继承Thread、Runnable接口、匿名类、lambda,r... 目录进程和线程进程线程进程和线程的区别创建线程的五种写法继承Thread,重写run实现Runnab

Java 方法重载Overload常见误区及注意事项

《Java方法重载Overload常见误区及注意事项》Java方法重载允许同一类中同名方法通过参数类型、数量、顺序差异实现功能扩展,提升代码灵活性,核心条件为参数列表不同,不涉及返回类型、访问修饰符... 目录Java 方法重载(Overload)详解一、方法重载的核心条件二、构成方法重载的具体情况三、不构

Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式

《Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式》本文详细介绍如何使用Java通过JDBC连接MySQL数据库,包括下载驱动、配置Eclipse环境、检测数据库连接等关键步骤,... 目录一、下载驱动包二、放jar包三、检测数据库连接JavaJava 如何使用 JDBC 连接 mys