50. Pow(x, n)

原题：50. Pow(x, n)

这道题用的是分治的思路。js实现可能会出现由于精度原因无法通过本地的单元测试，但是leetcode上面提交是能AC的。

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var myPow = function (x, n) {
  switch (n) {
    case 0:
      return 1;
    case 1:
      return x;
    case -1:
      return 1 / x;
    default:
      break;
  }

  const y = myPow(x, ~~(n / 2));
  return y * y * (n % 2 === 0 ? 1 : n > 0 ? x : 1 / x);
};

Test Cases:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
test("test1", () => {//本地精度问题无法通过单元测试
  expect(myPow(2.1, 3)).toEqual(9.261);
});

test("test2", () => {
  expect(myPow(2.0, -2)).toEqual(0.25);
});

test("test3", () => {
  expect(myPow(2.0, 1)).toEqual(2.0);
});

test("test4", () => {
  expect(myPow(2.0, -1)).toEqual(0.5);
});

test("test5", () => {
  expect(myPow(2.0, 0)).toEqual(1.0);
});

test("test6", () => {//本地精度问题无法通过单元测试
  expect(myPow(34.00515, -3)).toEqual(0.00003);
});

展开全文 >>

235. Lowest Common Ancestor of a Binary Search Tree

235. Lowest Common Ancestor of a Binary Search Tree

原题：235. Lowest Common Ancestor of a Binary Search Tree

时间复杂度：O(n)

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Runtime: 168 ms, faster than 5.31% of JavaScript online submissions for Lowest Common Ancestor of a Binary Search Tree.
// Memory Usage: 43.9 MB, less than 20.00% of JavaScript online submissions for Lowest Common Ancestor of a Binary Search Tree.
var lowestCommonAncestor = function(root, p, q) {
    const helper = function(root, p, q) {
        if(q.val<root.val) {
            return helper(root.left, p, q);
        }else if(p.val>root.val) {
            return helper(root.right, p, q);
        }else {
            return root;
        }
    };

    if(p.val>q.val) {
        [p, q] = [q, p];
    }

    return helper(root, p, q);
}

Test Cases

1
2
3
4
5
6
7
test("test1", ()=>{
    expect(lowestCommonAncestor(makeTree([6,2,8,0,4,7,9,null,null,3,5]), new TreeNode(2), new TreeNode(8)).val).toEqual(6);
})

test("test2", ()=>{
    expect(lowestCommonAncestor(makeTree([6,2,8,0,4,7,9,null,null,3,5]), new TreeNode(2), new TreeNode(4)).val).toEqual(2);
})

236. Lowest Common Ancestor of a Binary Tree

原题：236. Lowest Common Ancestor of a Binary Tree

时间复杂度：O(n)

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Runtime: 84 ms, faster than 22.42% of JavaScript online submissions for Lowest Common Ancestor of a Binary Tree.
// Memory Usage: 41.3 MB, less than 100.00% of JavaScript online submissions for Lowest Common Ancestor of a Binary Tree.
var lowestCommonAncestor = function(root, p, q) {
    const helper = function(root, p, q) {//find p or q
        if(!root || root.val==p.val || root.val==q.val) {
            return root;
        }
        const left = helper(root.left, p, q);
        const right = helper(root.right, p, q);
        
        return left ? (right ? root : left) : right;
    };

    return helper(root, p, q);
}

Test Cases

1
2
3
4
5
6
7
test("test1", ()=>{
    expect(lowestCommonAncestor(makeTree([3,5,1,6,2,0,8,null,null,7,4]), new TreeNode(5), new TreeNode(1)).val).toEqual(3);
})

test("test2", ()=>{
    expect(lowestCommonAncestor(makeTree([3,5,1,6,2,0,8,null,null,7,4]), new TreeNode(5), new TreeNode(4)).val).toEqual(5);
})

展开全文 >>

98. Validate Binary Search Tree

原题：98. Validate Binary Search Tree

解法一

时间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
// Runtime: 64 ms, faster than 73.11% of JavaScript online submissions for Validate Binary Search Tree.
// Memory Usage: 37.3 MB, less than 84.62% of JavaScript online submissions for Validate Binary Search Tree.
var isValidBST = function(root, min=-Infinity, max=Infinity) {
    if(!root) {
        return true;
    }

    if(root.val<=min || root.val>=max) {
        return false;
    }

    return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
};

解法二

时间复杂度：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
// Runtime: 68 ms, faster than 50.77% of JavaScript online submissions for Validate Binary Search Tree.
// Memory Usage: 37.1 MB, less than 100.00% of JavaScript online submissions for Validate Binary Search Tree.

