why

解决公网访问自己的内网设备(大部分公司,小区都是在内网中,IPv4历史原因导致),解决方案:

  • 路由器新增端口映射
  • 花生壳动态解析软件
  • natapp等免费软件提供的内网映射服务
  • 基于ngrok(不荐)或者frp自建内网映射服务

how

目前推荐使用frp搭建穿透服务,支持HTTP,SSH,TCP UDP FTP

最近更新hexo比较频繁,发现频繁性的推送master分支以及source源文件备份,比较繁琐,查询了官方文档,可以写一些监听函数,实现一些自动化部署,hexo默认将脚本放置在scripts文件夹下,以下代码可以在hexo new的时候自动打开默认编辑软件

1
2
3
4
5
var spawn = require('child_process').exec;

hexo.on('new', function(data){
spawn('start "markdown编辑器绝对路径.exe" ' + data.path);
});

非常的方便,省去了我打开typora的时间

以及以下的代码可以实现自动部署source分支

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
require('shelljs/global');//记得安装包

try {
hexo.on('deployAfter', function() {//当deploy完成后执行备份
run();
});
} catch (e) {
console.log("You make a wrong:" + e.toString());
}

function run() {
if (!which('git')) {
echo('Sorry, this script requires git');
exit(1);
} else {
echo("======================Auto Backup Begin===========================");
cd('./');
if (exec('git add --all').code !== 0) {
echo('Error: Git add failed');
exit(1);

}
if (exec('git commit -am "Form auto backup script\'s commit"').code !== 0) {
echo('Error: Git commit failed');
exit(1);

}
if (exec('git push origin source').code !== 0) {
echo('Error: Git push failed');
exit(1);

}
echo("==================Auto Backup Complete============================")
}
}

参考文献

https://hexo.io/zh-cn/docs/plugins#%E5%B7%A5%E5%85%B7

LeetCode28

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = “hello”, needle = “ll”
Output: 2
Example 2:

Input: haystack = “aaaaa”, needle = “bba”
Output: -1
Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

Solution

如果不考虑java偷懒的写法当然可以想到indexof的想法

1
2
3
4
5
6
class Solution {
public int strStr(String haystack, String needle) {
return haystack.indexOf(needle);
}
}
Runtime: 1 ms

先按照题意写了如下代码:

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
class Solution {
public int strStr(String haystack, String needle) {
if(needle.length()==0)return 0;
if(haystack.length()==0)return -1;
int index =-1;
boolean flag = true;
for(int i=0;i<haystack.length();i++){
if(haystack.charAt(i)==needle.charAt(0)){
flag=true;
for(int j =0;j<needle.length();j++){
if(i+j>=haystack.length()){
return -1;
}
if(haystack.charAt(i+j)!=needle.charAt(j)){
flag=false;
break;
};
}
if(flag){
return i;
}
}

}
return index;
}
}
Runtime: 4 ms
Memory Usage: 42.7 MB

LeetCode-69

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2
Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842…, and since
the decimal part is truncated, 2 is returned.

Solution

就是手写一个根号源码,首先想到的就是通过平方来做

1
2
3
4
5
6
7
8
9
10
public int mySqrt(int x) {
for(int i=46340;i<46341;i++){
if(x>=(long)i*i&&x<(long)(i+1)*(i+1)){
return i;
}
}
return x;
}
Runtime: 22 ms
Memory Usage: 34 MB

如果不遵循题目的要求,使用Math函数,所以我们的目标大概是3ms附近

1
2
3
4
public int mySqrt(int x) {
return (int)Math.sqrt(Double.parseDouble(String.valueOf(x)));
}
Runtime: 3 ms

解法粗暴,遇到大数的时候会从0重新开始计算,复杂度O(N)

第一次优化

思路就是避免做两次乘法然后去比较,这个地方可以去优化

1
2
3
4
5
6
7
8
9
10
class Solution {
public int mySqrt(int x) {
long n = 1;
while(n * n <= x) {
n++;
}
return (int) n - 1;
}
}
Runtime: 11 ms

第二次优化

可以使用二分法来逐步逼近i,没有必要从1开始顺序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int mySqrt(int x) {
if (x == 0 || x == 1) return x;

int left = 1;
int right = x;
while (left < right) {

int midPoint = (left + right) / 2;
if (midPoint == x / midPoint) {
return midPoint;
} else if (midPoint > x / midPoint) {
right = midPoint;
} else if (midPoint < x / midPoint) {
left = midPoint + 1;
}
}

return left - 1;
}
}
Runtime: 1 ms

