????一直以來，對算法既感到贊嘆，又感到痛苦。贊嘆的地方在于算法的美感，將問題抽象出來，以極為精煉的方式加以解決；有些算法還特別的巧妙，性能之高，讓人嘆為觀止。痛苦的地方在于很多算法不好理解，記住則更難。所以，這里做一些算法記錄，以供學(xué)習(xí)和查閱。部分問題可能會有多個算法實現(xiàn)，對此會列出它們。高效的也有，低效的也在，從對比中加深印象。
????本系列文章在文集《算法》里，分為這幾篇：由經(jīng)驗總結(jié)的算法、算法相關(guān)的基本概念、經(jīng)典排序查找算法、經(jīng)典趣題算法、經(jīng)典數(shù)學(xué)問題算法和業(yè)界經(jīng)典算法。它們來源于一些算法手冊、書籍、源碼和自己的歸納總結(jié)。
????本篇文章是第一篇，主要介紹一些由經(jīng)驗總結(jié)的算法和結(jié)構(gòu)。它們通常并不能抽象出來作為一般、常用的算法，但在實際開發(fā)中，底層經(jīng)常出現(xiàn)它們的身影。
(1)任意范圍的對數(shù)求解算法
????在Java中，基本整型都有一定的范圍，比如long類型，它的最大值是pow(2 , 64) -1 , 如果超出此范圍，則數(shù)據(jù)會溢出，結(jié)果是不確定的。pow(x , y)表示x的y次方。
????而且對于計算的中間值，也會有此限制。比如一個計算的結(jié)果是在long的范圍內(nèi)的，但某個中間變量超出了范圍，那么計算結(jié)果也是未知的。典型的比如兩個big long相乘再除以另外一個big long ，期待的結(jié)果是在long范圍內(nèi)的，尤其是以人的視角來看。但兩個big long相乘超出了long的范圍，該中間值就是錯誤的，再除以另外一個big long，所得結(jié)果也是錯誤的。
????在實際場景中，有這么一個需求：對任意給定long型值x，想知道它對應(yīng)的字符個數(shù)。這在將long型數(shù)值轉(zhuǎn)換成對應(yīng)的字符表示時就要用到。例如Java中的Long類有一個方法stringSize()，里面使用了一個邊界值19(來自Java 8的源碼，android 33源碼中也一樣)。對此沒有任何的注釋或說明。一開始看到這里的時候非常疑惑，為什么是19？下面就來解答這個問題。
????在數(shù)學(xué)中，這其實是對數(shù)求解問題，即：以10為底，x的對數(shù)是多少？當(dāng)然，在本需求中，需要一點變動，字符個數(shù)等于x以10為底的對數(shù)取整并加1。
????一個關(guān)鍵的問題是如何確定上邊界 N ，使得pow(10 , N) 大于Long.MAX_VALUE , 而pow(10 , N - 1)小于或等于Long.MAX_VALUE 。因為中間結(jié)果pow(10 , N) 超出了Long的范圍，所以不能用long型來存儲它。因此，BigInteger派上了用場。
????BigInteger表示的整數(shù)，是沒有范圍限制的。用它來存儲整數(shù)，可以獲得可靠的結(jié)果。
????Java版本算法：
//require n>0 , 返回x = 以10為底n的對數(shù)取整加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次方的結(jié)果，用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)參數(shù)n的類型可以很方便的改為BigInteger，以突破long的限制，擴(kuò)展至任意范圍的整數(shù)。這里只是為了直觀和方便。
????Kotlin版本：
//require n>0 , 返回x = 以10為底n的對數(shù)取整加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次方的結(jié)果，用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
}
????調(diào)用getLg(Long.MAX_VALUE)，獲得的結(jié)果是19。也就是說，任意long的值，它對應(yīng)的字符個數(shù)不會超過19 。
????將這個算法擴(kuò)展一下，不限制以10為底。擴(kuò)展后的Java版本：
//require n>0 , 返回x = 以value為底n的對數(shù)取整加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次方的結(jié)果，用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的對數(shù)取整加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次方的結(jié)果，用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)整數(shù)轉(zhuǎn)字符對應(yīng)的size算法
????如果想將整數(shù)輸出到屏幕，那么先要將它們轉(zhuǎn)為對應(yīng)的字符。在Java中，字符用char表示。將不同類型的整數(shù)(int 、long等)，轉(zhuǎn)成對應(yīng)的字符char數(shù)組，所需數(shù)組的大小，就是本次要描述的算法。本小節(jié)是基于Java源碼(Long類和Integer類)做的一些總結(jié)。
????用一個示例來更清晰地描述問題，比如 int i = 32 ; 將它轉(zhuǎn)換成字符數(shù)組的結(jié)果是： char[] result = { ‘3’ , ‘2’ } ; 所需的size為2，創(chuàng)建char數(shù)組時，數(shù)組的大小size被賦值為2 。
????先來說明一下數(shù)值和對應(yīng)字符的不同。在Java中，char是采用Unicode編碼的。數(shù)值3，對應(yīng)的字符是‘3’，它的Unicode編碼(也叫代碼點，code point)是51，" char c = 51 "和" char c = ‘3’ " 這兩種方式是完全等值的。從人的視角看，我們想打印數(shù)值3 ；從計算機(jī)視角看，它處理的卻是51。
????言歸正傳，該如果來求解這個size呢？先來看看int型的處理，Java版本：
/**
* int型的計算，require n >= 0 。 如果n<0，則 1+ stringSize(-n) 。加1是因為減號
*/
int stringSize(int n){
//int最大值是21億多，這個數(shù)組的倒數(shù)第二個約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億多，這個數(shù)組的倒數(shù)第二個約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 的類型，是將它們轉(zhuǎn)換成int后，再調(diào)用上面的算法。
????針對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，關(guān)于這個值的計算，可以看上面的第(5)條。
????擴(kuò)展一下，int型是否也可以用這種邊界值的算法呢？答案是可以的，它的邊界范圍是10，通過自然觀察和用上面第(5)條的算法求解都可以得到結(jié)果。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的高性能算法
????如果想將一個值擴(kuò)大10倍，再簡單不過，乘以10就完事了。對計算機(jī)來說，乘以10卻有不同的實現(xiàn)方式：乘法和移位(Shift) 。它們最底層的支持來自于電路，乘法需要乘法器電路，它比Shift方式更復(fù)雜，性能更低。
????乘法方式：
int q , r ;
r = q * 10 ;
????Shift方式：
int q , r ;
r = (q << 3) + (q << 1) ;
????在個人的mac電腦上做了一個實驗，將上述兩種方式分別放到一個100萬次的循環(huán)中，計算它們的耗時，結(jié)果如下(以納秒為單位)：
multiply time : 13714938
shift time : 1668211
????可以看出，性能不在一個量級。對于計算機(jī)來說，100萬次的計算量算是少的，現(xiàn)在流行的CPU每秒能執(zhí)行大約10億次計算(數(shù)據(jù)來源于《C Primer Plus》第6版 中文版1.4節(jié))。可以想象一下，當(dāng)計算量非常大時，性能差距會有多大。
????乘100的Shift方式：
int q , r ;
r = (q << 6) + (q << 5) + (q << 2))
(4)求商和余數(shù)的高性能算法
????通常，求商、求余的做法是這樣的：q = i / 10 ; r = i % 10;
????但這種方式并未在Java源碼中采用。如Integer類的getChars()方法。尤其是求余數(shù)時，沒有采用求模運算符，而采用移位運算符。這其中的原因是如(7)條中所說的，Shift方式更高效。采用Shift方式的算法如下：
int i ;
if (i < 65536) {
int q = (i * 52429) >>> (16+3); //求商
int r = i - ((q << 3) + (q << 1)); //求余數(shù)，i - 10 * q
}
????這里對整數(shù)進(jìn)行了區(qū)分，上面是小整數(shù)(小于65536)的求解算法。大整數(shù)的算法如下：
int i ;
if (i >= 65536) {
int q = i / 100; //求商
int r = i - ((q << 6) + (q << 5) + (q << 2)); //求余數(shù)
}
(5)整數(shù)轉(zhuǎn)字符算法
????數(shù)據(jù)準(zhǔn)備：
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 ，則除數(shù)設(shè)置為100，所得余數(shù)小于100，占2個字符，分別存儲個位和十位到適當(dāng)位置。
????????2）如果小于等于65536 ，則除數(shù)設(shè)置為10 ，余數(shù)占1個字符，然后將它存儲到適當(dāng)位置。
????如果是1），則使用數(shù)據(jù)DigitTens 和 DigitOnes ，前者方便獲取十位上的字符，后者方便獲取個位字符，例如，余數(shù)37 ，將它作為下標(biāo)，從DigitTens中獲取的值剛好是3，而從DigitOnes中獲取的值剛好是7。算法如下：
/**
* @param i: 是需要轉(zhuǎn)字符的int值，如34
* @param index：對應(yīng)的字符個數(shù)，如34對應(yīng)的字符個數(shù)為2，index 的值為2 ；如果是負(fù)數(shù)，則轉(zhuǎn)為相反數(shù)后加1
* @param buf: char[]數(shù)組，存儲對應(yīng)的字符
*/
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型的數(shù)據(jù)，基本思想是一樣的。只是在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）字符數(shù)組倒序算法
????主要思想：從中間開始，向高位、低位依次取值，并交換它們。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)整數(shù)轉(zhuǎn)二進(jìn)制字符串
????介紹三種方式，第一種遞歸算法，Java版本：
/**
* 遞歸：將int型轉(zhuǎn)為二進(jìn)制的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型轉(zhuǎn)為二進(jìn)制的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循環(huán)實現(xiàn)，Java版本：
/**
* shift 循環(huán)實現(xiàn)，
*/
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);
}
????這種實現(xiàn)開頭會包含多余的零，需要注意。
????Kotlin版本：
/**
* shift 循環(huán)實現(xiàn)，
*/
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實現(xiàn)，Java版如下：
/**
* api 實現(xiàn)
*/
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 實現(xiàn)
*/
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)字符轉(zhuǎn)int
???? 將char字符轉(zhuǎn)為對應(yīng)的int值，例如字符'3'轉(zhuǎn)為數(shù)值3。Java版如下：
/**
* char轉(zhuǎn)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轉(zhuǎn)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)文章評論結(jié)構(gòu)
????由看文章、帖子及關(guān)聯(lián)的評論，臨時起意，設(shè)計一種結(jié)構(gòu)來表示它們。
????特點：一篇文章有作者、標(biāo)題、內(nèi)容、發(fā)布時間等屬性，一條評論有評論者、評論內(nèi)容、評論時間等屬性；一篇文章可以有多個評論，每條評論還可以有多個子評論；每條子評論都有父評論；評論的數(shù)量是不限制的，隨時可能新增。
????設(shè)計：采用樹結(jié)構(gòu)，將文章作為根節(jié)點，一級評論作為它的直接后繼，二級評論作為一級評論的孩子節(jié)點，以此類推；文章是一級評論的父節(jié)點，一級評論是二級評論的父節(jié)點，以此類推；文章沒有父節(jié)點。
????Java版本：
import java.util.ArrayList;
import java.util.List;
public class ArticleCommentStruct {
String id; //編號
String authorName; //作者名稱
String iconUrl;//圖標(biāo)地址
long publishTime; //發(fā)布時間
int type; // 0表示文章，1表示評論
List<ArticleCommentStruct> childList; //子評論
ArticleCommentStruct father; //父評論，如果是文章，則為空；一級評論的father是文章
String content; //文章內(nèi)容
String title; //文章標(biāo)題，只有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);
}
/**
* 創(chuàng)建一個類型為文章的ArticleCommentStruct對象
* @param authorName 作者名稱
* @param content 文章內(nèi)容
* @return
*/
public static ArticleCommentStruct makeArticle(String authorName,String content){
ArticleCommentStruct tree = new ArticleCommentStruct();
tree.authorName = authorName;
tree.content = content;
return tree;
}
/**
* 創(chuàng)建一個類型為評論的ArticleCommentStruct對象
* @param authorName 作者名稱
* @param content 評論內(nèi)容
* @return
*/
public static ArticleCommentStruct makeComment(String authorName,String content){
ArticleCommentStruct comment = new ArticleCommentStruct(1);
comment.authorName = authorName;
comment.content = content;
return comment;
}
????其實還可以做的更多，比如根據(jù)hotNum排序。一些將高點贊、高熱度的評論置頂?shù)淖龇ň鸵玫剿?。這里就不再多說了。
????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 //圖標(biāo)地址
: String? = null
var publishTime //發(fā)布時間
: Long = 0
var type // 0表示文章，1表示評論
: Int
var childList //子評論
: MutableList<ArticleCommentStruct>? = null
var father //父評論，如果是文章，則為空；一級評論的father是文章
: ArticleCommentStruct? = null
var content //文章內(nèi)容
: String? = null
var title //文章標(biāo)題，只有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 {
/**
* 創(chuàng)建一個類型為文章的ArticleCommentStruct對象
* @param authorName 作者名稱
* @param content 文章內(nèi)容
* @return
*/
fun makeArticle(authorName: String?, content: String?): ArticleCommentStruct {
val tree = ArticleCommentStruct()
tree.authorName = authorName
tree.content = content
return tree
}
/**
* 創(chuàng)建一個類型為評論的ArticleCommentStruct對象
* @param authorName 作者名稱
* @param content 評論內(nèi)容
* @return
*/
fun makeComment(authorName: String?, content: String?): ArticleCommentStruct {
val comment = ArticleCommentStruct(1)
comment.authorName = authorName
comment.content = content
return comment
}
}
}
???? Over ！
