剑指Offer之Java算法习题精讲二叉搜索树与数组查找

剑指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;

}

eAehoPIwsZ 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

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 map =new HashMap();

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

nums[arr[i]+1000]+=1;

}

HashSet set =new HashSet();

for(int i =0;i

if(nums[i]==0) continue;

if(!set.add(nums[i])){

return false;

}else{

set.add(nums[i]);

}

}

return true;

}

}

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 map =new HashMap();

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

nums[arr[i]+1000]+=1;

}

HashSet set =new HashSet();

for(int i =0;i

if(nums[i]==0) continue;

if(!set.add(nums[i])){

return false;

}else{

set.add(nums[i]);

}

}

return true;

}

}

nums[arr[i]+1000]+=1;

}

HashSet set =new HashSet();

for(int i =0;i

if(nums[i]==0) continue;

if(!set.add(nums[i])){

return false;

}else{

set.add(nums[i]);

}

}

return true;

}

}

if(nums[i]==0) continue;

if(!set.add(nums[i])){

return false;

}else{

set.add(nums[i]);

}

}

return true;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。