PythonRobotics

Python codes for robotics algorithm.

PaddlePaddle Models

PaddlePaddle 提供了丰富的计算单元，使得用户可以采用模块化的方法解决各种学习问题。在此Repo中，我们展示了如何用 PaddlePaddle来解决常见的机器学习任务，提供若干种不同的易学易用的神经网络模型。PaddlePaddle用户可领取免费Tesla V100在线算力资源，高效训练模型，每日登陆即送12小时，连续五天运行再加送48小时，前往使用免费算力。

RSA算法详解

前言
总括： 本文详细讲述了RSA算法详解，包括内部使用数学原理以及产生的过程。

原文博客地址：RSA算法详解

知乎专栏&&简书专题：前端进击者（知乎）&&前端进击者（简书）

博主博客地址：Damonare的个人博客

相濡以沫。到底需要爱淡如水。

正文
之前写过一篇文章SSL协议之数据加密过程，里面详细讲述了数据加密的过程以及需要的算法。SSL协议很巧妙的利用对称加密和非对称加密两种算法来对数据进行加密。这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述。首先先来了解下这个算法的历史：

RSA算法的历史

RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

但实际上，在1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯（Clifford Cocks）在一个内部文件中提出了一个相同的算法，但他的发现被列入机密，一直到1997年才被发表。

所以谁是RSA算法的发明人呢？不好说，就好像贝尔并不是第一个发明电话的人但大家都记住的是贝尔一样，这个地方我们作为旁观者倒不用较真，重要的是这个算法的内容：

RSA算法的过程

RSA算法用到的数学知识特别多，所以在中间介绍这个算法生成私钥和公钥的过程中会穿插一些数学知识。生成步骤如下：

1. 寻找两个不相同的质数
   随意选择两个大的质数p和q，p不等于q，计算N=p*q;

什么是质数?我想可能会有一部分人已经忘记了，定义如下：

除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1该数本身两个正因数]的数）。

比如2，3，5，7这些都是质数，9就不是了，因为3*3=9了

2. 根据欧拉函数获取r
   r = φ(N) = φ(p)φ(q) = (p-1)(q-1)。

这里的数学概念就是什么是欧拉函数了，什么是欧拉函数呢？

欧拉函数的定义：

欧拉函数 φ(n)是小于或等于n的正整数中与n互质的数的数目。

互质的定义：

如果两个或两个以上的整数的最大公约数是 1，则称它们为互质

例如：φ(8) = 4，因为1,3,5,7均和8互质。

推导欧拉函数:

（1）如果n = 1, φ(1) = 1；(小于等于1的正整数中唯一和1互质的数就是1本身)；

（2）如果n为质数，φ(n) = n - 1；因为质数和每一个比它小的数字都互质。比如5，比它小的正整数1,2,3,4都和他互质；

(3) 如果n是a的k次幂，则 φ(n) = φ(a^k) = a^k - a^(k-1) = (a-1)a^(k-1)；

(4) 若m,n互质，则φ(mn) = φ(m)φ(n)

证明：设A, B, C是跟m, n, mn互质的数的集，据中国剩余定理(经常看数学典故的童鞋应该了解，剩余定理又叫韩信点兵，也叫孙子定理)，A*B和C可建立双射一一对应)的关系。（或者也可以从初等代数角度给出欧拉函数积性的简单证明） 因此的φ(n)值使用算术基本定理便知。（来自维基百科）

3. 选择一个小于r并与r互质的整数e
   选择一个小于r并与r互质的整数e，求得e关于r的模反元素，命名为d（ed = 1(mod r)模反元素存在，当且仅当e与r互质），e我们通常取65537。

模反元素：

如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。

比如3和5互质，3关于5的模反元素就可能是2，因为32-1=5可以被5整除。所以很明显模反元素不止一个，2加减5的整数倍都是3关于5的模反元素{…-3, 2,7,12…}* 放在公式里就是3*2 = 1 (mod 5)

上面所提到的欧拉函数用处实际上在于欧拉定理：

欧拉定理：

如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：

a^φ(n) = 1(mod n)

由此可得：a的φ(n - 1)次方肯定是a关于n的模反元素。

欧拉定理就可以用来证明模反元素必然存在。

