2017-08-27 周末随笔

发表于 | 分类于

周末随笔

8 月的最后一个周末，966 的上班模式，有一天可以休息是很难得的，计划了一下要做的几件事 1. 9 点 30 分的 LeetCode 周赛，2. 把博客的 CI(持续集成)搭起来 3. 做软工的作业。在这过程中出现了一点小差错，只完成了前 2 件事情

一、Leetcode 周赛

img

A.Non-decreasing Array

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:

1
2
3
Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

1
2
3
Input: [4,2,1]
Output: False
Explanation: You can't get a non-decreasing array by modify at most one element.

Note: The n belongs to [1, 10,000].

题意：给定一个序列，能不能只修改一个数字，使得数列变成不下降序列

题解：必须使用 nlogn 复杂度才能过，n^2 T 了。

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
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var checkPossibility = function(nums) {
  a = nums
  const n = nums.length
  let len = 0
  let dp = []

  function bs(x, l, r) {
    while (l + 1 < r) {
      let mid = parseInt((l + r) / 2)
      if (dp[mid] < x) l = mid
      else r = mid
    }
    if (dp[r] < x) l = r
    return l
  }
  dp[0] = -999999999
  for (let i = 0; i < n; i++) {
    let k
    if (dp[len] <= a[i]) k = ++len
    else k = bs(a[i], 0, len) + 1
    dp[k] = a[i]
  }
  return len + 1 == n || len == n
}

B.Path Sum IV

If the depth of a tree is smaller than 5, then this tree can be represented by a list of three-digits integers.

For each integer in this list:

  1. The hundreds digit represents the depth D of this node, 1 <= D <= 4.
  2. The tens digit represents the position P of this node in the level it belongs to, 1 <= P <= 8. The position is the same as that in a full binary tree.
  3. The units digit represents the value V of this node, 0 <= V <= 9.

Given a list of ascending three-digits integers representing a binary with the depth smaller than 5. You need to return the sum of all paths from the root towards the leaves.

Example 1:

1
2
3
4
5
6
7
8
9
Input: [113, 215, 221]
Output: 12
Explanation:
The tree that the list represents is:
    3
   / \
  5   1

The path sum is (3 + 5) + (3 + 1) = 12.

Example 2:

1
2
3
4
5
6
7
8
9
Input: [113, 221]
Output: 4
Explanation:
The tree that the list represents is:
    3
     \
      1

The path sum is (3 + 1) = 4.

题意：用一个 3 位数的数字表示一个二叉树的节点，问这颗二叉树所有路径的和

题解：还原二叉树，dfs

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
/**
 * @param {number[]} nums
 * @return {number}
 */
var pathSum = function(nums) {
  let tree = []
  for (let i = 0; i < 1000; i++) tree[i] = -1
  nums.forEach(item => {
    let arr = item
      .toString()
      .split('')
      .map(x => parseInt(x))
    let pos = Math.pow(2, arr[0] - 1)
    tree[pos + arr[1] - 1] = arr[2]
  })
  let ans = 0
  let isLeef = tree.map((item, index) => tree[index * 2] == -1 && tree[index * 2 + 1] == -1)
  // console.log(tree)

  function dfs(root, sum, level) {
    // console.log(root, sum)
    if (isLeef[root]) {
      ans += sum
      ans += tree[root]
      return
    }
    if (tree[root * 2] > -1) dfs(root * 2, tree[root] + sum, level + 1)
    if (tree[root * 2 + 1] > -1) dfs(root * 2 + 1, tree[root] + sum, level + 1)
  }
  dfs(1, 0, 1)
  // console.log(ans)
  return ans
}

C.Beautiful Arrangement II

Given two integers n and k, you need to construct a list which contains n different positive integers ranging from 1 to n and obeys the following requirement:
Suppose this list is [a1, a2, a3, … , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, … , |an-1 - an|] has exactly k distinct integers.

If there are multiple answers, print any of them.

Example 1:

1
2
3
Input: n = 3, k = 1
Output: [1, 2, 3]
Explanation: The [1, 2, 3] has three different positive integers ranging from 1 to 3, and the [1, 1] has exactly 1 distinct integer: 1.

Example 2:

1
2
3
Input: n = 3, k = 2
Output: [1, 3, 2]
Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.

Note:

  1. The n and k are in the range 1 <= k < n <= 10^4.

题意：构造一个符合题意的数列

题解：？？？？无法证明的一个构造

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} n
 * @param {number} k
 * @return {number[]}
 */
var constructArray = function(n, k) {
  let ans = [1]
  let flag = []
  flag[1] = true
  for (let i = 1; i < n; i++) {
    let t = ans[i - 1]
    if (!flag[t - k] && t - k > 0) {
      ans.push(t - k)
      flag[t - k] = true
    } else if (!flag[t + k] && t + k <= n) {
      ans.push(t + k)
      flag[t + k] = true
    }
    k--
    if (k == 1) break
  }
  for (let i = 1; i <= n; i++) if (!flag[i]) ans.push(i)
  return ans
}

无法证明

二、使用 TravisCI + github 实现自动构建博客

1.hexo 文档

2.将 source 分支作为 hexo 资源的分支,master 作为构造以后静态文件的分支(方便使用 github page)

3.写 CI 配置文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
language: node_js
node_js: stable
cache:
  directories:
    - node_modules
    - $(npm root -g)
    - $(npm config get prefix)/bin/hexo
branches:
  only:
    - source
before_install:
  - git config --global user.name "usernami"
  - git config --global user.email email
  - npm install hexo -g
script:
  - hexo g
  - sed -i'' "/^ *repo/s~github\.com~${GH_TOKEN}@github.com~" _config.yml
  - hexo d

4._config.yml 添加如下代码

1
2
3
4
deploy:
  type: git
  repo: https://github.com/chs97/Blog.git
  branch: master

5.生成 ACCESS TOKEN(github)

进入个人设置，如图所示img

6.配置 GH_TOKEN

img

img

配置成功就能进行持续集成了

大坑：下载主题 next 丢到 theme 中，因为直接 git clone 所以主题文件夹 next 中有一个.git 文件夹，然后 push 不上去。add 文件的时候没提示 push 也没提示，travis 每次 build 都是 pass 但是有好几个页面都是空白的，以为是自己没配置好持续集成，所以搞了一下午，最后输了一下 git status 显示 modified: xxx(modified content, untracked content) 才发现这个问题。

删除.git 文件夹后，还是无法提交，并且 add 文件的时候会失败 这里有个解决方案

Removing the directory from git and adding it again worked for me:

1
2
3
>  git rm --cached directory
>  git add directory
>

This works if you purposefully removed the .git directory because you wanted to add directoryto your main git project. In my specific case, I had git cloned an extension and ran git add .without thinking too much. Git decided to create a submodule, which I didn’t like. So I removed directory/.git and ran into Git: fatal: Pathspec is in submodule. I couldn’t find out how to remove the submodule stuff. Fixed with the two lines above.

三、软工作业

只能先欠着了。