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
Comments