Ahri-珊

day23将分享LeetCode算法题270，283，290。

LeetCode

今天的三道题涉及到二分查找、哈希表、游标。

278. First Bad Version

有一个版本坏了后面的版本就都是坏的，找出第一个坏版本

心路历程

1.本题要求不能调用太多次API，所以采用二分查找

2.如果当前检验的版本是坏的，那后面的都是坏的，不用查了

3.如果当前检验的版本是坏的，并且它是第一个或者它前面一个版本没坏，那我们找的就是它了

4.如果当前版本是好的，前面的都是好的，不用管了~

代码：

var solution = function(isBadVersion) {
    return function(n) {
        var low = 1;
        var high = n+1;
        var middle = Math.floor((low+high)/2);
        while(low<high)
            {
                if(isBadVersion(middle))
                    {
                         high = middle;
                            if(!isBadVersion(middle-1)||middle==1)
                                return middle;
                    }
                else
                    {
                        low = middle;
                    }
                middle = Math.floor((low+high)/2);
            }
        return n;
    }
};

283. Move Zeroes

把数组中的零都甩到最后去

心路历程

1.初始化游标cursor=0，遍历数组

2.如果游标指向的值为0，当前数组元素不为0，交换游标值和当前数组元素值

3.如果游标值不为零，游标后移

代码：

var moveZeroes = function(nums) {
    var cursor = 0;
    for(let i=1;i<nums.length;i++)
        {
            if(nums[cursor]==0&&nums[i]!=0)
                {
                    nums[cursor] = nums[i];
                    nums[i] = 0;
                }
            if(nums[cursor]!=0)
                cursor++;
        }
};

290. Word Pattern

懒得翻译系列

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:

pattern = “abba”, str = “dog cat cat dog” should return true.

pattern = “abba”, str = “dog cat cat fish” should return false.

pattern = “aaaa”, str = “dog cat cat dog” should return false.

pattern = “abba”, str = “dog dog dog dog” should return false.

心路历程

1.如果pattern字母数与str单词数不相等，return false

2.建立两张哈希表分别对应pattern对应字母：str对应单词和str对应单词：pattern对应字母

3.遍历字符串，如果哈希表不是第一被初始化并且键名对应的键值与当前遍历字母或单词不同，return false

4.遍历结束都符合return true

代码：

var wordPattern = function(pattern, str) {
    var arrS = str.split(' ');
    if(pattern.length!=arrS.length)
        return false;
    var hashP = {};
    var hashS = {};
    for(let i=0;i<pattern.length;i++)
        {
            if(!hashP[pattern[i]])
                hashP[pattern[i]] = arrS[i];
            else
                {
                    if(hashP[pattern[i]]!=arrS[i])
                        return false;
                }
            if(!hashS[arrS[i]])
                hashS[arrS[i]] = pattern[i];
            else
                {
                    if(hashS[arrS[i]]!=pattern[i])
                        return false;
                }
        }
    return true;
};

END