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. 克隆图

题目

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

图中的每个节点都包含它的值 val（int）和其邻居的列表（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 门课程，记为 0 到 numCourses - 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 门课需要选，记为 0 到 numCourses - 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;}
}