2020-01-18-plugins
最近更新hexo比较频繁,发现频繁性的推送master分支以及source源文件备份,比较繁琐,查询了官方文档,可以写一些监听函数,实现一些自动化部署,hexo默认将脚本放置在scripts文件夹下,以下代码可以在hexo new的时候自动打开默认编辑软件
1 | var spawn = require('child_process').exec; |
非常的方便,省去了我打开typora的时间
以及以下的代码可以实现自动部署source分支
1 | require('shelljs/global');//记得安装包 |
参考文献
2020-01-17-ImplementStr
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 | class Solution { |
先按照题意写了如下代码:
1 | class Solution { |
2020-01-15-sqrtx
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 | public int mySqrt(int x) { |
如果不遵循题目的要求,使用Math函数,所以我们的目标大概是3ms附近
1 | public int mySqrt(int x) { |
解法粗暴,遇到大数的时候会从0重新开始计算,复杂度O(N)
第一次优化
思路就是避免做两次乘法然后去比较,这个地方可以去优化
1 | class Solution { |
第二次优化
可以使用二分法来逐步逼近i,没有必要从1开始顺序遍历
1 | class Solution { |
2020-01-11-SameTree
LeetCode 100
1 | Given two binary trees, write a function to check if they are the same or not. |
Solution
题目其实很简单的一个递归Recursion,我们很轻松可以通过递归来解决
1 | class Solution { |
时间复杂度为O(n),控件复杂度为O(logn)~O(n)之间,这道题就不考虑其他解法了,recursion目前看来是最优解
2020-01-10-MatrixZero
LeetCode 73
1 | Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place. |
Solution
一开始以为递归可以解决,可以将矩阵一层层拆开,写下了如下的代码:
1 | public void setZeroes(int[][] matrix) { |
写完后很快发现不能够实现,原因就在于他只能管理到内层,外层标为0后,没办法做额外的标记(其实生产代码可以打一些标记),所以只能抛弃这个本以为很简单的方法,该用了set合集去记录要设置0行列的行号或者列号,这个复杂度并不是很复杂,但是执行完发现代码的效率还是很低,先放代码:
1 | class Solution { |
代码低效的原因在于动用了两层循环,时间复杂度非常低,题目的置0是有规律的,不是无规律的,所以我开始寻求更新简单的方法,先贴最优解,要睡觉了,我的头发啊
1 | class Solution { |
2020-01-09-RedisTransaction
官网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 | > MULTI |
可以看出EXEC返回一个数组,其中每个元素都是事务中单个命令的答复,其发出顺序与命令相同
当Reids连接处于MULTI的请求时,所有的命令都将以字符串queued答复,当EXEC时,将顺序执行
errors
可能存在两种命令错误:
- 命令可能无法排队,因此在EXEC之前可能有错误(包括命令语法错误)
- 调用EXEC后,命令执行失败
客户端通过检查已排队(queued)的命令返回值来判断第一种错误,另外从2.6.5开始,服务器将记住在命令排队期间发生的错误,并且拒绝执行事务,返回错误并自动丢弃事务
EXEC执行后错误不会特殊处理,所有的命令都将被执及时有些命令失败
1 | MULTI |
即时命令失败,队列里的其他命令也会处理
1 | { |
2020-01-08-MinimunPathSum
Leetcode-64
1 | 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. |
solution
解法为简单的动态规划,只要找到比较该元素,上方和左方的值的最小值,然后与该值相加,就可以得到解
1 | class Solution { |
2020-01-08-SortColors
Leetcode-75
1 | 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. |
solution
题目乍一看非常简单,但确实说使用简单的sort方法以及o(n^2)的排序确实会浪费时间复杂度,本着好奇心,我试了一下,果然成了吊车尾
1 | class Solution { |
该题优化的核心位置是该数组是一个一维数组,设置两个指针,左边遍历0,遇到0往左放,遇到2往右放,r和l为左右分界线,index记录最后一个0的位置
1 | class Solution { |
2020-01-07-关于Promise的思考
题目
(这道题在互联网上已经有了)
1 | 可以添加任务,任务包含任务数据,任务延迟触发的等待时间。 |
思路过程
1.Java上线
读题目就是延时队列的特征,Java有锁,有多线程,写起来多方便
1 | import java.util.concurrent.BlockingQueue; |
2.Node上线
被提醒该题目可以用node实现,且不需要借助redis来做,然后我上手就是一把操作:
1 | 'use strict' |
我以为设计的考点也就是立即执行函数,延时的使用,但是这里的for循环是个伪串行,实际上是并发的,也为第三步的修改提供了bug
3.Promise时代
一开始我是想把async函数放进去,写了如下的代码:
1 | 'use strict' |
发现代码还是串行的,然后查了一下可能的问题(以下为个人猜测,欢迎指正)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 | 'use strict' |