年前一个月，怎么能不跳动？

各大厂爆料不断，裁员信号到处闪烁，人心惶惶。

看到最多的一句话是：2019，保住饭碗！

裁团风波此起彼伏，有赞年会公然宣布 996，便利蜂裁员新招层出不穷，新东方的释放自我，微信、陌陌的令人羡慕……

据说 2018 是未来五年经济最好的一年，呜呼哀哉！

这是一个危机四伏的时代，同样也是一个充满机遇的时代，市场的一番大清洗将会把未来带向何处呢？

还是要保持自身的竞争力，技多不压身，仗技走天涯，学习思考不能断！

另外，保持健康最重要！2019 还是要坚持锻炼，自律。

我是 2018 年 3 月底来到现在这家公司的，也快满一年了。

很荣幸，被评为了 2018 年度最佳新人奖，也作为其中之一主持人主持了 2018 年的公司年会。

想想距离之前在大学做主持，已经过去了 5 年了，真是好快啊！

意料之中，抽奖无缘。一张来伊份购物卡，阳光普照。

年会结束跟同事又聚了下，说了不少东西。赚钱真不容易啊！

2019 年，毕业就快 2 年了，现在还是没有攒什么钱，对比别人真的感觉好失败。

打工没什么激情，创业没那个勇气，好难啊。

前段时间去看了场直火帮的现场，都市的夜晚是年轻人的狂欢。

白日里压抑的所有情绪都在夜晚爆发，肆意尖叫。

现场还是很不一样的，音乐鼓点直击心脏，就像是个泵在血海中抽放。

适当调节生活也是相当不错的。

在这里我要说说《大江大河》这部电视剧，真的很不错！

那几天一有空就看，晚上下班早早地就洗漱好躲被窝里看，本来被子就薄，还漏一个大口子，甚是好看甚是好看。

短短的电视剧中反映了很多东西，我真的是喜欢这类的作品。

例如：路遥《平凡的世界》，陈忠实《白鹿原》，余华《活着》、《兄弟》等作品。

现在怕是出不了这类大作了，时代不同了。

再过几天就回家过春节了，说到过年也是不怎么提得起兴致啊。

跟个国庆一样，回家呆一周就又得回来过上班日子了。

“回家就跟回娘家一样”难怪我爸如是说道……

谁想呢，我也不想啊，好难啊。

长大了，好多事情就自然而然变了。

小时候的过年总是伴着地上厚厚的积雪，一捆烟花棒，一盒火柴或是口袋里塞着个黑口打火机。

不一样咯。

最后，一段《站在悬崖边的我》

我站在悬崖边，视线慢慢下移
只看见一片山，飘着那一层云
都说居高思危，我却有点神往

那是一张床垫，还是一张薄纸
那下面是什么，是那汪洋大海
还是坚硬的沙石，血肉模糊

天色越来越暗，回去的路越来越糊
我站在悬崖边，开始犹豫

前方需要勇气，可能粉身碎骨
后方道路平坦，也许一世平庸

左右思索着，天却已经全黑了
我伸手，看不清楚自己的手指
一阵眩晕，脚下一滑，身体前倾

我还没来得及惊呼
眼睛就睁开了

站在悬崖边的我

全排列问题在这里有两个版本，其中略有差异。看完就会感觉似曾相识，一种莫名的熟悉感从心底喷涌上来。

第一个版本：

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

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

有什么感觉？

这不就是暗箱摸球，箱子里有不同颜色的球 n 个，列出你可能会摸出球的所有顺序，不放回。

先贴上大神的详细解析：链接

利用 List.add(int index, E element) 方法可以将元素插入指定的位置，可以满足题意。

整体分析：根据可插入的地方不同从而展开不同的分支，典型的树形结构。

代码如下：

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

public List<List<Integer>> permute(int[] nums) {

    List<List<Integer>> permutations = new ArrayList<>();
    if (nums.length == 0)
        return permutations;
    helper(nums, 0, new ArrayList<>(), permutations);
    return permutations;

}

/**
 * 
 * @param nums
 *            原数组
 * @param start
 *            选择填充数字下标
 * @param permutation
 *            单个集合
 * @param permutations
 *            目标返回集合
 */
private void helper(int[] nums, int start, List<Integer> permutation, List<List<Integer>> permutations) {

    // 满足条件添加 返回
    if (permutation.size() == nums.length) {
        permutations.add(permutation);
        return;
    }
    // 分别插入不同的位置
    for (int i = 0; i <= permutation.size(); i++) {
        // 避免在原集合上操作 需新集合
        List<Integer> newPermutation = new ArrayList<>(permutation);
        newPermutation.add(i, nums[start]);
        helper(nums, start + 1, newPermutation, permutations);
    }
}

注意每次插入前要 new 一个新集合对象，不能在原集合对象上操作。

第二个版本：

1
2
3
4
5
6
7
8
9
10
11

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

与第一个版本区别是：该版本数组中可以有重复元素，且返回的集合中不能有重复的元素（即重复的集合排列顺序）。

去重，我首先想到的是这样：不管你序列中有没有重复的数字，我就当满足条件的时候判断下是否已经存过了该排列顺序不就行了。

然后我就将使用过的数字全都按顺序拼接成字符串，too young …

指定位置插入元素，List 很好实现，可是 String 怎么办。方法肯定有啊，比如每个元素之间用自定义分隔符拼接，再转成数组找到指定的位置插入，再转。只要功夫深，铁杵磨成针。可是麻烦啊，算暴力解法，遂弃之。

解题代码如下：

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

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> permuteUniques = new ArrayList<>();
    if (nums == null || nums.length == 0)
        return permuteUniques;
    // 要去重 先排序
    Arrays.sort(nums);
    boolean[] used = new boolean[nums.length];
    dfs(nums, used, permuteUniques, new ArrayList<>());
    return permuteUniques;
}

/**
 * 
 * @param nums
 *            原数组
 * @param used
 *            标记数字使用状态
 * @param permuteUniques
 *            目标集合
 * @param permuteUnique
 *            单个集合
 */
private void dfs(int[] nums, boolean[] used, List<List<Integer>> permuteUniques, List<Integer> permuteUnique) {
    if (permuteUnique.size() == nums.length) {
        permuteUniques.add(new ArrayList<>(permuteUnique));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) // 已经标记过的略过
            continue;
        // 数字有重复的 说明刚释放的值与该值一样 略过
        if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1])
            continue;
        used[i] = true; // 标记使用
        permuteUnique.add(nums[i]); // 该数字加入集合
        // 重复操作 选择剩余数字
        dfs(nums, used, permuteUniques, permuteUnique);
        // 当出栈时将最后一个数从集合中删除 同时该数恢复未使用状态 继续操作
        used[i] = false;
        permuteUnique.remove(permuteUnique.size() - 1);
    }

}

由于要去重，所以先将数组排序。与第一版本的大致思路一样，遍历数组将未标记的值插入。

1
2

if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) // 数字有重复的 说明刚释放的值与该值一样 略过
    continue;

这行代码至关重要，与出栈时候的 used[i] = false; 相对应，实现了重复操作不执行的功能。

同样，permuteUniques.add(new ArrayList<>(permuteUnique)); 也是需要 new 一个新对象塞入。

想直接要源码的，点这里。

简介

Sharding-JDBC 定位为轻量级 Java 框架，在 Java 的 JDBC 层提供的额外服务。 它使用客户端直连数据库，以 jar 包形式提供服务，无需额外部署和依赖，可理解为增强版的 JDBC 驱动，完全兼容 JDBC 和各种 ORM 框架。

• 适用于任何基于 Java 的 ORM 框架，如：JPA, Hibernate, Mybatis, Spring JDBC Template 或直接使用 JDBC
• 基于任何第三方的数据库连接池，如：DBCP, C3P0, BoneCP, Druid, HikariCP 等
• 支持任意实现JDBC规范的数据库。目前支持 MySQL，Oracle，SQLServer 和 PostgreSQL

前言

本例只是简单实现了 Sharding-JDBC 中的读写分离功能，请注意。