//利用二叉搜索树先序遍历是升序的这个特性
var isValidBST = function(root) {
    let prev = -Infinity;
    const helper = function(node) {
        if(!node) {
            return true;
        }
        
        if(!helper(node.left)) {
            return false;
        }

        if(prev>=node.val) {
            return false;
        }
        prev = node.val;

        return helper(node.right);
    };

    return helper(root);
};

Test Cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
test("test1", ()=>{
    expect(isValidBST(makeTree([2,1,3]))).toEqual(true);
})

test("test2", ()=>{
    expect(isValidBST(makeTree([5,1,4,null,null,3,6]))).toEqual(false);
})

test("test3", ()=>{
    expect(isValidBST(makeTree([]))).toEqual(true);
})

test("test4", ()=>{
    expect(isValidBST(makeTree([1]))).toEqual(true);
})

test("test5", ()=>{
    expect(isValidBST(makeTree([1, 1]))).toEqual(false);
})

test("test6", ()=>{
    expect(isValidBST(makeTree([10,5,15,null,null,6,20]))).toEqual(false);
})

展开全文 >>

1. Two Sum

Two Sum

原题：1. Two Sum

source code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Runtime: 76 ms, faster than 52.22% of JavaScript online submissions for Two Sum.
// Memory Usage: 35.5 MB, less than 21.90% of JavaScript online submissions for Two Sum.

var twoSum = function(nums, target) {
    const map = {};
    for(let i = 0; i<nums.length; i++) {
        const targetIndex = map[target-nums[i]];
        if(targetIndex!==void 0) {
            return [targetIndex, i];
        }else {
            map[nums[i]] = i;
        }
    }

    //题干保证只有一个解
};

test cases:

1
2
3
test("test1", ()=>{
    expect(twoSum([2, 7, 11, 15], 9)).toEqual([0, 1]);
})

Three Sum

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//这个解法一直AC不过去，但是浏览器跑超时的test case速度还行。
var threeSum = function(nums) {
    nums.sort();
    const map = nums.reduce((prev, v, i)=>{
        prev[v] = i;
        return prev;
    }, {});
    const result = {};
    for(let i = 0; i<nums.length; i++) {
        for(let j= i+1; j<nums.length; j++) {
            const targetIndex = map[0-nums[i]-nums[j]];
            if(targetIndex>j) {
                const arr = [nums[i], nums[j], nums[targetIndex]];
                result[arr.join(',')] = arr;
            }
        }
    }

    return Object.values(result);
};


//这个解法可以AC
var threeSum = function(nums) {
    const cache = {};
    for(let num of nums) {
        cache[num] = (cache[num] || 0) + 1;
    }

    let result = {};
    nums.sort((a, b)=>a-b);
    for(let i = 0; i<nums.length; i++) {
        let low = i+1;
        let high = nums.length-1;
        while(low<high) {//这里主要利用数组有序的特性，用双指针从首尾向中间逼近
            let r = nums[i] + nums[low] + nums[high];
            if(r>0) {
                high--;
            }else if(r<0){
                low++;
            }else {
                result[`${nums[i]}_${nums[low]}_${nums[high]}`] = [nums[i], nums[low], nums[high]];
                low++;
                high--;
            }
        }
    }

    return Object.values(result);
};

Four Sum

和Three Sum类似，可以基于target + Three Some的方式写出类似的解答。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var fourSum = function(nums, target) {
    const cache = {};
    for(let i = 0; i<nums.length; i++) {
        let result = threeSum(nums.slice(0, i).concat(nums.slice(i+1)), target-nums[i]);
        for(let arr of result) {
            arr = [...arr, nums[i]];
            let cacheKey = arr.sort((a,b)=>a-b).join("_");
            if(!cache[cacheKey]) {
                cache[cacheKey] = arr;
            }
        }
    }
    
    return Object.values(cache);
};

展开全文 >>

239. Sliding Window Maximum

原题：239. Sliding Window Maximum

解法一

思路：滑动窗口，维护一个size为k的大堆。滑动过程中把最老的元素poll，offer最新的元素后调整堆。

时间复杂度：O(n * logk)

解法二（Recommend）

由于窗口大小固定，我们并不需要去维持大堆，只要记录窗口内的最大值即可。这里采用 双关队列（Dequeue） 的思路。

时间复杂度：O(n)

source code

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
// Runtime: 192 ms, faster than 18.08% of JavaScript online submissions for Sliding Window Maximum.
// Memory Usage: 48 MB, less than 33.33% of JavaScript online submissions for Sliding Window Maximum.

