AOSP 入门

源码下载

国内同步UTSC源

第一次同步数据量特别大，如果网络不稳定，中间失败就要从头再来了。所以我们提供了打包的 AOSP 镜像，为一个 tar 包，大约 16G（单文件 16G，注意你的磁盘格式要支持）。这样你 就可以通过 HTTP 的方式下载，该方法支持断点续传。

下载地址 http://mirrors.ustc.edu.cn/aosp-monthly/

请注意对比 checksum。

然后根据下文 已有仓库如何改用科大源 的方法更改同步地址。

解压后用命令 repo sync 就可以把代码都 checkout 出来。

Note: tar 包为定时从 https://mirrors.tuna.tsinghua.edu.cn/aosp-monthly/ 下载。

科学同步 googlesource

按照 Google 官方教程 https://source.android.com/source/downloading.html

https://android.googlesource.com/platform/manifest

具体做法摘录如下（以防墙抽风）：

首先下载 repo 工具。

1
2
3

mkdir ~/bin
PATH=~/bin:$PATH
curl https://storage.googleapis.com/git-repo-downloads/repo > ~/bin/repo

然后建立一个工作目录（名字任意）

1
2

mkdir WORKING_DIRECTORY
cd WORKING_DIRECTORY

初始化仓库：

1

repo init

同步源码树（以后只需执行这条命令来同步）：

1

repo sync

AOSP源码导入Android Studio

AOSP源码顶级目录下运行以下命令，生成google推荐的Idegen工具的配置文件android.ipr和android.iml

1
2
3

source build/envsetup.sh # 在新终端下需要执行这一步
mmma development/tools/idegen
development/tools/idegen/idegen.sh

过滤一些模块
如果把Android所有的源码全部导入到IDE里面去，工程将会非常大，而且会很耗时间，那么我们就可以把不需要的模块给过滤掉。
打开android.iml文件，加入以下代码，修改excludeFolder的配置：

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

<excludeFolder url="file://$MODULE_DIR$/.repo"/>
<excludeFolder url="file://$MODULE_DIR$/abi"/>
<excludeFolder url="file://$MODULE_DIR$/frameworks/base/docs"/>
<excludeFolder url="file://$MODULE_DIR$/art"/>
<excludeFolder url="file://$MODULE_DIR$/bionic"/>
<excludeFolder url="file://$MODULE_DIR$/bootable"/>
<excludeFolder url="file://$MODULE_DIR$/build"/>
<excludeFolder url="file://$MODULE_DIR$/cts"/>
<excludeFolder url="file://$MODULE_DIR$/dalvik"/>
<excludeFolder url="file://$MODULE_DIR$/developers"/>
<excludeFolder url="file://$MODULE_DIR$/development"/>
<excludeFolder url="file://$MODULE_DIR$/device"/>
<excludeFolder url="file://$MODULE_DIR$/docs"/>
<excludeFolder url="file://$MODULE_DIR$/external"/>
<excludeFolder url="file://$MODULE_DIR$/hardware"/>
<excludeFolder url="file://$MODULE_DIR$/kernel-3.18"/>
<excludeFolder url="file://$MODULE_DIR$/libcore"/>
<excludeFolder url="file://$MODULE_DIR$/libnativehelper"/>
<excludeFolder url="file://$MODULE_DIR$/ndk"/>
<excludeFolder url="file://$MODULE_DIR$/out"/>
<excludeFolder url="file://$MODULE_DIR$/pdk"/>
<excludeFolder url="file://$MODULE_DIR$/platform_testing"/>
<excludeFolder url="file://$MODULE_DIR$/prebuilts"/>
<excludeFolder url="file://$MODULE_DIR$/rc_projects"/>
<excludeFolder url="file://$MODULE_DIR$/sdk"/>
<excludeFolder url="file://$MODULE_DIR$/system"/>
<excludeFolder url="file://$MODULE_DIR$/tools"/>
<excludeFolder url="file://$MODULE_DIR$/trusty"/>
<excludeFolder url="file://$MODULE_DIR$/vendor"/>