所用到的技术栈及版本：

• SpringBoot 2.0.4
  • Spring Data JPA
  • HikariDataSource
  • Gson 2.8.5
  • lombok 1.16.22
  • mysql-connector-java 5.1.46
• sharding-jdbc-core 2.0.3

主要部分

配置文件：application.yml

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

# JPA
spring:
  jpa:
    show-sql: true
    database-platform: org.hibernate.dialect.MySQL5InnoDBDialect
    hibernate:
      ddl-auto: create

# Server
server:
  port: 8888

# Sharding JDBC
sharding:
  jdbc:
    data-sources:
      ds_master:
        type: com.zaxxer.hikari.HikariDataSource
        driver-class-name: com.mysql.jdbc.Driver
        jdbc-url: jdbc:mysql://localhost:3306/master?characterEncoding=utf8&useSSL=false
        username: root
        password: root
      ds_slave:
        type: com.zaxxer.hikari.HikariDataSource
        driver-class-name: com.mysql.jdbc.Driver
        jdbc-url: jdbc:mysql://localhost:3306/slave?characterEncoding=utf8&useSSL=false
        username: root
        password: root
    master-slave-rule:
      name: ds_ms
      master-data-source-name: ds_master
      slave-data-source-names: ds_slave
      load-balance-algorithm-type: round-robin

这里用的是 springboot2.0 默认的数据库连接池 HikariDataSource

• load-balance-algorithm-type：
  查询时的负载均衡算法，目前有2种算法，round_robin（轮询）和random（随机）
• master-data-source-name： 主数据源名称
• slave-data-source-names： 从数据源名称 多个用逗号隔开

存放数据源数据：ShardingMasterSlaveConfig.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

package com.example.shardingjdbc.config;

import java.util.HashMap;
import java.util.Map;

import org.springframework.boot.context.properties.ConfigurationProperties;

import com.zaxxer.hikari.HikariDataSource;

import io.shardingjdbc.core.api.config.MasterSlaveRuleConfiguration;
import lombok.Data;

/**
 * 存放数据源
 * 
 * @author ffj
 *
 */
@Data
@ConfigurationProperties(prefix = "sharding.jdbc")
public class ShardingMasterSlaveConfig {

    private Map<String, HikariDataSource> dataSources = new HashMap<>();

    private MasterSlaveRuleConfiguration masterSlaveRule;
}

用了 Lombok 显得简便了些

配置数据源：ShardingDataSourceConfig.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

package com.example.shardingjdbc.config;

import java.sql.SQLException;
import java.util.HashMap;
import java.util.Map;

import javax.sql.DataSource;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.autoconfigure.condition.ConditionalOnProperty;
import org.springframework.boot.context.properties.EnableConfigurationProperties;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

import com.zaxxer.hikari.HikariDataSource;

import io.shardingjdbc.core.api.MasterSlaveDataSourceFactory;

/**
 * 配置数据源详细信息
 * 
 * @author ffj
 *
 */
@Configuration
@EnableConfigurationProperties(ShardingMasterSlaveConfig.class)
@ConditionalOnProperty({ "sharding.jdbc.data-sources.ds_master.jdbc-url",
        "sharding.jdbc.master-slave-rule.master-data-source-name" })
public class ShardingDataSourceConfig {

    private static final Logger log = LoggerFactory.getLogger(ShardingDataSourceConfig.class);

    @Autowired(required = false)
    private ShardingMasterSlaveConfig shardingMasterSlaveConfig;

    /**
     * 配置数据源
     * 
     * @return
     * @throws SQLException
     */
    @Bean("dataSource")
    public DataSource masterSlaveDataSource() throws SQLException {
        shardingMasterSlaveConfig.getDataSources().forEach((k, v) -> configDataSource(v));
        Map<String, DataSource> dataSourceMap = new HashMap<>();
        dataSourceMap.putAll(shardingMasterSlaveConfig.getDataSources());
        DataSource dataSource = MasterSlaveDataSourceFactory.createDataSource(dataSourceMap,
                shardingMasterSlaveConfig.getMasterSlaveRule(), new HashMap<>());
        log.info("masterSlaveDataSource config complete！！");
        return dataSource;
    }

    /**
     * 可添加数据源一些配置信息
     * 
     * @param dataSource
     */
    private void configDataSource(HikariDataSource dataSource) {
        dataSource.setMaximumPoolSize(20);
        dataSource.setMinimumIdle(5);
    }
}

主要的配置内容就是这些了，接下来我们编写几个方法来测试。

测试

• 先创建一个实体类

大众测试实体类，我选 UserEntity:

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

package com.example.shardingjdbc.entity;

import java.io.Serializable;

import javax.persistence.Column;
import javax.persistence.Entity;
import javax.persistence.Id;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

/**
 * 测试用户类
 * 
 * @author ffj
 *
 */
@AllArgsConstructor
@NoArgsConstructor
@Data
@Entity(name = "user")
public class UserEntity implements Serializable {

    /**
     * 
     */
    private static final long serialVersionUID = -6171110531081112401L;
    @Id
    private int id;
    @Column(length = 32)
    private String name;
    @Column(length = 16)
    private int age;

}

同样，Lombok 不可少。由于之前 application.yml 中 ddl-auto 设置的是 create，所以每次重启程序都会重新生成空表。

• 我选择 JPA 的原因就是它作为简单测试最适合不过了

  1 2 3 4 5 6 7 8 9 10

  package com.example.shardingjdbc.repository; import org.springframework.data.jpa.repository.JpaRepository; import com.example.shardingjdbc.entity.UserEntity; public interface UserRepository extends JpaRepository<UserEntity, Integer> { }

  只要继承 JpaRepository 就可以了，我们只需要使用它的基本方法即可。

• 写个 Controller 类

  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

  package com.example.shardingjdbc.controller; import java.util.List; import javax.annotation.Resource; import org.springframework.web.bind.annotation.PostMapping; import org.springframework.web.bind.annotation.RestController; import com.example.shardingjdbc.entity.UserEntity; import com.example.shardingjdbc.service.UserService; import com.google.gson.Gson; /** * 用户测试类 * * @author ffj * */ @RestController public class UserController { @Resource private UserService userService; @PostMapping("/save") public String saveUser() { UserEntity user = new UserEntity(1, "张三", 22); userService.saveUser(user); return "success"; } @PostMapping("/getUser") public String getUsers() { List<UserEntity> users = userService.getUsers(); return new Gson().toJson(users); } }

  Service 就不贴了，就是简单调用。

方便查看测试结果，这里用 Gson 来转化为 Json 输出。

• 启动程序

从上到下看启动日志：

1
2
3
4
5

2018-12-27 15:16:12.907  INFO 2940 --- [           main] com.zaxxer.hikari.HikariDataSource       : HikariPool-1 - Starting...
2018-12-27 15:16:13.132  INFO 2940 --- [           main] com.zaxxer.hikari.HikariDataSource       : HikariPool-1 - Start completed.
2018-12-27 15:16:13.141  INFO 2940 --- [           main] com.zaxxer.hikari.HikariDataSource       : HikariPool-2 - Starting...
2018-12-27 15:16:13.147  INFO 2940 --- [           main] com.zaxxer.hikari.HikariDataSource       : HikariPool-2 - Start completed.
2018-12-27 15:16:13.148  INFO 2940 --- [           main] c.e.s.config.ShardingDataSourceConfig    : masterSlaveDataSource config complete

可以看出有两个数据源，没毛病。

1
2

Hibernate: drop table if exists user
Hibernate: create table user (id integer not null, age integer, name varchar(32), primary key (id)) engine=InnoDB

程序启动 user 表重建，没毛病。

1
2
3
4
5