由模反元素的定义和欧拉定理我们知道，a的φ(n)次方减去1，可以被n整除。比如，3和5互质，而5的欧拉函数φ(5)等于4，所以3的4次方(81)减去1，可以被5整除（80/5=16）。

小费马定理：

假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成

a^(p-1) = 1 (mod p)

这其实是欧拉定理的一个特例。

4. 销毁p和q
   此时我们的(N , e)是公钥，(N, d)为私钥，爱丽丝会把公钥(N, e)传给鲍勃，然后将(N, d)自己藏起来。一对公钥和私钥就产生了，然后具体的使用方法呢？请看：SSL协议之数据加密过程详解

RSA算法的安全性

我们知道像RSA这种非对称加密算法很安全，那么到底为啥子安全呢？ 我们来看看上面这几个过程产生的几个数字：

p,q：我们随机挑选的两个大质数；
N：是由两个大质数p和q相乘得到的。N = p * q；
r：由欧拉函数得到的N的值，r = φ(N) = φ(p)φ(q) = (p-1)(q-1)。
e：随机选择和和r互质的数字，实际中通常选择65537；
d： d是以欧拉定理为基础求得的e关于r的模反元素，ed = 1 (mod r)；
N和e我们都会公开使用，最为重要的就是私钥中的d，d一旦泄露，加密也就失去了意义。那么得到d的过程是如何的呢？如下:

比如知道e和r，因为d是e关于r的模反元素；r是φ(N) 的值
而φ(N)=(p-1)(q-1)，所以知道p和q我们就能得到d;
N = pq，从公开的数据中我们只知道N和e，所以问题的关键就是对N做因式分解能不能得出p和q
所以得出了在上篇博客说到的结论，非对称加密的原理：

将a和b相乘得出乘积c很容易，但要是想要通过乘积c推导出a和b极难。即对一个大数进行因式分解极难

目前公开破译的位数是768位，实际使用一般是1024位或是2048位，所以理论上特别的安全。

后记
RSA算法的核心就是欧拉定理，根据它我们才能得到私钥，从而保证整个通信的安全。

440. 字典序的第K小数字

题目

给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。

注意：1 ≤ k ≤ n ≤ 109。

示例 :

1
2
3
4
5
6
7
8

输入:
n: 13   k: 2

输出:
10

解释:
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

题解

乍一看这一题貌似毫无头绪，什么是字典序？如何定位这个数？没错，刚接触这个题目的时候，我的脑筋里也是一团乱麻。

但是我觉得作为一个拥有聪明才智的程序员来说，最重要的能力就是迅速抽象问题、拆解问题的能力。经过一段时间的思考，我的脑筋里还是没有答案。

哈哈。

言归正传，我们来分析一下这个问题。

首先，什么是字典序？

什么是字典序？
简而言之，就是根据数字的前缀进行排序，

比如10 < 9，因为10的前缀是1，比9小，

再比如112 < 12，因为112的前缀11小于12。

这样排序下来，会跟平常的升序排序会有非常大的不同。先给你一个直观的感受，一个数乘10，或者加1，哪个大？可能你会吃惊，后者会更大。

但其实掌握它的本质之后，你一点都不会吃惊。

问题建模
画一个图你就懂了。

每一个节点都拥有10个孩子节点，因为作为一个前缀 ，它后面可以接0~9这十个数字。而且你可以非常容易地发现，整个字典序排列也就是对十叉树进行层序遍历。1, 10, 11, 12, 13 … 100, 101, …

回到题目的意思，我们需要找到排在第k位的数。找到他的排位，需要搞清楚三件事情:

怎么确定一个前缀下所有子节点的个数？
如果第k个数在当前的前缀下，怎么继续往下面的子节点找？
如果第k个数不在当前的前缀，即当前的前缀比较小，如何扩大前缀，增大寻找的范围？
接下来 ，我们一一拆解这些问题。

理顺思路

1. 确定指定前缀下所有子节点数
   现在的任务就是给定一个前缀，返回下面子节点总数。

我们现在的思路就是用下一个前缀的起点减去当前前缀的起点，那么就是当前前缀下的所有子节点数总和啦。

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

