Shortest subarray with sum at least k

在LeetCode刷算法题，记录一下一道比较难的题目和至少为 K 的最短子数组

问题描述

返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。

如果没有和至少为 K 的非空子数组，返回 -1 。

其中：

  • 1 <= A.length <= 50000
  • -10 ^ 5 <= A[i] <= 10 ^ 5
  • 1 <= K <= 10 ^ 9

最先想到的是依照数值长度进行遍历，但时间复杂度为O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[]} A
 * @param {number} K
 * @return {number}
 */
const shortestSubarray = (A, K) => {
  let preSum = 0
  let count = 1
  while (count <= A.length) {
    preSum += A[count - 1]
    let sum = preSum
    if (sum >= K) return count
    for (let i = 1; i + count <= A.length; i ++) {
      sum = sum - A[i - 1] + A[i + count - 1]
      if (sum >= K) return count
    }
    count += 1
  }
  return -1
}

之后参考了网上的资料，可以使用Sliding Window的方法，复杂度可以下降到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
/**
 * @param {number[]} A
 * @param {number} K
 * @return {number}
 */
const shortestSubarray = (A, K) => {
  if (!A.length) return -1
  let S = [0]
  for (let i = 0; i < A.length; i++) {
    S[i + 1] = S[i] + A[i]
  }
  const queue = []
  let ans = A.length + 1
  for (let j = 0; j < A.length + 1; j++) { 
    while (queue.length && S[j] <= S[queue[queue.length - 1]]) {
      queue.pop()
    }
    while(queue.length && S[j] >= S[queue[0]] + K) {
      ans = Math.min(ans, j - queue.shift())
    }
    queue.push(j)
  }
  return ans < A.length + 1 ? ans : -1
}
Algorithm

Some bash scripts

setInterval in bash

1
while true; do ls -l; sleep 2; done

count files fastly

1
find . -type f | wc -l

find files that large than 1 GiB

1
find . -type f -size +1G

test if file exist

1
2
3
4
5
6
myFile="/home/lxw/abc"
if [ ! -f "$myFile" ]; then
touch "$myFile"
else
echo "skip"
fi

kill process

find all dart process and kill them all

1
2
3
4
# find
ps -aux | grep dart
# find && kill
pgrep -f dart | xargs kill

Wifi

1
2
3
4
5
# connect to wifi
sudo nmcli d wifi connect iPhone password 11345678
# show saved connections
ls -sail /etc/NetworkManager/system-connections/
Bash

show colored word in bash

echo color in bash console

1
echo -e "\033[01;32m 绿色字体 √ \033[0m"
1
console.log('\033[01;32m', '绿色字体 √')

color matrix

1
2
3
4
5
6
7
8
9
for (let i = 0; i < 64; i++) {
  for (let j = 32; j < 48; j++) {
    const ii = i.toString().padStart(2, '0')
    const jj = j.toString().padStart(2, '0')
    const str = '\033' + `[${ii};${jj}m` + `[${ii};${jj}m` + '\033[0m '
    process.stdout.write(str)
  }
  process.stdout.write('\n')
}

Check Chinese Word

使用grep -r读取当前文件夹下的所有文件内容，使用正则匹配筛选中文

1
2
3
const child = require('child_process')
const all = child.execSync(`grep -r ''`).toString().split('\n').map(l => l.trim()).filter(l => l.length)
const chinese = all.filter(l => /[\u4E00-\u9FFF\u3400-\u4dbf\uf900-\ufaff\u3040-\u309f\uac00-\ud7af]+/.test(l))

call(), apply() and bind()

call(), apply()和bind()

js中的call(), apply()和bind()是Function.prototype下的方法，都是用于改变函数运行时上下文，最终的返回值是你调用的方法的返回值，若该方法没有返回值，则返回undefined。

  • apply()

使用 apply， 你可以继承其他对象的方法：注意这里apply()的第一个参数是null，在非严格模式下，第一个参数为null或者undefined时会自动替换为指向全局对象，apply()的第二个参数为数组或类数组。

1
2
const arr = [1,2,3,4,9,8,7]
const max = Math.max.apply(Math, arr)
  • call()

call()是apply()的一颗语法糖，作用和apply()一样，同样可实现继承，唯一的区别就在于call()接收的是参数列表，而apply()则接收参数数组。

1
2
const arr = [1,2,3,4,9,8,7]
const max = Math.max.apply(Math, ...arr)
  • bind()

bind()的作用与call()和apply()一样，都是可以改变函数运行时上下文，区别是call()和apply()在调用函数之后会立即执行，而bind()方法调用并改变函数运行时上下文后， 返回一个新的函数，供我们需要时再调用。

JavaScript

CSS Flex布局

Flex布局

Flex是Flexible Box的缩写，即“弹性盒子”

  • flex-direction，决定主轴的方向（即项目的排列方向）: row | row-reverse | column | column-reverse;

  • flex-wrap，定义换行情况: nowrap | wrap | wrap-reverse;

  • flex-flow：flex-direction和flex-wrap的简写，默认row nowrap

  • justify-content属性，定义项目在主轴上的对齐方式：flex-start | flex-end | center space-between | space-around

  • align-items属性，定义在交叉轴上的对齐方式：flex-start | flex-end | center | baseline | stretch;

  • 子项目： flex-grow，定义项目的放大比例，默认值为0，即如果空间有剩余，也不放大

CSS