2018-12-27 15:16:15.198  INFO 2940 --- [           main] o.s.w.s.handler.SimpleUrlHandlerMapping  : Mapped URL path [/**] onto handler of type [class org.springframework.web.servlet.resource.ResourceHttpRequestHandler]
2018-12-27 15:16:15.550  INFO 2940 --- [           main] o.s.j.e.a.AnnotationMBeanExporter        : Registering beans for JMX exposure on startup
2018-12-27 15:16:15.587  INFO 2940 --- [           main] o.s.b.w.embedded.tomcat.TomcatWebServer  : Tomcat started on port(s): 8888 (http) with context path ''
2018-12-27 15:16:15.591  INFO 2940 --- [           main] c.e.s.ShardingJdbcApplication            : Started ShardingJdbcApplication in 5.36 seconds (JVM running for 5.725)
2018-12-27 15:16:15.592  INFO 2940 --- [           main] c.e.s.ShardingJdbcApplication            : ----------启动成功----------

端口为配置文件中指定的 8888，启动成功日志打印，也没毛病，成功。

注意：启动程序前别忘了先自行创建数据库！

现在我们在 slave 库中执行以下提供的 sql 文件，或者自行创建对应表（表结构必须一致，可以先建库然后从主库中复制已生成的表），并在其中添加数据。

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

/*
Navicat MySQL Data Transfer

Source Server         : localhost
Source Server Version : 50720
Source Host           : localhost:3306
Source Database       : slave

Target Server Type    : MYSQL
Target Server Version : 50720
File Encoding         : 65001

Date: 2018-12-27 16:23:00
*/

SET FOREIGN_KEY_CHECKS=0;

-- ----------------------------
-- Table structure for user
-- ----------------------------
DROP TABLE IF EXISTS `user`;
CREATE TABLE `user` (
  `id` int(11) NOT NULL,
  `age` int(11) DEFAULT NULL,
  `name` varchar(32) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

-- ----------------------------
-- Records of user
-- ----------------------------
INSERT INTO `user` VALUES ('2', '23', '李四');

好了，从库中表和数据都有了，进入正题。

• 测试主库插入数据
  我用的是 Postman ：选择 POST 方式，url：localhost:8888/save，点击 Send。

  1	Hibernate: insert into user (age, name, id) values (?, ?, ?) // 打印出这条日志

  返回 success，成功执行。查看主数据库中 user 表数据，确实插入，成功！

• 测试从库查询数据
  还是 Postman ：选择 POST 方式，url：localhost:8888/getUser，点击 Send。

  1	Hibernate: select userentity0_.id as id1_0_, userentity0_.age as age2_0_, userentity0_.name as name3_0_ from user userentity0_ // 打印出这条日志

  返回： [{"id":2,"name":"李四","age":23}]，数据正确，成功！

以上就是 SpringBoot2.0 + ShardingJDBC 实现数据库读写分离的全部内容了。

参考博文

• springboot2.0中用sharding-jdbc实现读写分离，集成Druid
• Spring Boot中整合Sharding-JDBC读写分离示例

你好，依旧 此篇作为对 2018 的整年回顾

尾巴，走了；你好，依旧。

2018 的尾巴已经来到，也是到了时候该让她的尾巴跟头部围成一个圈圈了。

2018，看过几场电影，吃过几场温馨的饭，睡过几场懒觉，看过几次凌晨的星空。

2018，分过一次手，游过几次怪味的泳，红过几次眼，回过不超五次的家。

2018，我重新拾起了运动，不为别的，只为自己能够多活两年。

2018，我重新调整了饮食，却始终调不过来作息。

2018，我看了好多书，有科幻代表《三体》，有经典散文集《自在独行》，有轻描淡写一生历程的《浮生六记》，也有极具讽刺的《兄弟》等等。当然，专业书籍也不能拉下。我自知是个爱书之人，我爱看书与爱看电影是一回事，都是喜欢故事，喜欢在这些源于生活中而来的作品之间，有所感悟，体会情愫。我想，这与我善于思考，善于总结，有些许相关吧。最近在看《城南旧事》。

今年 3 月，我换了份工作，因此也搬了个新的住处。很幸运，两位室友人很不错，还都是个硕士生，与优秀的人一同来往，谁人不喜欢呢？期间我还买了个方形玻璃缸，作为我那鳄龟的新住处（去年 8 月份买的两只苗子，现在只剩一只，长得倍儿快！有时间我可再另开一篇来专门絮叨絮叨）。后觉着这么个大缸就供着个龟大爷，浪费至极。于是我之后又陆陆续续往里丢过虾（包含着龙虾）、泥鳅，可几日后往往就不见其踪影，只有可怜的残骸在水中无目的晃荡。我不甘心，10 月份左右又进购了一批草金苗，大约五六十只。直到今日，12 月中旬，还剩下 7 只幸运儿，不知是否因为这气温影响了龟爷，还是幸运儿的过人闪躲之处，或是他们惺惺相惜，已成为了朋友？我不得知，我只知三天两头给它喂食鸡肉，应该是饿不着它的吧。话说幸运儿草金们，其中有两三条我甚是得意，身上条纹十分漂亮，尾巴又大又长，要是最终也遭遇不幸，我怕是会难过会后悔吧。可是，住所实在是小，我还能做些什么呢？我喜欢各种宠物，本想养猫养狗，一想处境，我便立刻就会打消这种不实际的念头，这也是我选择养龟的原因吧。

由于换了份工作，该司并非互联网公司，工作强度自然也没有那么大。也正是因为如此，我有了更多的时间能做我自己喜欢做的事情，就比如看书，跑步。独处的日子，看书是最好的项目了。晚上我也有了时间自己随意煮煮蔬菜，煮煮鸡胸，煮煮面条，健康又便宜，因此还与菜场的大爷变得熟知。虽然这种生活长期也不错，但是我是知道的，我是不愿意的。在这段时间里，我有了时间可以巩固基础，有了时间可以学习其他的东西，有了时间可以将之前未完全消化的东西一一吸干。我并没忘给自己充电，虽然也看了不少非专业书籍，但是那也是必要的，那些充实了我的灵魂，渐渐造就了我的气质，每每读完一本书我都有所收获。厚积而薄发，我一直在等待它的到来！

我在以前的随记中写过：时间往往在你回顾的时候，才会觉得过得好快。我也写过：原来我早已习惯了孤独，只是在孤独的岁月之中穿插了一段不那么孤独的时光，使我暂忘孤独。一个人的时候，往往会思考更多。虽说人类是群居动物，但是现在正慢慢走向独居世界，与外界网络相连即可。人们经常会畅想未来，畅想未来会变得多么科幻多么神奇多么智能，无可厚非，因为过去几年我们确实是发展可谓“神速”。但是我在想，过去是因为西方的互联网本就比中国发展要快，所以中国可以借鉴西方来避坑，从而快速发展。而如今，中国互联网已是首屈一指，无从可借鉴，只能我们自己一步一脚印来创新推进。畅想固然是好，人们也都想时代发展越快越好，可是我个人觉得还是不能太过于“妄想”，没必要过于急躁，就怕大家都在畅想美好未来的时候，天突然就塌了。当然，这也是我个人想法，磨刀不误砍柴工，美好生活人人都想，前提还是应脚踏实地。

也是在今年，租了服务器，重新注册了域名，搭建了自己的个人博客，开始了持续的记录总结。简书却是我最近才注册的，不为别的，我只想把一些生活感悟、牢骚，在这记录，也只会记录这些。从今年开始，每月我在自己博客都会写上一篇月结记录，初衷是为了让自己觉得过得不会那么虚空，同样更重要的是为了记录我的岁月。为了这些宝贵资料不丢失，我也做了备份。曾经，年少气盛的我丢失过许多美好记忆的书信，使得现在我都后悔不已，这些都是属于我们独一无二的财富。生活无远虑，只有近忧。不管如何，我们都要学会记录生活，也许也许，终有一日我也会有个幸福的家庭，子孙后辈也会静静坐在身边听一个糟老头子讲述他的过往。

犹记得去年 12 月底与朋友们欢聚苏州，共游园林。今年怕是没有机会了，前几日刚好去杭州出差，两位好友在杭州做事，便约出来一同吃了顿饭。这顿饭，我们吃了半小时，等了却将近两小时。那几日刚好是今年雪下得最大的日子，又正值周末，饭点，想想也难免。吃完后各自回府，下了地铁我本想打车，无奈道路积雪严重，天气恶劣。于是在等了十几分钟出租车后，我撑着小黑伞，踩着雪地，走了两三公里回到了宾馆，小黑伞已早成了小白伞了。距离毕业已过去了一年有余，大家身上也都多了一丝成熟稳重，几日前我还翻了下毕业相册，嗯，变化大倒是不大，就是头发好像都少了一些！

2018，我放慢了工作节奏，给了自己更多的时间去回顾，去务实基础，博观约取，厚积薄发！

2018，我同时也加强了锻炼，没有一个好身体将来又怎么能够撑得起一番事业！

2018，是积累的一年，寒冬虽冷，却总有见到明媚一天的啊！

你好，19！

住在对面的居民，我想与我这边环境也相似，只是人口数量略有差异。

有段时间，每晚下班我进房间打开房灯，第一件事就是站在窗外静静的看着对面的居民们。因为是老式小区，楼层不高，每栋之间的间隔也不大，看不清对面的模样但至少看得清对面的举动。

住在对面的居民，每户人家做的事皆不相同，作息时间皆不相同，窗外布置也是皆不相同。有时我就呆呆的站在那看，不知为什么，我就是能呆呆的站在那看。

住在对面的居民，能看见内部情况的户数不多，却给我有种人生百态的感觉。我想这也是吸引我的原因，是我在此执笔想要记录的原因吧。

住在对面楼斜上角的住户，是一家三口。看不清他们具体模样，只是知道小孩还小，还不会走路。往往见到他们都是在轮流抱着孩子，哄着睡觉，经常就是一哄一两个小时。当小孩入睡后，夫妻俩才开始走到厨房，不知是洗吃完饭后的碗筷还是才开始动手做饭。

住在夫妻俩下两层的是一位好学之人，对其的了解甚少，因为当我驻窗前“偷窥”时，他八成是坐在桌前，也只有桌前那扇窗没拉窗帘。由于晚上视线昏暗加之一定的观察距离，我只知他是位男性，大多独自一人坐在桌前，看书或是写字，我便看不大清了。纵上观之，好学之人，那是定错不了的了。

住在正对面楼偏上一点的是一个大家庭，观察至今我看到出现过一个老头、一个老太、还有较之年轻的一男一女。因为楼层的原因，我只能看到其窗外晾晒的衣物，无法窥视到内部的情形。只是有时能看到一男的或是女的走过来拉上窗户，拉上窗帘，像似要与外界隔绝，美美地做个美美的梦。有个周末，我坐在床上看着投影中的电影，眼睛往窗外一瞥，霎时汗毛直立。待我定睛瞧时，原来是这户窗外挂了个人形玩偶在那晾晒，好不瘆人。

住在对面稍偏右下的一个小房间里住着一个人，应该是男性。经常看他坐在电脑桌前，毛玻璃的蒙眬使我看不清他在键盘上的手速，但我想，那定是青轴。偶尔起身，那便应该是尿意来袭或是口干舌燥了吧。

再往右数米处有间房间最近一直在粉刷装修，往往十一二点还能见到粉刷匠在吊灯下的身影。背后有个美满的家庭，再多的重担肩上扛着，脸上还是挂着幸福的笑容。

再往上一点有个房间好像是个女性独处，有次晚上偶尔看到其窗帘未拉上，她正趴在床上玩手机，还是毛玻璃蒙眬，也许是男性也说不准。后来我每每往那边瞧时，皆是漆黑一片。恐是精神作祟？好不瘆人。

前些日子降了几场大雪，我去杭州出差那几日正是雪下得最大的时候。出门时撑的是黑伞，没过几分钟便已是白伞了。一夜过后，清晨出门，看着路边单车坐垫上足足有五六公分积雪，已是多少年没下过如此大雪了。犹记得儿时，记忆中的过年都是在厚厚的白雪上渡过。那时我们喜欢玩鞭炮，点火花棒在空中使劲了甩，不像如今，我们老家已经禁炮许多年了。都说现在过年越来越没有年味儿了，不是年味儿它消失了，是我们不知觉中已然长大。

忙碌，如今整日忙碌，却有时又不知到底在忙碌些什么。我们不妨自己找个时间，静静呆会，可以看看月亮看看星星，看看过往的路人，也可以跟我一样看看住在对面的居民。

Life is like a box of chocolate,you never know what you are going to get.

共勉。

看标题不知是否让您想起了有向图中的最短路径，是有些许类似，不过该题比其更简单更加清晰、直观、好理解。相信您看完这个之后，脑回路肯定更加的明亮！

题目描述如下：

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

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（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
25
26
27
28
29
30
31
32
33
34
35
36
37
38

int size = 0;
TreeSet<Integer> ts = new TreeSet<>();
List<List<Integer>> list;

/**
 * 超时
 * 
 * @param triangle
 * @return
 */
public int minimumTotal(List<List<Integer>> triangle) {
    list = triangle;
    size = triangle.size();
    if (size == 0)
        return 0;

    helper(0, 0, 0);
    return ts.first();
}

/**
 * 
 * @param row
 *            行数
 * @param index
 *            在该行中下标
 * @param sum_length
 *            路径之和
 */
private void helper(int row, int index, int sum_length) {
    if (row >= size) {
        ts.add(sum_length);
        return;
    }
    sum_length += list.get(row).get(index);
    helper(row + 1, index, sum_length);
    helper(row + 1, index + 1, sum_length);
}

是的，代码没有问题，可是拿去跑的时候，数据较大的测试用例却给了一个大红色的 超出时间限制。这里将 TreeSet 换成一个 MIN_LENGTH 整型变量每次进行比较取较小值，结果一样，都是超时。

本来是满怀欣喜，豪气撸码，结果给撞了个豆腐墙。

墙不硬，问题不大。我们换个思路，再摸摸青青草地。

以往出现这种求最小值、最大值啊，需要数据之间相关联相加减乘除的啊，用的都是 DP 居多啊！

脑浆乍现，回路高速擦亮，越擦越亮，越擦越闪，终于“吡”得一身，为数不多的小草又飘下几根，成了！

我也不用额外的空间了，就在你身上肆虐！

再回头看下那个“三角形”：

1
2
3
4
5
6

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

既然是要一个最小值，那我就逐步缩减法，自下而上攻之。

根据题目要求我们知道如果上一行的元素下标为 i，那它只能跟它下一行的下标为 i 和 i+1 两元素相加。当然，我们只需要这两者的较小值。

即：

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

 [6,5,7]   // i 行
[4,1,8,3]  // j 行

以这两行为例 （条件：j = i + 1）

i 行中的 6 可以跟 j 行中的 4 或者 1 相加，由于我们结果取的是最小值，所以我们只留较小值
6 + 4 = 10, 6 + 1 = 7
因为 10 > 7，所以 i 行中的 6 我们就随之替换为 7

剩余元素同理，i 行最终便成了：
[7,6,10]

再由此，层层攻上。随着数量越来越少，最终顶上的那位佼佼者便是我们要取的首级！

武器献之：

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

/**
 * DP
 * 
 * @param triangle
 * @return
 */
public int minimumTotal(List<List<Integer>> triangle) {

    // 从倒数第二行开始往上走
    for (int i = triangle.size() - 2; i >= 0; i--) {
        // 从每行的起始下标开始直到 i
        for (int j = 0; j <= i; j++) {
            // i 行 j 下标的值
            int self = triangle.get(i).get(j);
            // 将 i 行 j 下标的值赋为 ： i 行 j 下标的值 与 i+1 行 j 下标和 j+1 下标值之和的较小值
            triangle.get(i).set(j,
                    Math.min(triangle.get(i + 1).get(j) + self, triangle.get(i + 1).get(j + 1) + self));
        }
    }
    // 层层往上 顶层值便是路径最小值
    return triangle.get(0).get(0);
}

这道题容易理解，对 DP（动态规划） 会有一个较为清晰的认知，我认为还是很不错的，故特意整理之。

文笔不好，望见谅！ End.

代码编译的结果从本地机器码转变为字节码，是存储格式发展的一小步，却是编程语言发展的一大步。

概述

执行引擎是 Java 虚拟机最核心的组成部分之一。在不同的虚拟机实现里面，执行引擎在执行 Java 代码的时候可能会有解释执行（通过解释器执行）和编译执行（通过即时编译器产生本地代码执行）两种选择，也可能两者兼备，甚至还可能会包含几个不同级别的编译器执行引擎。

但从外观上看起来，所有的 Java 虚拟机的执行引擎都是一致的：输入的是字节码文件，处理过程是字节码解析的等效过程，输出的是执行结果。接下来将主要从 概念模型的角度来总结下虚拟机的 方法调用和 字节码执行。

运行时栈帧结构

栈帧是用于支持虚拟机进行方法调用和方法执行的数据结构，它是虚拟机运行时数据区中的虚拟机栈的栈元素。每一个方法从调用开始至执行完成的过程，都对应着一个栈帧在虚拟机栈里面从入栈到出栈的过程。

每一个栈帧都包括了局部变量表、操作数栈、动态连接、方法返回地址和一些额外的附加信息。在编译程序代码的时候，栈帧中需要多大的局部变量表，多深的操作数栈都已经完全确定了，并且写入到方法表的 Code 属性之中，因此，一个栈帧需要分配多少内存，不会受到程序运行期变量数据的影响，而仅仅取决于具体的虚拟机实现。

局部变量表

局部变量表是一组变量值存储空间，用于存放方法参数和方法内部定义的局部变量。它的容量以变量槽（Variable Slot，下称 Slot）为最小单位。

在方法执行时，虚拟机是使用局部变量表来完成参数值到参数变量列表的传递过程的，如果执行的是实例方法（非 static 的方法），那局部变量表中第 0 位索引的 Slot 默认是用于传递方法所属对象实例的引用，在方法中可以通过关键字 this 来访问到这个隐含的参数。其余参数则按照参数表顺序排列，占用从 1 开始的局部变量 Slot，参数表分配完毕后，再根据方法体内部定义的变量顺序和作用域分配其余的 Slot。

局部变量定义了但没有赋初始值，是不能使用的，切记！

操作数栈

操作数栈也常称为操作栈，它是一个后入先出栈。同局部变量表一样，它的最大深度也是在编译时就写入到 Code 属性的 max_stacks 数据项中。

当一个方法刚刚开始执行时，这个方法的操作数栈是空的，在方法的执行过程中，会有各种字节码指令往操作数栈中写入和提取内容，也就是出栈 / 入栈操作。如：在做算术运算的时候是通过操作数栈来进行的，又或者在调用其他方法的时候是通过操作数栈来进行参数传递的。

动态连接

每个栈帧都包含一个指向运行时常量池中该栈帧所属方法的引用，持有这个引用是为了支持方法调用过程中的动态连接。

字节码中的方法调用指令就以常量池中指向方法的符号引用作为参数。这些符号引用一部分会在类加载阶段或者第一次使用的时候就转化为直接引用，这种转化称为 静态解析。另外一部分将在每一次运行期间转化为直接引用，这部分称为 动态连接。

方法返回地址

当一个方法开始执行后，只有两种方式可以退出这个方法：

• 执行引擎遇到任意一个方法返回的字节码指令，这时候可能会有返回值传递给上层的方法调用者，是否有返回值和返回值的类型将根据遇到何种方法返回指令来决定，这种退出方法的方式称为正常完成出口。
• 在方法执行过程中遇到了异常，并且这个异常没有在方法体内得到处理，无论是 Java 虚拟机内部产生的异常还是代码中使用 athrow 字节码指令产生的异常，只要在本方法的异常表中没有搜索到匹配的异常处理器，就会导致方法退出，这种退出方法的方式称为异常完成出口。

一个方法使用异常完成出口的方式退出，是不会给它的上层调用者产生任何返回值的。

方法退出的过程实际上就等同于把当前栈帧出栈，因此退出时可能执行的操作有：恢复上层方法的局部变量表和操作数栈，把返回值（如果有的话）压入调用者栈帧的操作数栈中，调整 PC 计数器的值以指向方法调用指令后面的一条指令等。

附加信息

虚拟机规范允许具体的虚拟机实现增加一些规范中没有描述的信息到栈帧之中，例如与调试相关的信息，这部分信息完全取决于具体的虚拟机实现。

在实际开发中，一般会把动态连接、方法返回地址与其他附加信息全部归为一类，称为栈帧信息。

方法调用

方法调用并不等同于方法执行，方法调用阶段唯一的任务就是确定被调用方法的版本（即调用哪一个方法），暂时还不涉及方法内部的具体运行过程。

一切方法调用在 Class 文件里面存储的都只是符号引用，而不是方法在实际运行时内存布局中的入口地址（相当于之前说的直接引用）。

解析

调用目标在程序代码写好、编译器进行编译时就必须确定下来。这类方法的调用称为解析。

在 Java 虚拟机里面提供了 5 条方法调用字节码指令：

• invokestatic：调用静态方法
• invokespecial：调用实例构造器 <init> 方法、私有方法和父类方法
• invokevirtual：调用所有的虚方法
• invokeinterface：调用接口方法，会在运行时再确定一个实现此接口的对象
• invokedynamic：先在运行时动态解析出调用点限定符所引用的方法，然后再执行该方法，在此之前的 4 条调用指令，分派逻辑是固化在 Java 虚拟机内部的，而 invokedynamic 指令的分派逻辑是由用户所设定的引导方法决定的

只要能被 invokestatic 和 invokespecial 指令调用的方法，都可以在解析阶段中确定唯一的调用版本，符合这个条件的有静态方法、私有方法、实例构造器和父类方法 4 类。它们在类加载的时候就会把符号引用解析为该方法的直接引用，称为 非虚方法。其余的称为 虚方法。

final 方法是一种非虚方法。

分派

静态分派

Human man = new Man()

上面代码中的 Human 称为变量的静态类型，或是外观类型，Man 称为变量的实际类型。静态类型和实际类型在程序中都可以发生一些变化，但是静态类型的变化仅仅在使用时发生，变量本身的静态类型不会被改变，并且最终的静态类型是在编译期可知的；而实际类型变化的结果在运行期才可确定，编译器在编译程序时并不知道一个对象的实际类型是什么。

编译器在重载时是通过参数的静态类型而不是实际类型作为判断依据的，所以，两个静态类型相同但实际类型不同的变量，在编译阶段，Javac 编译器会根据参数的静态类型决定使用哪一个重载版本。

动态分派

我们先说说重写，重写与动态分派关系密切。invokevirtual 指令执行是在 运行期确定接收者的实际类型，所以调用中的 invokevirtual 指令把常量池中的类方法符号引用解析到了不同的直接引用上，这个过程就是 Java 语言中方法重写的本质。

我们把这种在运行期根据实际类型确定方法执行版本的分派过程称为动态分派。

单分派与多分派

方法的接收者与方法的参数统称为方法的宗量，根据分派基于多少种宗量，可以将分派划分为单分派和多分派两种。

单分派是根据一个宗量对目标方法进行选择，多分派是根据多于一个宗量对目标方法进行选择。

基于栈的字节码解释执行引擎

探讨虚拟机是如何执行方法中的字节码指令的。

解释执行

Java 语言中，Javac 编译器完成了程序代码经过词法分析、语法分析到抽象语法树，再遍历语法树生成线性的字节码指令流的过程。因为这一部分动作是在 Java 虚拟机之外进行的，而解释器在虚拟机的内部，所以 Java 程序的编译就是半独立的实现。

基于栈的指令集与基于寄存器的指令集

基于栈的指令集主要优点就是可移植，还可把一些访问频繁的数据放到寄存器中获取尽量好的性能，代码会相对更加紧凑，编译器实现更加简单等。

栈架构指令集的主要缺点是执行速度相对来说会稍慢一些，完成相同功能所需的指令数量较寄存器架构多，频繁的栈访问导致频繁的内存访问。

End.

这个十一月为什么说忙碌呢，因为忙着抽纸巾擤鼻涕，感冒了；因为忙着买买买，剁手了；因为忙着来来回回，出差了。

• 感冒

怪我，都怪我，前一段时间温差变化大，我懒啊，没及时加被子，还没穿裤子就睡了，半夜那个冻的，知道冷但就是没爬起来加被子，然后，感冒了一周，鼻子都搞破皮了……

后来晚上还去夜跑，跑完当时感觉好点了，结果洗了个澡之后，鼻涕又来了，睡觉时候那个呼吸难受的啊，还好我床头纸管够……

• 买买买

最近买了不少东西，买了件大衣，结果稍稍大了点，不换了吧来来回回的，凑活穿。还买了几双鞋，什么耐克阿迪的，便宜的太丑，好看的太贵还没货，倒是对彪马越来越感兴趣，价格还行，款式也还行（不还是因为较之便宜嘛……）。

气的是有双鞋刚买了不到一个月就又看到大降价，差了一百来块呢，唉，安慰自己毕竟早穿上了这么多天呢不是……

平时感觉穿的也都有，但是人嘛，喜新厌旧，而且这个购物啊，确实是精神上不一样啊，单身狗的刺激手段之一了，避免一直陷在麻木的生活状态之中。偶尔还是需要精神刺激的，啊，好疼~

搞了套迪卡侬的运动装备，迪卡侬性价比真高，懊恼自己以前怎么不去了解，东西感觉都不错，大赞！以后运动装备就尽量选择迪卡侬了。

• 金链子

去年就跟老姐说过今年要给老妈买条大金链子的，身上什么首饰也没有，着实不好了点。故趁着发工资了，给老姐打过去 2000 块，“给老妈买条大金链子！其余的你补上！”哈哈，2000 肯定是不够买的，怪儿子出门在外没挣到什么钱，心意到了啊。回头给老爸搞双皮鞋，本来是去年买的，唉，加油加油！

说到金，家里爷爷还留给我一个纯金戒指来着。小时候我看着那戒指，心想，这纯金戒指，得值多少钱啊。现在知道了，也就值个千把块钱……还用来传家呢……看什么时候给它化了，弄成其他的，金戒指也忒俗气了些。

• 路上姑娘

今儿早又看到这姑娘了，所以我才把这提上来。

姑娘长发小脸，笑意浓浓，纤细身材，气质不凡。

我们往往是在五角场附近相遇的。我骑着车，她低着头。

虽然我看她时她没看过我，但我却看到她眼睛在笑，即使我那只是短短的一瞥，看得却异常清楚。有一种熟悉的感觉爬上了我的心头。可能是我接触异性少了，脑子出现了毛病……用我大学室友一句口头禅来说就是：这个不孬。

也正是这几个月来遇到了很多次，且位置都大差不差，我这才记住了，不知道她是否注意到我没……

人的一生会遇到许许多多的人。佛说，前世的五百次回眸，才换来今生的擦肩而过。

如果无缘，我只愿你一生安好，陌生人。

• 出差

出差了出差了，人生中的第一次出差啊。这次去杭州出差了一周，期间自然不是很顺利。项目上的就不多说了，这个晚上啊，因为还有一位同事一起的，所以我们就定的标间。

我那几天都是凌晨才慢慢睡去。为什么？旁边有位打呼跟电钻工装修一样的，要搁你，你能睡得着不……我还那会感冒没好全，身体素质是真不好，鼻血都流了好几回也不知道是不是擤鼻涕用力过猛了。

而且我这个头啊，右脑勺还真刺疼，公司体检卡发了，不过要下月才开始能预约，希望一切健康，买的保险用不上啊……

说到买的保险，买了个泰康的，送了个洗牙套餐，上月预约的都只能预约到一月份了，全家现在就我这口牙还行，最近好像也是开始出问题了，我得勤刷牙了，晚上不忘记能刷就刷。

拉回来说这个出差。由于我也没有经验，也没有什么准备，导致我根本就找不到可以冲账的发票，最后还是用的领导的燃油发票来报。看来，以后要多攒攒发票了，虽说出差少，备着吧。

• 余华

余华，当代著名作家，他的许多作品获过国内外奖项。

不知道，没关系。《活着》这部小说，总看过吧，没看过总听说过吧。没听说过？那我劝你现在就拿起手机打开 APP，订购一本，不要 998，也不要 198，它只要二十来块就能买到。

记得当时我是花了一个晚上把《活着》给看完的，情节太紧凑了根本不给我歇的机会，看了停不下来，等歇下来了，原来后面没了，翻到了最后一页。

最近我又在看他的另一本长篇小说《兄弟》。文人骚客，不骚就不叫文人了。不过里面骚的恰到好处，连接情节，更能吸引读者，引人入胜。

大体上，我看到现在，主色调还是悲的，也是在文革前后那段时间下描述的故事。极具讽刺意味。

只要能捱过来，那就都不是事。

• 蒋劲夫家暴

今天早上又刷到了这个新闻。家暴，我是不可能家暴的，真的很气愤也只会动动嘴皮子，大不了就出门透透气。个人认为，家暴确实是做不得，也不是男人该做的事。当然，会有些人有暴力倾向，更可怕的是有些女人还会十分享受被家暴的过程，这种人呢肯定是有的，而且可能还不少。

大家夫妻之间，情侣之间搞搞 SM 啊什么的我倒是觉得很正常，别动不动就搞出血还搞出命，不值当啊！所以，两人在一起，这些东西都是需要熟知的，要了解清楚，三观不合的怎么可能长久，那种一夜情的就没必要查户口了。

真快啊都要 2018 12 月份了，下次写个年终总结，好好借机回顾一下自己这一年来的成长。长肯定是有长的，长哪就不知道了。

哈哈，生死本无常，人应多思量。

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

想必大家对二叉树也不陌生，被各种二叉树面试题支配的恐惧仍记忆犹新……

这篇就总结一下二叉树的各种遍历，包括前、中、后序遍历还有层次遍历。

让我们来想象，大脑是个无底洞，这个栈它没有深度，所以我们要时而把栈底那些强行挖上来，以防痴呆！你不想痴呆吧！go go go.

层次遍历

先来这个层次遍历，二叉树一层又一层，它有深度。既然是一层接着一层，那很清楚了，我们逐层遍历就行。

题目描述：

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

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

清晰得不能再清晰了。递归调用 + 循环节点。代码如下：

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

public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> list = new ArrayList<>();
        List<TreeNode> l = new ArrayList<>();
        l.add(root);
        helper(list, l);
        return list;

    }

    /**
     * 递归 层层遍历
     * 
     * @param list
     * @param treeList
     */
    private void helper(List<List<Integer>> list, List<TreeNode> treeList) {
        if (treeList.size() == 0)
            return;
        List<Integer> listInt = new ArrayList<>();
        List<TreeNode> treeL = new ArrayList<>();
        // 逐层添值
        for (TreeNode node : treeList) {
            if (node != null) {
                listInt.add(node.val);
                treeL.add(node.left);
                treeL.add(node.right);
            }
        }
        if (listInt.size() > 0)
            list.add(listInt);

        helper(list, treeL);
    }

或者是使用队列 + while 循环搞定：

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

/**
     * 使用队列 queue
     * 
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder1(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> wrapList = new LinkedList<List<Integer>>();

        if (root == null)
            return wrapList;

        queue.offer(root);
        while (!queue.isEmpty()) {
            // 有值就塞入集合 同时将其左右子节点添加到队列中
            int levelNum = queue.size();
            List<Integer> subList = new LinkedList<Integer>();
            for (int i = 0; i < levelNum; i++) {
                if (queue.peek().left != null)
                    queue.offer(queue.peek().left);
                if (queue.peek().right != null)
                    queue.offer(queue.peek().right);
                subList.add(queue.poll().val);
            }
            wrapList.add(subList);
        }
        return wrapList;
    }

这个问题不大。

中序遍历

中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。

也就是根结点遍历位置在中间： 左 -> 根 -> 右

题目描述：

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

给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

既然都说了递归算法很简单，确实也很简单，先上递归算法：

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

public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    /**
     * 递归
     * 
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        helper(list, root);
        return list;
    }

    private void helper(List<Integer> list, TreeNode node) {
        if (node != null) {
            if (node.left != null)
                helper(list, node.left);
            list.add(node.val);
            if (node.right != null)
                helper(list, node.right);
        }
    }

这个递归算法在前、中、后序遍历都可以套用的，着实好用也好记。下面就不重复该代码了，无非就是结点的顺序换一换。

迭代算法，这里我们思考一下，我们需要先读其左结点，读完之后再读其根结点，左结点若是存在，那它不就是下一层的根结点吗？然后我们再一层层往上读。此时脑壳一抖，栈！

Stack 来解决：

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

/**
 * 栈 stack 来解决
 * 
 * @param root
 * @return
 */
public List<Integer> inorderTraversal1(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            // 将其左节点依次放入 因为先读左节点
            stack.push(curr);
            curr = curr.left;
        }
        // 将栈顶弹出
        curr = stack.pop();
        // 塞值
        res.add(curr.val);
        // 将右节点赋值给它 完美呈现了中序遍历 ： 左 -> 根 -> 右
        curr = curr.right;
    }
    return res;
}

