最近斷斷續(xù)續(xù)的刷了一些基礎(chǔ)算法題. 我們做移動端開發(fā)的, 刷算法題有意義嗎? 如果對這個問題有疑問, 可以在讀這篇文章之前先讀下巧神的文章: 搞 iOS 的學(xué)算法有意義嗎获三？
下面這篇文章, 主要是用 OC 語言練習(xí)的幾個小算法, 會不定期更新. 首先放兩個不錯的鏈接地址: 劍指offer 算法題, Leetcode 題解, 有興趣的童鞋可以一起學(xué)習(xí)哈!
1. 1-n 階乘之和
1-n階乘之和怎么算屹篓？
- 1的階乘是1
- 2的階乘是1*2
- 3的階乘是123
- 4的階乘是123*4
- .........
現(xiàn)在我們要求這些階乘的和鸠项。思路：
- 3階乘的和其實上就是2階乘的和+3的階乘
- 4階乘的和其實上就是3階乘的和+4的階乘
- .......
/** 1-n 階乘之和 */
- (NSInteger)factorialWithNumber:(NSInteger)number {
// 總和
NSInteger sum = 0;
// 階乘值, 初始化為1
NSInteger factorial = 1;
for (NSInteger i = 1; i <= number; i++) {
factorial = factorial * i;
sum = (int) (sum + factorial);
}
return sum;
}
2. 跳臺階問題
一只青蛙一次可以跳上 1 級臺階做粤，也可以跳上 2 級贴唇。求該青蛙跳上一個 n 級的臺階總共有多少種跳法絮记。
我們假設(shè)到第 n 階總共有 f(n) 種跳法肝集，而且想跳到第 n 階只有兩種可能瞪讼，要么從第 n-1 階跳一階到達岭参，要么從第 n-2 階跳兩階到達，所以遞推式為f(n) = f(n-1) + f(n-2)尝艘。特殊情況為演侯，n=0 的時候跳法為 0；n=1時背亥，跳法為1秒际；n=2時，跳法為2;
/** 跳臺階問題 */
- (NSInteger)jumpFloor:(NSInteger)number {
if(number < 1)
return 0;
if(number == 1)
return 1;
if(number == 2)
return 2;
return [self jumpFloor:(number-1)] + [self jumpFloor:(number-2)];
}
3. 變態(tài)跳臺階問題
一只青蛙一次可以跳上 1 級臺階狡汉，也可以跳上 2 級……它也可以跳上 n 級娄徊。求該青蛙跳上一個n級的臺階總共有多少種跳法。
- 先看 n = 0 時盾戴，跳法 f(0) = 0寄锐；
- n = 1，只能是從第 0 個臺階跳過來，跳法 f(1) = 1;
- n = 2橄仆，可能是第 0 個臺階跳了 2 階或者從第 1 個臺階跳了 1 階剩膘，跳法f(2) = 2 * f(1) = 2;
- n = 3，可能是第 0 個臺階跳了 3 階盆顾、第 1 個臺階跳了 2 階怠褐、第 2 個臺階跳了 1 階、各跳 1 階您宪，跳法 f(3) = 2 * f(2) = 4;
- ...
- n = n-1奈懒，跳法 f(n-1) = 2f(n-2);
- n = n，跳法 2f(n-1);
- 由上面兩個等式得：f(n) = 2f(n-1)
/** 變態(tài)跳臺階問題 */
- (NSInteger)jumpFloorII:(NSInteger)number {
if(number < 1)
return 0;
if(number == 1)
return 1;
return 2*[self jumpFloorII:(number-1)];
}
4. 求1+2+3+...+n
求1+2+3+...+n宪巨，要求不能使用乘除法磷杏、for、while捏卓、if茴丰、else、switch天吓、case等關(guān)鍵字及條件判斷語句（A?B:C）
題目要求不能使用乘除法贿肩、for、while龄寞、if汰规、else、switch物邑、case 等關(guān)鍵字及條件判斷語句溜哮，那么首先就要思考怎么才能使 n 一次次的相加且到 0 的時候結(jié)束。首先遞歸可以實現(xiàn)每次 n-1 的相加色解，即類似于 n + f(n-1) 這樣的茂嗓。但是這樣做的話遞歸的出口在哪呢，也就是我們不能使用條件語句來控制遞歸何時停止科阎。
仔細想想還有什么運算符可以達到條件控制的效果述吸，這個時候 && 運算符就出現(xiàn)了
/** 求1+2+3+...+n */
- (NSInteger)sum_Solution:(NSInteger)number {
number && (number += [self sum_Solution:(number-1)]);
return number;
}
5. 不用加減乘除做加法
寫一個函數(shù)，求兩個整數(shù)之和锣笨，要求在函數(shù)體內(nèi)不得使用 +蝌矛、-、*错英、/ 四則運算符號入撒。
a ^ b 表示沒有考慮進位的情況下兩數(shù)的和，(a & b) << 1 就是進位椭岩。
遞歸會終止的原因是 (a & b) << 1 最右邊會多一個 0茅逮，那么繼續(xù)遞歸璃赡，進位最右邊的 0 會慢慢增多，最后進位會變?yōu)?0献雅，遞歸終止碉考。
/** 不用加減乘除做加法 */
- (NSInteger)sumA:(NSInteger)a b:(NSInteger)b {
return b == 0 ? a : [self sumA:(a ^ b) b:((a & b) << 1)];
}
6. 圓圈中最后剩下的數(shù)
讓小朋友們圍成一個大圈。然后惩琉，他隨機指定一個數(shù) m，讓編號為 0 的小朋友開始報數(shù)夺荒。每次喊到 m-1 的那個小朋友要出列唱首歌瞒渠，然后可以在禮品箱中任意的挑選禮物，并且不再回到圈中技扼，從他的下一個小朋友開始伍玖，繼續(xù) 0...m-1 報數(shù) .... 這樣下去 .... 直到剩下最后一個小朋友，可以不用表演剿吻。
約瑟夫環(huán)窍箍，圓圈長度為 n 的解可以看成長度為 n-1 的解再加上報數(shù)的長度 m。因為是圓圈丽旅，所以最后需要對 n 取余椰棘。
/** 圓圈中最后剩下的數(shù) */
- (NSInteger)lastRemaining_Solution:(NSInteger)n m:(NSInteger)m {
// 特殊輸入的處理
if (n == 0)
return -1;
if (n == 1)
return 0;
return ([self lastRemaining_Solution:n-1 m:m] + m) % n;
}
7. 從 1 到 n 整數(shù)中 1 出現(xiàn)的次數(shù)
/** 從 1 到 n 整數(shù)中 1 出現(xiàn)的次數(shù) */
- (NSInteger)numberOf1Between1AndN:(NSInteger)n {
NSInteger number = 0;
for (NSInteger m = 1; m <= n; m *= 10) {
NSInteger a = n / m, b = n % m;
number += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);
}
return number;
}
代碼在這里, 算法練習(xí): NNAlgorithm, 有興趣的童鞋可以下載下 demo, 看下打印效果.