这样我们就只导入了frameworks和packages的代码。

AOSP工程项目很大，在导入源码到IDEA之前需要先修改IDEA的配置：
修改内存大小：
打开IDEA 菜单栏Help >Edit Custom VM Options，添加

1
2

-Xms1g 
-Xmx5g

修改文件大小限制，打开区分大小写选项:
打开IDEA 菜单栏 Help -> Edit custom properties， 添加

1
2

idea.max.intellisense.filesize=100000
idea.case.sensitive.fs=true

NOTE: 重启IDEA使配置生效

用IDEA找到AOSP目录下的development/tools/idegen/android.ipr文件，打开AOSP工程，耐心等待，索引需要一定时间

Reference

AOSP(Android) 镜像使用帮助
AOSP Intellij IDE 导入源码阅读

字符串 trick

分享个字母大小写转换的方法：

1. 统一转成大写：ch & 0b11011111 简写：ch & 0xDF
2. 统一转成小写：ch | 0b00100000 简写：ch | 0x20
3. 大小写互换：ch …… 0b00100000 简写：ch ^ 0x20，原来是小写转成大写，原来是大写则转成小写

比较的时候注意加上小括号哦，因为位运算优先级比较低。

原理：65～90为26个大写英文字母，97～122号为26个小写英文字母

65（0100 0001）到 90（0101 1010），刚好第5位（从0开始）都为0

97（0110 0001）到 122（0111 1010），刚好第5位（从0开始）都为1

说明： ch & 0b11011111 ，效果就是将第5位（从0开始）清0，即如果第5位原来为0（大写字母），则保持不变，否则，减去32（小写转大写），小写字母转换成对应的大写字母正好就是减32

同理，ch | 0b00100000，效果是如果第5位（从0开始）为0（大写字母），则加32，否（大写转小写）则，保持不变

蓄水池抽样

给定一个数据流，数据流长度N很大，且N直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出k个不重复的数据。

算法应用的场景特点：

1. online算法，数据流一遍输入一遍抽样
2. 时间复杂度O(N)
3. 每个样本抽中概率=k/N，（k是事先确定的，与N无关）$^1$

抽样过程:

• 假设数据序列的规模为 n，需要采样的数量的为 k。

• 首先构建一个可容纳 k 个元素的数组，将序列的前 k 个元素放入数组中。

• 然后从第 i = k+1 个元素开始，生成一个随机数 d∈[1,i]， 如果 d <= k， 那么蓄水池的第 d 个元素被替换为数据流中的第 i 个元素

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

int[] reservoir;

public void sample(int[] dataStream) {
    for (int i = 0; i < reservoir.length; i++) {
        reservoir[i] = dataStream[i];
    }

    for (int i = k; i < dataStream.length; i++) {
        int d = rand.nextInt(i + 1);
        if (d < k) {
            reservoir[d] = dataStream[i];
        }
    }
}

算法正确性：

1. 对于第 i 个数（i ≤ k）。在 k 步之前，被选中的概率为 1。当走到第 k+1 步时，被 k+1 个元素替换的概率 = k+1 个元素被选中的概率 x i 被选中替换的概率，即为 $\frac{k}{k+1}\frac{1}{k}=\frac{1}{k+1}$。则被保留的概率为 $1-\frac{1}{k+1}=\frac{k}{k+1}$。依次类推，不被 k+2 个元素替换的概率为 $1-\frac{k}{k+2}\frac{1}{k}=\frac{k+1}{k+2}$。则运行到第 n 步时，被保留的概率 = 被选中的概率 x 不被替换的概率，即：
   $$1\frac{k}{k+1}\frac{k+1}{k+2}\frac{k+2}{k+3}…\frac{N-1}{N} = \frac{k}{N}$$

