剑指Offer之Java算法习题精讲二叉搜索树与数组查找
时间：2023-02-26 08:35:06 | 栏目：JAVA代码 | 点击：次
题目一
数组题——查找数组中交集
根据给定的两个数组按照指定条件查找它们的交集并返回
具体题目如下
解法
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
int[] a = new int[1000];
HashSet<Integer> set = new HashSet<Integer>();
for(int i = 0;i<nums1.length;i++){
if(a[nums1[i]]==0){
a[nums1[i]]=1;
}
}
for(int i = 0;i<nums2.length;i++){
if(a[nums2[i]]!=0){
set.add(nums2[i]);
}
}
int[] w = new int[set.size()];
int p = 0;
Iterator<Integer> iterator = set.iterator();
while (iterator.hasNext()){
w[p] = iterator.next();
p++;
}
return w;
}
}
题目二
数组题——查找数组中交集
根据给定的两个数组按照指定条件查找它们的交集并返回
具体题目如下
解法
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
int[] a = new int[1001];
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i = 0;i<nums1.length;i++){
a[nums1[i]]+=1;
}
for(int i = 0;i<nums2.length;i++){
if(a[nums2[i]]>0){
list.add(nums2[i]);
a[nums2[i]]--;
}
}
int[] w = new int[list.size()];
for(int j = 0;j<w.length;j++){
w[j] = list.get(j);
}
return w;
}
}
题目三
概率题——猜数字
根据给定的猜数字规则编写函数比较猜数大小
具体题目如下
解法
/**
* Forward declaration of guess API.
* @param num your guess
* @return -1 if num is lower than the guess number
* 1 if num is higher than the guess number
* otherwise return 0
* int guess(int num);
*/
public class Solution extends GuessGame {
public int guessNumber(int n) {
int left = 1;
int right = n;
while(left<=right){
int mid = left+(right-left)/2;
if(guess(mid)==-1){
right = mid-1;
}
if(guess(mid)==1){
left = mid+1;
}
if(guess(mid)==0){
return mid;
}
}
return 0;
}
}