logo头像

总有人间一两风，填我十万八千梦

Leetcode的JS实现——Easy篇（上）

算法 JS leetcode 算法 2017/03/31

由于要找实习，所以最近几周一直在刷 leetcode（打算先把 easy 刷完，大概一天 10 道左右）；而作为一个前端码农，也就只能用 JS 实现算法了，但是众所周知，JS 在算法实现方面是真的不如其他知名语言（java、python、c++），所以绝大多数题都没有 JS 的标准答案，这让我刷 leetcode 的过程变得异常艰难；为了方便和我一样用 JS 刷 leetcode 的小伙伴，打算写一篇纯干货（代码）的文章，对如何用 JS 实现 leetcode 算法题进行总结。（鉴于我水平有限和 JS 本身的局限性，有好多题目我虽然看到了，但是最终没有用 JS 实现，如果你知道某些题目的 JS 实现或有更优解法，请通过网站中的联系方式联系我，O(∩_∩)O谢谢）

介绍

leetcode 地址：https://leetcode.com/problemset/algorithms/，本文章不会贴出题目，可以点击标题链接查看原题目

排序方式：按照本难度中题目的 accepted 统计

JS代码实现

461-Hamming distance

方法一：利用 replace() 方法

1
2
3
4
5
6
7
8
/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function(x, y) {
    return (x^y).toString(2).replace(/0/g,"").length;
};

方法二：利用异或

1
2
3
4
5
6
7
8
9
10
/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function(x, y) {
    var xor = x ^ y, count = 0;
    for (var i=0;i<32;i++) count += (xor >> i) & 1;
    return count;
};

476-Number Complement

方法一：利用二进制

1
2
3
4
5
6
7
/**
 * @param {number} num
 * @return {number}
 */
var findComplement = function(num) {
    return num^(Math.pow(2,(num.toString(2).length))-1);
};

方法二：利用位运算中的移位

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number} num
 * @return {number}
 */
var findComplement = function(num) {
    var mask = num;
    mask |= mask >> 1;
    mask |= mask >> 2;
    mask |= mask >> 4;
    mask |= mask >> 8;
    mask |= mask >> 16;
    return num ^ mask;
};

500-Keyboard Row

暂无

412-Fizz Buzz

方法一：各种 if

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number} n
 * @return {string[]}
 */
var fizzBuzz = function(n) {
    var arr = [];
    for(var i=1;i<n+1;i++){
        if(i%15 == 0){
            arr[i-1] = "FizzBuzz"
        }else if(i%5 == 0){
            arr[i-1] = "Buzz"
        }else if(i%3 == 0){
            arr[i-1] = "Fizz"
        }else{
            arr[i-1] = "" + i
        }
    }
    return arr;
};

344-Reverse String

方法一：从后往前遍历

1
2
3
4
5
6
7
8
9
10
11
/**
 * @param {string} s
 * @return {string}
 */
var reverseString = function(s) {
    var str = "";
    for(var i=1,n=s.length;i<n+1;i++){
        str += s[n-i];
    }
    return str;
};

方法二：递归

1
2
3
4
5
6
7
8
9
10
11
/**
 * @param {string} s
 * @return {string}
 */
var reverseString = function(s) {
    var length = s.length;
    if (length <= 1) return s;
    var leftStr = s.substring(0, length / 2);
    var rightStr = s.substring(length / 2, length);
    return reverseString(rightStr) + reverseString(leftStr);
};

496-Next Greater Element I

暂无

463-Island Perimeter

方法一：每块陆地都加 4，遇到有相邻陆地时减 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[][]} grid
 * @return {number}
 */
var islandPerimeter = function(grid) {
    var result=0;
    for(var i=0,n=grid.length;i<n;i++){
        for(var j=0,m=grid[0].length;j<m;j++){
            if(grid[i][j] ==1){
                result +=4;
                if(i>0 && grid[i-1][j] == 1){result -=2}
                if(j>0 && grid[i][j-1] ==1 ){result -=2}
            }
        }
    }
    return result;
};

292-Nim Game

方法一：只要数字能被 4 整除就赢不了

1
2
3
4
5
6
7
/**
 * @param {number} n
 * @return {boolean}
 */
var canWinNim = function(n) {
    return !!(n%4)
};

485-Max Consecutive Ones

方法一：看到 0 时就将 max 置为 0，否则 max 加 1

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxConsecutiveOnes = function(nums) {
    var result = 0;
    var num = 0;
    
    for(var i = 0;i<nums.length;i++){
        result = Math.max(result,num =(nums[i]==0) ? 0: num+1);
    }
    return result;
};

