劍指offer10-I.斐波那契數列

題目鏈接

題目：斐波那契數（通常用F(n)表示）形成的序列稱為斐波那契數列 。該數列由 0 和 1 開始，后面的每一項數字都是前面兩項數字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

給定n ，請計算 F(n) 。

答案需要取模1e9+7(1000000007) ，如計算初始結果為：1000000008，請返回1。

思路：雖然矩陣快速冪也能做，但是這里用動態規劃。

通過代碼：

class Solution {
public:int fib(int n) {if(n < 2)return n;int mod = 1e9 + 7;int a = 0, b = 1;int res;for(int i = 0; i < n - 1; i++){res = (a + b) % mod;a = b;b = res;}return res;}
};

劍指offer10-II.青蛙跳臺階問題

題目鏈接

題目：今天的有氧運動訓練內容是在一個長條形的平臺上跳躍。平臺有num個小格子，每次可以選擇跳一個格子或者兩個格子。請返回在訓練過程中，學員們共有多少種不同的跳躍方式。

結果可能過大，因此結果需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請返回 1。

思路：本質上和上一題一樣。

通過代碼：

class Solution {
public:int trainWays(int num) {if(num < 2)return 1;int mod = 1e9 + 7;int a = 1, b = 1;int res;for(int i = 0; i < num - 1; i++){res = (a + b) % mod;a = b;b = res;}return res;}
};

劍指offer19.正則表達式匹配

題目鏈接

題目：請設計一個程序來支持用戶在文本編輯器中的模糊搜索功能。用戶輸入內容中可能使用到如下兩種通配符：

• '.'匹配任意單個字符。
• '*'匹配零個或多個前面的那一個元素。

請返回用戶輸入內容 input 所有字符是否可以匹配原文字符串 article。

思路：見Leetcode題解

通過代碼：

class Solution {
public:bool articleMatch(string s, string p) {int m = s.size() + 1, n = p.size() + 1;vector<vector<bool>> dp(m, vector<bool> (n, false));dp[0][0] = true;for(int i = 2; i < n; i += 2)dp[0][i] = dp[0][i - 2] && p[i - 1] == '*';for(int i = 1; i < m; i++)for(int j = 1; j < n; j++){if(p[j - 1] == '*')dp[i][j] = dp[i][j - 2] || dp[i - 1][j] && s[i - 1] == p[j - 2] || dp[i - 1][j] && p[j - 2] == '.';elsedp[i][j] = dp[i - 1][j - 1] && s[i - 1] == p[j - 1] || dp[i - 1][j - 1] && p[j - 1] == '.';}return dp[m - 1][n - 1];}
};

劍指offer42.連續子數組的最大和

題目鏈接

題目：某公司每日銷售額記于整數數組sales，請返回所有連續一或多天銷售額總和的最大值。

要求實現時間復雜度為O(n)的算法。

思路：dp[i]表示以第i天結尾的子數組的最大和。從第i-1天轉移到第i天有兩種選擇：（1）第i天接在前一段得到最大和為dp[i-1] + sales[i]，（2）第i天單獨成段，最大和為sales[i]，二者取較大值完成狀態轉移即可。最后，遍歷過程中用res記錄最大值即可。

通過代碼：

class Solution {
public:int maxSales(vector<int>& sales) {vector<int> dp(sales.size());dp[0] = sales[0];int res = dp[0];for(int i = 1; i < sales.size(); i++){dp[i] = max(dp[i - 1] + sales[i], sales[i]);res = max(res, dp[i]);}return res;}
};

劍指offer46.把數字翻譯成字符串

題目鏈接

題目：現有一串神秘的密文ciphertext，經調查，密文的特點和規則如下：

• 密文由非負整數組成
• 數字0-25分別對應字母a-z

請根據上述規則將密文ciphertext解密為字母，并返回共有多少種解密結果。

思路：首先需要注意，包含前導0不屬于合法密文，即01這種無法解密為字母b。dp[i]表示前i個數字的解密結果種數，對于當前數字s[i-1]，它可以選擇單獨作為一個密文，也可以選擇和s[i-2]合成一個兩位數作為密文。合成兩位數需要判斷其數值范圍是否在10-25之間。

通過代碼：

class Solution {
public:int crackNumber(int ciphertext) {string s = to_string(ciphertext);vector<int> dp(s.size() + 1);dp[0] = 1;dp[1] = 1;for(int i = 2; i < dp.size(); i++){string alph = s.substr(i - 2, 2);int num = stoi(alph);if(num >= 10 && num <= 25)dp[i] = dp[i - 1] + dp[i - 2];elsedp[i] = dp[i - 1];}return dp[s.size()];}
};

劍指offer47.禮物的最大值

題目鏈接

題目：現有一個記作二維矩陣frame的珠寶架，其中frame[i][j] 為該位置珠寶的價值。拿取珠寶的規則為：

• 只能從架子的左上角開始拿珠寶
• 每次可以移動到右側或下側的相鄰位置
• 到達珠寶架子的右下角時，停止拿取

注意：珠寶的價值都是大于 0 的。除非這個架子上沒有任何珠寶，比如frame = [[0]]。

思路：dp[i][j]表示走到該位置時的最大價值。要想到達dp[i][j]，只能從上面或者左側到達，因此，取其二者中的最大值加上當前位置的價值即可。

通過代碼：

class Solution {
public:int jewelleryValue(vector<vector<int>>& frame) {int n = frame.size(), m = frame[0].size();vector<vector<int>> dp(n + 1, vector<int> (m + 1));for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];return dp[n][m];}
};

劍指offer60.n個骰子的點數

題目鏈接

題目：你選擇擲出 num 個色子，請返回所有點數總和的概率。

你需要用一個浮點數數組返回答案，其中第 i 個元素代表這 num 個骰子所能擲出的點數集合中第 i 小的那個的概率。

思路：dp[i][j]表示色子個數為i時第j小的點數的概率，即dp[num]為所需要范圍的答案。已知dp[1]的各個點數的概率為1/6，所以對dp[1]進行相應的初始化。已知i-1個色子的概率，需要將狀態轉移到i個色子。由于多了一個色子，這個色子的點數只能為1-6，且概率分別為1/6。對于dp[i-1][j]，加上多的色子的點數，就是對dp[i]造成的影響。收集這種影響即可完成狀態轉移。

通過代碼：

class Solution {
public:vector<double> statisticsProbability(int num) {vector<vector<double>> dp(num + 1, vector<double> (5 * num + 1));for(int i = 0; i < 6; i++)dp[1][i] = 1.0 / 6.0;for(int i = 2; i <= num; i++){for(int j = 0; j < 5 * (i - 1) + 1; j++){for(int k = 0; k < 6; k++)dp[i][j + k] += dp[i - 1][j] / 6.0;}}return dp[num];}
};

劍指offer62.圓圈中最后剩下的數字

題目鏈接

題目：社團共有num位成員參與破冰游戲，編號為0 ~ num-1。成員們按照編號順序圍繞圓桌而坐。社長抽取一個數字target，從 0 號成員起開始計數，排在第 target位的成員離開圓桌，且成員離開后從下一個成員開始計數。請返回游戲結束時最后一位成員的編號。

思路：約瑟夫環問題。

通過代碼：

class Solution {
public:int iceBreakingGame(int num, int target) {int res = 0;for(int i = 2; i <= num; i++)res = (res + target) % i;return res;}
};