一直以来，对算法既感到赞叹，又感到痛苦。赞叹的地方在于算法的美感，将问题抽象出来，以极为精炼的方式加以解决；有些算法还特别的巧妙，性能之高，让人叹为观止。痛苦的地方在于很多算法不好理解，记住则更难。所以，这里做一些算法记录，以供学习和查阅。部分问题可能会有多个算法实现，对此会列出它们。高效的也有，低效的也在，从对比中加深印象。
本系列文章在文集《算法》里，分为这几篇：由经验总结的算法、算法相关的基本概念、经典排序查找算法、经典趣题算法、经典数学问题算法和业界经典算法。它们来源于一些算法手册、书籍、源码和自己的归纳总结。
本篇文章是第一篇，主要介绍一些由经验总结的算法和结构。它们通常并不能抽象出来作为一般、常用的算法，但在实际开发中，底层经常出现它们的身影。
(1)任意范围的对数求解算法
在Java中，基本整型都有一定的范围，比如long类型，它的最大值是pow(2 , 64) -1 , 如果超出此范围，则数据会溢出，结果是不确定的。pow(x , y)表示x的y次方。
而且对于计算的中间值，也会有此限制。比如一个计算的结果是在long的范围内的，但某个中间变量超出了范围，那么计算结果也是未知的。典型的比如两个big long相乘再除以另外一个big long ，期待的结果是在long范围内的，尤其是以人的视角来看。但两个big long相乘超出了long的范围，该中间值就是错误的，再除以另外一个big long，所得结果也是错误的。
在实际场景中，有这么一个需求：对任意给定long型值x，想知道它对应的字符个数。这在将long型数值转换成对应的字符表示时就要用到。例如Java中的Long类有一个方法stringSize()，里面使用了一个边界值19(来自Java 8的源码，android 33源码中也一样)。对此没有任何的注释或说明。一开始看到这里的时候非常疑惑，为什么是19？下面就来解答这个问题。
在数学中，这其实是对数求解问题，即：以10为底，x的对数是多少？当然，在本需求中，需要一点变动，字符个数等于x以10为底的对数取整并加1。
一个关键的问题是如何确定上边界 N ，使得pow(10 , N) 大于Long.MAX_VALUE , 而pow(10 , N - 1)小于或等于Long.MAX_VALUE 。因为中间结果pow(10 , N) 超出了Long的范围，所以不能用long型来存储它。因此，BigInteger派上了用场。
BigInteger表示的整数，是没有范围限制的。用它来存储整数，可以获得可靠的结果。
Java版本算法：
//require n>0 , 返回x = 以10为底n的对数取整加1，即使得10的x次方大于n，10的(x-1)次方小于等于n
int getLg(long n){
BigInteger bigN = BigInteger.valueOf(n);
int pow = 0;
while(powerOf(pow).compareTo(bigN)<=0){
pow++;
}
return pow;
}
//require x >= 0 , 返回10的x次方的结果，用BigInteger表示
BigInteger powerOf(int x){
BigInteger ten = BigInteger.valueOf(10l);
BigInteger result = BigInteger.valueOf(1l);
for(int i =0;i<x;i++){
result = result.multiply(ten);
}
return result;
}
方法getLg(long n)参数n的类型可以很方便的改为BigInteger，以突破long的限制，扩展至任意范围的整数。这里只是为了直观和方便。
Kotlin版本：
//require n>0 , 返回x = 以10为底n的对数取整加1，即使得10的x次方大于n，10的(x-1)次方小于等于n
fun getLg(n: Long): Int {
val bigN = BigInteger.valueOf(n)
var pow = 0
while (powerOf(pow).compareTo(bigN) <= 0) {
pow++
}
return pow
}
//require x >= 0 , 返回10的x次方的结果，用BigInteger表示
fun powerOf(x: Int): BigInteger {
val ten = BigInteger.valueOf(10L)
var result = BigInteger.valueOf(1L)
for (i in 0 until x) {
result = result.multiply(ten)
}
return result
}
调用getLg(Long.MAX_VALUE)，获得的结果是19。也就是说，任意long的值，它对应的字符个数不会超过19 。
将这个算法扩展一下，不限制以10为底。扩展后的Java版本：
//require n>0 , 返回x = 以value为底n的对数取整加1，即使得value的x次方大于n，value的(x-1)次方小于等于n
int getLgOfV(long n,int value){
BigInteger bigN = BigInteger.valueOf(n);
int pow = 0;
while(powerOf(pow,value).compareTo(bigN)<=0){
pow++;
}
return pow;
}
//require x >=0 , n > 0 ,返回n的x次方的结果，用BigInteger表示
BigInteger powerOf(int x,int n){
BigInteger nBig = BigInteger.valueOf(n);
BigInteger result = BigInteger.valueOf(1l);
for(int i =0;i<x;i++){
result = result.multiply(nBig);
}
return result;
}
Kotlin版本：
//require n>0 , 返回x = 以value为底n的对数取整加1，即使得value的x次方大于n，value的(x-1)次方小于等于n
fun getLgOfV(n: Long, value: Int): Int {
val bigN = BigInteger.valueOf(n)
var pow = 0
while (powerOf(pow, value).compareTo(bigN) <= 0) {
pow++
}
return pow
}
//require x >=0 , n > 0 ,返回n的x次方的结果，用BigInteger表示
fun powerOf(x: Int, n: Int): BigInteger {
val nBig = BigInteger.valueOf(n.toLong())
var result = BigInteger.valueOf(1L)
for (i in 0 until x) {
result = result.multiply(nBig)
}
return result
}
(2)整数转字符对应的size算法
如果想将整数输出到屏幕，那么先要将它们转为对应的字符。在Java中，字符用char表示。将不同类型的整数(int 、long等)，转成对应的字符char数组，所需数组的大小，就是本次要描述的算法。本小节是基于Java源码(Long类和Integer类)做的一些总结。
用一个示例来更清晰地描述问题，比如 int i = 32 ; 将它转换成字符数组的结果是： char[] result = { ‘3’ , ‘2’ } ; 所需的size为2，创建char数组时，数组的大小size被赋值为2 。
先来说明一下数值和对应字符的不同。在Java中，char是采用Unicode编码的。数值3，对应的字符是‘3’，它的Unicode编码(也叫代码点，code point)是51，" char c = 51 "和" char c = ‘3’ " 这两种方式是完全等值的。从人的视角看，我们想打印数值3 ；从计算机视角看，它处理的却是51。
言归正传，该如果来求解这个size呢？先来看看int型的处理，Java版本：
/**
* int型的计算，require n >= 0 。 如果n<0，则 1+ stringSize(-n) 。加1是因为减号
*/
int stringSize(int n){
//int最大值是21亿多，这个数组的倒数第二个约9.9亿，再加个9，就是约99.9亿，超出了int最大值
final int[] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,99999999, 999999999, Integer.MAX_VALUE };
for(int i = 0;;i++){
if(n <= sizeTable[i]){
return i+1;
}
}
}
Kotlin版本：
fun stringSize(n: Int): Int {
//int最大值是21亿多，这个数组的倒数第二个约9.9亿，再加个9，就是约99.9亿，超出了int最大值
val sizeTable =
intArrayOf(9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999, Int.MAX_VALUE)
var i = 0
while (true) {
if (n <= sizeTable[i]) {
return i + 1
}
i++
}
}
short 、byte 的类型，是将它们转换成int后，再调用上面的算法。
针对long型，情况有点不同，它的Java版本算法如下：
/**
* long型的计算，require n >= 0
*/
int stringSize(long n){
long p = 10;
for (int i=1; i<19; i++) {
if (n < p)
return i;
p = 10*p;
}
return 19;
}
Kotlin版本如下：
/**
* long型的计算，require n >= 0
*/
fun stringSize(n: Long): Int {
var p: Long = 10
for (i in 1..18) {
if (n < p) return i
p = 10 * p
}
return 19
}
这里用到了值19，关于这个值的计算，可以看上面的第(5)条。
扩展一下，int型是否也可以用这种边界值的算法呢？答案是可以的，它的边界范围是10，通过自然观察和用上面第(5)条的算法求解都可以得到结果。Java版本如下：
/**
* int型的计算，采用long型的类似算法
*/
int stringSizeLg(int n){
long p = 10;
for (int i=1; i<10; i++) {
if (n < p)
return i;
p = 10*p;
}
return 10;
}
Kotlin版本如下：
/**
* int型的计算，采用long型的类似算法
*/
fun stringSizeLg(n: Int): Int {
var p: Long = 10
for (i in 1..9) {
if (n < p) return i
p = 10 * p
}
return 10
}
(3)乘10、乘100的高性能算法
如果想将一个值扩大10倍，再简单不过，乘以10就完事了。对计算机来说，乘以10却有不同的实现方式：乘法和移位(Shift) 。它们最底层的支持来自于电路，乘法需要乘法器电路，它比Shift方式更复杂，性能更低。
乘法方式：
int q , r ;
r = q * 10 ;
Shift方式：
int q , r ;
r = (q << 3) + (q << 1) ;
在个人的mac电脑上做了一个实验，将上述两种方式分别放到一个100万次的循环中，计算它们的耗时，结果如下(以纳秒为单位)：
multiply time : 13714938
shift time : 1668211
可以看出，性能不在一个量级。对于计算机来说，100万次的计算量算是少的，现在流行的CPU每秒能执行大约10亿次计算(数据来源于《C Primer Plus》第6版 中文版1.4节)。可以想象一下，当计算量非常大时，性能差距会有多大。
乘100的Shift方式：
int q , r ;
r = (q << 6) + (q << 5) + (q << 2))
(4)求商和余数的高性能算法
通常，求商、求余的做法是这样的：q = i / 10 ; r = i % 10;
但这种方式并未在Java源码中采用。如Integer类的getChars()方法。尤其是求余数时，没有采用求模运算符，而采用移位运算符。这其中的原因是如(7)条中所说的，Shift方式更高效。采用Shift方式的算法如下：
int i ;
if (i < 65536) {
int q = (i * 52429) >>> (16+3); //求商
int r = i - ((q << 3) + (q << 1)); //求余数，i - 10 * q
}
这里对整数进行了区分，上面是小整数(小于65536)的求解算法。大整数的算法如下：
int i ;
if (i >= 65536) {
int q = i / 100; //求商
int r = i - ((q << 6) + (q << 5) + (q << 2)); //求余数
}
(5)整数转字符算法
数据准备：
final static char[] digits = {
'0' , '1' , '2' , '3' , '4' , '5' ,
'6' , '7' , '8' , '9'
};
final static char [] DigitTens = {
'0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
'1', '1', '1', '1', '1', '1', '1', '1', '1', '1',
'2', '2', '2', '2', '2', '2', '2', '2', '2', '2',
'3', '3', '3', '3', '3', '3', '3', '3', '3', '3',
'4', '4', '4', '4', '4', '4', '4', '4', '4', '4',
'5', '5', '5', '5', '5', '5', '5', '5', '5', '5',
'6', '6', '6', '6', '6', '6', '6', '6', '6', '6',
'7', '7', '7', '7', '7', '7', '7', '7', '7', '7',
'8', '8', '8', '8', '8', '8', '8', '8', '8', '8',
'9', '9', '9', '9', '9', '9', '9', '9', '9', '9',
} ;
final static char [] DigitOnes = {
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
} ;
先来看int型：
1）如果大于65536 ，则除数设置为100，所得余数小于100，占2个字符，分别存储个位和十位到适当位置。
2）如果小于等于65536 ，则除数设置为10 ，余数占1个字符，然后将它存储到适当位置。
如果是1），则使用数据DigitTens 和 DigitOnes ，前者方便获取十位上的字符，后者方便获取个位字符，例如，余数37 ，将它作为下标，从DigitTens中获取的值刚好是3，而从DigitOnes中获取的值刚好是7。算法如下：
/**
* @param i: 是需要转字符的int值，如34
* @param index：对应的字符个数，如34对应的字符个数为2，index 的值为2 ；如果是负数，则转为相反数后加1
* @param buf: char[]数组，存储对应的字符
*/
static void getChars(int i, int index, char[] buf) {
int q, r;
int charPos = index;
char sign = 0;
if (i < 0) {
sign = '-';
i = -i;
}
// Generate two digits per iteration
while (i >= 65536) {
q = i / 100;
// really: r = i - (q * 100);
r = i - ((q << 6) + (q << 5) + (q << 2));
i = q;
buf [--charPos] = DigitOnes[r];
buf [--charPos] = DigitTens[r];
}
// Fall thru to fast mode for smaller numbers
// assert(i <= 65536, i);
for (;;) {
q = (i * 52429) >>> (16+3);
r = i - ((q << 3) + (q << 1)); // r = i-(q*10) ...
buf [--charPos] = digits [r];
i = q;
if (i == 0) break;
}
if (sign != 0) {
buf [--charPos] = sign;
}
}
这里用到了上面第(8)条的算法。
对于long型的数据，基本思想是一样的。只是在while (i >= 65536)前再加上：
while (i > Integer.MAX_VALUE) {
q = i / 100;
// really: r = i - (q * 100);
r = (int)(i - ((q << 6) + (q << 5) + (q << 2)));
i = q;
buf[--charPos] = Integer.DigitOnes[r];
buf[--charPos] = Integer.DigitTens[r];
}
（6）字符数组倒序算法
主要思想：从中间开始，向高位、低位依次取值，并交换它们。Java版如下：
public char[] reverse(char[] value , int count) {
int n = count - 1;
for (int j = (n-1) >> 1; j >= 0; j--) {
int k = n - j;
char cj = value[j];
char ck = value[k];
value[j] = ck;
value[k] = cj;
}
return value;
}
Kotlin版本如下：
fun reverse(value: CharArray, count: Int): CharArray {
val n = count - 1
for (j in n - 1 shr 1 downTo 0) {
val k = n - j
val cj = value[j]
val ck = value[k]
value[j] = ck
value[k] = cj
}
return value
}
(7)整数转二进制字符串
介绍三种方式，第一种递归算法，Java版本：
/**
* 递归：将int型转为二进制的String
*/
public static String intToBinary(int n) {
if (n == 0) {
return "0";
} else if (n == 1) {
return "1";
} else {
int remain = n % 2;
String other = intToBinary(n / 2);
return other + remain;
}
}
Kotlin版本：
/**
* 递归：将int型转为二进制的String
*/
fun intToBinary(n: Int): String {
return if (n == 0) {
"0"
} else if (n == 1) {
"1"
} else {
val remain = n % 2
val other = intToBinary(n / 2)
other + remain
}
}
第二种，shift循环实现，Java版本：
/**
* shift 循环实现，
*/
public static String intToBinaryShift(int n){
char[] intChars = new char[32];//Java中int型为32位
for(int i=31;i>=0;i--,n>>=1){
intChars[i] = (0x1 & n) == 1 ? '1':'0';
}
return new String(intChars);
}
这种实现开头会包含多余的零，需要注意。
Kotlin版本：
/**
* shift 循环实现，
*/
fun intToBinaryShift(n: Int): String {
var n = n
val intChars = CharArray(32) //Java中int型为32位
var i = 31
while (i >= 0) {
intChars[i] = if (0x1 and n == 1) '1' else '0'
i--
n = n shr 1
}
return String(intChars)
}
第三种，借助Java API实现，Java版如下：
/**
* api 实现
*/
public static String intToBinaryW(int n) {
StringBuilder builder = new StringBuilder();
while (n > 0) {
int remain = n % 2;
builder.append(remain);
n = n >> 1;
}
return builder.reverse().toString();
}
Kotlin版：
/**
* api 实现
*/
fun intToBinaryW(n: Int): String {
var n = n
val builder = StringBuilder()
while (n > 0) {
val remain = n % 2
builder.append(remain)
n = n shr 1
}
return builder.reverse().toString()
}
(8)字符转int
将char字符转为对应的int值，例如字符'3'转为数值3。Java版如下：
/**
* char转int值
*/
public static int charToInt(char c) {
int codePoint = (int) c;//c的代码点，unicode码
if (codePoint >= '0' && codePoint <= '9') {
return codePoint - '0';
}
return -1;
}
Kotlin版：
/**
* char转int值
*/
fun charToInt(c: Char): Int {
val codePoint = c.code //c的代码点，unicode码
return if (codePoint >= '0'.code && codePoint <= '9'.code) {
codePoint - '0'.code
} else -1
}
(9)文章评论结构
由看文章、帖子及关联的评论，临时起意，设计一种结构来表示它们。
特点：一篇文章有作者、标题、内容、发布时间等属性，一条评论有评论者、评论内容、评论时间等属性；一篇文章可以有多个评论，每条评论还可以有多个子评论；每条子评论都有父评论；评论的数量是不限制的，随时可能新增。
设计：采用树结构，将文章作为根节点，一级评论作为它的直接后继，二级评论作为一级评论的孩子节点，以此类推；文章是一级评论的父节点，一级评论是二级评论的父节点，以此类推；文章没有父节点。
Java版本：
import java.util.ArrayList;
import java.util.List;
public class ArticleCommentStruct {
String id; //编号
String authorName; //作者名称
String iconUrl;//图标地址
long publishTime; //发布时间
int type; // 0表示文章，1表示评论
List<ArticleCommentStruct> childList; //子评论
ArticleCommentStruct father; //父评论，如果是文章，则为空；一级评论的father是文章
String content; //文章内容
String title; //文章标题，只有type=0时才有值
int hotNum;//热度值，可以用来排序
public ArticleCommentStruct(){
this(0);
}
public ArticleCommentStruct(int type){
assert (type == 0 || type == 1);
this.type = type;
}
/**
* 如果是一篇文章，返回true
* @return
*/
public boolean isArticle(){
return this.type == 0;
}
/**
* 如果是一个评论，返回true
* @return
*/
public boolean isComment(){
return this.type == 1;
}
/**
* 如果是一级评论，返回true
* @return
*/
public boolean isFirstClassComment(){
if (isComment() && father != null && father.isArticle()){
return true;
}
return false;
}
/**
* 添加一个子评论
* @param child
*/
public void addChild(ArticleCommentStruct child){
if (childList == null){
childList = new ArrayList<>();
}
childList.add(child);
}
/**
* 创建一个类型为文章的ArticleCommentStruct对象
* @param authorName 作者名称
* @param content 文章内容
* @return
*/
public static ArticleCommentStruct makeArticle(String authorName,String content){
ArticleCommentStruct tree = new ArticleCommentStruct();
tree.authorName = authorName;
tree.content = content;
return tree;
}
/**
* 创建一个类型为评论的ArticleCommentStruct对象
* @param authorName 作者名称
* @param content 评论内容
* @return
*/
public static ArticleCommentStruct makeComment(String authorName,String content){
ArticleCommentStruct comment = new ArticleCommentStruct(1);
comment.authorName = authorName;
comment.content = content;
return comment;
}
其实还可以做的更多，比如根据hotNum排序。一些将高点赞、高热度的评论置顶的做法就要用到它。这里就不再多说了。
Kotlin版本：
import kotlin.jvm.JvmOverloads
import java.util.ArrayList
class ArticleCommentStruct @JvmOverloads constructor(type: Int = 0) {
var id //编号
: String? = null
var authorName //作者名称
: String? = null
var iconUrl //图标地址
: String? = null
var publishTime //发布时间
: Long = 0
var type // 0表示文章，1表示评论
: Int
var childList //子评论
: MutableList<ArticleCommentStruct>? = null
var father //父评论，如果是文章，则为空；一级评论的father是文章
: ArticleCommentStruct? = null
var content //文章内容
: String? = null
var title //文章标题，只有type=0时才有值
: String? = null
var hotNum //热度值，可以用来排序
= 0
init {
assert(type == 0 || type == 1)
this.type = type
}
/**
* 如果是一篇文章，返回true
* @return
*/
val isArticle: Boolean
get() = type == 0
/**
* 如果是一个评论，返回true
* @return
*/
val isComment: Boolean
get() = type == 1
/**
* 如果是一级评论，返回true
* @return
*/
val isFirstClassComment: Boolean
get() = if (isComment && father != null && father!!.isArticle) {
true
} else false
/**
* 添加一个子评论
* @param child
*/
fun addChild(child: ArticleCommentStruct) {
if (childList == null) {
childList = ArrayList()
}
childList!!.add(child)
}
companion object {
/**
* 创建一个类型为文章的ArticleCommentStruct对象
* @param authorName 作者名称
* @param content 文章内容
* @return
*/
fun makeArticle(authorName: String?, content: String?): ArticleCommentStruct {
val tree = ArticleCommentStruct()
tree.authorName = authorName
tree.content = content
return tree
}
/**
* 创建一个类型为评论的ArticleCommentStruct对象
* @param authorName 作者名称
* @param content 评论内容
* @return
*/
fun makeComment(authorName: String?, content: String?): ArticleCommentStruct {
val comment = ArticleCommentStruct(1)
comment.authorName = authorName
comment.content = content
return comment
}
}
}
Over ！