136-Single Number

方法一：利用位运算中的异或（异或运算可交换位置，且相同数字异或结果为 0）

1
2
3
4
5
6
7
8
9
10
11
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    var result;
    for(var i=0,n=nums.length;i<n;i++){
        result ^= nums[i]
    }
    return result
};

448-Find All Numbers Disappeared in an Array

方法一：利用哈希表将看到的数字变为负数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    var n= nums.length;
    var result = [];
    for(var i=0;i<n;i++){
        var j = Math.abs(nums[i]) -1;
        nums[j] = -Math.abs(nums[j]);
    }
    
    for(var k=0; k<n;k++){
        if(nums[k]>0){
            result.push(k+1);
        }
    }
    return result; 
};

520-Detect Capital

方法一：巧用 indexOf

1
2
3
4
5
6
7
/**
 * @param {string} word
 * @return {boolean}
 */
var detectCapitalUse = function(word) {
    return !(word.indexOf(word.toUpperCase()) && word.indexOf(word.toLowerCase()) && word.indexOf(word.substring(0,1).toUpperCase() + word.substring(1).toLowerCase()))
};

方法二：正则

暂无

104-Maximum Depth of Binary Tree

方法一：递归，其实很容易发现规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    return root === null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

389-Find the Difference

方法一：依然是 replace()

1
2
3
4
5
6
7
8
9
10
11
/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function(s, t) {
    for(var i=0,n=s.length;i<n;i++){
        t = t.replace(s[i],"");
    }
    return t;
};

方法二：位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function(s, t) {
    var n = t.length,c = t.charCodeAt(n - 1);
	for (var i = 0; i < n - 1; i++) {
		c ^= s.charCodeAt(i);
		c ^= t.charCodeAt(i);
	}
	return String.fromCharCode(c);
};

371-Sum of Two Integers

方法一：位运算

1
2
3
4
5
6
7
8
/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var getSum = function(a, b) {
    return b==0? a:getSum(a^b, (a&b)<<1);
};

226-Invert Binary Tree

方法一：二叉树基本上都是递归，只不过这次规律很容易发现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if(!root){
        return null;
    }
    var left = root.left,
        right = root.right;
        
    root.left = invertTree(right);
    root.right = invertTree(left);
    return root;
};

492-Construct the Rectangle

方法一：越和正方形相似越好，所以需要先求根值确定大致范围

1
2
3
4
5
6
7
8
9
10
11
/**
 * @param {number} area
 * @return {number[]}
 */
var constructRectangle = function(area) {
    var w = Math.floor(Math.sqrt(area));
	while (area % w !== 0) {
	    w--;
	}
	return [area/w,w];
};

283-Move Zeroes

方法一：碰到 0 就先去掉再 push 进数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    for(var i=0,m=0,n=nums.length;i<n;i++){
        if(nums[m] === 0){
            nums.splice(m,1);
            nums.push(0);
        }else{
            m++;
        }
    }
};

方法二：类似于冒泡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    var j = 0;
    for(var i = 0; i < nums.length; i++) {
        if(nums[i] !== 0) {
            var temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
            j++;
        }
    }
};

方法三：用一个变量记录当前多少个元素不为 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    if (nums === null || nums.length === 0) return;        
    var insertPos = 0;
    for (var i=0;i<nums.length;i++) {
        if (nums[i] !== 0) nums[insertPos++] = nums[i];
    }        
    while (insertPos < nums.length) {
        nums[insertPos++] = 0;
    }
};

530-Minimum Absolute Difference in BST

暂无

506-Relative Ranks

暂无

167-Two Sum II - Input array is sorted

方法一：两个指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    
    if (numbers === null || numbers.length < 2) return null;
    var left = 0, right = numbers.length - 1;
    while (left < right) {
        var v = numbers[left] + numbers[right];
        if (v == target) {
            return[left+1,right+1];
        } else if (v > target) {
            right --;
        } else {
            left ++;
        }
    }
    return null;
};

方法二：二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    if(numbers.length<2) return null;
    for(var i=0; i<numbers.length-1; i++) {
        var start=i+1, end=numbers.length-1, gap=target-numbers[i];
        while(start <= end) {
            var m = Math.floor(start+(end-start)/2);
            if(numbers[m] == gap) return [i+1,m+1];
            else if(numbers[m] > gap) end=m-1;
            else start=m+1;
        }
    }
};