var maxSlidingWindow = function(nums, k) {
    const window = [];//存储的是nums的索引，这是时间复杂度为O(n)的关键
    const result = [];
    for(let i = 0; i<nums.length; i++) {
        const num = nums[i];
        for(let j = 0; j<window.length && window[j]<=i-k; j++) {//把超出窗口容量的最老的索引出列
            window.shift();
        }
        while(true) {
            if(window.length && nums[window[window.length-1]]<=num) {//每个新增的元素后续只会被比较一次就出列了，所以内层循环的时间复杂度为O(1)
                window.pop();
            }else {
                break;
            }
        }
        window.push(i);
        
        if(i>=k-1) {
            result.push(nums[window[0]]);
        }
    }

    return result;
};

test cases

1
2
3
4
5
6
7
test("test1", ()=>{
    expect(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3)).toEqual([3,3,5,5,6,7]);
})

test("test2", ()=>{
    expect(maxSlidingWindow([1,3,1,2,0,5], 3)).toEqual([3,3,2,5]);
})

展开全文 >>

703. Kth Largest Element in a Stream

原题：703. Kth Largest Element in a Stream

这道题主要考察优先队列（小堆）的用法，但是js里面没有优先队列，只能自己实现。具体可以参考leetcode上一个大神的实现：
priority-queue.js

Source Code

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
// Runtime: 196 ms, faster than 78.06% of JavaScript online submissions for Kth Largest Element in a Stream.
// Memory Usage: 45 MB, less than 75.00% of JavaScript online submissions for Kth Largest Element in a Stream.

var KthLargest = function(k, nums) {
    this.pq = new PriorityQueue(true);
    this.k = k;
    for(let num of nums) {
        this.add(num);
    }
};


/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
  if(this.pq.size()<this.k) {
      this.pq.offer(val, val);
  }else {
      const peek = this.pq.peek();
      if(peek<val) {
          this.pq.poll();
          this.pq.offer(val, val);
      }
  }
  return this.pq.peek();//nums' length ≥ k-1, 所以不需要考虑队列长度小于k需要返回什么
};

Test Cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
test("test1", ()=>{
    expect(kthLargest.add(3)).toEqual(4);
})

test("test2", ()=>{
    expect(kthLargest.add(5)).toEqual(5);
})

test("test3", ()=>{
    expect(kthLargest.add(10)).toEqual(5);
})

test("test4", ()=>{
    expect(kthLargest.add(9)).toEqual(8);
})

test("test5", ()=>{
    expect(kthLargest.add(4)).toEqual(8);
})

展开全文 >>

232. Implement Queue using Stacks

原题：232. Implement Queue using Stacks
类似的题有：225. Implement Stack using Queues

栈是FILO，队列是FIFO，想用栈实现队列，用的是 “负负得正” 的思想。

Source Code

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Stack {
    constructor() {
        this.stack = [];
    }
    push(x) {
        this.stack.push(x);
    }
    pop() {
        return this.stack.pop();
    }
    empty() {
        return !this.stack.length;
    }
}

var MyQueue = function() {
    this.input = new Stack();
    this.output = new Stack();
};