//prefix是前缀，n是上界
var getCount = (prefix, n) => {
    let cur = prefix;
    let next = prefix + 1;//下一个前缀
    let count = 0;
    //当前的前缀当然不能大于上界
    while(cur <= n) {
        count += next - cur;//下一个前缀的起点减去当前前缀的起点
        cur *= 10; 
        next *= 10;
        // 如果说刚刚prefix是1，next是2，那么现在分别变成10和20
        // 1为前缀的子节点增加10个，十叉树增加一层, 变成了两层
        
        // 如果说现在prefix是10，next是20，那么现在分别变成100和200，
        // 1为前缀的子节点增加100个，十叉树又增加了一层，变成了三层
    }
    return count;//把当前前缀下的子节点和返回去。
}

当然，不知道大家发现一个问题没有，当next的值大于上界的时候，那以这个前缀为根节点的十叉树就不是满十叉树了啊，应该到上界那里，后面都不再有子节点。因此，count += next - cur还是有些问题的，我们来修正这个问题:

1

count += Math.max(n+1, next) - cur;

你可能会问:咦？怎么是n+1,而不是n呢？不是说好了n是上界吗？

我举个例子，假若现在上界n为12，算出以1为前缀的子节点数，首先1本身是一个节点，接下来要算下面10，11，12，一共有4个子节点。

那么如果用Math.max(n, next) - cur会怎么样？

这时候算出来会少一个，12 - 10加上根节点，最后只有3个。因此我们务必要写n+1。

现在，我们搞定了前缀的子节点数问题。

2. 第k个数在当前前缀下
   现在无非就是往子树里面去看。

prefix这样处理就可以了。

1

prefix *= 10

3.第k个数不在当前前缀下
说白了，当前的前缀小了嘛，我们扩大前缀。

1

prefix ++;

框架搭建
整合一下刚刚的思路。

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

let findKthNumber = function(n, k) {
  let p = 1;//作为一个指针，指向当前所在位置，当p==k时，也就是到了排位第k的数
  let prefix = 1;//前缀
  while(p < k) {
    let count = getNumber(prefix, n);//获得当前前缀下所有子节点的和
    if(p + count > k) { //第k个数在当前前缀下
      prefix *= 10;
      p++; //把指针指向了第一个子节点的位置，比如11乘10后变成110，指针从11指向了110
    } else if(p + count <= k) { //第k个数不在当前前缀下
      prefix ++;
      p += count;//注意这里的操作，把指针指向了下一前缀的起点
    }
  }
  return prefix;
};

完整代码展示

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

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var findKthNumber = function(n, k) {
  let getCount = (prefix, n) => {
    let count =  0;
    for(let cur = prefix, next = prefix + 1; cur <= n; cur *= 10, next *= 10) 
      count += Math.min(next, n+1) - cur;
    return count;
  }
  let p = 1;
  let prefix = 1;
  while(p < k) {
    let count = getCount(prefix, n);
    if(p + count > k) {
      prefix *= 10;
      p++;
    } else if(p + count <= k) {
      prefix ++;
      p += count;
    }
  }
  return prefix;
};

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

public class Solution {
    /**
     * @param n: a integer
     * @param k: a integer
     * @return: return a integer
     */
    public int findKthNumber(int n, int k) {
        int curr = 1;
        k = k - 1;
        while (k > 0) {
            int steps = calSteps(n, curr, curr + 1);
            if (steps <= k) {   //如果不在当前层，减去steps
                curr += 1;      
                k -= steps;  
            } 
            else {              //说明在当前层,curr*10缩小搜索范围继续查找
                curr *= 10;
                k -= 1;
            }
        }
        return curr;
    }
    //use long in case of overflow
    public int calSteps(int n, long n1, long n2) { //计算curr开头和curr+1开头之间的字符串数量
        int steps = 0;
        while (n1 <= n) {
            steps += Math.min(n + 1, n2) - n1;  //每次加上当前的字符串数量
            n1 *= 10;       //每次均扩大10倍
            n2 *= 10;
        }
        return steps;
    }
}

什么是红黑树

红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(logn)。

它的统计性能要好于平衡二叉树（AVL树），因此，红黑树在很多地方都有应用。比如在 Java 集合框架中，很多部分(HashMap, TreeMap, TreeSet 等)都有红黑树的应用，这些集合均提供了很好的性能。

由于 TreeMap 就是由红黑树实现的，因此本文将使用 TreeMap 的相关操作的代码进行分析、论证。

黑色高度
从根节点到叶节点的路径上黑色节点的个数，叫做树的黑色高度。