2. 对于第 j 个数（j > k）。在第 j 步被选中的概率为 $\frac{k}{j}$。不被 j+1 个元素替换的概率为 $1 - \frac{k}{j+1}\frac{1}{k} = \frac{j}{j+1}$。则运行到第 n 步时，被保留的概率 = 被选中的概率 x 不被替换的概率，即：
   $$\frac{k}{j}\frac{j}{j+1}\frac{j+1}{j+2}\frac{j+2}{j+3}…\frac{N-1}{N} = \frac{k}{N}$$

所以对于其中每个元素，被保留的概率都为 $\frac{k}{N}$.

题外

抽样证明过程看起来和Knuth-shuffle算法有点像

1
2
3
4
5
6
7
8
9

public static <T> void shuffle(T[] A) {
    for (int i = A.length - 1; i > 0; i--) {
        int rand = (int) (Math.random() * (i + 1));
        // swap A[i] and A[rand]
        T temp = A[i];
        A[i] = A[rand];
        A[rand] = temp;
    }
}

reference

蓄水池抽样算法（Reservoir Sampling）

【算法34】蓄水池抽样算法 (Reservoir Sampling Algorithm)

蓄水池采样算法

$^1$ 如果k与N有关呢？ 例如k=N/3，怎么抽样，思考一下

二进制数中1的个数

1. naive，一位一位数

   1 2 3 4 5 6 7 8 9 10 11

   unsigned int popcount(unsigned int x) { unsigned n = 0; for (int i = 0; i < 32; i++) { if (x == 0) { break; } n += x & 1; x = x >> 1; } return n; }

2. 相对暴力，只数有1的位，复杂度O(有多少个1)

   1 2 3 4 5 6 7 8

   unsigned int popcount(unsigned int x) { unsigned n = 0; while (x) { x = x & (x - 1); ++n; } return n; }

3. 二分法, 复杂度O(log32)

   1 2 3 4 5 6 7 8 9 10 11

   unsigned int popcount(unsigned int n) { /* * swar algorithm, work on 32 bit integer */ n = (n & 0x55555555) + ((n >> 1) & 0x55555555); n = (n & 0x33333333) + ((n >> 2) & 0x33333333); n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F); n = (n & 0x00FF00FF) + ((n >> 8) & 0x00FF00FF); n = (n & 0x0000FFFF) + ((n >> 16) & 0x0000FFFF); return n; }

   想法类似二分，两两相加

   

   将32位数看成相互独立的32个 0-1 数字,
   然后两两相加, 这样我们就有16个数字了,
   然后再两两相加, 就变成8个数字了,
   接着再两两相加变成4个,
   然后两个, 最后一个数字,
   由于是32位数字的和, 所以答案刚好就是1的个数啦。

   1 2 3 4 5

   右移 1位. 与数字: 01010101010101010101010101010101 => 0x55555555 右移 2位. 与数字: 00110011001100110011001100110011 => 0x33333333 右移 4位. 与数字: 00001111000011110000111100001111 => 0x0F0F0F0F 右移 8位. 与数字: 00000000111111110000000011111111 => 0x00FF00FF 右移16位. 与数字: 00000000000000001111111111111111 => 0x0000FFFF

4. 查表，预先算好，查询时直接读

   表的大小可以改，比如256，适当取

   1 2 3 4 5 6 7 8 9 10 11

   #define MAXN 1<<16 int table[MAXN]; void pre() { for (int i = 1; i < MAXN; i++) { table[i] = table[i >> 1] + (i & 1); } } unsigned popcount(unsigned x) { return (table[x >> 16] + table[x & 0xFFFF]); }

reference

详解二进制数中1的个数

Java中的char类型和中文字符

开篇发问

1

Java里的char类型能不能存储一个中文字符？

答案是：可以，但细究起来，并不是简简单单的可以

Unicode

