面試算法代碼知識梳理系列
面試算法知識梳理(1) - 排序算法
面試算法知識梳理(2) - 字符串算法第一部分
面試算法知識梳理(3) - 字符串算法第二部分
面試算法知識梳理(4) - 數(shù)組第一部分
面試算法知識梳理(5) - 數(shù)組第二部分
面試算法知識梳理(6) - 數(shù)組第三部分
面試算法知識梳理(7) - 數(shù)組第四部分
面試算法知識梳理(8) - 二分查找算法及其變型
面試算法知識梳理(9) - 鏈表算法第一部分
面試算法知識梳理(10) - 二叉查找樹
面試算法知識梳理(11) - 二叉樹算法第一部分
面試算法知識梳理(12) - 二叉樹算法第二部分
面試算法知識梳理(13) - 二叉樹算法第三部分
一栖榨、目錄
- 斐波那契數(shù)列(循環(huán)算法昆汹、矩陣算法)
- 跳臺階問題
- 數(shù)值的整數(shù)次方
- 打印
1
到最大的n
位數(shù) - 計(jì)算從
1
到n
中1
出現(xiàn)的個(gè)數(shù) - 求兩個(gè)數(shù)的二進(jìn)制表示中有多少個(gè)是不同的
- 給定一個(gè)整數(shù)
N
,求N!
的末尾有多少個(gè)0
- 給定一個(gè)整數(shù)
N
婴栽,求N!
的二進(jìn)制表示中最低位1
的位置 - 最大公約數(shù)
- 精確地表達(dá)有限/無限循環(huán)小數(shù)
二满粗、代碼實(shí)現(xiàn)
2.1 斐波那契數(shù)列(循環(huán)算法、矩陣算法)
問題描述
斐波那契數(shù)列 滿足下面的通項(xiàng)公式愚争,要求給出N
映皆,輸出第N
項(xiàng)的F(N)
F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)
解決思路
這里介紹兩種解決辦法轰枝,循環(huán)算法 和 矩陣算法捅彻。循環(huán)算法比較容易理解,就是從F(0)
開始鞍陨,根據(jù)通項(xiàng)公式步淹,得到下一個(gè)斐波那契數(shù)列中的數(shù)字即可。
循環(huán)算法代碼實(shí)現(xiàn)
class Untitled {
static double fibonacci(int n) {
if (n < 2) {
return n;
}
//f(n-2)
double fnMinus2 = 0;
//f(n-1)
double fnMinus1 = 1;
double result = 0;
for (int i=2; i<=n; i++) {
//根據(jù)通項(xiàng)公式計(jì)算湾戳。
result = fnMinus2 + fnMinus1;
fnMinus2 = fnMinus1;
fnMinus1 = result;
}
return result;
}
public static void main(String[] args) {
double loopResult = fibonacci(10);
System.out.println("loopResult=" + loopResult);
}
}
循環(huán)算法運(yùn)行結(jié)果
>> loopResult=55.0
矩陣算法解決思路
對于上面的通項(xiàng)公式贤旷,可以用下面的矩陣乘法的形式來表示
那么,我們的問題就變成了求該特殊矩陣的
N-1
次方的值砾脑。
矩陣算法代碼實(shí)現(xiàn)
class Untitled {
static class Matrix {
double a;
double b;
double c;
double d;
public Matrix(double a, double b, double c, double d) {
this.a = a;
this.b = b;
this.c = c;
this.d = d;
}
}
//矩陣乘法函數(shù)幼驶。
static Matrix multiMatrix(Matrix a, Matrix b) {
Matrix result = new Matrix(0, 0, 0, 0);
result.a = a.a*b.a + a.b*b.c;
result.b = a.a*b.b + a.b*b.d;
result.c = a.c*b.a + a.d*b.c;
result.d = a.c*b.b + a.d*b.d;
return result;
}
//核心函數(shù)。
static double fibonacciMatrix(int n) {
if (n < 2) {
return n;
}
Matrix r = new Matrix(1, 0, 0, 1);
Matrix tmp = new Matrix(1, 1, 1, 0);
n--;
while (n > 0) {
if ((n&1) > 0) {
r = multiMatrix(r, tmp);
}
tmp = multiMatrix(tmp, tmp);
n >>= 1;
}
return r.a;
}
public static void main(String[] args) {
double matrixResult = fibonacciMatrix(10);
System.out.println("matrixResult=" + matrixResult);
}
}
矩陣算法運(yùn)行結(jié)果
>> matrixResult=55.0
2.2 跳臺階問題
問題描述
一個(gè)臺階總共有n
級韧衣,如果一次可以跳1
級盅藻,也可以跳2
級,求總共有多少總跳法畅铭。
解決思路
由于有兩種跳臺階方式氏淑,因此跳n
級臺階可以轉(zhuǎn)換為下面兩個(gè)問題之和:
- 第一次跳
1
級臺階,之后的解法數(shù)為f(n-1)
- 第一次跳
2
級臺階硕噩,之后的解法數(shù)為f(n-2)
這就和之前的斐波那契數(shù)列的通項(xiàng)公式相同假残。
實(shí)現(xiàn)代碼
class Untitled {
static class Matrix {
double a;
double b;
double c;
double d;
public Matrix(double a, double b, double c, double d) {
this.a = a;
this.b = b;
this.c = c;
this.d = d;
}
}
//矩陣乘法函數(shù)。
static Matrix multiMatrix(Matrix a, Matrix b) {
Matrix result = new Matrix(0, 0, 0, 0);
result.a = a.a*b.a + a.b*b.c;
result.b = a.a*b.b + a.b*b.d;
result.c = a.c*b.a + a.d*b.c;
result.d = a.c*b.b + a.d*b.d;
return result;
}
//核心函數(shù)炉擅。
static double fibonacciMatrix(int n) {
if (n < 2) {
return n;
}
Matrix r = new Matrix(1, 0, 0, 1);
Matrix tmp = new Matrix(1, 1, 1, 0);
n--;
while (n > 0) {
if ((n&1) > 0) {
r = multiMatrix(r, tmp);
}
tmp = multiMatrix(tmp, tmp);
n >>= 1;
}
return r.a;
}
static double stepCounter(int step) {
if (step <= 2) {
return step;
}
return fibonacciMatrix(step);
}
public static void main(String[] args) {
double count = stepCounter(50);
System.out.println("counter=" + count);
}
}
2.3 數(shù)值整數(shù)次方
實(shí)現(xiàn)代碼
class Untitled {
static double powerOfNum(int num, int power) {
int tmp = num;
int r = 1;
while (power > 0) {
//如果在該位上為1辉懒,那么就乘上對應(yīng)的n次方。
if ((power&1) > 0) {
r = r*tmp;
}
tmp = tmp*tmp;
power >>= 1;
}
return r;
}
public static void main(String[] args) {
System.out.println("powerOfNum=" + powerOfNum(2, 10));
}
}
運(yùn)行結(jié)果
>> powerOfNum=1024.0
2.4 打印 1 到最大的 n 位數(shù)
class Untitled {
static void printNumberCore(int p[], int depth, int len) {
//到達(dá)末尾谍失,打印當(dāng)前數(shù)組中的元素眶俩。
if (depth == len+1) {
StringBuilder builder = new StringBuilder();
for (int i=1; i<=len; i++) {
builder.append(String.valueOf(p[i]));
}
System.out.println(builder.toString());
return;
}
//如果是首位,那么從1開始快鱼,否則從0開始颠印。
int pStart = 0;
if (depth == 1) {
pStart = 1;
}
for (int i=pStart; i<=9; i++) {
//替換該位纲岭,并進(jìn)行遞歸。
p[depth] = i;
printNumberCore(p, depth+1, len);
}
}
static void printNumber(int n) {
//首先建立數(shù)組线罕。
int p[] = new int[n+1];
//len表示有幾位數(shù)止潮。
for (int len=1; len<=n; len++) {
//對應(yīng)于len位數(shù)的全排列。
printNumberCore(p, 1, len);
}
}
public static void main(String[] args) {
printNumber(3);
}
}
2.5 計(jì)算從 1 到 n 中 1 出現(xiàn)的個(gè)數(shù)
解決思路
這個(gè)問題钞楼,需要先總結(jié)一下規(guī)律沽翔,我們根據(jù)數(shù)字N
的 位數(shù) 來進(jìn)行分析:
一位數(shù)
那么N>=1
時(shí)才會(huì)出現(xiàn)1
,并且出現(xiàn)1
的次數(shù)為1
次
兩位數(shù)
在這種情況下窿凤,出現(xiàn)1
的次數(shù)等于個(gè)位上出現(xiàn)1
的次數(shù)加上十位上出現(xiàn)1
的個(gè)數(shù)。
-
個(gè)位上出現(xiàn)
1
的次數(shù)不僅和個(gè)位的數(shù)字有關(guān)跨蟹,還和十位的數(shù)字有關(guān):- 如果個(gè)位為
0
雳殊,那么個(gè)位上出現(xiàn)1
的次數(shù)等于十位的數(shù)字。 - 如果個(gè)位大于
0
窗轩,那么個(gè)位上出現(xiàn)1
的次數(shù)等于十位的數(shù)字加1
夯秃。
- 如果個(gè)位為
-
十位上出現(xiàn)
1
的次數(shù)不僅和十位的數(shù)字有關(guān),還和個(gè)位的數(shù)字有關(guān):- 如果十位為
1
痢艺,那么十位上出現(xiàn)1
的次數(shù)等于個(gè)位的數(shù)字加1
仓洼。 - 如果十位大于
1
,那么十位上出現(xiàn)1
的次數(shù)等于10
堤舒。
- 如果十位為
N 位數(shù)
例如色建,如果要計(jì)算百位上1
出現(xiàn)的次數(shù),它要受到三方面的影響:百位上的數(shù)字舌缤,百位以下的數(shù)字箕戳,百位以上的數(shù)字。
如果百位上數(shù)字為
0
国撵,百位上可能出現(xiàn)1
的次數(shù)僅由更高位決定陵吸,等于更高位數(shù)字乘以當(dāng)前位數(shù)。-
如果百位上數(shù)字為
1
介牙,百位上可能出現(xiàn)1
的次數(shù)不僅受更高位影響還受低位影響:- 受高位影響的部分等于更高位數(shù)字乘以當(dāng)前位數(shù)
- 受低位影響等于低位數(shù)字加上
1
壮虫。
如果百位上數(shù)字大于
1
,則百位上出現(xiàn)1
的情況僅由更高位決定环础,等于更高位數(shù)字加上1
乘以當(dāng)前位數(shù)囚似。
代碼實(shí)現(xiàn)
class Untitled {
static int countOneNum(int data) {
int iFac = 1;
int countNum = 0;
int lowNum = 0;
int curNum = data % 10;
int highNum = data / 10;
//從個(gè)位數(shù)開始遍歷,每次while循環(huán)向前移動(dòng)一位喳整,計(jì)算每一位出現(xiàn)1的次數(shù)谆构,總和就是問題的解。
while (curNum > 0 || highNum > 0) {
if (curNum == 0) {
countNum += highNum * iFac;
} else if (curNum == 1) {
countNum += highNum * iFac + (lowNum + 1);
} else {
countNum += (highNum+1)*iFac;
}
lowNum = lowNum + curNum*iFac;
curNum = highNum % 10;
highNum = highNum / 10;
iFac *= 10;
}
return countNum;
}
public static void main(String[] args) {
System.out.println("n=" + 123 + ",result=" + countOneNum(123));
}
}
運(yùn)行結(jié)果
>> n=123,result=57
2.6 求兩個(gè)數(shù)的二進(jìn)制表示中有多少個(gè)是不同的
解決思路
對于一個(gè)二進(jìn)制數(shù)框都,例如1010
搬素,將其減1
后得到的結(jié)果是1001
呵晨,也就是將最后一個(gè)1
(倒數(shù)第二位)及其之后的0
變成1
,1
變成0
熬尺,再將該結(jié)果與原二進(jìn)制數(shù)相與摸屠,也就是1010 & 1001 = 1000
,那么就可以去掉最后一個(gè)1
粱哼。
因此季二,如果需要計(jì)算兩個(gè)數(shù)的二進(jìn)制表示中有多少位是不同的,可以 先將這兩個(gè)數(shù)異或揭措,那么不相同的位數(shù)就會(huì)變成1
胯舷,之后利用上面的技巧,通過每次去掉最后一個(gè)1
绊含,來 統(tǒng)計(jì)該結(jié)果中1
的個(gè)數(shù)桑嘶,就可以知道兩個(gè)數(shù)的二進(jìn)制表示中有多少是不同的了。
代碼實(shí)現(xiàn)
class Untitled {
static int getDiffBit(int a, int b) {
int diff = a^b;
int count = 0;
while (diff > 0) {
count++;
diff = diff & (diff-1);
}
return count;
}
public static void main(String[] args) {
System.out.println("result=" + getDiffBit(1999, 2299));
}
}
運(yùn)行結(jié)果
>> result=7
2.7 給定一個(gè)整數(shù) N躬充,求 N! 的末尾有多少個(gè) 0
問題描述
N!
的含義為1*2*3*...*(N-1)*N
逃顶,計(jì)算N!
的十進(jìn)制表示中,末尾有多少個(gè)0
充甚。
解答思路
N!
中能產(chǎn)生末尾是0
的質(zhì)數(shù)組合是2*5
以政,所以N!
末尾的0
的個(gè)數(shù)取決了2
的個(gè)數(shù)和5
的個(gè)數(shù)的最小值,有因?yàn)楸?code>2整除的數(shù)出現(xiàn)的概率大于5
伴找,因此5
出現(xiàn)的次數(shù)就是N!
末尾0
的個(gè)數(shù)盈蛮。因此,該問題就轉(zhuǎn)換成為計(jì)算從1~N
疆瑰,每個(gè)數(shù)可以貢獻(xiàn)5
的個(gè)數(shù)眉反,也就是每個(gè)數(shù)除以5
的值。
上面的解法需要從1
到N
遍歷每一個(gè)數(shù)穆役,當(dāng)然還有更加簡便的方法寸五。以26!
為例,貢獻(xiàn)5
的數(shù)有5耿币、10梳杏、15、20淹接、25
十性,一共貢獻(xiàn)了6
個(gè)5
,可以理解為5
的倍數(shù)5塑悼、10劲适、15、20厢蒜、25
貢獻(xiàn)了一個(gè)5
霞势,而25
的倍數(shù)又貢獻(xiàn)了一個(gè)5
烹植,得到下面的公式:
Z = [N/5] +[N/5^2] +[N/5^3] + …(總存在一個(gè)K,使得5^K > N愕贡,[N/5^K]=0)
代碼實(shí)現(xiàn)
class Untitled {
static int lowZeroN(int N) {
int count = 0;
while (N > 0) {
N = N / 5;
count = count + N;
}
return count;
}
public static void main(String[] args) {
System.out.println("26!的十進(jìn)制表示中末尾0的個(gè)數(shù)=" + lowZeroN(26));
}
}
運(yùn)行結(jié)果
>> 26!的十進(jìn)制表示中末尾0的個(gè)數(shù)=6
2.8 給定一個(gè)整數(shù) N草雕,求 N! 的二進(jìn)制表示中最低位 1 的位置
解答思路
首先,讓我們換一個(gè)角度考慮固以,其實(shí)這個(gè)問題就是求解二進(jìn)制表示中從最低位開始0
的個(gè)數(shù)墩虹,因?yàn)槎M(jìn)制最低位為0
代表的是偶數(shù),能夠被2
整除憨琳,所以質(zhì)因數(shù)2
的個(gè)數(shù)就是二進(jìn)制表示中最低位1
后面的0
的個(gè)數(shù)诫钓。
因此,我們的實(shí)現(xiàn)這就和上面2.7
中求解質(zhì)因數(shù)5
的個(gè)數(shù)是一樣的篙螟。
代碼實(shí)現(xiàn)
class Untitled {
static int lowOneN(int N) {
int count = 0;
while (N > 0) {
N = N >> 1;
count = count + N;
}
return count+1;
}
public static void main(String[] args) {
System.out.println("3!的二進(jìn)制表示中最低位1的位置=" + lowOneN(3));
}
}
運(yùn)行結(jié)果
>> 3!的二進(jìn)制表示中最低位1的位置=2
2.9 最大公約數(shù)
問題描述
最大公約數(shù) 的定義為 兩個(gè)或多個(gè)整數(shù)的共有約數(shù)中最大的一個(gè)尖坤。這里采用的是 更相止損法,其操作步驟為:
- 第一步:任意給定兩個(gè)正整數(shù)闲擦;判斷它們是否都是偶數(shù)。若是场梆,則用
2
約簡墅冷;若不是則執(zhí)行第二步。 - 第二步:以較大的數(shù)減較小的數(shù)或油,接著把所得的差與較小的數(shù)比較寞忿,并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作顶岸,直到所得的減數(shù)和差相等為止腔彰。
則第一步中約掉的若干個(gè)2
與第二步中等數(shù)的乘積就是所求的最大公約數(shù)。
代碼實(shí)現(xiàn)
class Untitled {
static int gcd(int big, int small) {
int fac = 1;
int temp;
while (small > 0) {
//保證數(shù)字的先后順序辖佣。
if (small > big) {
temp = big;
big = small;
small = temp;
}
if ((big & 1) > 0) {
//奇奇霹抛。
if ((small & 1) > 0) {
temp = big;
big = small;
small = temp - small;
//奇偶。
} else {
small >>= 1;
}
} else {
//偶奇卷谈。
if ((small & 1) > 0) {
big >>= 1;
//偶偶杯拐。
} else {
small >>= 1;
big >>= 1;
fac *= 2;
}
}
}
return big * fac;
}
public static void main(String[] args) {
int result = gcd(319, 377);
System.out.println("result=" + result);
}
}
運(yùn)行結(jié)果
>> result=29
2.10 精確地表達(dá)有限/無限循環(huán)小數(shù)
問題描述
有限小數(shù)或者無限循環(huán)小數(shù)都可以轉(zhuǎn)化為分?jǐn)?shù),例如:
有限小數(shù):0.9 = 9/10
無限循環(huán)小數(shù):0.333(3)= 1/3
解決思路
在 http://blog.csdn.net/flyfish1986/article/details/47783545 這邊文章中世蔗,詳細(xì)地描述了該題的解決思路端逼,核心思想就是將原小數(shù)分為 有限部分 和 無限循環(huán)小數(shù) 部分,對于這兩部分別進(jìn)行處理污淋。
代碼實(shí)現(xiàn)
class Untitled {
public static class Fraction {
//分子顶滩。
public double numerator;
//分母。
public double denominator;
}
public static double powerOf(int num, int mi) {
double temp = 10;
double result = 1;
while (mi > 0) {
if ((mi & 1) > 0) {
result = result * temp;
}
temp = temp * temp;
mi >>= 1;
}
return result;
}
//分為有限循環(huán)和無限循環(huán)兩個(gè)部分寸爆,按照公式計(jì)算礁鲁。
public static Fraction getDescription(int limit, int limitLen, int unLimit, int unLimitLen) {
//分別計(jì)算對應(yīng)長度的10的n/m次冪盐欺。
double limitPower = powerOf(10, limitLen);
double unLimitPower = powerOf(10, unLimitLen);
Fraction fraction = new Fraction();
//根據(jù)公式計(jì)算分子和分母即可。
fraction.numerator = limit * (unLimitPower - 1) + unLimit;
fraction.denominator = (unLimitPower - 1) * limitPower;
return fraction;
}
public static void main(String[] args) {
Fraction f = getDescription(285714, 6, 285714, 6);
System.out.println("res= " + f.numerator + "/" + f.denominator);
}
}
運(yùn)行結(jié)果
>> res= 2.85714E11/9.99999E11
更多文章救氯,歡迎訪問我的 Android 知識梳理系列:
- Android 知識梳理目錄:http://www.reibang.com/p/fd82d18994ce
- Android 面試文檔分享:http://www.reibang.com/p/8456fe6b27c4