Ahri-珊
day31将分享LeetCode算法题367,349,350。
LeetCode
今天的三道题涉及到二分查找、哈希表。
367. Valid Perfect Square
判断这个数是不是某个数的平方
心路历程
1.判断这个数是不是某个数的平方就要看能不能找到他的平方根
2.使用二分查找减少查询时间
代码:
var isPerfectSquare = function(num) {
if(num == 0)
return false;
if(num == 1)
return true;
return isSqrt(num,0,num);
};
//二分查找平方根
var isSqrt = function(num,low,high){
var middle = Math.floor((low+high)/2);
if(middle*middle < num && (middle+1)*(middle+1) > num)
return false;
if(middle*middle < num)
{
low = middle;
return isSqrt(num,low,high);
}
if(middle*middle > num)
{
high = middle;
return isSqrt(num,low,high);
}
if(middle*middle == num)
return true;
};
349. Intersection of Two Arrays
寻找两个数组交集(重复数只出现一次)
心路历程
1.使用哈希表记录第一个数组出现的值
2.遍历数组2,将nums1与nums2的交集放入res
代码:
var intersection = function(nums1, nums2) {
var hash = {};
var res = []; // 存放交集
for(let i = 0;i < nums1.length;i++)
{
if(!hash[nums1[i]])
hash[nums1[i]] = 1;
}
for(let i = 0;i < nums2.length;i++)
{
if(hash[nums2[i]]==1)
{
res.push(nums2[i]);
hash[nums2[i]] = 2;
}
}
return res;
};
350. Intersection of Two Arrays II
寻找两个数组的交集(包括重复的数)
心路历程
1.使用哈希表记录第一个数组的值以及每个值的出现次数
2.遍历数组2,将nums1与nums2的交集放入res
代码:
var intersect = function(nums1, nums2) {
var hash = {};
var res = [];
// 记录nums1出现的数以及出现的次数
for(let i = 0;i < nums1.length;i++)
{
if(!hash[nums1[i]])
hash[nums1[i]] = 1;
else
hash[nums1[i]]++;
}
// 将nums1与nums2的交集放入res
for(let i = 0;i < nums2.length;i++)
{
if(hash[nums2[i]])
{
res.push(nums2[i]);
hash[nums2[i]]--;
}
}
return res;
};
Comments