对于中文来说，编码方式的使用字节大小各有不同。utf-8：一个中文占用三个字节，utf-16：一个中文占2个字节；gbk(中国人的编码方式)一个汉字2个字节等。Unicode类似一个文字容器，编码方式是一个解码工具，目的是在unicode的字符集中寻找一个对应的字符(我的理解是编码方式是快递员)。众所周知，Unicode有3种编码方式：utf-8, utf-16, utf-32。Unicode标准把代码点分成了17个代码平面（Code Plane），编号为#0到#16。每个代码平面包含65,536（2^16）个代码点（17*65,536=1,114,112）。其中，Plane#0叫做基本多语言平面（Basic Multilingual Plane，BMP），其余平面叫做补充平面（Supplementary Planes）。

下面是这些平面的名字和用途：

Plane#0 BMP（Basic Multilingual Plane）大部分常用的字符都坐落在这个平面内，比如ASCII字符，汉字等。
Plane#1 SMP（Supplementary Multilingual Plane）这个平面定义了一些古老的文字，不常用。
Plane#2 SIP（Supplementary Ideographic Plane）这个平面主要是一些BMP中没有包含汉字。
Plane#14 SSP（Supplementary Special-purpose Plane）这个平面定义了一些非图形字符。
Plane#15 SPUA-A（Supplementary Private Use Area A）
Plane#16 SPUA-B（Supplementary Private Use Area B）

Java中char类型

Java中的char类型是按照Unicode规范实现的一种数据类型，固定16bit大小。现如今，Unicode字符集已经进行了扩展，表示的范围已经超过了16bit。Unicode字符集的数值范围扩大到了[U+0000,U+10FFFF]。一个char值可以表示BMP范围内的Unicode字符。BMP表示[U+0000, U+FFFF]之间的Unicode字符。而且，绝大部分的中文字符的Unicode范围是[0x4E00, 0x9FBB],恰好是在BMP范围内。

就常用的UTF-8编码来说，我们都听说过他是用3或者4个字节来表示一个汉字的。就拿3个字节来算的话，一个char也存不下？？

UTF-8编码和代码点对应关系:

当一个字节表示一个字符时，二进制开头是0；当两个字节表示一个字符时，二进制开头是11；当3个字节表示一个字符时，二进制开头是111。UTF-8编码加入了多余的标识位来区分一个Unicode代码点！才会出现中文汉字集中在[0x4E00, 0x9FBB]范围的16bit数值内，UTF-8却需要3个字节存储的原因。

那么UTF-8占用3到4个字节，char只能存2个字节（16bit），然而UTF-8中的几乎所有汉字都是在BMP范围内，也就是在char可存储的范围内，是不是矛盾了？

其实不然，

1. char字符存储的是Unicode编码的代码点，也就是存储的是U+FF00这样的数值，然而我们在调试或者输出到输出流的时候，是JVM或者开发工具按照代码点对应的编码字符输出的，Java内部使用UTF-16编码。

2. 所以虽然UTF-8编码的中文字符是占用3个或者4个字节，但是对应的代码点仍然集中在[0x4E00, 0x9FBB]，所以char是能够存下在这个范围内的中文字符的。

3. 但是对于超过16bit的Unicode字符集，也就是Unicode的扩展字符集，一个char是放不下的，需要两个char才能放下。

另外，如何判断java字符串是否包含中文？

1
2
3
4
5
6
7
8
9
10
11

/**
 * 判断某个字符是否为汉字
 *
 * @param c 需要判断的字符
 * @return 是汉字返回true，否则返回false
 */
public static boolean isChinese(char c)
{
    String regex = "[\\u4e00-\\u9fa5]";
    return String.valueOf(c).matches(regex);
}

这里没有考虑CJK扩展字符集。

PS: 一个查找中文字符utf-8编码网址：http://www.mytju.com/classcode/tools/encode_utf8.asp

reference

Java中的char究竟能存中文吗？

细说Java中的字符和字符串（一）

HanLP自然语言处理库

Binary Indexed Tree

树状数组（或者直译过来就是：二进制下标树）支持两种操作，时间复杂度均为$O(logn)$

