Prolem 104

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

return its depth = 3.

key

判断树的深浅，采用

int left = max(root.left);
int right = max(root.right);
return Math.max(left,right) + 1;

//或者简写

return Math.max(max(root.left) + 1, max(root.right) + 1);

进行递归

Runtime: 0 ms, faster than 100.00% of Java online submissions for Maximum Depth of Binary Tree.

Memory Usage: 39.2 MB, less than 94.62% of Java online submissions for Maximum Depth of Binary Tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
         return max(root);
    }
    public int max(TreeNode root){
        if (root == null) {
            return 0;
        }
        return Math.max(max(root.left) + 1, max(root.right) + 1);
    }
}

Problem101

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1
2
3
4
5

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

1
2
3
4
5

  1
 / \
2   2
 \   \
 3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

key

一道验证树是否是对称的问题，主要采取递归的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root,root);
    }
    public boolean isMirror(TreeNode root,TreeNode self){
        if(root==null && self==null)return true;
        if(root==null ||self==null) return false;
        return root.val==self.val && isMirror(root.left,self.right)&&isMirror(root.right,self.left);
        
    }
}

AMD:Asynchronous Module Definition (RequireJS)

CMD:Common Module Definition（SeaJS）

AMD

待补充，import-export

CMD

define Function

一个文件就是一个模块，在我们的代码外层，会套上一层CMD规范,这也就是为什么我们可以直接引用require,export,module的原因

1
2
3

define(function(require, exports, module) {
  // code
});

单个参数

1
2
3
4

define(factory)
param-->factory:funtion|Object|String
define({ "foo": "bar" });
define('I am a template. My name is {{name}}.');

多个参数define define(id?, deps?, factory)

1
2
3
4
5

define('hello', ['jquery'], function(require, exports, module) {
  // code
});
id：String模块标识
deps：Array模块依赖

define.cmd Object

1
2
3
4

if (typeof define === "function" && define.cmd) {
  // 有 Sea.js 等 CMD 模块加载器存在
}
//用来判断当前页面是否有CMD模块加载器

require Function

同步加载

1
2
3
4
5
6
7
8
9

define(function(require, exports) {

  // 获取模块 a 的接口
  var a = require('./a');

  // 调用模块 a 的方法
  a.doSomething();

});

require.async Function

异步加载

1
2
3
4
5
6
7
8
9
10
11
12
13
14

define(function(require, exports, module) {

  // 异步加载一个模块，在加载完成时，执行回调
  require.async('./b', function(b) {
    b.doSomething();
  });

  // 异步加载多个模块，在加载完成时，执行回调
  require.async(['./c', './d'], function(c, d) {
    c.doSomething();
    d.doSomething();
  });

});

require.resolve

返回解析后的绝对路径

exprots

return Object，对外提供接口

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

define(function(require, exports) {

  // 对外提供 foo 属性
  exports.foo = 'bar';

  // 对外提供 doSomething 方法
  exports.doSomething = function() {};

});

retrun可以实现同等效果
define(function(require) {

  // 通过 return 直接提供接口
  return {
    foo: 'bar',
    doSomething: function() {}
  };

});
以及个人不太喜欢的缩略写法
define({
  foo: 'bar',
  doSomething: function() {}
});

但以下写法是错误的

1
2
3
4
5
6
7
8
9

define(function(require, exports) {

  // 错误用法！！!
  exports = {
    foo: 'bar',
    doSomething: function() {}
  };

});

exports 仅仅是 module.exports 的一个引用。在 factory 内部给 exports 重新赋值时，并不会改变 module.exports 的值。因此给 exports 赋值是无效的，不能用来更改模块接口。

我说句简单的话：exports和module.exports，都是地址，指向同一个内容，如果你给exports赋值了一个新对象，他指向的内容就完全变了，和module.exprots就指向不是同一个地方了

module

modeule是一个对象，存储与当前模块相关联的一些属性和方法，默认为{}

module:function

module.id:String模块标识

module.url：String返回绝对路径（默认id=url，除非手写id）

module.dependencies:Array模块依赖

module.export:Object 大部分情况下和exports通用，但如果模块是一个类，就应该直接赋值给module.exports，这样调用就是一个类的构造器，可以直接new实例

1
2
3
4
5
6
7
8

module.exports=new Person();
const p = require(./xxx.js);
p.say();
//or
exports.p = new Person();
const {p} = require(./xxxjs);
p.say();

Problem105

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

1
2

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

key

题目是一个根据前序中序，生成二叉树的题目