LeetCode 100

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
Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input: 1 1
/ \ / \
2 3 2 3

[1,2,3], [1,2,3]

Output: true
Example 2:

Input: 1 1
/ \
2 2

[1,2], [1,null,2]

Output: false
Example 3:

Input: 1 1
/ \ / \
2 1 1 2

[1,2,1], [1,1,2]

Output: false

Solution

题目其实很简单的一个递归Recursion,我们很轻松可以通过递归来解决

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// p and q are both null
if (p == null && q == null) return true;
// one of p and q is null
if (q == null || p == null) return false;
if (p.val != q.val) return false;
return isSameTree(p.right, q.right) &&
isSameTree(p.left, q.left);
}
}

时间复杂度为O(n),控件复杂度为O(logn)~O(n)之间,这道题就不考虑其他解法了,recursion目前看来是最优解

LeetCode 73

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
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
Example 2:

Input:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
Follow up:

A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Solution

一开始以为递归可以解决,可以将矩阵一层层拆开,写下了如下的代码:

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
public void setZeroes(int[][] matrix) {
int rows = matrix.length-1;
int cols = matrix[0].length-1;
regression(matrix, rows>=cols?cols:rows);
}
public void regression(int[][] matrix,int index){
if(index<0){
return;
}
boolean flag = false;
for(int i =index;i<matrix[0].length;i++){
if(matrix[index][i]==0)
{
handleZero(matrix,i);
flag=true;
break;
}
}
if(flag==false){
for(int j =index;j<matrix.length;j++){
if(matrix[j][index]==0)
{
handleZero(matrix,j);
break;
}
}
}

regression(matrix, --index);
}
private void handleZero(int[][] matrix,int pos) {

for(int i=matrix[0].length-1;i>=pos;i--){
matrix[pos][i]=0;
}
for(int j=matrix.length-1;j>=pos;j--){
matrix[j][pos]=0;
}
}

写完后很快发现不能够实现,原因就在于他只能管理到内层,外层标为0后,没办法做额外的标记(其实生产代码可以打一些标记),所以只能抛弃这个本以为很简单的方法,该用了set合集去记录要设置0行列的行号或者列号,这个复杂度并不是很复杂,但是执行完发现代码的效率还是很低,先放代码:

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
class Solution {
public void setZeroes(int[][] matrix) {
int R = matrix.length;
int C = matrix[0].length;
Set<Integer> rows = new HashSet<Integer>();
Set<Integer> cols = new HashSet<Integer>();

for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (matrix[i][j] == 0) {
rows.add(i);
cols.add(j);
}
}
}

for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (rows.contains(i) || cols.contains(j)) {
matrix[i][j] = 0;
}
}
}
}
}

代码低效的原因在于动用了两层循环,时间复杂度非常低,题目的置0是有规律的,不是无规律的,所以我开始寻求更新简单的方法,先贴最优解,要睡觉了,我的头发啊

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
class Solution {
public void setZeroes(int[][] matrix) {
int R = matrix.length;
int C = matrix[0].length;
boolean isCol = false;

for(int i=0; i<R; i++) {
if (matrix[i][0] == 0) {
isCol = true;
}
for(int j=1; j<C; j++) {
if(matrix[i][j]==0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}

// Iterate over the array once again and using the first row and first column, update the elements.
for(int i=1; i<R; i++) {
for(int j=1; j<C; j++) {
if(matrix[i][0]==0 || matrix[0][j]==0) {
matrix[i][j] = 0;
}
}
}

// See if the first row needs to be set to zero as well
if(matrix[0][0]==0) {
for(int j=0; j<C; j++) {
matrix[0][j] = 0;
}
}

// See if the first column needs to be set to zero as well
if(isCol) {
for(int i=0; i<R; i++) {
matrix[i][0] = 0;
}
}
}
}

官网doc:https://redis.io/topics/transactions

本文纯属阅读笔记,无学术参考价值

what

事务(transaction)的本质就是处理好几个动作,要么都成功,要么其中一个失败就全部回滚

每门语言都会有事务的支持,node也有async的方法实现事务几个动作串行,或者并行,一个失败全部回滚,之前写过支付的例子,使用async.waterfall,购买会员后

1.查询支付宝返回支付是否成功

2.获取用户所买会员的等级及相关权限

3.将权益插入用户表中

4.将订单数据记录到订单表中,方便后台查看订单量

大致步骤就是这些

Redis主要使用MULTI ,EXEC,DISCARD WATCH来实现事务的功能

遵循以下原则:

  • 所有命令被序列化后顺序执行,且执行期间不接受其他请求,保证隔离性
  • EXEC命令触发事务中所有命令的执行,因此,如果客户端调用MULTI命令之前失去连接,则不执行任何操作。如果EXEC命令调用过,则所有的命令都会被执行

how

MULTI输入事务以OK答复,此时用户可以发送多个命令,Redis都不会执行,而是排队,一旦调用EXEC,则将会执行所有命令,调用DISCARD将刷新(Flush?清空?重新执行?)事务队列并退出事务

示例代码:

1
2
3
4
5
6
7
8
9
> MULTI
OK
> INCR foo
QUEUED
> INCR bar
QUEUED
> EXEC
1) (integer) 1
2) (integer) 1

