剑指Offer之Java算法习题精讲二叉搜索树与数组查找
题目一
解法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int ans;
int pre;
public int minDiffInBST(TreeNode root) {
ans = Integer.MAX_VALUE;
pre = -1;
method(root);
return ans;
}
public void method(TreeNode root){
if(root==null) return;
method(root.left);
if(pre==-1){
pre = root.val;
}else{
ans = Math.min(ans,root.val-pre);
pre = root.val;
}
method(root.right);
}
}
题目二
解法
class Solution {
public int dominantIndex(int[] nums) {
int f = Integer.MIN_VALUE;
int fi = 0;
int s = Integer.MIN_VALUE;
int si = 0;
for(int i = 0; i<nums.length;i++){
if(nums[i]>f){
s = f;
f = nums[i];
fi = i;
}else if(nums[i]>s){
s = nums[i];
}
}
if(nums.length==1) return 0;
if(2*s<=f) return fi;
return -1;
}
}
题目三
解法
class Solution {
public int repeatedNTimes(int[] nums) {
int n = nums.length/2;
HashMap<Integer,Integer> map =new HashMap<Integer,Integer>();
for(int key : nums){
if(map.containsKey(key)){
map.put(key,map.get(key)+1);
if(map.get(key)==n){
return key;
}
}else{
map.put(key,1);
}
}
return 0;
}
}
题目四
解法
class Solution {
public boolean uniqueOccurrences(int[] arr) {
int[] nums = new int[2000];
for(int i =0;i<arr.length;i++){
nums[arr[i]+1000]+=1;
}
HashSet<Integer> set =new HashSet<Integer>();
for(int i =0;i<nums.length;i++){
if(nums[i]==0) continue;
if(!set.add(nums[i])){
return false;
}else{
set.add(nums[i]);
}
}
return true;
}
}
到此这篇关于剑指Offer之Java算法习题精讲二叉搜索树与数组查找的文章就介绍到这了,更多相关Java 二叉搜索树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
java基础二叉搜索树图文详解
目录 概念 直接实践 准备工作:定义一个树节点的类,和二叉搜索树的类. 搜索二叉树的查找功能 搜索二叉树的插入操作 搜索二叉树删除节点的操作-难点 性能分析 总程序-模拟实现二叉搜索树 和java类集的关系 总结 概念 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:1.若它的左子树不为空,则左子树上所有节点的值都小于根结点的值.2.若它的右子树不为空,则右子树上所有节点的值都大于根结点的值.3.它的左右子树也分别为二叉搜索树 直接实践 准备工作:定义一个树节点的类,和二
-
利用java实现二叉搜索树
二叉搜索树的定义 它是一颗二叉树 任一节点的左子树上的所有节点的值一定小于该节点的值 任一节点的右子树上的所有节点的值一定大于该节点的值 特点: 二叉搜索树的中序遍历结果是有序的(升序)! 实现一颗二叉搜索树 实现二叉搜索树,将实现插入,删除,查找三个方面 二叉搜索树的节点是不可以进行修改的,如果修改,则可能会导致搜索树的错误 二叉搜索树的定义类 二叉搜索树的节点类 -- class Node 二叉搜索树的属性:要找到一颗二叉搜索树只需要知道这颗树的根节点. public class BST {
-
Java 求解如何把二叉搜索树转换为累加树
一.题目 给出二叉搜索树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和. 提醒一下,二叉搜索树满足下列约束条件: 节点的左子树仅包含键 小于 节点键的节点. 节点的右子树仅包含键 大于 节点键的节点. 左右子树也必须是二叉搜索树. 二.题解 观察示例图发现,树的遍历顺序为右,中,左的顺序,每个节点的值,是按照这个顺序累加的状态 由于是需要累加,所以需要pre指针记录当前遍历节点
-
Java二维数组查找功能代码实现
题目描述: 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. 题目分析: 根据二维数组的特点可知,二维数组相当于一个矩阵: 根据题意可知该数组是有序的,因此该矩阵元素相当于是从小到大排列的: 如果从左下角开始查找较方便,因为左下角的值向上是递减的,向右是递增的: 当从左下角开始比较时,如果target传入的数大于它则列数加一进行比较 ,如果小于它则行数减
-
Java基础之二叉搜索树的基本操作
一.二叉搜索树插入元素 /** * user:ypc: * date:2021-05-18; * time: 15:09; */ class Node { int val; Node left; Node right; Node(int val) { this.val = val; } } public void insert(int key) { Node node = new Node(key); if (this.root == null) { root = node; } Node cu
-
Java实现二叉搜索树的插入、删除功能
二叉树的结构 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() { } TreeNode(int val) { this.val = val; } } 中序遍历 中序遍历:从根节点开始遍历,遍历顺序是:左子树->当前节点->右子树,在中序遍历中,对每个节点来说: 只有当它的左子树都被遍历过了(或者没有左子树),它才会被遍历到.在遍历右子树之前,一定会先遍历当前节点. 中序遍历得到的第一个节点是没
-
剑指Offer之Java算法习题精讲二叉搜索树与数组查找
题目一 解法 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; *
-
剑指Offer之Java算法习题精讲链表与字符串及数组
题目一 解法 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Soluti
-
剑指Offer之Java算法习题精讲链表专题篇
题目一 解法 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solut
-
剑指Offer之Java算法习题精讲二叉树与斐波那契函数
题目一 解法 class Solution { public int fib(int n) { int[] arr = new int[31]; arr[0] = 0; arr[1] = 1; for(int i = 2;i<=n;i++){ arr[i] = arr[i-2]+arr[i-1]; } return arr[n]; } } 题目二 解法 /** * Definition for a binary tree node. * public class TreeNode { * in
-
剑指Offer之Java算法习题精讲二叉树与N叉树
题目一 解法 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; *
-
剑指Offer之Java算法习题精讲二叉树专题篇下
题目一 解法 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; *
-
剑指Offer之Java算法习题精讲二叉树专题篇上
来和二叉树玩耍吧~ 题目一 解法 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val
-
剑指Offer之Java算法习题精讲数组与字符和等差数列
题目一 解法 class Solution { public int[] relativeSortArray(int[] arr1, int[] arr2) { int[] arr = new int[1001]; int[] ans = new int[arr1.length]; int index = 0; for(int i =0;i<arr1.length;i++){ arr[arr1[i]]+=1; } for(int i = 0;i<arr2.length;i++){ while
-
剑指Offer之Java算法习题精讲排列与N叉树
题目一 解法 class Solution { LinkedList<List<Integer>> ans = new LinkedList<List<Integer>>(); public List<List<Integer>> permute(int[] nums) { LinkedList<Integer> list = new LinkedList<Integer>(); boolean[] bo =
-
剑指Offer之Java算法习题精讲二叉树专项解析
题目一 解法 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * t