300. Longest Increasing Subsequence

原题：300. Longest Increasing Subsequence

方法一

DP。时间复杂度O(n^2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Runtime: 84 ms, faster than 37.27% of JavaScript online submissions for Longest Increasing Subsequence.
// Memory Usage: 36.7 MB, less than 11.11% of JavaScript online submissions for Longest Increasing Subsequence.
var lengthOfLIS = function (nums) {
  if (!nums.length) {
    return 0;
  }
  const dp = [1]; //dp[i]表示从0...i的最长上升子序列长度（序列中必须包含nums[i]）
  let maxLength = 1;
  for (let i = 1; i < nums.length; i++) {
    let tmpMax = 0;
    for (let j = i - 1; j >= 0; j--) {
      if (nums[i] > nums[j]) {
        tmpMax = Math.max(tmpMax, dp[j]);
      }
    }
    dp[i] = tmpMax + 1;
  }

  return Math.max(...dp);
};

方法二

类似贪心的思想。

维护局部最优解（每次都把result中比num大的最小一个数替换掉，这样后面就“有更大的机会”插入新的元素），使用二分法插入，时间复杂度O(nlogn)。

注意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
25
26
27
28
29
// Runtime: 68 ms, faster than 74.97% of JavaScript online submissions for Longest Increasing Subsequence.
// Memory Usage: 35.8 MB, less than 11.11% of JavaScript online submissions for Longest Increasing Subsequence.
var lengthOfLIS = function (nums) {
  const result = []; //思路：每次都把result中比num大的最小一个数替换掉
  const helper = function (num) {
    let left = 0;
    let right = result.length - 1;
    while (left <= right) {
      let mid = ~~((left + right) / 2);
      if (result[mid] >= num) {
        if (mid == 0 || result[mid - 1] < num) {
          result[mid] = num;
          return;
        } else {
          right = mid - 1;
        }
      } else {
        left = mid + 1;
      }
    }
    result.push(num);
  };

  for (let num of nums) {
    helper(num);
  }

  return result.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
test("test1", () => {
  expect(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])).toEqual(4);
});

test("test2", () => {
  expect(lengthOfLIS([])).toEqual(0);
});

test("test3", () => {
  expect(lengthOfLIS([1])).toEqual(1);
});

test("test4", () => {
  expect(lengthOfLIS([2, 1])).toEqual(1);
});

test("test5", () => {
  expect(lengthOfLIS([1, 3, 6, 7, 9, 4, 10, 5, 6])).toEqual(6);
});

test("test6", () => {
  expect(lengthOfLIS([2, 2])).toEqual(1);
});

展开全文 >>

188. Best Time to Buy and Sell Stock IV

原题：188. Best Time to Buy and Sell Stock IV

source code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var maxProfit = function (k, prices) {
  const dp = new Array(k + 1)
    .fill(0)
    .map((v) => new Array(prices.length).fill(0)); //dp[i][j]标识从price[0...j)进行了i次交易的最大收益
  let maxProfit = 0;
  for (let i = 1; i <= k; i++) {
    let tmpMax = dp[i - 1][0] - prices[0]; //上一轮买入后的最大收益
    for (let j = 1; j < prices.length; j++) {
      //注意这里不用j<=prices.length的原因是结果不是存在dp里面而是maxProfit
      dp[i][j] = Math.max(dp[i][j - 1], tmpMax + prices[j]);
      tmpMax = Math.max(tmpMax, dp[i - 1][j] - prices[j]);
      maxProfit = Math.max(maxProfit, dp[i][j]);
    }
  }

  return maxProfit;
};

test cases

1
2
3
4
5
6
7
8
9
10
11
test("test1", () => {
  expect(maxProfit(2, [2, 4, 1])).toEqual(2);
});

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

test("test3", () => {
  expect(maxProfit(2, [1, 3, 2, 8, 4, 9])).toEqual(8);
});

展开全文 >>

买卖股票问题通用解法

思路

leetcode上买卖股票系列问题：

大体思路都是DP，用通用解法能暴力过121、122、123，稍加修改能过309。

188用通用解法会提示runtime error，需要进行状态压缩，解法可以参考这个;

通用解法

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
var maxProfit = function (maxTransTimes, prices) {
  if (!maxTransTimes || !prices || !prices.length) {
    return 0;
  }

  const helper = function (prices, maxTransTimes) {
    //三维数组mp[i][k][j]
    //i标识第几天（0<=i<=prices.length-1）
    //k标识到第i天进行了多少笔交易（0<=k<=maxTransTimes），注意买入后并卖出才算一笔完整的交易
    //j标识第i天手上有没有股票（0<=j<=1）
    const mp = new Array(prices.length).fill(0).map((v) => {
      return new Array(maxTransTimes + 1).fill(0).map((v) => {
        return [0, 0];
      });
    });

    for (let k = 0; k <= maxTransTimes; k++) {
      if (k === 0) {
        mp[0][k][1] = -prices[0]; //第1天买入
      } else {
        //第1天是无法完成交易的
        mp[0][k][0] = -Infinity;
        mp[0][k][1] = -Infinity;
      }
    }

    for (let i = 1; i < prices.length; i++) {
      for (let k = 0; k <= maxTransTimes; k++) {
        mp[i][k][0] = Math.max(
          mp[i - 1][k][0], //第i天不动
          k === 0 ? -Infinity : mp[i - 1][k - 1][1] + prices[i] //第i天卖
        );
        mp[i][k][1] = Math.max(
          mp[i - 1][k][1], //第i天不动
          mp[i - 1][k][0] - prices[i] //第i天买
        );
      }
    }

    return mp;
  };

  const mp = helper(prices, maxTransTimes);
  let max = 0;
  for (let i = 0; i < prices.length; i++) {
    for (let k = 0; k <= maxTransTimes; k++) {
      max = Math.max(max, mp[i][k][0]);
    }
  }

  return max;
};

展开全文 >>

用generator+promise实现async/await

今天来探究下怎么用generator + promise实现async/await。对，就是当年Koa做的事情。。。

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
const Koa = function (generator) {
  const handler = generator();
  const helper = function () {
    const { value, done } = handler.next();
    if (done) {
      return;
    }
    if (value instanceof Promise) {
      value.then(function () {
        helper();
      });
    } else {
      helper();
    }
  };
  helper();
};

Koa(function* () {
  yield new Promise(function (resolve) {
    console.log(1);
    resolve();
  });

  console.log(2);

  yield new Promise(function (resolve, reject) {
    console.log(3);
    setTimeout(function () {
      resolve();
      // reject();
    }, 3000);
  });

  console.log(4);
});

//output:
// 1
// 2
// 3
// //（wait 3000 ms）
// 4

展开全文 >>

152. Maximum Product Subarray

原题：152. Maximum Product Subarray

source code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Runtime: 92 ms, faster than 22.07% of JavaScript online submissions for Maximum Product Subarray.
// Memory Usage: 44 MB, less than 14.29% of JavaScript online submissions for Maximum Product Subarray.
var maxProduct = function (nums) {
  if (!nums.length) {
    return 0;
  }
  const min = [nums[0]]; //表示已nums[i]为结尾的最小乘积
  const max = [nums[0]]; //表示已nums[i]为结尾的最大乘积
  for (let i = 1; i < nums.length; i++) {
    [min[i], , max[i]] = [
      nums[i],
      min[i - 1] * nums[i],
      max[i - 1] * nums[i],
    ].sort((a, b) => a - b);
  }

  return Math.max(...max);
};

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
test("test1", () => {
  expect(maxProduct([])).toEqual(0);
});

test("test2", () => {
  expect(maxProduct([1])).toEqual(1);
});

test("test3", () => {
  expect(maxProduct([-1])).toEqual(-1);
});

test("test4", () => {
  expect(maxProduct([2, 3, -2, 4])).toEqual(6);
});

test("test5", () => {
  expect(maxProduct([-2, 0, -1]) == 0).toEqual(true); //注意jest中expect(-0).toBe(0)返回的是false
});

test("test6", () => {
  expect(maxProduct([0, 2])).toEqual(2);
});

test("test6", () => {
  expect(maxProduct([0, -2, -3])).toEqual(6);
});

test("test7", () => {
  expect(maxProduct([-2, -3, 7])).toEqual(42);
});

展开全文 >>

实现 simplifyUrl

面试时候的一道题，当时用的是a.pathname.split('/') + 队列来实现，后来觉得createElement('a')有环境依赖而且需要加入很多协议、端口的判断，于是重新写了一版

原题

JS、CSS等静态资源路径，允许出现 “..”、”.” 、 “//“，请简化这些资源路径，把它们变成最短字符串。
注：一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。