代码也不长，该过程可以用大脑无底栈来走一遍。闭上眼睛，冥想。

前序遍历

前序遍历（DLR），是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。

即根结点遍历位置在前面： 根 -> 左 -> 右

题目描述：

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

给定一个二叉树，返回它的 前序 遍历。

 示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归算法不说了，见上。

迭代这里用双向链表 LinkedList，数据量大时存取数据性能好点。

代码如下：

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

/**
 * 双向队列
 * 
 * @param root
 * @return
 */
public List<Integer> preorderTraversal1(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> output = new LinkedList<>();
    if (root == null) {
        return output;
    }
    stack.add(root);
    while (!stack.isEmpty()) {
        // 弹出队列中最后一个
        TreeNode node = stack.pollLast();
        output.add(node.val);
        if (node.right != null) {
            stack.add(node.right);
        }
        if (node.left != null) {
            // 该节点就是下一个要读的根节点
            stack.add(node.left);
        }
    }
    return output;
}

这里需要注意的就是 stack.add() 先添加右结点在添加左结点，因为 stack.pollLast() 取出的是最后一个数据，这样就是左结点先弹出，满足前序遍历的顺序。

后序遍历

后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。

即根结点遍历位置在前面： 左 -> 右 -> 根

题目描述：

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

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

同样，递归算法不重复，见上。