• 单点修改：更改数组中的一个元素的值
• 区间查询：查询一个区间内所有元素的和

先放个图，直观感受一下树状数组如何维护数据的

可以看到，树状数组（以下简称BIT）里的$C_i$维护一个小区间。BIT选择的维护的区间长度和i的二进制表示息息相关，从而做到了查询和修改的复杂度都在O(logn)内。借用BIT原始论文中的图来展示数组的$C_i$对应原始数组的哪些项，可以看到一个竖条对应一个$C_{i}$维护的区间，竖条顶端的阴影方块对应的数字就是这个区间累加和存在BIT中相应的下标。

BIT巧妙利用了二进制的表示。例如查询前11项和query(11)，这在BIT中是如何判断该合并那些区间来输出前11项的和呢？先看11的二进制表示$(1011)_2$，在BIT中前11项的和由$((0000)_2, (1000)_2]$，$((1000)_2, (1010)_2]$，$((1010)_2, (1011)_2]$这些区间组成，其中奥秘如下图：

区间下标的变化：不断移出二进制下标最低位的1

求二进制最右边的1到末尾的大小（最右边的1和之后的0组成的数字），这里用到了补码的知识。对于$(1011)_2$，先取反得到$(0100)_2$，再加1变成$(0101)_2$，再和原数相加，1011 & 0100，最后得到$(0011)_2$。其中，取反加一，根据补码的知识，可以通过语言中整数取相反数得到。

lowbit的实现

1
2
3

public int lowbit(int x) {
    return (x & -x);
}

单点修改

那么更新过程如同在“爬树”，从更新的index沿着下图中的树型结构向ancestor爬，知道超出数组界限。顺便说明一下，树状数组的下标从1开始，tree[0]是不存东西的。比如，原始数组中的3这个位置的数据更新了，那么相应的3->4->8->…都需要更新，正好每次向上爬的index加的正是lowbit(x)

1
2
3
4
5
6
7
8
9

public void update(int i, int inc) {
    /*
	* @param inc increment value for i-th array item
	*/
    while (i <= MAX_N) {
        tree[i] += inc;
        i += lowbit(i);
    }
}

区间查询

区间和的查询过程也有一个树型结构。比如查询前11项的和，初始n=11，沿着树向上，11->10->8->0到0为止，前11项的和=BIT[11] + BIT[10] + BIT[8]。这和之前讲lowbit函数，解释树状数组中区间的下标变化，是一样的过程。

前n项前缀和

1
2
3
4
5
6
7
8
9
10
11

public int query(int n) {
    /*
    * @return the sum of first n items
    */
    int sum = 0;
    while (n > 0) {
        sum += tree[n];
        n -= lowbit(n);
    }
    return sum;
}

区间查询

1
2
3
4
5
6
7

public int query(int l, int r) {
    /*
    * query range sum begins at the specified index l and extends to the index r,
    * range length is (r - l + 1)
    */
    return (query(r) - query(l - 1));
}

有趣的是，树状数组还可以求逆序对，见（洛谷P1908）逆序对

Reference

算法学习笔记(2) : 树状数组

二叉索引树（树状数组）的原理

1. vim系统剪切板
   “+y 复制到系统clipboard
   “+p clipboard粘贴到vim
   在Ubuntu中使用vim, 发现无法使用系统clipboard，可能是缺少相关的包

   1 2 3

   sudo apt-get install vim-scripts vim-gtk # 检测vim是否支持system clipboard vim --version | grep clipboard

2. Vim寄存器
   :help register查看10类48个寄存器

• a-z命名寄存器（26个）
• "*, "+, "- 选取拖放
• ": 只读，vim命令行
• "/ 搜说模式寄存器

Reference:

使用Vim寄存器

快速幂算法的原理及实现

先放代码实现

1
2
3
4
5
6
7
8
9
10
11

public int pow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1 == 1) {
            res *= a;
        }
        a *= a;
        b >>= 1;
    }
    return res;
}