<script src=”//s3.pstatp.com/eesz/.././resource/./bear/js//app.0fa757caa42b59caf8f0.js”></script>

  • 示例1：//s3.pstatp.com/eesz/.././resource/./bear/js//app.0fa757caa42b59caf8f0.js
  • 结果：//s3.pstatp.com/resource/bear/js/app.0fa757caa42b59caf8f0.js
  • 示例3：/eesz/.././resource/./bear/js//app.0fa757caa42b59caf8f0.js
  • 结果：/resource/bear/js/app.0fa757caa42b59caf8f0.js
  • 示例4：../eesz/aaa../b.b..b../dsds/../app.0fa757caa42b59caf8f0.js
  • 结果：../eesz/aaa../b.b..b../app.0fa757caa42b59caf8f0.js

source code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const simplifyUrl = function (url) {
  while (true) {
    if (/[\d\w\.]\/\.\.\//.test(url)) {
      url = url.replace(/[^\/]+\/\.\.\//, "");
    } else if (/\/\.\//.test(url)) {
      url = url.replace(/\/\.\//, "/");
    } else if (/[^^:]\/\//.test(url)) {
      //这里用断言不知道为啥不能匹配
      url = url.replace(/([^^:])\/\//, "$1/");
    } else {
      break;
    }
  }

  return url;
};

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
test("test1", () => {
  expect(
    simplifyUrl(
      "//s3.pstatp.com/eesz/.././resource/./bear/js//app.0fa757caa42b59caf8f0.js"
    )
  ).toEqual("//s3.pstatp.com/resource/bear/js/app.0fa757caa42b59caf8f0.js");
});

test("test2", () => {
  expect(
    simplifyUrl(
      "http://s3.pstatp.com/eesz/.././resource/./bear/js//app.0fa757caa42b59caf8f0.js"
    )
  ).toEqual(
    "http://s3.pstatp.com/resource/bear/js/app.0fa757caa42b59caf8f0.js"
  );
});

test("test3", () => {
  expect(
    simplifyUrl("/eesz/.././resource/./bear/js//app.0fa757caa42b59caf8f0.js")
  ).toEqual("/resource/bear/js/app.0fa757caa42b59caf8f0.js");
});

test("test4", () => {
  expect(
    simplifyUrl("../eesz/aaa../b.b..b../dsds/../app.0fa757caa42b59caf8f0.js")
  ).toEqual("../eesz/aaa../b.b..b../app.0fa757caa42b59caf8f0.js");
});

展开全文 >>

microTask/macroTask执行顺序

原题

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
//写出下面的输出顺序
var startTime = Date.now();

async function async1() {
  console.log("async1 start"); //1，主线程
  await async2();
  console.log("async1 end"); //2，micro task
}

async function async2() {
  console.log("async2"); //3，主线程
}

console.log("script start"); //4，主线程

setTimeout(function () {
  console.log("setTimeout"); //5，macro task
}, 0);

requestAnimationFrame(function () {
  console.log("requestAnimationFrame", Date.now() - startTime); //6，macro task
});

async1();

new Promise(function (resolve) {
  console.log("promise1"); //7，主线程
  resolve();
}).then(function () {
  console.log("promise2"); //8，micro task
});

console.log("script end"); //9，主线程

Chrome

先说chrome的输出顺序：4 -> 1 -> 3 -> 7 -> 9 -> 8 -> 2 -> 6/5。
解释：

  • event loop的执行机制：主线程 -> 清空微任务队列 -> 宏任务 -> 循环2、3…
  • async返回一个Promise，如果return非Promise的内容c，则会自动包装成Promise.resolve(c)
  • await后面挂起的内容可以理解成一个微任务（个人理解，不一定正确）
  • setTimeout 0和requestAnimationFrame的执行顺序不一定，和浏览器的执行速度、帧率有关。因为requestAnimationFrame总是尽可能快地在合适的时间执行

Firefox

输出顺序：4 -> 1 -> 3 -> 7 -> 9 -> (2 -> 8) -> 6/5

注意和chrome不一样的地方，先输出了Promise.then的内容，再输出await后面的内容。感觉ff的处理比chrome更符合直觉，因为await是比Promise.then更早加入微任务队列的。

笔记

这篇文章里面对macro task和micro task的分类挺好：微任务、宏任务与Event-Loop

宏任务：

# 浏览器 Node
I/O ✅ ✅
setTimeout ✅ ✅
setInterval ✅ ✅
setImmediate ❌ ✅
requestAnimationFrame ✅ ❌

微任务：

# 浏览器 Node
process.nextTick ❌ ✅
MutationObserver ✅ ❌
Promise.then catch finally ✅ ✅

展开全文 >>

120. Triangle

原题：120. Triangle

思路

DP。走到第i层第j个节点的最小路径和为dp[i][j] = min( dp[i-1][j-1], dp[i-1][j] )。

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
// Runtime: 60 ms, faster than 57.29% of JavaScript online submissions for Triangle.
// Memory Usage: 37.4 MB, less than 100.00% of JavaScript online submissions for Triangle.
var minimumTotal = function (triangle) {
  if (!triangle || !triangle.length) {
    return 0;
  }
  const dp = new Array(triangle.length).fill(1).map((v) => []);
  for (let i = 0; i < triangle.length; i++) {
    for (let j = 0; j < triangle[i].length; j++) {
      if (i > 0) {
        const a = dp[i - 1][j - 1];
        const b = dp[i - 1][j];
        dp[i][j] =
          triangle[i][j] +
          Math.min(a === void 0 ? Infinity : a, b === void 0 ? Infinity : b);
      } else {
        dp[i][j] = triangle[i][j];
      }
    }
  }

  return Math.min(...dp[dp.length - 1]);
};

test cases

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

test("test2", () => {
  const triangle = [];
  expect(minimumTotal(triangle)).toEqual(0);
});

test("test3", () => {
  const triangle = [[1]];
  expect(minimumTotal(triangle)).toEqual(1);
});

test("test4", () => {
  const triangle = [[1], [-5, -2], [3, 6, 1], [-1, 2, 4, -3]];
  expect(minimumTotal(triangle)).toEqual(-3);
});

更简洁的写法

1
2
3
4
5
6
7
// discuss中发现的更简洁写法，巧妙地避免了边界的判断
var minimumTotal = function (triangle) {
  for (let i = triangle.length - 2; i >= 0; i--)
    for (let j = 0; j < triangle[i].length; j++)
      triangle[i][j] += Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]);
  return triangle[0][0];
};

展开全文 >>

70. Climbing Stairs

70. Climbing Stairs

思路

DP。走到第n级的走法f(n)有f(n) = f(n-1) + f(n-2)。

source code

1
2
3
4
5
6
7
8
9
10
// Runtime: 56 ms, faster than 46.66% of JavaScript online submissions for Climbing Stairs.
// Memory Usage: 32.8 MB, less than 100.00% of JavaScript online submissions for Climbing Stairs.
var climbStairs = function (n) {
  const arr = [1, 1];
  for (let i = 2; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }

  return arr[n];
};

test cases

1
2
3
4
5
6
7
8
9
10
11
test("test1", () => {
  expect(climbStairs(2)).toEqual(2);
});

test("test2", () => {
  expect(climbStairs(0)).toEqual(1);
});

test("test3", () => {
  expect(climbStairs(3)).toEqual(3);
});

展开全文 >>

52. N-Queens II

原题：52. N-Queens II

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
// Runtime: 72 ms, faster than 43.26% of JavaScript online submissions for N-Queens II.
// Memory Usage: 34.6 MB, less than 100.00% of JavaScript online submissions for N-Queens II.
var totalNQueens = function (n) {
  let count = 0;
  //row：标记第几行
  //col：二进制的中1标记哪些列已被占用
  //pie：二进制的中1标记哪些撇已被占用
  //na：二进制的中1标记哪些捺已被占用
  const dfs = function (row, col, pie, na) {
    if (row >= n) {
      count++;
    }
    //(col | pie | na) 找出已经被占用的位置
    //~(col | pie | na) 找出没被占用的位置（01互换，因为后面的位运算都是基于1的）
    //& ((1 << n) - 1) 上一步取反后前面都是1，这一步则是打掉前面多余的1
    let bits = ~(col | pie | na) & ((1 << n) - 1);
    while (bits > 0) {
      //得到最低位1
      const p = bits & -bits;
      //row+1：下一行
      //col|p：把当前Q的位置填入
      //(pie | p) << 1：把当前Q的位置填入，因为当前Q对下一行撇的影响是左下角45°，所以左移一位
      //(na | p) >> 1：把当前Q的位置填入，因为当前Q对下一行捺的影响是右下角45°，所以右移一位
      dfs(row + 1, col | p, (pie | p) << 1, (na | p) >> 1);
      //最低位1已经试过了，打掉
      bits = bits & (bits - 1);
    }
  };

  dfs(0, 0, 0, 0);

  return count;
};

test cases

1
2
3
test("test1", () => {
  expect(totalNQueens(4)).toEqual(2);
});

展开全文 >>

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>梦想是躺着也能拯救世界。