模式共计八种:

  • 单例模式
  • 构造器模式
  • 建造者模式
  • 代理模式
  • 外观模式
  • 观察者模式
  • 策略模式
  • 迭代器模式

设计模式的提出,为了更好的解耦,可拓展,服务可靠,不限定某种语言的实现

单例模式

概念

一个类只有一个实例,如果存在就不实例化,如果不存在则new,以保证一个类只有一个实例

作用

  • 模块间通信
  • 保证某个类的对象的唯一性
  • 防止变量污染

注意

  • this的使用
  • 闭包容易stack over flow需要及时清理
  • 创建新对象成本较高

实际案例

如网站的计数器,多线程的线程池

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
(function(){
// 养鱼游戏
let fish = null
function catchFish() {
// 如果鱼存在,则直接返回
if(fish) {
return fish
}else {
// 如果鱼不存在,则获取鱼再返回
fish = document.querySelector('#cat')
return {
fish,
water: function() {
let water = this.fish.getAttribute('weight')
this.fish.setAttribute('weight', ++water)
}
}
}
}

// 每隔3小时喂一次水
setInterval(() => {
catchFish().water()
}, 3*60*60*1000)
})()

构造器模式

Leetcode13

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: “III”
Output: 3
Example 2:

Input: “IV”
Output: 4
Example 3:

Input: “IX”
Output: 9
Example 4:

Input: “LVIII”
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 5:

Input: “MCMXCIV”
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

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
class Solution {
public int romanToInt(String s) {
int nums[]=new int[s.length()];
for(int i=0;i<s.length();i++){
switch (s.charAt(i)){
case 'M':
nums[i]=1000;
break;
case 'D':
nums[i]=500;
break;
case 'C':
nums[i]=100;
break;
case 'L':
nums[i]=50;
break;
case 'X' :
nums[i]=10;
break;
case 'V':
nums[i]=5;
break;
case 'I':
nums[i]=1;
break;
}
}
int sum=0;
for(int i=0;i<nums.length-1;i++){
if(nums[i]<nums[i+1])
sum-=nums[i];
else
sum+=nums[i];
}
return sum+nums[nums.length-1];
}
}

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];
}
}
0%