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;
};

END