这里的迭代算法我是看了官网的解法。秒。利用双向链表每次在起始位置添加值，顺序为根 -> 右 -> 左，然后遍历完后整个顺序从前往后就是左 -> 右 -> 根，后序遍历。

双向链表 LinkedList + 栈 Stack，代码如下：

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

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

/**
 * 根 -> 右 -> 左 存入，遍历完全后从前往后即是 左 -> 右 -> 根
 * 
 * @param root
 * @return
 */
public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> ans = new LinkedList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null)
        return ans;

    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode cur = stack.pop();
        // 将值塞到最前面
        ans.addFirst(cur.val);
        // 先左结点入栈
        if (cur.left != null) {
            stack.push(cur.left);
        }
        // 再是右结点入栈
        if (cur.right != null) {
            stack.push(cur.right);
        }
    }
    return ans;
}

从后往前推，一气呵成。

其实，还是递归最好使……

代码编译的结果从本地机器码转变为字节码，是存储格式发展的一小步，却是编程语言发展的一大步。

概述

虚拟机把描述类的数据从 Class 文件加载到内存，并对数据进行校验、转换解析和初始化，最终形成可以被虚拟机直接使用的 Java 类型，这就是虚拟机的类加载机制。

与那些在编译时需要进行连接工作的语言不同，在 Java 语言里面，类型的加载、连接和初始化过程都是在程序运行期间完成的，Java 里天生可以动态扩展的语言特性就是依赖 运行期动态加载和 动态连接这个特点实现的。