455-Assign Cookies

方法一：Just assign the cookies starting from the child with less greediness to maximize the number of happy children .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function(g, s) {
    g.sort(function(a,b){return a-b});
    s.sort(function(a,b){return a-b});
    var i=0,m=g.length,n=s.length;
    for(var j=0;j<n&&i<m;j++){
        if(g[i]<=s[j]){
            i++;
        }
    }
    return i;
};

453-Minimum Moves to Equal Array Elements

方法一：每次让 n-1 个元素 +1，其实可以理解为每次让 1 个元素减 1，知道都等于数组中的最小元素为止

1
2
3
4
5
6
7
8
9
10
11
/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves = function(nums) {
    var min = Math.min.apply(null, nums),n=nums.length,result=0;
    for(i=0;i<n;i++){
        result += nums[i] -min;
    }
    return result;
};

383-Ransom Note

方法一：用一个数组作为字典表（其实应该是哈希表，在 JS 中就是数组）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    var n = ransomNote.length;
    for(var i=0;i<n;i++){
        var s = ransomNote[i];
        if(magazine.indexOf(s) == -1){
            return false;
        }else{
            magazine = magazine.replace(s,"");
        }
    }
    return !!(magazine.length + 1);
};

404-Sum of Left Leaves

方法一：将叶子节点区分出来就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumOfLeftLeaves = function(root) {
    if(root === null) {return 0;}
    var ans = 0;
    if(root.left !== null) {
        if(root.left.left === null && root.left.right === null) {
            ans += root.left.val;
        }else {
            ans += sumOfLeftLeaves(root.left);
        }
    }
    ans += sumOfLeftLeaves(root.right);
    return ans;
};

349-Intersection of Two Arrays

方法一：两个指针进行遍历（哈希表，复杂度为 O(n)）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
        nums1.sort(function(a,b){return a-b});
        nums2.sort(function(a,b){return a-b});
        var i = 0,
            j = 0,
            result = [];
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                if(result.indexOf(nums1[i]) == -1){
                    result.push(nums1[i]);
                }
                i++;
                j++;
            }
        }
        return result.sort(function(a,b){return a-b});
};

方法二：二分查找（复杂度为 O(nlgn)）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    var result = [];
    nums2.sort(function(a,b){return a-b;});
    for (var i=0;i<nums1.length;i++) {
        if (binarySearch(nums2, nums1[i]) && result.indexOf(nums1[i]) == -1) {
            result.push(nums1[i]);
        }
    }
    return result;
};

var binarySearch = function(nums,target) {
    var low = 0,high = nums.length - 1;
    while (low <= high) {
        var mid = Math.floor(low + (high - low) / 2);
        if (nums[mid] == target) {
            return true;
        }
        if (nums[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return false;
};

122-Best Time to Buy and Sell Stock II

方法一：只要第二天价格比第一天价格高，就卖掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    var result=0,n=prices.length;
    for(var i=0;i<n-1;i++){
        if(prices[i]<prices[i+1]){
            result += prices[i+1] - prices[i];
            
        }
    }
    return result;
};

387-First Unique Character in a String

方法一：用一个数组记录字符出现的位置及次数（哈希表）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
    var freq = new Array(26);
    var a = 'a'.charCodeAt();
    for(var i = 0; i < s.length; i ++) {
        if (freq [s[i].charCodeAt() - a] === undefined) {
            freq [s[i].charCodeAt() - a] = 1;
        } else {
            freq [s[i].charCodeAt() - a]++;
        }
    }
    for(var k = 0; k < s.length; k ++){
        if(freq [s[k].charCodeAt() - a] == 1){
            return k;
        }
    }
    return -1;
};

171-Excel Sheet Column Number

方法一：很容易发现规律，类似二进制转换成 10 进制

1
2
3
4
5
6
7
8
9
10
11
/**
 * @param {string} s
 * @return {number}
 */
var titleToNumber = function(s) {
    var result = 0;
    for(var i=0,n=s.length;i<n;i++){
        result += Math.pow(26,n-i-1)*(s[i].charCodeAt() - 64);
    }
    return result;
};

504-Base 7

方法一：递归取余，很经典的一道题和解法，用的比较多

1
2
3
4
5
6
7
/**
 * @param {number} num
 * @return {string}
 */
var convertToBase7 = function(num) {
    return num>=0 ? "" + (num>=7 ? convertToBase7(Math.floor(num/7)) + "" + num%7 : num) : '-'+convertToBase7(-num);
};

237-Delete Node in a Linked List

方法一：很智障的一道题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
    node.val = node.next.val;
    node.next = node.next.next;
};

