Jad(JAva Decompiler)

Jad(JAva Decompiler)是一个Java的反编译器，可以通过命令行把Java的class文件反编译成源代码。下载点击

使用方法：

[1] 反编译一个class文件：jad example.class，会生成example.jad，用文本编辑器打开就是java源代码

[2] 指定生成源代码的后缀名：jad -sjava example.class，生成example.java

[3] 改变生成的源代码的名称，可以先使用-p将反编译后的源代码输出到控制台窗口，然后使用重定向，输出到文件：jad -p example.class > myexample.java

[4] 把源代码文件输出到指定的目录：jad -dnewdir -sjava example.class，在newdir目录下生成example.java

[5] 把packages目录下的class文件全部反编译：jad -sjava packages/*.class

[6] 把packages目录以及子目录下的文件全部反编译：jad -sjava packages/*/.class，不过你仍然会发现所有的源代码文件被放到了同一个文件中，没有按照class文件的包路径建立起路径

[7] 把packages目录以及子目录下的文件全部反编译并建立和java包一致的文件夹路径，可以使用-r命令：jad -r -sjava packages/*/.class

[8] 当重复使用命令反编译时，Jad会提示“whether you want to overwrite it or not”，使用-o可以强制覆盖旧文件

[9] 还有其他的参数可以设置生成的源代码的格式，可以输入jad命令查看帮助，这里有个人做了简单的翻译：jad命令总结

[10] 当然，你会发现有些源文件头部有些注释信息，不用找了，jad没有参数可以去掉它，用别的办法吧。

测试

Main.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

public class Main {

    static volatile int t = 0;
    public static void main(String[] args) {
        int n = 100;
        Thread[] threads = new Thread[n];
        for (int i = 0; i < n; i++) {
            threads[i] = new Thread(new Runnable() {

                @Override
                public void run() {
                    for (int i = 0; i < 10000; i++) {
                        add();
                    }
                }
            });
            threads[i].start();
        }

        while (Thread.activeCount() > 1)
            Thread.yield();

        System.out.println(t);
    }

    static void add() {
        t++;
    }
}

Main.class

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

cafe babe 0000 0034 0037 0a00 0d00 1d07
001e 0700 1f0a 0003 001d 0a00 0200 200a
0002 0021 0a00 0200 220a 0002 0023 0900
2400 2509 000c 0026 0a00 2700 2807 0029
0700 2a01 000c 496e 6e65 7243 6c61 7373
6573 0100 0174 0100 0149 0100 063c 696e
6974 3e01 0003 2829 5601 0004 436f 6465
0100 0f4c 696e 654e 756d 6265 7254 6162
6c65 0100 046d 6169 6e01 0016 285b 4c6a
6176 612f 6c61 6e67 2f53 7472 696e 673b
2956 0100 0d53 7461 636b 4d61 7054 6162
6c65 0700 2b01 0003 6164 6401 0008 3c63
6c69 6e69 743e 0100 0a53 6f75 7263 6546
696c 6501 0009 4d61 696e 2e6a 6176 610c
0011 0012 0100 106a 6176 612f 6c61 6e67
2f54 6872 6561 6401 0006 4d61 696e 2431
...

反编译后的结果

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

// Decompiled by Jad v1.5.8g. Copyright 2001 Pavel Kouznetsov.
// Jad home page: http://www.kpdus.com/jad.html
// Decompiler options: packimports(3) 
// Source File Name:   Main.java

import java.io.PrintStream;

public class Main
{

    public Main()
    {
    }

    public static void main(String args[])
    {
        byte byte0 = 100;
        Thread athread[] = new Thread[byte0];
        for(int i = 0; i < byte0; i++)
        {
            athread[i] = new Thread(new Runnable() {

                public void run()
                {
                    for(int j = 0; j < 10000; j++)
                        Main.add();

                }

            }
);
            athread[i].start();
        }

        for(; Thread.activeCount() > 1; Thread.yield());
        System.out.println(t);
    }

    static void add()
    {
        t++;
    }

    static volatile int t = 0;

}

素数

• 质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。
• 0和1既不是质数也不是合数，最小的质数是2

1. 最直观，但效率最低的写法

这里特殊处理了一下小于等于3的数，因为小于等于3的自然数只有2和3是质数。

然后，我们只需要从2开始，一直到小于其自身，依次判断能否被n整除即可，能够整除则不是质数，否则是质数。

1
2
3
4
5
6
7
8
9
10
11

public static boolean isPrime(int n){
    if (n <= 3) {
        return n > 1;
    }
    for(int i = 2; i < n; i++){
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

2. 优化

我们继续分析，其实质数还有一个特点，就是它总是等于 6x-1 或者 6x+1，其中 x 是大于等于1的自然数。

如何论证这个结论呢，其实不难。首先 6x 肯定不是质数，因为它能被 6 整除；其次 6x+2 肯定也不是质数，因为它还能被2整除；依次类推，6x+3 肯定能被 3 整除；6x+4 肯定能被 2 整除。那么，就只有 6x+1 和 6x+5 (即等同于6x-1) 可能是质数了。所以循环的步长可以设为 6，然后每次只判断 6 两侧的数即可。

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

public static boolean isPrime(int num) {
    if (num <= 3) {
        return num > 1;
    }
    // 不在6的倍数两侧的一定不是质数
    if (num % 6 != 1 && num % 6 != 5) {
        return false;
    }
    int sqrt = (int) Math.sqrt(num);
    for (int i = 5; i <= sqrt; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

3. 性能对比

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

import java.util.*;

public class Main {

    public static void main(String[] args) {
        // Scanner in = new Scanner(System.in);
        // int n = in.nextInt();
        // in.close();
        Stack<Integer> a = new Stack<>(), b = new Stack<>();
        int n = 100000;
        long s = System.currentTimeMillis(), e;
        for (int i = 1; i < n; i++) {
            if (f(i))
                a.push(i);
        }
        e = System.currentTimeMillis();
        System.out.println(e - s + " ms");
        s = System.currentTimeMillis();
        for (int i = 1; i < n; i++) {
            if (func(i))
                b.push(i);
        }
        e = System.currentTimeMillis();
        System.out.println(e - s + " ms");
        System.gc();
    }

    static boolean f(int n) {
        if (n <= 3)
            return n > 1;
        for (int i = 2; i < n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    static boolean func(int n) {
        if (n <= 3)
            return n > 1;
        if (n % 6 != 1 && n % 6 != 5) {
            return false;
        }
        int tem = (int) Math.sqrt(n);
        for (int i = 5; i <= tem; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        }
        return true;
    }
}

1
2

1392 ms
5 ms

前言

进程与线程是一个程序员的必知概念，面试经常被问及，但是一些文章内容只是讲讲理论知识，可能一些小伙伴并没有真的理解，在实际开发中应用也比较少。本篇文章除了介绍概念，通过Node.js 的角度讲解进程与线程，并且讲解一些在项目中的实战的应用，让你不仅能迎战面试官还可以在实战中完美应用。

面试会问

Node.js是单线程吗？

Node.js 做耗时的计算时候，如何避免阻塞？

Node.js如何实现多进程的开启和关闭？

Node.js可以创建线程吗？

你们开发过程中如何实现进程守护的？

除了使用第三方模块，你们自己是否封装过一个多进程架构?

进程

进程Process是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础，进程是线程的容器（来自百科）。进程是资源分配的最小单位。我们启动一个服务、运行一个实例，就是开一个服务进程，例如 Java 里的 JVM 本身就是一个进程，Node.js 里通过 node app.js 开启一个服务进程，多进程就是进程的复制（fork），fork 出来的每个进程都拥有自己的独立空间地址、数据栈，一个进程无法访问另外一个进程里定义的变量、数据结构，只有建立了 IPC 通信，进程之间才可数据共享。

1
2
3
4
5
6
7

const http = require('http');

const server = http.createServer();
server.listen(3000,()=>{
    process.title='程序员成长指北测试进程';
    console.log('进程id',process.pid)
})

运行上面代码后，以下为 Mac 系统自带的监控工具 “活动监视器” 所展示的效果，可以看到我们刚开启的 Nodejs 进程 7663

线程

线程是操作系统能够进行运算调度的最小单位，首先我们要清楚线程是隶属于进程的，被包含于进程之中。一个线程只能隶属于一个进程，但是一个进程是可以拥有多个线程的。

单线程

单线程就是一个进程只开一个线程

Javascript 就是属于单线程，程序顺序执行(这里暂且不提JS异步)，可以想象一下队列，前面一个执行完之后，后面才可以执行，当你在使用单线程语言编码时切勿有过多耗时的同步操作，否则线程会造成阻塞，导致后续响应无法处理。你如果采用 Javascript 进行编码时候，请尽可能的利用Javascript异步操作的特性。

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

const http = require('http');
const longComputation = () => {
  let sum = 0;
  for (let i = 0; i < 1e10; i++) {
    sum += i;
  };
  return sum;
};
const server = http.createServer();
server.on('request', (req, res) => {
  if (req.url === '/compute') {
    console.info('计算开始',new Date());
    const sum = longComputation();
    console.info('计算结束',new Date());
    return res.end(`Sum is ${sum}`);
  } else {
    res.end('Ok')
  }
});

server.listen(3000);
//打印结果
//计算开始 2019-07-28T07:08:49.849Z
//计算结束 2019-07-28T07:09:04.522Z

查看打印结果，当我们调用127.0.0.1:3000/compute
的时候，如果想要调用其他的路由地址比如127.0.0.1/大约需要15秒时间，也可以说一个用户请求完第一个compute接口后需要等待15秒，这对于用户来说是极其不友好的。下文我会通过创建多进程的方式child_process.fork 和cluster 来解决解决这个问题。

单线程的一些说明

• Node.js 虽然是单线程模型，但是其基于事件驱动、异步非阻塞模式，可以应用于高并发场景，避免了线程创建、线程之间上下文切换所产生的资源开销。
• 当你的项目中需要有大量计算，CPU 耗时的操作时候，要注意考虑开启多进程来完成了。
• Node.js 开发过程中，错误会引起整个应用退出，应用的健壮性值得考验，尤其是错误的异常抛出，以及进程守护是必须要做的。
• 单线程无法利用多核CPU，但是后来Node.js 提供的API以及一些第三方工具相应都得到了解决，文章后面都会讲到。

树的高度（小米2017秋招真题）

题目

题目描述

现在有一棵合法的二叉树，树的节点都是用数字表示，现在给定这棵树上所有的父子关系，求这棵树的高度

时间限制
C/C++语言：1000MS 其它语言：3000MS

内存限制
C/C++语言：65536KB 其它语言：589824KB

输入

输入的第一行表示节点的个数n（1<=n<=1000，节点的编号为0到n-1）组成，下面是n-1行，每行有两个整数，第一个数表示父节点的编号，第二个数表示子节点的编号

输出

输出树的高度，为一个整数

样例输入

1
2
3
4
5

5
0 1
0 2
1 3
1 4

样例输出

1

3

题解

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

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] parent = new int[n];

        for (int i = 0; i < n; i++) {
            parent[i] = -1;
        }

        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            parent[b] = a;
        }

        int h = 0;
        for (int i = 0; i < n; i++) {
            int max = 1;
            int j = i;
            while (parent[j] != -1) {
                j = parent[j];
                max++;
            }
            h = max > h ? max : h;
        }
        System.out.println(h);
    }
}

python

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

import sys

def get(x):
    try:
        return 1 + get(dic_s[x])
    except KeyError:
        return 1

n = int(sys.stdin.readline().strip())
dic_s = {}
for i in range(int(n)-1):
    j_1,j_2 = sys.stdin.readline().strip().split()
    dic_s[j_2] = j_1
print max([get(i) for i in set(dic_s.keys()) - set(dic_s.values())]) if n>1 else 1

javascript

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

var n=readInt(),rec={},dps={},rs=1
while(n-->1) {
  var a=readInt(),b=readInt()
  rec[a]=rec[a]||[]
  rec[a].push(b)
}
for(var k in rec) rs=Math.max(rs,maxDps(k))
print(rs)
function maxDps(n){
  if(!rec[n]) return 1
  if(dps[n]) return dps[n]
  var r=1
  for(var x of rec[n]) r=Math.max(r,maxDps(x)+1)
  dps[n]=r
  return dps[n]
}

兰博基尼

法拉利

布加迪

迈凯伦

兰博基尼

风神

介绍spring框架

它是一个一站式（full-stack全栈式）框架，提供了从表现层-springMVC到业务层-spring再到持久层-springdata的一套完整的解决方案。我们在项目中可以只使用spring一个框架，它就可以提供表现层的mvc框架，持久层的Dao框架。它的两大核心IoC和AOP更是为我们程序解耦和代码简洁易维护提供了支持。

Spring的优点？

1. 降低了组件之间的耦合性 ，实现了软件各层之间的解耦
2. 可以使用容易提供的众多服务，如事务管理，消息服务等
3. 容器提供单例模式支持
4. 容器提供了AOP技术，利用它很容易实现如权限拦截，运行期监控等功能
5. 容器提供了众多的辅助类，能加快应用的开发
6. spring对于主流的应用框架提供了集成支持，如hibernate， JPA，Struts等
7. spring属于低侵入式设计，代码的污染极低
8. 独立于各种应用服务器
9. spring的DI机制降低了业务对象替换的复杂性
10. Spring的高度开放性，并不强制应用完全依赖于Spring，开发者可以自由选择spring 的部分或全部

spring有两种代理方式：

答: 若目标对象实现了若干接口，spring使用JDK的java.lang.reflect.Proxy类代理。

优点：因为有接口，所以使系统更加松耦合

缺点：为每一个目标类创建接口

若目标对象没有实现任何接口，spring使用CGLIB库生成目标对象的子类。

优点：因为代理类与目标类是继承关系，所以不需要有接口的存在。

缺点：因为没有使用接口，所以系统的耦合性没有使用JDK的动态代理好

如何给Spring 容器提供配置元数据?

这里有三种重要的方法给Spring 容器提供配置元数据。

XML配置文件。

基于注解的配置。

基于java的配置。

构造方法注入和设值注入有什么区别？

请注意以下明显的区别：

在设值注入方法支持大部分的依赖注入，如果我们仅需要注入int、string和long型的变量，我们不要用设值的方法注入。

对于基本类型，如果我们没有注入的话，可以为基本类型设置默认值。

在构造方法注入不支持大部分的依赖注入，因为在调用构造方法中必须传入正确的构造参数，否则的话为报错。

设值注入不会重写构造方法的值。

在使用设值注入时有可能还不能保证某种依赖是否已经被注入，也就是说这时对象的依赖关系有可能是不完整的。而在另一种情况下，构造器注入则不允许生成依赖关系不完整的对象。

请介绍一下Spring框架中Bean的生命周期

一、Bean的定义

Spring通常通过配置文件定义Bean。如：

这个配置文件就定义了一个标识为 HelloWorld 的Bean。在一个配置文档中可以定义多个Bean。

二、Bean的初始化

有两种方式初始化Bean。

1、在配置文档中通过指定init-method 属性来完成

2、实现 org.springframwork.beans.factory.InitializingBean接口

那么，当这个Bean的所有属性被Spring的BeanFactory设置完后，会自动调用afterPropertiesSet()方法对Bean进行初始化，于是，配置文件就不用指定 init-method属性了。

三、Bean的调用

有三种方式可以得到Bean并进行调用：

1、使用BeanWrapper

2、使用BeanFactory

3、使用ApplicationConttext

四、Bean的销毁

1、使用配置文件中的 destory-method 属性

2、实现 org.springframwork.bean.factory.DisposebleBean接口

Spring中AOP的应用场景、Aop原理、好处？

答：AOP–Aspect Oriented Programming面向切面编程；用来封装横切关注点，具体可以在下面的场景中使用:

Authentication 权限、Caching 缓存、Context passing 内容传递、Error handling 错误处理Lazy loading懒加载、Debugging调试、logging, tracing, profiling and monitoring 记录跟踪优化　校准、Performance optimization　性能优化、Persistence 持久化、Resource pooling　资源池、Synchronization　同步、Transactions 事务

原理：AOP是面向切面编程，是通过动态代理的方式为程序添加统一功能，集中解决一些公共问题。

优点：1.各个步骤之间的良好隔离性耦合性大大降低

2.源代码无关性，再扩展功能的同时不对源码进行修改操作 

有几种不同类型的自动代理？

BeanNameAutoProxyCreator

DefaultAdvisorAutoProxyCreator

Metadata autoproxying

ApplicationContext通常的实现是什么?

FileSystemXmlApplicationContext ：此容器从一个XML文件中加载beans的定义，XML Bean 配置文件的全路径名必须提供给它的构造函数。

ClassPathXmlApplicationContext：此容器也从一个XML文件中加载beans的定义，这里，你需要正确设置classpath因为这个容器将在classpath里找bean配置。

WebXmlApplicationContext：此容器加载一个XML文件，此文件定义了一个WEB应用的所有bean。

有哪些不同类型的IOC（依赖注入）方式？

构造器依赖注入：构造器依赖注入通过容器触发一个类的构造器来实现的，该类有一系列参数，每个参数代表一个对其他类的依赖。

Setter方法注入：Setter方法注入是容器通过调用无参构造器或无参static工厂 方法实例化bean之后，调用该bean的setter方法，即实现了基于setter的依赖注入。

什么是IOC，什么又是DI，他们有什么区别？

一、IOC介绍

IOC是控制反转。

创建对象实例的控制权从代码控制剥离到IOC容器控制(之前的写法，由程序代码直接操控使用new关键字)，实际就是你在xml文件控制，控制权的转移是所谓反转，侧重于原理。

二、DI介绍

DI是依赖注入

创建对象实例时，为这个对象注入属性值或其它对象实例，侧重于实现。

spring事务定义

事务的定义：事务是指多个操作单元组成的合集，多个单元操作是整体不可分割的，要么都操作不成功，要么都成功。其必须遵循四个原则（ACID）。

原子性（Atomicity）：即事务是不可分割的最小工作单元，事务内的操作要么全做，要么全不做；

一致性（Consistency）：在事务执行前数据库的数据处于正确的状态，而事务执行完成后数据库的数据还是应该处于正确的状态，即数据完整性约束没有被破坏；如银行转帐，A转帐给B，必须保证A的钱一定转给B，一定不会出现A的钱转了但B没收到，否则数据库的数据就处于不一致（不正确）的状态。

隔离性（Isolation）：并发事务执行之间互不影响，在一个事务内部的操作对其他事务是不产生影响，这需要事务隔离级别来指定隔离性；

持久性（Durability）：事务一旦执行成功，它对数据库的数据的改变必须是永久的，不会因比如遇到系统故障或断电造成数据不一致或丢失。

Spring框架中的单例Beans是线程安全的么？

Spring框架并没有对单例bean进行任何多线程的封装处理。关于单例bean的线程安全和并发问题需要开发者自行去搞定。但实际上，大部分的Spring bean并没有可变的状态(比如Serview类和DAO类)，所以在某种程度上说Spring的单例bean是线程安全的。如果你的bean有多种状态的话（比如 View Model 对象），就需要自行保证线程安全。

题目

一个天平上有6个位置，左右各三个位置，有6个砝码，分别是1、2、3、4、5、6克重。
要使天平平衡，有多少种方法？（对称摆放算作一种方法）

题解

暴力求解

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int t = 6;
    int count = 0;
    vector<string> v;
    for (int i = 1; i <= t; ++i) {
        for (int j = 1; j <= t; ++j) {
            for (int k = 1; k <= t; ++k) {
                for (int l = 1; l <= t; ++l) {
                    for (int m = 1; m <= t; ++m) {
                        for (int n = 1; n <= t; ++n) {
                            if (i == j ||
                                i == k || j == k ||
                                i == l || j == l || k == l ||
                                i == m || j == m || k == m || l == m ||
                                i == n || j == n || k == n || l == n || m == n)
                                continue;
                            if ((3 * i + 2 * j + k) == (l + 2 * m + 3 * n)) {
                                string s = to_string(i) + to_string(j) + to_string(k) + to_string(l) + to_string(m) +
                                           to_string(n);
                                int te = 0;
                                if (v.size() > 0) {
                                    string tem = s;
                                    reverse(tem.begin(), tem.end());
                                    vector<string>::iterator it;
                                    for (it = v.begin(); it != v.end(); it++) {
                                        if (*it == tem) {
                                            //cout<<tem<<endl;
                                            te = 1;
                                            break;
                                        }
                                    }
                                }
                                if (te == 0) {
                                    v.push_back(s);
                                    count++;
                                    printf(" %d %d %d | %d %d %d\n", i, j, k, l, m, n);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout << count << endl;
    return 0;
}

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

1 4 6 | 5 3 2
1 5 6 | 2 4 3
1 5 6 | 3 2 4
1 6 4 | 3 5 2
1 6 5 | 2 3 4
2 4 6 | 1 5 3
2 4 6 | 3 1 5
2 6 3 | 4 1 5
2 6 4 | 1 3 5
3 2 6 | 5 1 4
3 4 5 | 2 1 6
3 5 4 | 1 2 6
3 6 2 | 1 5 4
4 2 6 | 1 3 5
4 3 5 | 1 2 6
5 2 4 | 3 1 6
5 4 2 | 1 3 6
17

杨辉三角

题目

给定一个非负整数 numRows，生成杨辉三角的前 numRows行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

1
2
3
4
5
6
7
8
9

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

题解

1. 动态规划

思路

如果能够知道一行杨辉三角，我们就可以根据每对相邻的值轻松地计算出它的下一行。

算法

虽然这一算法非常简单，但用于构造杨辉三角的迭代方法可以归类为动态规划，因为我们需要基于前一行来构造每一行。

首先，我们会生成整个 triangle 列表，三角形的每一行都以子列表的形式存储。然后，我们会检查行数为 0 的特殊情况，否则我们会返回 [1]。如果 numRows > 0，那么我们用 [1] 作为第一行来初始化 triangle with [1]，并按如下方式继续填充：

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

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<List<Integer>>();

        // First base case; if user requests zero rows, they get zero rows.
        if (numRows == 0) {
            return triangle;
        }

        // Second base case; first row is always [1].
        triangle.add(new ArrayList<>());
        triangle.get(0).add(1);

        for (int rowNum = 1; rowNum < numRows; rowNum++) {
            List<Integer> row = new ArrayList<>();
            List<Integer> prevRow = triangle.get(rowNum-1);

            // The first row element is always 1.
            row.add(1);

            // Each triangle element (other than the first and last of each row)
            // is equal to the sum of the elements above-and-to-the-left and
            // above-and-to-the-right.
            for (int j = 1; j < rowNum; j++) {
                row.add(prevRow.get(j-1) + prevRow.get(j));
            }

            // The last row element is always 1.
            row.add(1);

            triangle.add(row);
        }

        return triangle;
    }
}

复杂度分析

• 时间复杂度： O(numRows²)

虽然更新 triangle 中的每个值都是在常量时间内发生的，
但它会被执行 O(numRows²) 次。想要了解原因，就需要考虑总共有多少次循环迭代。很明显外层循环需要运行 numRows 次，但在外层循环的每次迭代中，内层循环要运行 rowNumrowNum 次。因此，triangle 发生的更新总数为
1 + 2 + 3 + ... + *numRows*，根据高斯公式有

• 空间复杂度：O(numRows²)

因为我们需要存储我们在 triangle 中更新的每个数字，
所以空间需求与时间复杂度相同。

2. Python解法

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

class Solution:
    def generate(self, num_rows):
        triangle = []

        for row_num in range(num_rows):
            # The first and last row elements are always 1.
            row = [None for _ in range(row_num+1)]
            row[0], row[-1] = 1, 1

            # Each triangle element is equal to the sum of the elements
            # above-and-to-the-left and above-and-to-the-right.
            for j in range(1, len(row)-1):
                row[j] = triangle[row_num-1][j-1] + triangle[row_num-1][j]

            triangle.append(row)

        return triangle

3. 递归解法

通过numRows-1，求numRows行，递归求解

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

class Solution {
    List<List<Integer>> listw = new ArrayList<List<Integer>>();

    public List<List<Integer>> generate(int numRows) {
        List<Integer> listn = new ArrayList<Integer>();
        if (numRows == 0)
            return listw;
        generate(numRows - 1);
        for (int i = 0; i < numRows; i++) {
            if (i == 0) {
                listn.add(1);
                continue;
            } else if (i == numRows - 1) {
                listn.add(1);
                continue;
            } else if (i == numRows - 2) {
                listn.add(listw.get(numRows - 2).get(i - 1) + 1);
                continue;
            } else {
                listn.add(listw.get(numRows - 2).get(i - 1) + listw.get(numRows - 2).get(i));
            }
        }
        listw.add(listn);
        return listw;
    }
}

24. 两两交换链表中的节点

题目

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

题解

1. 非递归

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode temp = pre;
        while(temp.next != null && temp.next.next != null) {
            ListNode start = temp.next;
            ListNode end = temp.next.next;
            temp.next = end;
            start.next = end.next;
            end.next = start;
            temp = start;
        }
        return pre.next;
    }
}

2. 递归解法

   1. 详细介绍一下递归的思路;
   2. 递归和栈处理问题类似,先把问题从前往后收集起来,然后再从后往前处理每一个问题;
   3. 两两交换链表结点,先处理最后两个或一个节点,然后再从后往前处理每一对节点;
   4. 先创建一个next临时结点保存head的下一个结点,然后让head指向下下一个节点,最后让 next节点指向head结点;
   5. 此题只有处理完后面的结点才可处理前面的结点,画图更容易理解;

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

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null)
            return head;

        // 三个节点顺序:head, next, swapPairs(next.next)
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }
}

334. 反转字符串

题目

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]    

题解

1. 递归解法

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

class Solution {
    public void reverseString(char[] s) {
        swap(0, s.length-1, s);
    }
    
    public void swap(int start, int end, char[] s) {
        if(start >= end){
            return;
        }
        char temp = s[start];
        s[start] = s[end];
        s[end] = temp;
        swap(start+1, end-1, s);
    }
}

2. 循环解法

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public void reverseString(char[] s) {
        int j=s.length-1;
        for(int i=0;i<s.length/2;i++){
            char tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
            j--;
        }
    }
}

3. Python解法

1
2

def reverseString(self, s: List[str]) -> None:
    s[0::]=s[::-1]

4. c++解法

双指针，交换头尾两个指针所指的两个位置的值，指针向中间移动一个位置，重复以上操作，直到两个指针交错；

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

class Solution {
public:
    void reverseString(vector<char>& s) {
        int i = 0;
        int j = s.size() - 1;
        while(i<j)
        {
            swap(s[i],s[j]);
            ++ i;
            -- j;
        }
    }
};

基础与框架

1. String类能被继承吗，为什么
2. String，Stringbuffer，StringBuilder的区别？
3. ArrayList和LinkedList有什么区别
4. 类的实例化顺序，比如父类静态数据，构造函数，字段，子类静态数据，构造函数，字段，他们的执行顺序
5. 用过哪些Map，都有什么区别，HashMap是线程安全的吗,并发下使用的Map是什么，他们内部原理分别是什么，比如hashcode，扩容等
6. HashMap为什么get和set那么快，concurrentHashMap为什么能提高并发
7. 抽象类和接口的区别，类可以继承多个类么，接口可以继承多个接口么,类可以实现多个接口么
8. 什么情况下会发生栈内存溢出
9. 什么是nio，原理
10. 反射中，Class.forName和ClassLoader区别
11. tomcat结构，类加载器流程
12. 讲讲Spring事务的传播属性,AOP原理，动态代理与cglib实现的区别，AOP有哪几种实现方式
13. Spring的beanFactory和factoryBean的区别
14. Spring加载流程
15. Spring如何管理事务的

多线程

1. 线城池的最大线程数目根据什么确定
2. 多线程的几种实现方式，什么是线程安全，什么是重排序3.volatile的原理，作用，能代替锁么
3. sleep和wait的区别，以及wait的实现原理
4. Lock与synchronized 的区别，synchronized 的原理，什么是自旋锁，偏向锁，轻量级锁，什么叫可重入锁，什么叫公平锁和非公平锁
5. 用过哪些原子类，他们的参数以及原理是什么
6. 用过哪些线程池，他们的原理简单概括下，构造函数的各个参数的含义，比如coreSize，maxsize等
7. 有一个第三方接口，有很多个线程去调用获取数据，现在规定每秒钟最多有10个线程同时调用它，如何做到。
8. spring的controller是单例还是多例，怎么保证并发的安全
9. 用三个线程按顺序循环打印abc三个字母，比如abcabcabc
10. ThreadLocal用过么，原理是什么，用的时候要注意什么
11. 如果让你实现一个并发安全的链表，你会怎么做

JVM相关

1. jvm中一次完整的GC流程（从ygc到fgc）是怎样的，重点讲讲对象如何晋升到老年代，几种主要的jvm参数等
2. 你知道哪几种垃圾收集器，各自的优缺点，重点讲下cms
3. 当出现了内存溢出，你怎么排错
4. JVM内存模型的相关知识了解多少
5. 简单说说你了解的类加载器
6. JAVA的反射机制

网络

1. http1.0和http1.1有什么区别
2. TCP三次握手和四次挥手的流程，为什么断开连接要4次,如果握手只有两次，会出现什么
3. TIME_WAIT和CLOSE_WAIT的区别
4. 说说你知道的几种HTTP响应码
5. 当你用浏览器打开一个链接的时候，计算机做了哪些工作步骤
6. Linux下IO模型有几种，各自的含义是什么
7. TCP/IP如何保证可靠性，数据包有哪些数据组成
8. 架构设计与分布式：
9. tomcat如何调优，各种参数的意义
10. 常见的缓存策略有哪些，你们项目中用到了什么缓存系统，如何设计的，Redis的使用要注意什么，持久化方式，内存设置，集群，淘汰策略等
11. 如何防止缓存雪崩12.用java自己实现一个LRU
12. 分布式集群下如何做到唯一序列号
13. 设计一个秒杀系统，30分钟没付款就自动关闭交易
14. 如何做一个分布式锁
15. 用过哪些MQ，怎么用的，和其他mq比较有什么优缺点，MQ的连接是线程安全的吗
16. MQ系统的数据如何保证不丢失
17. 分布式事务的原理，如何使用分布式事务
18. 什么是一致性hash
19. 什么是restful，讲讲你理解的restful
20. 如何设计建立和保持100w的长连接？
21. 解释什么是MESI协议(缓存一致性)
22. 说说你知道的几种HASH算法，简单的也可以
23. 什么是paxos算法
24. redis和memcached 的内存管理的区别
25. 一个在线文档系统，文档可以被编辑，如何防止多人同时对同一份文档进行编辑更新

算法

1. 10亿个数字里里面找最小的10个2、有1亿个数字，其中有2个是重复的，快速找到它，时间和空间要最优3、2亿个随机生成的无序整数,找出中间大小的值4、遍历二叉树六、数据库1.数据库隔离级别有哪些，各自的含义是什么，MYsql默认的隔离级别是是什么，各个存储引擎优缺点
2. 高并发下，如何做到安全的修改同一行数据，乐观锁和悲观锁是什么，INNODB的行级锁有哪2种，解释其含义
3. SQL优化的一般步骤是什么，怎么看执行计划，如何理解其中各个字段的含义，索引的原理？
4. 数据库会死锁吗，举一个死锁的例子，mysql怎么解决死锁
5. MYsql的索引实现方式
6. 聚集索引和非聚集索引的区别
7. 数据库中 BTREE和B+tree区别

作者：程序汪追风
链接：https://juejin.im/post/5d5fd40bf265da03df5f1b3a
来源：掘金

HTML / CSS

• 【HTML】
  HTML，即超文本标记语言（Hyper Text Markup Language）
• 【HTML5】
  HTML5 是下一代 HTML 标准
• 【CSS】
  层叠样式表（Cascading StyleSheet）
• 【CSS3】
  CSS3是CSS技术的升级版本
• 【Bootstrap3】
  Bootstrap，来自 Twitter，是目前最受欢迎的前端框架
• 【Bootstrap4】
  Bootstrap4 目前是 Bootstrap 的最新版本
• 【Font Awesome】
  Font Awesome 是一套绝佳的图标字体库和CSS框架。
• 【Foundation】
  Foundation 用于开发响应式的 HTML, CSS and JavaScript 框架

  JavaScript

• 【JavaScript】
  JavaScript 是 Web 的编程语言
• 【HTML DOM】
  HTML DOM 定义了访问和操作 HTML 文档的标准方法
• 【jQuery】
  jQuery 是一个 JavaScript 库
• 【AngularJS】
  AngularJS 通过新的属性和表达式扩展了 HTML
• 【AngularJS2】
  AngularJS2 是一款开源JavaScript库，由Google维护。
• 【Vue.js】
  Vue.js 是一套构建用户界面的渐进式框架。
• 【React】
  React 是一个用于构建用户界面的 JAVASCRIPT 库
• 【TypeScript】
  TypeScript 是 JavaScript 的一个超集，支持 ECMAScript 6 标准
• 【jQuery UI】
  jQuery UI 是建立在 jQuery上的一组用户界面交互、特效、小部件及主题
• 【jQuery EasyUI 】
  jQuery EasyUI 是一个基于 jQuery 的框架，集成了各种用户界面插件
• 【Node.js】
  Node.js 是运行在服务端的 JavaScript
• 【AJAX】
  AJAX = Asynchronous JavaScript and XML（异步的 JavaScript 和 XML）
• 【JSON】
  JSON 是存储和交换文本信息的语法
• 【Highcharts】
  Highcharts 是一个用纯JavaScript编写的一个图表库
• 【Google 地图】
  Google 地图接口使用说明

服务端

• 【PHP】
  PHP 是一种通用开源脚本语言
• 【Python】
  Python 是一种面向对象、解释型计算机程序设计语言
• 【Python3】
  Python 升级版，变化较大
• 【Django】
  Django是一个开放源代码的Web应用框架，由Python写成
• 【Linux】
  Linux是一套免费使用和自由传播的类Unix操作系统
• 【Docker】
  Docker 是一个开源的应用容器引擎，基于 Go 语言
• 【Ruby】
  一种为简单快捷的面向对象编程（面向对象程序设计）而创的脚本语言
• 【Java】
  一种可以撰写跨平台应用软件的面向对象的程序设计语言
• 【C】
  一门通用计算机编程语言
• 【C++】
  C++是在C语言的基础上开发的一种通用编程语言
• 【Perl】
  Perl 是高级、通用、直译式、动态的程序语言
• 【Servlet 】
  运行在 Web 服务器或应用服务器上的程序
• 【JSP】
  JSP与PHP、ASP、ASP.NET等语言类似，运行在服务端的语言
• 【Lua】
  Lua 是一种轻量小巧的脚本语言，用标准C语言编写并以源代码形式开放
• 【Scala】
  Scala 是一门多范式（multi-paradigm）的编程语言。
• 【Go】
  Go语言是谷歌推出的一种全新的编程语言
• 【设计模式】
  设计模式代表了最佳的实践，通常被有经验的面向对象的软件开发人员所采用
• 【正则表达式】
  正则表达式是对字符串操作的一种逻辑公式
• 【Maven】
  Maven 是一个项目管理工具，可以对 Java 项目进行构建、依赖管理。
• 【NumPy】
  NumPy 是 Python 语言的一个扩展程序库，支持大量的维度数组与矩阵运算。
• 【ASP】
  ASP（Active Server Pages 动态服务器页面）是一种生成动态交互性网页的强有力工具
• 【AppML】
  AppML 是一个为web应用程序设计的HTML扩展框
• 【VBScript】
  一种微软环境下的轻量级的解释型语言

数据库

• 【SQL】
  结构化查询语言(Structured Query Language)
• 【Mysql】
  MySQL是一个关系型数据库管理系统
• 【PostgreSQL】
  PostgreSQL 是一个免费的对象-关系数据库服务器(ORDBMS)
• 【SQLite】
  一款轻型的数据库
• 【MongoDB】
  Mongo DB 是目前在IT行业非常流行的一种非关系型数据库(NoSql)
• 【Redis】
  一个高性能的key-value数据库
• 【Memcached】
  Memcached是一个自由开源的，高性能，分布式内存对象缓存系统。

移动端

• 【Android】
  Android 是一种基于Linux的自由及开放源代码的操作系统，主要使用于移动设备
• 【Swift】
  Swift 是一种支持多编程范式和编译式的编程语言,用于开发 iOS，OS X 和 watchOS应用程序。
• 【jQuery Mobile】
  jQuery Mobile是jQuery 在手机上和平板设备上的版本
• 【ionic】
  ionic 是一个强大的 HTML5 应用程序开发框架(HTML5 Hybrid Mobile App Framework )
• 【Kotlin】
  在 Java 虚拟机上运行的静态类型编程语言，Android 官方开发语言

XML 教程

• 【XML】
  XML 被设计用来传输和存储数据
• 【DTD】
  DTD（文档类型定义）的作用是定义 XML 文档的合法构建模块
• 【XML DOM】
  XML DOM 定义访问和操作XML文档的标准方法
• 【XSLT】
  XSL 是一个 XML 文档的样式表语言，XSLT 指 XSL 转换
• 【XPath】
  XPath 是一门在 XML 文档中查找信息的语言
• 【XQuery】
  XQuery 被设计用来查询 XML 数据
• 【XLink】
  XLink 定义在 XML 文档中创建超级链接的标准方法
• 【XPointer】
  XPointer是在可扩展标志语言（XML）文件中定位数据的一种语言
• 【XML Schema】
  XML Schema 描述了 XML文档的结构
• 【XSL-FO】
  XSL-FO 指可扩展样式表语言格式化对象
• 【SVG】
  SVG 使用 XML 格式定义图像

ASP.NET

• 【ASP.NET】
  ASP.NET 是一个使用 HTML、CSS、JavaScript 和服务器脚本创建网页和网站的开发框架
• 【C#】
  C# 是一个简单的、现代的、通用的、面向对象的编程语言
• 【Web Pages】
  Web Pages 是三种网页编程模型中的一种，用于创建网站和web 应用程序
• 【Razor】
  Razor 是一种标记语法，可以让您将基于服务器的代码（Visual Basic 和 C#）嵌入到网页中
• 【MVC】
  MVC（Model View Controller 模型-视图-控制器）
• 【Web Forms】
  Web Forms 是三种创建 ASP.NET 网站和 Web 应用程序的编程模式中的一种

Web Service

• 【Web Service】
  Web Service 脚本平台需支持 XML + HTTP
• 【WSDL】
  WSDL是一门基于 XML 的语言，用于描述 Web Service 以及如何对它们进行访问
• 【SOAP】
  SOAP 是一种简单的基于 XML 的协议，它使应用程序通过 HTTP 来交换信息
• 【RSS】
  RSS基于XML标准，在互联网上被广泛采用的内容包装和投递协议
• 【RDF】
  DF(资源描述框架)是描述网络资源的 W3C 标准

开发工具

• 【Eclipse】
  Eclipse 是一个开放源代码的、基于 Java 的可扩展开发平台
• 【Git】
  Git是一个开源的分布式版本控制系统，用于敏捷高效地处理任何或小或大的项目
• 【Svn】
  SVN 是一个开放源代码的版本控制系统
• 【Markdown】
  Markdown 是一种轻量级标记语

网站建设

• 【HTTP】
  HTTP协议（HyperText Transfer Protocol，超文本传输协议）是因特网上应用最为广泛的一种网络传输协议
• 【网站建设指南】
  网站建设指导课程
• 【浏览器信息】
  对于网站开发人员来说，浏览器信息和统计数据都是非常重要的
• 【网站主机教程】
  如果您希望向全世界发布自己的网站，那么您的网站就需要被放置于一个 WEB 服务器
• 【TCP/IP】
  TCP/IP 是因特网的通信协议
• 【W3C】
  W3C 让每个人都能在互联网上分享资源
• 【网站品质】
  何创建高质量的web网站

菜鸟教程