类加载的时机

类从被加载到虚拟机内存中开始，到卸载出内存为止，它的整个生命周期包括：加载、验证、准备、解析、初始化、使用和卸载 7 个阶段。其中验证、准备、解析 3 个部分统称为连接。

加载、验证、准备、初始化和卸载这 5 个阶段的顺序是确定的，类的加载过程必须按照这种顺序按部就班地开始，而解析阶段则不一定：它在某些情况下可以在初始化阶段之后再开始，这是为了支持 Java 语言的运行时绑定（也称为动态绑定或晚期绑定）。

对于初始化阶段，虚拟机规范是严格规定了 有且只有 5 中情况必须对类进行“初始化”（而加载、验证、准备自然需要在此之前开始）：

• 遇到 new、getstatic、putstatic 或 invokestatic 这 4 条字节码指令时，如果类没有进行过初始化，则需要先触发其初始化
• 使用 java.lang.reflect 包的方法对类进行反射调用的时候，如果类没有进行过初始化，则需要先触发其初始化
• 当初始化一个类的时候，如果发现其父类还没有进行过初始化，则需要先触发其父类的初始化
• 当虚拟机启动时，用户需要指定一个要执行的主类（包含 main() 方法的那个类），虚拟机会先初始化这个主类
• 当使用 JDK 1.7 的动态语言支持时，如果一个 java.lang.invoke.MethodHandle 实例最后的解析结果 REF_getStatic、REF_putStatic、REF_invokeStatic 的方法句柄，并且这个方法句柄所对应的类没有进行过初始化，则需要先触发其初始化