100-Same Tree

方法一：递归，相等的依据除了值相等之外还有不能为 null

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if (p === null && q === null){
        return true;
    }
    return p !== null && q !== null && p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

169-Maiority Element

方法一：每找出两个不同的 element，就成对删除即 count–，最终剩下的一定就是所求的（O(n)）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    var major=nums[0], count = 1;
        for(var i=1,n=nums.length; i<n;i++){
            if(count===0){
                count++;
                major=nums[i];
            }else if(major==nums[i]){
                count++;
            }else count--;
        }
    return major;
};

方法二：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    var counts = [],n = nums.length;
    for (var i = 0; i < n; i++){
        if(counts[nums[i]] === undefined){
            counts[nums[i]] = 1;
        }else{
            if(counts[nums[i]] + 1> Math.floor(n / 2)) { return nums[i];}
            counts[nums[i]]++;
        }
    }
    return nums[0];
};

方法三：Since the majority element appears more than n / 2 times, the n / 2-th element in the sorted nums must be the majority element.

1
2
3
4
5
6
7
8
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    nums.sort();
    return nums[Math.floor(nums.length/2)];
};

方法四：随机挑选一个元素，然后看它是否是多数元素

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    var n = nums.length;
    while (true) {
        var idx = Math.floor(Math.random()*n),candidate = nums[idx],counts = 0; 
        for (var i = 0; i < n; i++)
            if (nums[i] == candidate) {counts++;}
        if (counts > n / 2) return candidate;
    }
};

方法五：摩尔投票算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    var major, counts = 0, n = nums.length;
    for (var i = 0; i < n; i++) {
        if (!counts) {
            major = nums[i];
            counts = 1;
        }
        else counts += (nums[i] == major) ? 1 : -1;
    }
    return major;
};

方法六：位运算，The key lies in how to count the number of 1‘s on a specific bit. Specifically, you need a mask with a 1 on the i-the bit and 0 otherwise to get the i-th bit of each element in nums

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    var major = 0, n = nums.length;
    for (var i = 0, mask = 1; i < 32; i++, mask <<= 1) {
        var bitCounts = 0;
        for (var j = 0; j < n; j++) {
            if (nums[j] & mask) bitCounts++;
            if (bitCounts > n / 2) {
                major |= mask;
                break;
            }
        }
    } 
    return major;
};

242-Valid Anagram

方法一：用一个数组作为桶，s 中的字符用来加 1，t 中的字符用来减 1；如果最后桶中没有元素就返回 true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    if(s===""&&t===""){return true;}
    var alphabet = new Array(26);
        for(var m=0;m<alphabet.length;m++){
            alphabet[m] =0;
        }
        for (var i = 0; i < s.length; i++) {
            alphabet[s[i].charCodeAt() - 97]++;
        }
        for (var j = 0; j < t.length; j++) {
            alphabet[t[j].charCodeAt() - 97]--;
        }
        for (var k=0;k<alphabet.length;k++) {
            if (alphabet[k]!== 0) {
                return false;
            }
        }
    return true;
};

409-Longest Palindrome

方法一：将数组中的元素分为偶数和奇数两种情况，因为回文字符串的字符个数有这两种情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function(s) {
    var even = 0,odd = 0,arr = [];
    for(var i=0,n=s.length;i<n;i++){
        var c = s[i].charCodeAt() - 65;
        if(arr[c] === undefined){
            arr[c] = 1;
        }else{
            arr[c]++;
        }
        if(arr[c]%2 === 0){
            even += 2;
            odd--;
        }else{
            odd++;
        }
    }
    return even + (odd===0? 0 :1); 
};

541-Reverse String II

暂无

401-Binary Watch

方法一：从结果出发，满足条件时 push 进数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number} num
 * @return {string[]}
 */
var readBinaryWatch = function(num) {
    var result = [];
    for(var h=0;h<12;h++){
        for(var m=0;m<60;m++){
            if((h.toString(2) + m.toString(2)).replace(/0/g,"").length == num){
                m = m>9 ? m : "0" + m;
                item = h + ":" + m;
                result.push(item);
            }
        }
    }
    return result;
};

217-Contains Duplicate

方法一：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    if(nums.length===0){return false;}
    var opt = {};
    for(var i=0,n=nums.length;i<n;i++){
        if(opt[nums[i]]){
            return true;
        }else{
            opt[nums[i]] = 1;
        }
    }
    return false;
};