前序遍历有个特点：根节点在前面，root -left-right

则遍历到3作为root，根据中序可以知道左子树是9，右子树是15 20 7

然后遍历9作为root，根据中序得到没有左子树，没有右子树

然后遍历20作为root，依次类推可以得到

1
2
3

TreeNode root = new TreeNode(rootVal);
root.left = buildTree(pre, preStart+1, preStart+len, in, inStart, rootIndex-1);
root.right = buildTree(pre, preStart+len+1, preEnd, in, rootIndex+1, inEnd);

其中insort比较好理解，确定root后

左子树在inStart, rootIndex-1之间

右子树在rootIndex+1, inEnd之间

对于presort

int len = rootIndex - inStart;获得root的左子树长度（根据中序获取rootIndex）

左子树在preStart+1, preStart+len之间

右子树在preStart+len+1, preEnd之间

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }
    public TreeNode buildTree(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd){
        if(inStart > inEnd || preStart > preEnd)
            return null;

        int rootVal = pre[preStart];
        int rootIndex = 0;
        for(int i = inStart; i <= inEnd; i++){
            if(in[i] == rootVal){
                rootIndex = i;
                break;
            }
        }

        int len = rootIndex - inStart;
        TreeNode root = new TreeNode(rootVal);
        root.left = buildTree(pre, preStart+1, preStart+len, in, inStart, rootIndex-1);
        root.right = buildTree(pre, preStart+len+1, preEnd, in, rootIndex+1, inEnd);

        return root;
    }
}

tip

参考于百度，在递归条件乱了

Problem94

Given a binary tree, return the inorder traversal of its nodes’ values.

给定一二叉树，中序遍历输出

ps:preorder,inorder,postorder，前中后

Key

recursive approach

利用递归解决B树的遍历问题，这种问题的代码其实大同小异，前中后的遍历输出，只需要调整递归部分即可

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

//preorder
public void preorder(node t)
	if (t != null) {
		System.out.print(t.value + " ");
		preorder(t.left);
		preorder(t.right);
	}
}
//inorder
public void inorder(node t)
{
	if (t != null) {
		inorder(t.left);
		System.out.print(t.value + " ");
		inorder(t.right);
	}
}
//postorder
public void postorder(node t)
{
    if (t != null) {
        postorder(t.left);
        postorder(t.right);
        System.out.print(t.value + " ");
    }
}
//leverorder

Solution

Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Inorder Traversal.

Memory Usage: 37.9 MB, less than 5.11% of Java online submissions for Binary Tree Inorder Traversal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List < Integer > res = new ArrayList < > ();
        inorder(root, res);
        return res;
    }
     public void inorder(TreeNode root, List < Integer > res) {
        if (root != null) {
            inorder(root.left, res);
            res.add(root.val);
            inorder(root.right, res);
        }
    }
}

Complexity Analysis

• Time complexity : O(n)O(n). The time complexity is O(n)O(n) because the recursive function is T(n) = 2 \cdot T(n/2)+1T(n)=2⋅T(n/2)+1.
• Space complexity : The worst case space required is O(n)O(n), and in the average case it’s O(\log n)O(logn) where nn is number of nodes.

stack

solution还提供了另外一种方法通过stack pop的方式来完成：

https://leetcode.com/problems/binary-tree-inorder-traversal/solution/

Morris

同上

I find hexo’s theme:nexT v7.7.2 has some new features

native dark mode

we can set

1

darkmode:true

to open native dark mode

and there are other features like

• support MathJax v3.0,we use $$
• add next_config helper

how to update newest version

1.git clone https://github.com/theme-next/hexo-theme-next themes/next

or in releases to download newest source code

2.copy file to hexo/theme/ such as :

/themes/hexo-theme-next-7.7.2/

3.open hexo’s _config.yml,and change theme’s value to hexo-theme-next-7.7.2 and u change your them successfully

4.update /themes/hexo-theme-next-7.7.2/_config.yml

Last , u can create new post to log your daily life

1

yarn upgrade caniuse-lite browserslist

and these days ,zehai.info ,may Expired ,sad

今天确实发生了一些事情，避之不谈

让我想起来了之前我在bili遇到的一件事情，一个up主癌症，自己经济能力不是很好，拍了一些很粗糙，没有剪辑过的视频，大意交代了自己得病，没有钱，拍了病历本，化验单，希望大家有能力的捐一点，后来up大概是拿到了一部分钱，具体多少我不太清楚，后来不知道发生了什么，画风开始转变