这 5 中场景中的行为称为对一个类进行主动引用。除此之外，所有引用类的方式都不会触发初始化，称为被动引用。

被动引用举例：

• 通过子类引用父类的静态字段，不会导致子类初始化
• 通过数组定义来引用类，不会触发此类的初始化
• 常量在编译阶段存入常量池中，调用时不会触发定义常量的类的初始化

接口的加载过程与类加载过程稍有一些不同，针对接口需要做一些特殊处理：接口也有初始化过程，虽然接口中不能使用 “static{}” 语句块，但编译器仍然会为接口生成 “<clinit>()” 类构造器，用于初始化接口中所定义的成员变量。

当一个类在初始化时，要求其父类全部都已经初始化过了，但是一个接口在初始化时，并不要求其父接口全部都完成了初始化，只有在真正使用到父接口的时候（如引用接口中定义的常量）才会初始化。

类加载的过程

类加载的全过程也就是加载、验证、准备、解析和初始化这 5 个阶段所执行的具体动作。

加载

“加载”是“类加载”过程的一个阶段，在加载阶段，虚拟机需要完成以下 3 件事情：

• 通过一个类的全限定名来获取定义此类的二进制字节流
• 将这个字节流所代表的静态存储结构转化为方法区的运行时数据结构
• 在内存中生成一个代表这个类的 java.lang.Class 对象，作为方法区这个类的各种数据的访问入口

加载阶段完成后，虚拟机外部的二进制字节流就按照虚拟机所需的格式存储在方法区之中，方法区中的数据存储格式由虚拟机实现自行定义，虚拟机规范未规定此区域的具体数据结构。然后在内存中实例化一个 java.lang.Class 类的对象（并没有明确规定是在 Java 堆中，对于 HotSpot 虚拟机而言，Class 对象比较特殊，它虽然是对象，但是存放在方法区里面），这个对象将作为程序访问方法区中的这些类型数据的外部接口。

加载阶段与连接阶段的部分内容是交叉进行的，如一部分字节码文件格式验证动作。

验证

验证是连接阶段的第一步，这一阶段的目的是为了确保 Class 文件的字节流中包含的信息符合当前虚拟机的要求，并且不会危害虚拟机自身的安全。

从整体上看，验证阶段大致上会完成下面 4 个阶段的校验动作：

文件格式验证

第一阶段要验证字节流是否符合 Class 文件格式的规范，保证输入的字节流能正确地解析并存储于方法区之内，并且能被当前版本的虚拟机处理。

该阶段的验证是基于二进制字节流进行的，只有通过了这个阶段的验证后，字节流才会进入内存的方法区中进行存储。