红黑树的 5 个特性

红黑树在原有的二叉查找树基础上增加了如下几个要求：

1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

中文意思是：

1. 每个节点要么是红色，要么是黑色；
2. 根节点永远是黑色的；
3. 所有的叶节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）；
4. 每个红色节点的两个子节点一定都是黑色；
5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；

注意：
性质 3 中指定红黑树的每个叶子节点都是空节点，而且并叶子节点都是黑色。但 Java 实现的红黑树将使用 null 来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的。

性质 4 的意思是：从每个根到节点的路径上不会有两个连续的红色节点，但黑色节点是可以连续的。
因此若给定黑色节点的个数 N，最短路径的情况是连续的 N 个黑色，树的高度为 N - 1;最长路径的情况为节点红黑相间，树的高度为 2(N - 1) 。

性质 5 是成为红黑树最主要的条件，后序的插入、删除操作都是为了遵守这个规定。

红黑树并不是标准平衡二叉树，它以性质 5 作为一种平衡方法，使自己的性能得到了提升。

红黑树的左旋右旋

红黑树的左右旋是比较重要的操作，左右旋的目的是调整红黑节点结构，转移黑色节点位置，使其在进行插入、删除后仍能保持红黑树的 5 条性质。

比如 X 左旋(右图转成左图)的结果，是让在 Y 左子树的黑色节点跑到 X 右子树去。

我们以 Java 集合框架中的 TreeMap 中的代码来看下左右旋的具体操作方法：

指定节点 x 的左旋 (右图转成左图)：

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

 //这里 p 代表 x
private void rotateLeft(Entry p) {
    if (p != null) {
        Entry r = p.right; // p 是上图中的 x，r 就是 y
        p.right = r.left;       // 左旋后，x 的右子树变成了 y 的左子树 β 
        if (r.left != null)         
            r.left.parent = p;  //β 确认父亲为 x
        r.parent = p.parent;        //y 取代 x 的第一步：认 x 的父亲为爹
        if (p.parent == null)       //要是 x 没有父亲，那 y 就是最老的根节点
            root = r;
        else if (p.parent.left == p) //如果 x 有父亲并且是它父亲的左孩子，x 的父亲现在认 y 为左孩子，不要 x 了
            p.parent.left = r;
        else                            //如果 x 是父亲的右孩子，父亲就认 y 为右孩子，抛弃 x
            p.parent.right = r;
        r.left = p;     //y 逆袭成功，以前的爸爸 x 现在成了它的左孩子
        p.parent = r;
    }
}

可以看到，x 节点的左旋就是把 x 变成 右孩子 y 的左孩子，同时把 y 的左孩子送给 x 当右子树。

简单点记就是：左旋把右子树里的一个节点（上图 β）移动到了左子树。

指定节点 y 的右旋（左图转成右图）：

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

private void rotateRight(Entry p) {
    if (p != null) {
        Entry l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}

同理，y 节点的右旋就是把 y 变成 左孩子 x 的右孩子，同时把 x 的右孩子送给 x 当左子树。

简单点记就是：右旋把左子树里的一个节点（上图 β）移动到了右子树。

了解左旋、右旋的方法及意义后，就可以了解红黑树的主要操作：插入、删除。

总结

红黑树并不是真正的平衡二叉树，但在实际应用中，红黑树的统计性能要高于平衡二叉树，但极端性能略差。

红黑树的插入、删除调整逻辑比较复杂，但最终目的是满足红黑树的 5 个特性，尤其是 4 和 5。

在插入调整时为了简化操作我们直接把插入的节点涂成红色，这样只要保证插入节点的父节点不是红色就可以了。

而在删除后的调整中，针对删除黑色节点，所在子树缺少一个节点，需要进行弥补或者对别人造成一个黑色节点的伤害。具体调整方法取决于兄弟节点所在子树的情况。

红黑树的插入、删除在树形数据结构中算比较复杂的，理解起来比较难，但只要记住，红黑树有其特殊的平衡规则，而我们为了维持平衡，根据邻树的状况进行旋转或者涂色。

红黑树这么难理解，必定有其过人之处。它的有序、快速特性在很多场景下都有用到，比如 Java 集合框架的 TreeMap, TreeSet 等。

树的高度（小米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]
}

题目

一个天平上有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
来源：掘金