方法二：先将数组排序，然后只需要比较相邻元素

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    nums.sort();
    for(var ind = 1; ind < nums.length; ind++) {
        if(nums[ind] == nums[ind - 1]) {
            return true;
        }
    }
    return false;
};

13-Roman to Integer

方法一：知道罗马数字的规则之后就好写了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    var opt = {'M': 1000,'D': 500 ,'C': 100,'L': 50,'X': 10,'V': 5,'I': 1},
        z = 0,
        n=s.length;
    for(var i=0;i<n-1;i++){
        if(opt[s[i]] < opt[s[i+1]]){
            z -= opt[s[i]];
        }else{
            z += opt[s[i]];
        }
    }
    return z + opt[s[n-1]];
};

206-Reverse Linked List

方法一：反转的条件就是 head.next.next = head 和 head.next = null

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if (!head || !(head.next)) {return head;}
    var node = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return node; 
};

350-Intersection of Two Arrays II

方法一：先对 nums1 遍历，生成哈希表，然后对 nums2 遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    var arr = [],result=[];
    for(var i=0,n=nums1.length;i<n;i++){
        var numi = arr[nums1[i]];
        if(numi){
            arr[nums1[i]]++;
        }else{
            arr[nums1[i]] = 1;
        }
    }
    for(var j=0,m=nums2.length;j<m;j++){
        var numj = arr[nums2[j]];
        if(numj){
            result.push(nums2[j]);
            arr[nums2[j]]--;
        }
    }
    return result;
};

方法二：先进行排序，然后用两个指针遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    nums1.sort(function(a,b){return a-b;});
    nums2.sort(function(a,b){return a-b;});
    var n1 = nums1.length, n2 = nums2.length,i1 = 0, i2 = 0,res = [];
    while(i1 < n1 && i2 < n2){
        if(nums1[i1] == nums2[i2]) {
            res.push(nums1[i1]);
            i1++;
            i2++;
        }
        else if(nums1[i1] > nums2[i2]){
            i2++;
        }
        else{
            i1++;
        }
    }
    return res;
};

268-Missing Number

方法一：因为有且只有一个数字丢失，所以可以先排序再遍历，根据索引值和数值的关系判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    var sort = nums.sort(function(a,b){
        return a-b;
    }),n=nums.length;
    for(var i=0;i<n;i++){
        if(sort[i] != i){
            return i;
        }
    }
    return n;
};

方法二：位运算，利用异或

1
2
3
4
5
6
7
8
9
10
11
/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    var xor = 0, i = 0;
	for (i = 0; i < nums.length; i++) {
		xor = xor ^ i ^ nums[i];
	}
	return xor ^ i;
};

方法三：因为数值范围确定，所以可以先求和，再减去数组中的元素，剩下的数字就是丢失数字

1
2
3
4
5
6
7
8
9
10
11
/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    var len = nums.length,sum = (0+len)*(len+1)/2;
    for(var i=0; i<len; i++){
        sum-=nums[i];
    }
    return sum;
};

方法四：二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    nums.sort(function(a,b){return a-b;});
    var left = 0, right = nums.length, mid= Math.floor((left + right)/2);
    while(left<right){
        mid = Math.floor((left + right)/2);
        if(nums[mid]>mid) {right = mid;}
        else left = mid+1;
    }
    return left;
};

447-Number of Boomerangs

暂无

543-Diameter of Binary Tree

暂无

415-Add Strings

方法一：遍历，用一个变量记录当前位进位情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addStrings = function(num1, num2) {
    var carry=0,str = '';
    for(var i=num1.length-1,j=num2.length-1;i>=0||j>=0||carry==1;i--,j--){
        var n1 = num1[i] ? num1[i] - '0' : 0,
            n2 = num2[j] ? num2[j] - '0' : 0;
        var sum = (n1 + n2 + carry)%10;
            carry = Math.floor((n1 + n2 + carry)/10);
        str = sum + str;
    }
    return str;
};

108-Convert Sorted Array to Binary Search Tree

暂无

405-Convert a Number to Hexadecimal

暂无

赏
支付宝打赏 微信打赏

听说赞过就能年薪百万

转载声明：商业转载请联系作者获得授权,非商业转载请注明出处 © Merrier说
访问量:   |   访客数:
Copyright © 2018 | Powered by Hexo | Theme by Snippet | ICP 证： 京ICP备17022347号-1