快速幂算法的原理是通过将指数拆分成几个因数相乘的形式，来简化幂运算。在我们计算$3^{13}$的时候，普通的幂运算算法需要计算13次，但是如果我们将它拆分成$3^{8+4+1}$，再进一步拆分成 $3^{8}*3^{4}*3^{1}$只需要计算4次。嗯？哪来的4次？，别急，接着看。

这种拆分思想其实就是借鉴了二进制与十进制转换的算法思想，我们知道13的二进制是1101，可以知道：

$13 = 1 * 2^{3} + 1 * 2^{2} + 0 * 2^{1} + 1 * 2^{0} = 8 + 4 + 1$

实现的代码已经给出，原理就是利用位运算里的位移>>和按位与&运算，代码中b & 1其实就是取b二进制的最低位，用来判断最低位是0还是1，再根据是0还是1决定乘不乘，不理解的话联系一下二进制转换的过程。b >>= 1其实就是将b的二进制向右移动一位，就这样位移、取最低位、位移、取最低位，这样循环计算，直到指数b为0为止，整个过程和我们手动将二进制转换成十进制是非常相似的。普通幂算法是需要循环指数次，也就是指数是多少就要循环计算多少次，而快速幂因为利用了位移运算，只需要算“指数二进制位的位数”次，对于13来说，二进制是1101，有4位，就只需要计算4次，快速幂算法时间复杂度是O(logn)级别，对于普通幂需要计算一百万次的$10^{10^{6}}$来说，快速幂只需要计算6次，这是速度上质的飞跃，但是需要多注意溢出的问题。

转载: 快速幂算法的原理及实现

康托展开

简单说：

给出一个1-n的全排列 -> 问这是第几个排列(字典序), 这是康托展开

知道全排列长度和字典序 -> 问这个全排列长啥样，这是逆展开

来自Wikipedia的说明：康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序。

把1-n的所有排列按字典序排序，这个排列的位次就是它的排名。排列和它的排名是一一对应的，也就是说康托展开是双射，正反过程都是行得通的，才有逆展开。例子可以看LeetCode 60.排列序列的问题描述，对字典序和逆过程可以直观理解一下。

简单展开

$X = a_n(n-1)! + a_{n-1}(n-2)! + … + a_10!$

一个全排列，第i位有n-1-i种选择。

比如4321这个全排列，第一个数为4，比4小的选择有{1, 2, 3} 3个数

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

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

考虑到后面还有3位（n=3的全排列有3!种），所以开头为4的排列的序号从3*3!开始。首位为k的n阶全排列，它表示的数在从0开始第k个长为(n-1)!的区间，这个区间为[(k-1)*(n-1)!, k*(n-1)!]

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

0   X 2 3 4  <==>  1 2 3
1   X 2 4 3  <==>  1 3 2
2   X 3 2 4  <==>  2 1 3
3   X 3 4 2  <==>  2 3 1
4   X 4 2 3  <==>  3 1 2
5   X 4 3 2  <==>  3 2 1
6   X 1 3 4  <==>  1 2 3
7   X 1 4 3  <==>  1 3 2
8   X 3 1 4  <==>  2 1 3
9   X 3 4 1  <==>  2 3 1
10  X 4 3 1  <==>  3 1 2
11  X 4 3 1  <==>  3 2 1
12  X 1 2 4  <==>  1 2 3
13  ...

上图展示了4阶全排列和3阶全排列的关系，也就是说，去掉第1位后，4阶全排列可以转化为3阶全排列

公式中的$a_n$可以理解为第n位的数字排在还没使用的数字中第几位（从0开始），或者以$a_n$为前项的逆序对的个数。$a_n$组成的序列也被叫做Lehmer Code。

例子：

2314 -> 1100

14523 -> 02200

得到的逆序对序列可以当成一个特殊进制的数（第n位对应(n-1)!权重），转换成10进制就是要求的全排列的字典序（别忘了+1）

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