可以看出EXEC返回一个数组,其中每个元素都是事务中单个命令的答复,其发出顺序与命令相同

当Reids连接处于MULTI的请求时,所有的命令都将以字符串queued答复,当EXEC时,将顺序执行

errors

可能存在两种命令错误:

  • 命令可能无法排队,因此在EXEC之前可能有错误(包括命令语法错误)
  • 调用EXEC后,命令执行失败

客户端通过检查已排队(queued)的命令返回值来判断第一种错误,另外从2.6.5开始,服务器将记住在命令排队期间发生的错误,并且拒绝执行事务,返回错误并自动丢弃事务

EXEC执行后错误不会特殊处理,所有的命令都将被执及时有些命令失败

1
2
3
4
5
6
7
8
9
10
MULTI
+OK
SET a abc
+QUEUED
LPOP a
+QUEUED
EXEC
*2
+OK
-ERR Operation against a key holding the wrong kind of value

即时命令失败,队列里的其他命令也会处理

1
2
3
4
{
name:stu
time:1
}

Leetcode-64

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

solution

解法为简单的动态规划,只要找到比较该元素,上方和左方的值的最小值,然后与该值相加,就可以得到解

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int minPathSum(int[][] grid) {
for(int i=1; i<grid.length; i++) grid[i][0] += grid[i-1][0];
for(int j=1; j<grid[0].length; j++) grid[0][j] += grid[0][j-1];
for (int i=1; i<grid.length; i++) {
for (int j=1; j<grid[0].length; j++) {
grid[i][j] = Math.min(grid[i][j-1], grid[i-1][j]) + grid[i][j];
}
}
return grid[grid.length-1][grid[0].length-1];
}
}

Leetcode-75

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library's sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Follow up:

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with a one-pass algorithm using only constant space?

solution

题目乍一看非常简单,但确实说使用简单的sort方法以及o(n^2)的排序确实会浪费时间复杂度,本着好奇心,我试了一下,果然成了吊车尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public void sortColors(int[] nums) {
for(int i =0;i<nums.length-1;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[i]>nums[j]){
int tmp=nums[i];
nums[i]=nums[j];
nums[j]=tmp;
}
}
}
}
}
Runtime: 1 ms, faster than 6.35% of Java online submissions for Sort Colors.

该题优化的核心位置是该数组是一个一维数组,设置两个指针,左边遍历0,遇到0往左放,遇到2往右放,r和l为左右分界线,index记录最后一个0的位置

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
class Solution {
public void sortColors(int[] nums) {
int l = 0;
int r = nums.length - 1;
int index = 0;
while(l <= r) {
if(nums[l] == 0) {
if(l > index) {
int tmp = nums[index];
nums[index] = nums[l];
nums[l] = tmp;
index++;
}
else {
l++;
index++;
}
}
else if(nums[l] == 2) {
int tmp = nums[r];
nums[r] = 2;
nums[l] = tmp;
r--;
}
else l++;
}

}
}

题目

(这道题在互联网上已经有了)

1
2
3
可以添加任务,任务包含任务数据,任务延迟触发的等待时间。
在任务到达触发时间点时,自动触发执行此任务。
队列中任务保持先进先出原则:假设 A 任务的触发等待时间为 X,B 任务的触发等待时间为 Y,B 在 A 之后被添加入队列,则 A 的前驱任务执行完成后等待时间 X 后,才执行 A,同理在 A 执行完成后,等待时间 Y,才执行 B。