/**
 * Push element x to the back of queue. 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.input.push(x);
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    this._adjust();
    return this.output.pop();
};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    this._adjust();
    const peekEl = this.output.pop();
    this.output.push(peekEl);

    return peekEl;
};

MyQueue.prototype._adjust = function() {
    if(!this.output.empty()) {
        return;
    }

    while(!this.input.empty()) {
        this.output.push(this.input.pop());
    }
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return this.input.empty() && this.output.empty();
};

Test Cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const queue = new MyQueue();
queue.push(1);
queue.push(2);
test("test1", ()=>{
    expect(queue.peek()).toEqual(1);
})

test("test2", ()=>{
    expect(queue.pop()).toEqual(1);
})

test("test3", ()=>{
    expect(queue.empty()).toEqual(false);
})

test("test4", ()=>{
    queue.pop();
    expect(queue.empty()).toEqual(true);
})

展开全文 >>

20. Valid Parentheses

原题：20. Valid Parentheses

解法一（Recommended）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Runtime: 52 ms, faster than 83.97% of JavaScript online submissions for Valid Parentheses.
// Memory Usage: 33.7 MB, less than 95.00% of JavaScript online submissions for Valid Parentheses.
//时间复杂度：O(n)
var isValid = function(s) {
    const queue = [];
    const match = {'(':')', '[':']', '{':'}'};
    let cur = 0;
    while(cur<s.length) {
        const ch = s[cur];
        if(match[ch]) {
            queue.push(ch);
        }else {
            const pre = queue.pop();
            if(!pre || !match[pre] || match[pre]!=ch) {
                return false;
            }
        }
        cur++;
    }

    return !queue.length;
};

解法二

1
2
3
4
5
6
7
8
9
10
11
12
// Runtime: 76 ms, faster than 18.01% of JavaScript online submissions for Valid Parentheses.
// Memory Usage: 35.9 MB, less than 8.33% of JavaScript online submissions for Valid Parentheses.
//时间复杂度：O(n^2)
var isValid = function(s) {
    let length;
    while(length != s.length) {
        length = s.length;
        s = s.replace('{}', '').replace('[]', '').replace('()', '');
    }

    return !s.length;
};

Test Cases

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
32
33
34
35
test("test1", ()=>{
    expect(isValid("")).toEqual(true);
})

test("test2", ()=>{
    expect(isValid("{")).toEqual(false);
})

test("test3", ()=>{
    expect(isValid("{}}")).toEqual(false);
})

test("test4", ()=>{
    expect(isValid("{}")).toEqual(true);
})

test("test5", ()=>{
    expect(isValid("[]{}()")).toEqual(true);
})

test("test6", ()=>{
    expect(isValid("[[[[]")).toEqual(false);
})

test("test7", ()=>{
    expect(isValid("[{}]")).toEqual(true);
})

test("test8", ()=>{
    expect(isValid("[{]}")).toEqual(false);
})

test("test8", ()=>{
    expect(isValid("]][[")).toEqual(false);
})

展开全文 >>

Reverse Nodes in k-Group

原题：25.Reverse Nodes in k-Group

Source Code

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

// Runtime: 112 ms, faster than 12.97% of JavaScript online submissions for Reverse Nodes in k-Group.
// Memory Usage: 38.3 MB, less than 100.00% of JavaScript online submissions for Reverse Nodes in k-Group.

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
    const helper = function(pre) {
        let count = 0;
        let cur = pre.next;
        while(cur && count++<k) {
            cur = cur.next;
        }
        if(count<k) {
            return null;
        }
        let head = pre.next;
        let stub = pre.next;
        cur = stub.next;
        let i = 0;
        while(cur && ++i<k) {
            [head.next, stub, cur.next, cur] = [cur.next, cur, stub, cur.next];
        }
        pre.next = stub;
        
        return head;
    };

    const root = new ListNode();
    root.next = head;
    let pre = root;
    while(pre) {
        pre = helper(pre);
    }
    
    return root.next;
};

Test Cases

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
32
33
34
test("test1", ()=>{
    const list = makeLink([]);
    expect(reverseKGroup(list, 1)).toEqual(makeLink([]));
})

test("test2", ()=>{
    const list = makeLink([1]);
    expect(reverseKGroup(list, 1)).toEqual(makeLink([1]));
})

test("test3", ()=>{
    const list = makeLink([1]);
    expect(reverseKGroup(list, 2)).toEqual(makeLink([1]));
})

test("test4", ()=>{
    const list = makeLink([1,2,3]);
    expect(reverseKGroup(list, 2)).toEqual(makeLink([2,1,3]));
})

test("test5", ()=>{
    const list = makeLink([1,2,3]);
    expect(reverseKGroup(list, 3)).toEqual(makeLink([3,2,1]));
})

test("test6", ()=>{
    const list = makeLink([1,2,3,4,5,6]);
    expect(reverseKGroup(list, 3)).toEqual(makeLink([3,2,1,6,5,4]));
})

test("test7", ()=>{
    const list = makeLink([1,2,3,4,5]);
    expect(reverseKGroup(list, 3)).toEqual(makeLink([3,2,1,4,5]));
})

展开全文 >>

142. Linked List Cycle II

原题地址：142. Linked List Cycle II

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
//brute force，很容易想到
var detectCycle = function(head) {
    const set = new Set();
    while(head) {
        if(set.has(head)) {
            return head;
        }
        set.add(head);
        head = head.next;
    }

    return null;
};

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var detectCycle = function(head) {
    let slow = head;
    let fast = head;
    while (slow && fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow === fast) { //这里有些难理解
            while (head !== fast) {
                head = head.next;
                fast = fast.next;
            }
            return head;
        }
    }
    return null;
};

这个解法用的还是 Linked List Cycle里面的快慢双指针的思路。

外层循环通过快慢指针判断是否有环，内层循环找出环的起始点。

下面用一幅图解释下为什么内层循环这样做可以找到环的起始点：
pic
假设链表起点到环起点距离为x1，环起点到快慢指针相遇节点距离为x3，环的长度为2*x2。

快慢指针相遇时慢指针走的距离是：

1
slowDistance = x1 + x2

快指针有的距离是：

1
fastDistance = x1 + x3 + 2 * x2

由于快指针移动速度是慢指针两倍：

1
fastDistance = 2 * slowDistance

由上可得：

1
x1 = 2 * x2 - x3

x1是链表起点到环起点的距离，2 * x2 - x3是快指针绕回环起点的距离。因此只要以相同速度移动链表起点和快指针，它们第一次一定会在环起点相遇。

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

不思进取的前端开发攻城狮。<br>梦想是躺着也能拯救世界。