public static int getOrder(int n, String permutation) {
    int[] num = new int[n];
    for (int i = 0; i < n; i++) {
        num[i] = Integer.valueOf(permutation.charAt(i));
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        int inverse = 0;
        for (int j = i + 1; j < n; j++) {
            if (num[i] > num[j]) {
                inverse++;
            }
        }
        res = res * (n - i) + inverse;
        // res += res + inverse * factorial[n - 1 - i];
    }
    return res + 1; // start at 1
}

逆展开

逆展开就是上面字典序到全排列的过程，利用进制转换的代码完成字典序到逆序对序列（相当于10进制转换到以n!为进制的数），在根据逆序个数还原全排列（每次剩下还没使用的数字集合都在改变！）

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

public String getPermutation(int n, int k) {
    List<Integer> bits = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        bits.add(i);
    }
    int[] factorial = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
    StringBuilder sb = new StringBuilder();
    int residue = k - 1;
    for (int i = 0; i < n; i++) {
        int iid = residue / factorial[n - 1 - i];
        residue = residue % factorial[n - 1 - i];
        sb.append(bits.get(iid));
        bits.remove(iid);
    }
    return sb.toString();
}

升级版展开

简单版本康托展开使用一个循环来数逆序个数，整体代码的复杂度是O(n^2)。可以改进的地方就在如何更快地数逆序，一种办法可以用分治类比merge sort的代码来计算逆序，复杂度为O(logn)；另外也可以用线段树或者树状数组来统计逆序，复杂度同样为O(logn)。

Reference

迟到的【洛谷日报#187】浅谈康托展开

【给初心者的】康托展开

PostgreSQL 12 Installation

1. add postgresql-12 repository

   1 2 3

   $ wget --quiet -O - https://www.postgresql.org/media/keys/ACCC4CF8.asc | sudo apt-key add - $ echo "deb http://apt.postgresql.org/pub/repos/apt/ `lsb_release -cs`-pgdg main" |sudo tee /etc/apt/sources.list.d/pgdg.list $ sudo apt update

   the repository contains packages including:

   • postgresql-client
   • postgresql
   • libpq-dev
   • postgresql-server-dev
   • pgadmin packages

2. install postgresql server and client

   1	$ sudo apt -y install postgresql-12 postgresql-client-12

3. postgresql first-time login

   Switch to user postgres to login database postgres. Postgresql has by default 3 databases “postgres, template 0, template 1”.

   1	$ sudo -u postgres psql postgres

   create a test database and a test user

   (CREATE USER = CREATE ROLE + LOGIN permission)

   1 2 3 4 5 6

   postgres=# CREATE DATABASE mytestdb; CREATE DATABASE postgres=# CREATE USER mytestuser WITH ENCRYPTED PASSWORD 'MyStr0ngP@ss'; CREATE ROLE postgres=# GRANT ALL PRIVILEGES ON DATABASE mytestdb TO mytestuser; GRANT

   now list all databases

   1	postgres=# \l

   connect to newly-created database

   1	postgres=# \c mytestdb

4. “Peer authentication failed for user XXX”

   edit in file /etc/postgresql/12/main/pg_hba.conf, replace peer with md5

   • peer means it will trust the authenticity of UNIX user hence does not prompt for the password.
   • md5 means it will always ask for a password, and validate it after hashing with MD5

   from

   1 2 3 4 5 6

   # TYPE DATABASE USER ADDRESS METHOD # "local" is for Unix domain socket connections only local all all peer # IPv4 local connections: host all all 127.0.0.1/32 md5

   to

   1 2 3 4 5 6

   # TYPE DATABASE USER ADDRESS METHOD # "local" is for Unix domain socket connections only local all all md5 # IPv4 local connections: host all all 127.0.0.1/32 md5

   then restart postgresql

   sudo systemctl restart postgresql.service

Reference

How To Install PostgreSQL 12 on Ubuntu 20.04/18.04/16.04