up视频的下面出现了很多评论

评论up有两个手机，家里有钱，然后up就对焦给大家看了他的两个手机，我记得两个都是红米类似的便宜机器，而且买了很久了

后来又人评论他家多有钱，然后up就拍下了回家和奶奶在一起的场面（当时已经没钱住院，就回家筹钱换医院试试）

后来又有人评论up主根本就没病，出来骗人钱，up就拍视频给人看治疗过程中的病历，化验单，至少我看不出来造假的证据

后来up出院了，买了张车票回家，和一个月前相比头发掉了很多，弹幕里面各种质疑，评论里面一片质疑，

亲身经历，环顾整个过程，我没有给up捐赠一分钱，也没有给予他任何帮助，就看了他整个生病的过程，从开始的加油，变成了一个‘骗子’，人们存在于网络之后，确实可以发表自己对于一件事情的看法，我想我如果是那个up，深陷其中一定很无奈

陈述结束

最后疫情一定会过去的

今天中午有收到Egg团队公开的文件调查，提及了很多技术名词，虽然不一定用到，但我也觉得列举出来会方便大家了解和比较，后续可能更新我用过的部分

代码检查工具

• ESLint
• JSCS
• JSHint
• JSDoc
• Standard
• TSLint
• Flow

使用感受

解决了以下问题

• node是一门弱语言，进行校验（非变量类型校验，仅校验变量是否声明，是否可改等）
• node在use strict模式下，eslint可以校验
• 团队合作，防止队友挖坑

其实ESLint只是一种语法校验，更多的还有流程上的规范，就像网传阿里的开发规范一样，就好比node中你可以用类的语法糖，也可以用原型，当一件事情有多种实现方式时，需要规范来选择一个普遍公用的，易维护，易扩展的方案

除去语法校验，还有TS的类型校验，比如GIT的分支规范，如master,staging,backup,develop,other branch

转义语言

• TS
• ClojureScript
• CoffeeScript
• Dart
• Elm
• Scala.js
• Haxe
• Nim
• PureScript
• Reason

转移语言是2019年聊的比较多的，解决问题：

• 类型校验，能够很好解决JS开发中，你不知道这个object里面有什么key，或者某个对象里面有什么方法（egg.js实际开发过程中，ctx.service.v1.handlexxx()就ctrl跳转不了，也不会有提示）

WEB框架

• Express
• Koa
• Egg
• Nest.js
• Next.js
• Fastify.js
• Hapi.js
• Restify.js
• Loopback.io
• Sails.js
• Midway.js

面试常被问到框架的问题，因为很多公司不会将项目搭建在原生的node服务上

• 缺少约束，合作模式下，个人有个人的风格
• 项目配置繁琐，很多东西配置零散堆放
• 重复造轮子，框架提供较好的轮子
• 安全事宜，框架处理
• etc

一个好的框架事半功倍，
express是一个非常轻量的框架

• fast
• unopinionated(干净的)
• minimalist

Egg是一个企业级框架，约定大于配置

• Provide capability to customizd framework base on Egg（可扩展）
• Highly extensible plugin mechanism（插件牛逼）
• Built-in cluster（多进程牛逼）
• Based on Koa with high performance（企业级别性能优异）
• Stable core framework with high test coverage（稳定）
• Progressive development（业务迭代，代码可以渐进继承）

数据库

• MySQL
• PostgreSql
• Redis
• MongoDB
• SQL Server
• SQLLite
• influxdb
• HBASE
• TiDB
• Oracle
• DB2

数据库是仅此于语言本身，另外的考点了，因为没有一个服务不涉猎存储，而数据库作为系统的数据基础，不仅重要也成为了面试的重点

• mysql等关系型数据库，范式，事务，innodb，读写分离，分表
• Mongo,Redis等非关系型数据基础类型，聚合等

反向代理

• Nginx

• Tomcat

• Apache

• 解决负载均衡

• 预处理一些请求，如过滤重复请求

进程管理

• Docker
• PM2
• forever
• naught
• node-supervisor
• Supervisord(Unix)

docker集大成者，在微服务等场景应用较多

RPC方式

• HTTP
• Thrift
• gRPC
• dubbo
• MQ

开发场景

• 服务端API
• SSR应用
• Proxy层
• BFF层
• 代码片段，如Spark代码片段
• CLI & 工具

tips

模式共计八种：

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

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

单例模式

概念

一个类只有一个实例，如果存在就不实例化，如果不存在则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];
    }
}