思路过程

1.Java上线

读题目就是延时队列的特征,Java有锁,有多线程,写起来多方便

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.DelayQueue;
import java.util.concurrent.Delayed;
import java.util.concurrent.TimeUnit;
public class HandWritingQueue {
public static void main(String[] args) {
final BlockingQueue<DelayedElement> deque = new DelayQueue<>();
Runnable producerRunnable = new Runnable() {
int i = 10;
public void run() {
while (true && i>0) {
try {
--i;
System.out.println("producing "+i+",wait "+i+" seconds");
deque.put(new DelayedElement(1000 * i, "i=" + i));
Thread.sleep(200);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
};
Runnable customerRunnable = new Runnable() {
public void run() {
while (true) {
try {
System.out.println("consuming:" + deque.take().msg);
//Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
};

Runnable getSize= new Runnable() {
@Override
public void run() {
while (true) {
System.out.println("size="+deque.size());
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}

}
}
};

Thread thread1 = new Thread(producerRunnable);
thread1.start();

Thread thread2 = new Thread(customerRunnable);
thread2.start();

Thread thread3 = new Thread(getSize);
thread3.start();

}

static class DelayedElement implements Delayed {

private final long expire;
private final String msg;

public DelayedElement(long delay, String msg) {
this.msg = msg;
expire = System.currentTimeMillis() + delay;
}

@Override
public long getDelay(TimeUnit unit) {
return unit.convert(this.expire - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
}
@Override
public int compareTo(Delayed o) {
return -1;//FIFO
}
}
}

2.Node上线

被提醒该题目可以用node实现,且不需要借助redis来做,然后我上手就是一把操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
'use strict'
class DelayElement {
constructor(data, expire) {
this.data = data;
this.expire = expire;//second
}
}
const delayArray = [];

//push two element in delayArray
delayArray.push(new DelayElement(1, 2));
delayArray.push(new DelayElement(2, 1));
let length = delayArray.length;

let time_cnt = 0;
while (delayArray.length > 0) {
let de = delayArray.shift();
time_cnt += de.expire;//serial
(function () {
setTimeout(() => {
console.log('expire data is :' + de.data + ',expire time is :' + de.expire);
}, time_cnt * 1000);
})();
}

我以为设计的考点也就是立即执行函数,延时的使用,但是这里的for循环是个伪串行,实际上是并发的,也为第三步的修改提供了bug

3.Promise时代

一开始我是想把async函数放进去,写了如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'use strict'
const delayArray = [];
const daPush = (data, expire) => {
delayArray.push(async () => {
setTimeout(() => {
console.log('data is ' + data + ' and expire is ' + expire);
}, expire * 1000);
});
}
daPush(1, 4);//2 seconds
daPush(2, 5);

(async () => {
for (const da of delayArray) {
await da();
}
})();

发现代码还是串行的,然后查了一下可能的问题(以下为个人猜测,欢迎指正)async声明的函数会包装成Promise不假,但是for循环会并发去执行await中的async

4.正解

promise执行会阻塞主线程

Macrotasks和Microtasks 都属于上述的异步任务中的一种,他们分别有如下API:
macrotasks: setTimeout, setInterval, setImmediate, I/O, UI rendering
microtasks: process.nextTick, Promise, MutationObserver

任务队列中,在每一次事件循环中,macrotask只会提取一个执行,而microtask一直提取,直到microsoft队列为空为止。

也就是说如果某个microtask任务被推入到执行中,那么当主线程任务执行完成后,会循环调用该队列任务中的下一个任务来执行,直到该任务队列到最后一个任务为止。

而事件循环每次只会入栈一个macrotask,主线程执行完成该任务后又会检查microtasks队列并完成里面的所有任务后再执行macrotask的任务。

以及macrotask应该对应的是check队列(该行未验证)

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
'use strict'
const delayArray = [];
const daPush = (data, expire) => {
delayArray.push(() => new Promise((resolve,reject) => {
setTimeout(() => {
if(data)
{
console.log('data is ' + data + ' and expire is ' + expire);
resolve(true);
}
else{
reject('there is nodata');
}
}, expire * 1000);
}));
};
daPush(1, 4);//2 seconds
daPush(2, 5);

(async () => {
for (const da of delayArray) {
da().then((value)=>{
// console.log(value);
}).catch((value)=>{
console.log(value);
});
//没有28-33,只35行也可以
// await da();
}
})();
0%