一、面試題 08.01. 三步問題 - 力扣（LeetCode）
算法代碼：
class Solution {
public:const int MOD = 1e9 + 7;int waysToStep(int n) {// 1. 創建 dp 表// 2. 初始化// 3. 填表// 4. 返回// 處理邊界情況if (n == 1 || n == 2)return n;if (n == 3)return 4;vector<int> dp(n + 1);dp[1] = 1, dp[2] = 2, dp[3] = 4;for (int i = 4; i <= n; i++)dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;return dp[n];}
};????????這段代碼的目的是計算上樓梯的方式數，每次可以走1步、2步或3步。代碼使用了動態規劃（DP）來解決這個問題。下面是代碼的詳細思路：
1. 創建 DP 表
-
使用一個數組?
dp?來存儲每個臺階對應的上樓梯方式數。 -
dp[i]?表示上到第?i?個臺階的方式數。
2. 初始化
-
對于前三個臺階，直接初始化：
-
dp[1] = 1：只有一種方式（走1步）。 -
dp[2] = 2：有兩種方式（1+1 或 2）。 -
dp[3] = 4：有四種方式（1+1+1, 1+2, 2+1, 3）。
-
3. 填表
-
從第4個臺階開始，每個臺階的方式數等于前三個臺階方式數的和：
-
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
-
-
由于結果可能非常大，每次計算后都對?
MOD?取模，防止溢出。
4. 返回結果
-
最終返回?
dp[n]，即上到第?n?個臺階的方式數。
邊界情況處理
-
如果?
n?是1、2或3，直接返回對應的值，避免不必要的計算。
代碼優化
-
由于每次只需要前三個狀態，可以優化空間復雜度，使用三個變量代替整個?
dp?數組。
優化后的代碼
class Solution {
public:const int MOD = 1e9 + 7;int waysToStep(int n) {if (n == 1 || n == 2)return n;if (n == 3)return 4;int a = 1, b = 2, c = 4; // 分別代表 dp[i-3], dp[i-2], dp[i-1]int result = 0;for (int i = 4; i <= n; i++) {result = ((a + b) % MOD + c) % MOD;a = b;b = c;c = result;}return result;}
};優化思路
-
使用三個變量?
a,?b,?c?來存儲前三個狀態，減少空間復雜度。 -
每次更新?
result?后，滾動更新?a,?b,?c?的值。
這樣，代碼的空間復雜度從?O(n)?降低到了?O(1)，同時保持了時間復雜度的?O(n)。
二、5. 最長回文子串 - 力扣（LeetCode）
算法代碼：
class Solution {
public:string longestPalindrome(string s) {// 中?擴展算法int begin = 0, len = 0, n = s.size();for (int i = 0; i < n; i++) // 依次枚舉所有的中點{// 先做?次奇數?度的擴展int left = i, right = i;while (left >= 0 && right < n && s[left] == s[right]) {left--;right++;}if (right - left - 1 > len) {begin = left + 1;len = right - left - 1;}// 偶數?度的擴展left = i, right = i + 1;while (left >= 0 && right < n && s[left] == s[right]) {left--;right++;}if (right - left - 1 > len) {begin = left + 1;len = right - left - 1;}}return s.substr(begin, len);}
};?????????這段代碼的目的是找到字符串?s?中的最長回文子串。它使用了中心擴展算法，通過枚舉每個可能的中心點，向左右擴展，找到最長的回文子串。以下是代碼的詳細思路：
1.?中心擴展算法的核心思想
-
回文串可以分為兩種：
-
奇數長度：中心是一個字符（例如?
"aba"）。 -
偶數長度：中心是兩個字符（例如?
"abba"）。
-
-
通過枚舉每個可能的中心點，向左右擴展，找到以該中心點為基準的最長回文子串。
2.?代碼實現思路
變量說明
-
begin：記錄最長回文子串的起始位置。 -
len：記錄最長回文子串的長度。 -
n：字符串?s?的長度。
步驟
-
枚舉所有可能的中心點：
-
遍歷字符串?
s，每個字符?s[i]?都可能是回文串的中心點。
-
-
奇數長度的擴展：
-
初始化?
left?和?right?為當前中心點?i。 -
向左右擴展，檢查?
s[left]?和?s[right]?是否相等。 -
如果相等，繼續擴展；否則停止。
-
計算當前回文子串的長度?
right - left - 1，如果比?len?大，則更新?begin?和?len。
-
-
偶數長度的擴展：
-
初始化?
left?為?i，right?為?i + 1（表示中心是兩個字符）。 -
向左右擴展，檢查?
s[left]?和?s[right]?是否相等。 -
如果相等，繼續擴展；否則停止。
-
計算當前回文子串的長度?
right - left - 1，如果比?len?大，則更新?begin?和?len。
-
-
返回結果：
-
使用?
s.substr(begin, len)?截取最長回文子串并返回。
-
3.?代碼優化
-
時間復雜度：
O(n^2)，其中?n?是字符串的長度。每個中心點最多擴展?n?次。 -
空間復雜度：
O(1)，只使用了常數級別的額外空間。
4.?優化后的代碼
class Solution {
public:string longestPalindrome(string s) {int begin = 0, len = 0, n = s.size();for (int i = 0; i < n; i++) {// 奇數長度擴展int l = i, r = i;expandAroundCenter(s, l, r, begin, len);// 偶數長度擴展l = i, r = i + 1;expandAroundCenter(s, l, r, begin, len);}return s.substr(begin, len);}private:void expandAroundCenter(const string& s, int l, int r, int& begin, int& len) {while (l >= 0 && r < s.size() && s[l] == s[r]) {l--;r++;}int currentLen = r - l - 1;if (currentLen > len) {begin = l + 1;len = currentLen;}}
};5.?優化思路
-
將奇數長度和偶數長度的擴展邏輯提取到一個單獨的函數?
expandAroundCenter?中，避免代碼重復。 -
通過傳遞?
begin?和?len?的引用，直接更新最長回文子串的起始位置和長度。
6.?示例運行
輸入：
string s = "babad";
Solution sol;
cout << sol.longestPalindrome(s); // 輸出 "bab" 或 "aba"運行過程：
-
枚舉中心點?
i：-
i = 0：奇數擴展得到?"b"，偶數擴展得到?""。 -
i = 1：奇數擴展得到?"bab"，偶數擴展得到?""。 -
i = 2：奇數擴展得到?"aba"，偶數擴展得到?""。 -
i = 3：奇數擴展得到?"a"，偶數擴展得到?""。 -
i = 4：奇數擴展得到?"d"，偶數擴展得到?""。
-
-
最終最長回文子串為?
"bab"?或?"aba"。
7.?總結
-
中心擴展算法是一種直觀且高效的方法，適用于解決最長回文子串問題。
-
通過優化代碼結構，可以提高代碼的可讀性和可維護性。
還沒更新完...)
