Ahri-珊

这篇博客将分享Leetcode算法题261，371，383。

LeetCode

268. Missing Number

题目要求：

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

For example, Given nums = [0, 1, 3] return 2.

心路历程

最开始真的没懂这个题的意思，以为是找中间不是连着的数。正确题意：给一个数组包含n个元素，这个数组应为[0,1,2…,n],现在缺了一个元素，数组元素个数只有n-1了，找出这个数。

方法1：

1.把数组元素值累加值为sum

2.没丢失前和judge应为0+1+2+…+n

3.返回judge-sum

(这个方法太简单 不写了)

方法2:

由于a^a=0，a^0=a,所以我们让数组元素跟1，2，3…n异或，异或结果就是丢失的元素

我的代码

var missingNumber = function(nums) {
    var res = 0;
    for(let i=1;i<=nums.length;i++)
        res = res^nums[i-1]^i;
    return res;
};

371. Sum of Two Integers

题目要求：

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example: Given a = 1 and b = 2, return 3.

心路历程

1.不允许使用+，-，所以使用位运算符

2.自己算一下就知道a+b = a^b + 2*(a&b)了

3.这时候a^b成了新的a，2*(a&b)成了新的b，如果b=0的话，我们就不用再加了

我的代码

 var getSum = function(a, b) {
    if(b==0)
        return a;
    var x = a^b;
    var c = 2*(a&b);
    return getSum(x,c);
};

383. Ransom Note

题目要求：

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note: You may assume that both strings contain only lowercase letters.

canConstruct(“a”, “b”) -> false canConstruct(“aa”, “ab”) -> false canConstruct(“aa”, “aab”) -> true

心路历程

1.遍历magazine字符串，将magazine字符串中每个字母和对应的个数存到hash对象中。

2.遍历ransomNote字符串，对照hash对象查找ransomNote中的字母是否存在于magazine中并且字母在ransomNote出现的次数小于在magazine中出现的次数

3.满足2中的要求返回true，否则返回false

我的代码

var canConstruct = function(ransomNote, magazine) {
   var hash = {};
    for(let i=0;i<magazine.length;i++){
        if(!hash[magazine[i]])
            hash[magazine[i]] = 1;
        else
            hash[magazine[i]]++;
    }
    for(let i=0;i<ransomNote.length;i++){
        if(hash[ransomNote[i]]&&hash[ransomNote[i]]>0)
            hash[ransomNote[i]]--;
        else
            return false;
    }
    return true;
};

End