2016年12月7日星期三

leetcode做题记录 —— kth-smallest-element-in-a-sorted-matrix

kth-smallest-element-in-a-sorted-matrix
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
Example:
1.matrix = [
2.   [ 1,  5,  9],
3.   [10, 11, 13],
4.   [12, 13, 15]
5.],
6.k = 8,
7.return 13.
Note: 
You may assume k is always valid, 1 ≤ k ≤ n2.
输入一个矩阵和一个整数 k ，求矩阵中第 k 小的数。

解法一

因为行和列都是有序的，所以第 k 小的数的上界可以算出来，然后把上界之内的所有数放进数组里，排序后输出 k 位。
1.//Javascript
2.var kthSmallest = function(matrix, k) {
3.    let n = matrix.length;
4.    let upper = ~~Math.sqrt(k - 1);
5.    let result = [matrix[upper][upper]];
6.    for( let i = 0; i < upper; i++ )
7.    {
8.        for( let j = upper; j < n; j++ )
9.        {
10.            result.push(matrix[i][j]);
11.        }
12.    }
13.    for( let i = 0; i < upper; i++ )
14.    {
15.        for( let j = 0; j < n; j++ )
16.        {
17.            result.push(matrix[j][i]);
18.        }
19.    }
20.    return result.sort((a, b)=>a - b)[k - 1];
21.};

解法二

因为行和列都是有序的，所以行 i 肯定有 i 个比他小的数，列 j 肯定比 j - 1大 
只需要二分找到当前下界和上界的中值，然后对于每个中值，用这个性质从左下角开始查找，找到比这个数小的数的个数 
用这个个数和k比较，逼近出结果
1.//Javascript
2./**
3. * @param {number[][]} matrix
4. * @param {number} k
5. * @return {number}
6. */
7.let kthSmallest = function (matrix, k) {
8.    let left = matrix[0][0];
9.    let right = matrix[matrix.length - 1][matrix.length - 1];
10.    while (left < right) 
11.    {
12.        let mid = (left + right) >> 1;
13.        let cnt = search_less_equal(matrix, mid);
14.        if (cnt < k) 
15.        {
16.            left = mid + 1;
17.        }
18.        else
19.        {
20.            right = mid;
21.        }
22.    }
23.    return left;
24.}
25.let search_less_equal = function (matrix, target) {
26.    let n = matrix.length;
27.    let i = n - 1;
28.    let j = 0;
29.    let res = 0;
30.    while (i >= 0 && j < n) 
31.    {
32.        if (matrix[i][j] <= target) 
33.        {
34.            res += i + 1;
35.            ++j;
36.        } 
37.        else 
38.        {
39.            --i;
40.        }
41.    }
42.    return res;
43.}
End

2016年12月6日星期二

leetcode做题记录 —— different-ways-to-add-parentheses

different-ways-to-add-parentheses 
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
Example 1 
Input: "2-1-1".
1.((2-1)-1) = 0
2.(2-(1-1)) = 2
Output: [0, 2]
Example 2 
Input: "2*3-4*5".
1.(2*(3-(4*5))) = -34
2.((2*3)-(4*5)) = -14
3.((2*(3-4))*5) = -10
4.(2*((3-4)*5)) = -10
5.(((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]
给定一个表达式，要求返回所有不同括号划分后计算的的结果。

解法

  1. 对原始的字符串进行处理，把数字和操作符分别用一个数组存储
  2. 循环 1 -> nums.length -1 之间的所有数字，比如标记为i 
    • 分别递归计算 i 左边和右边的所有数字
    • 取得当前 i 对应的运算符
    • 用当前的运算符对所有左边和右边的计算结果进行计算，添加到结果数组里
    • 返回数组
1.//Javascript
2./**
3. * @param {string} input
4. * @return {number[]}
5. */
6.var operate = function(num1, num2, operator) {
7.    let res = 0;
8.    switch (operator) 
9.    {
10.        case "+":
11.            res = num1 + num2;
12.            break;
13.        case "-":
14.            res = num1 - num2;
15.            break;
16.        case "*":
17.            res = num1 * num2;
18.            break;
19.        default: 
20.            res = 0;
21.            break;
22.    }
23.    return res;
24.};
25.var compute = function(nums, operators) {
26.    let len = nums.length;
27.    if( len === 1 )
28.    {
29.        return nums;
30.    }
31.    if( len === 2 )
32.    {
33.        return [operate(nums[0], nums[1], operators[0])];
34.    }
35.    let res = [];
36.    for( let i = 1; i < len; i++ )
37.    {
38.        let operator = operators[i - 1];
39.        let leftRes = compute(nums.slice(0, i), operators.slice(0, i - 1));
40.        let rightRes = compute(nums.slice(i, len), operators.slice(i));
41.        for( let l = 0; l < leftRes.length; l++ ) 
42.        {
43.            for( let r = 0; r < rightRes.length; r++ ) 
44.            {
45.                res.push(operate(leftRes[l], rightRes[r], operator));
46.            }
47.        }
48.    }
49.    return res;
50.};
51.var diffWaysToCompute = function(input) {
52.    let nums = input.match(/\d+/g).map(e=>+e);
53.    let operators = input.match(/[\+\-\*]/g);
54.    return compute(nums, operators);
55.};
End

leetcode做题记录 —— unique-binary-search-trees-ii

unique-binary-search-trees-ii 
Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.
For example, 
Given n = 3, your program should return all 5 unique BST’s shown below
1.   1         3     3      2      1
2.    \       /     /      / \      \
3.     3     2     1      1   3      2
4.    /     /       \                 \
5.   2     1         2                 3
求 n 个节点的所有搜索二叉树 
比如，n = 3 的时候，总共有5总不同的结构，返回一个包含这 5 棵树的数组
1.   1         3     3      2      1
2.    \       /     /      / \      \
3.     3     2     1      1   3      2
4.    /     /       \                 \
5.   2     1         2                 3

解法

  • 遍历start ~ end 之间的所有值作为根，比如设为 i 
    • start ~ i - 1 之间的值即为根为 i 的左子树所包含的值，递归获取这个区间的所有子树
    • i + 1 ~ end 之间的值即为根为 i 的右子树所包含的值，递归获取这个区间的所有子树
    • 遍历所有子树的组合，以 i 为根结合在一起
    • 返回构造好的数组
1.//Javascript
2./**
3. * Definition for a binary tree node.
4. * function TreeNode(val) {
5. *     this.val = val;
6. *     this.left = this.right = null;
7. * }
8. */
9./**
10. * @param {number} n
11. * @return {TreeNode[]}
12. */
13.
14.var generateTrees = function(n) {
15.    return n === 0 ? [] : generateFrom(1, n);
16.};
17.var generateFrom = function(start, end) {
18.    if( start > end )
19.    {
20.        return [null];
21.    }
22.    let res = [];
23.    for( let i = start; i <= end; i++)
24.    {
25.        let leftTrees = generateFrom(start, i - 1);
26.        let rightTrees = generateFrom(i + 1, end);
27.        for( let l = 0; l < leftTrees.length; l++ )
28.        {
29.            for( let r = 0; r < rightTrees.length; r++ )
30.            {
31.                let root = new TreeNode(i);
32.                root.left = leftTrees[l];
33.                root.right = rightTrees[r];
34.                res.push(root);
35.            }
36.        }
37.    }
38.    return res;
39.}
End