元数据验证

第二阶段是对字节码描述的信息进行语义分析，对类的元数据信息进行语义校验，以保证其描述的信息符合 Java 语言规范的要求。

字节码验证

第三阶段是整个验证过程中最复杂的一个阶段，主要目的是通过数据流和控制流分析，确定程序语义是合法的、符合逻辑的。

如果一个类方法体的字节码没有通过字节码验证，那肯定是有问题的；但如果一个方法体通过了字节码验证，也不能说明其一定就是安全的。即使字节码验证之中进行了大量的检查，也不能保证这一点。即通过程序去校验程序逻辑是无法做到绝对准确的——不能通过程序准确地检查出程序是否能在有限的时间之内结束运行。

符号引用验证

最后一个阶段的校验发生在虚拟机将符号引用转化为直接引用的时候，这个转化动作将在连接的第三阶段——解析阶段中发生。符号引用验证可以看做是对类自身以外（常量池中的各种符号引用）的信息进行匹配性校验。

符号引用验证的目的是确保解析动作能正常执行。

对于虚拟机的类加载机制来说，验证阶段是一个非常重要的、但不是一定必要的阶段。

准备

准备阶段是正式为类变量分配内存并设置类变量初始值的阶段，这些变量所使用的内存都将在方法区中进行分配。

这时候进行内存分配的仅包括类变量（被 static 修饰的变量），而不包括实例变量，实例变量将会在对象实例化时随着对象一起分配在 Java 堆中。

public static int value = 123;

上述的 value 变量在准备阶段过后的初始值为 0 而不是 123，因为这时候尚未开始执行任何 Java 方法，而把 value 赋值为 123 的 putstatic 指令是程序被编译后，存放于类构造器 <clinit>() 方法之中，所以把 value 赋值为 123 的动作将在初始化阶段才会执行。

如果类字段的字段属性表中存在 ConstantValue 属性，那在准备阶段变量 value 就会被初始化为 ConstantValue 属性所指定的值，如：

public static final int value = 123;

编译时 Javac 将会为 value 生成 ConstantValue 属性，在准备阶段虚拟机就会根据 ConstantValue 的设置将 value 赋值为 123。

解析

解析阶段是虚拟机将常量池内的符号引用替换为直接引用的过程。

• 符号引用：符号引用以一组符号来描述所引用的目标，符号可以是任何形式的字面量，只要使用时能无歧义地定位到目标即可。
• 直接引用：直接引用可以是直接指向目标的指针、相对偏移量或是一个能间接定位到目标的句柄。

解析动作主要针对以下 7 类符号引用进行：

• 类或接口的解析
• 字段解析
• 类方法解析
• 接口方法解析
• 方法类型解析
• 方法句柄解析
• 调用点限定符解析

初始化

类初始化阶段是类加载过程的最后一步，前面的类加载过程中，除了在加载阶段用户应用程序可以通过自定义类加载器参与之外，其余动作完全由虚拟机主导和控制。到了初始化阶段，才真正开始执行类中定义的 Java 程序代码（或者说是字节码）。

初始化阶段是执行类构造器 <clinit>() 方法的过程，在这执行过程中一些可能会影响程序运行行为的特点和细节：

• <clinit>() 方法是由编译器自动收集类中所有类变量的赋值动作和静态语句块（static{} 块）中的语句合并产生的，编译器收集的顺序是由语句在源文件中出现的顺序所决定的，静态语句块中只能访问到定义在静态语句块之前的变量，定义在它之后的变量，在前面的静态语句块可以赋值，但是不能访问。
• <clinit>() 方法与类的构造函数（或者说实例构造器 <init>() 方法）不同，它不需要显式地调用父类构造器，虚拟机会保证在子类的 <clinit>() 方法执行之前，父类的 <clinit>() 方法已经执行完毕。因此在虚拟机中第一个被执行的 <clinit>() 方法的类肯定是 java.lang.Object。
• 由于父类的 <clinit>() 方法先执行，也就意味着父类中定义的静态语句块要优先于子类的变量赋值操作。
• <clinit>() 方法对于类或接口来说并不是必需的，如果一个类中没有静态语句块，也没有对变量的赋值操作，那么编译器可以不为这个类生成 <clinit>() 方法。
• 接口中不能使用静态语句块，但仍然有变量初始化的赋值操作，因此接口与类一样都会生成 <clinit>() 方法。但接口与类不同的是，执行接口的 <clinit>() 方法不需要先执行父接口的 <clinit>() 方法。只有当父接口中定义的变量使用时，父接口才会初始化。另外，接口的实现类在初始化时也一样不会执行接口的 <clinit>() 方法。
• 虚拟机会保证一个类的 <clinit>() 方法在多线程环境中被正确地加锁、同步，如果多个线程同时去初始化一个类，那么只会有一个线程去执行这个类的 <clinit>() 方法，其他线程都需要阻塞等待，直到活动线程执行 <clinit>() 方法完毕。如果在一个类的 <clinit>() 方法中有耗时很长的操作，就可能造成多个进程阻塞，在实际应用中这种阻塞往往是很隐蔽的。

类加载器

虚拟机设计团队把类加载器阶段中的“通过一个类的全限定名来获取描述此类的二进制字节流”这个动作放到 Java 虚拟机外部去实现，以便让应用程序自己决定如何去获取所需要的类。实现这个动作的代码模块称为“类加载器”。

类与类加载器

对于任意一个类，都需要由加载它的类加载器和这个类本身一同确立其在 Java 虚拟机中的唯一性，每一个类加载器，都拥有一个独立的类名称空间。

双亲委派模型

从 Java 虚拟机的角度来讲，只存在两种不同的类加载器：

• 启动类加载器，这个类加载器使用 C++ 语言实现，是虚拟机自身的一部分
• 所有其他的类加载器，这些类加载器都由 Java 语言实现，独立于虚拟机外部，并且全部都继承自抽象类 java.lang.ClassLoader

类加载器还可以划分得更细致一些，绝大部分 Java 程序都会使用到一下 3 种系统提供的类加载器：

• 启动类加载器（Bootstrap ClassLoader）：这个类加载器负责将存放在 <JAVA_HOME>\lib 目录中的，或者被 -Xbootclasspath 参数所指定的路径中的，并且是虚拟机识别的类库加载到虚拟机内存中。启动类加载器无法被 Java 程序直接引用，用户在编写自定义类加载器时，如果需要把加载请求委派给引导类加载器，那直接使用 null 代替即可。
• 扩展类加载器（Extension ClassLoader）：这个加载器由 sun.misc.Launcher$ExtClassLoader 实现，它负责加载 <JAVA_HOME>\lib\ext 目录中的，或者被 java.ext.dirs 系统变量所指定的路径中的所有类库，开发者可以直接使用扩展类加载器。
• 应用程序类加载器（Application ClassLoader）：这个类加载器由 sun.misc.Launcher$AppClassLoader 实现。由于这个类加载器是 ClassLoader 中的 getSystemClassLoader() 方法的返回值，所以一般也称它为系统类加载器。它负责加载用户类路径（ClassPath）上所指定的类库，开发者可以直接使用这个类加载器，如果应用程序中没有自定义过自己的类加载器，一般情况下这个就是程序中默认的类加载器。

我们的应用程序都是由这 3 种类加载器互相配合进行加载的，如果有必要，还可以加入自己定义的类加载器。

上图中展示的类加载器之间的这种层次关系，称为类加载器的双亲委派模型。

双亲委派模型的工作过程是：如果一个类加载器收到了类加载器的请求，它首先不会自己去尝试加载这个类，而是把这个请求委派给父类加载器去完成，每一个层次的类加载器都是如此，因此所有的加载请求最终都应该传送到顶层的启动类加载器中，只有当父加载器反馈自己无法完成这个加载请求（它的搜索范围中没有找到所需的类）时，子加载器才会尝试自己去加载。

End.这一篇由于篇幅过大，故手稿就不丢出来了。还是一些概念，类加载是经常会被面试问到的知识点，可见其重要性了。该啃还是要啃的，就点醋……