代碼學習總結（一）

這個系列的博客是記錄下自己學習代碼的歷程，有來自平臺上的，有來自筆試題回憶的，主要基于 C++ 語言，包括題目內容，代碼實現，思路，并會注明題目難度，保證代碼運行結果

1 最長公共前綴

簡單 字典樹 匹配

編寫一個函數來查找字符串數組中的最長公共前綴。如果不存在公共前綴，返回空字符串 “”。

示例輸入輸出 1：
輸入：strs = [“flower”,“flow”,“flight”]
輸出：“fl”

示例輸入輸出 2：
輸入：strs = [“dog”,“racecar”,“car”]
輸出：“”
解釋：輸入不存在公共前綴。

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 如果非空，則僅由小寫英文字母組成

思路解析：

1. 把第一個字符串作為基準，然后把它和第二個進行匹配，把二者的公共前綴取出來
2. 把基準替換為公共前綴，分別和其他的字符串進行比較，再把新的公共替換為基準
3. 返回最終的基準

本地 debug 代碼

#include <iostream>
#include <vector>
#include <string>using namespace std;string longestCommonPrefix(vector<string>& strs) {if (strs.empty()) return "";// 取第一個字符串作為基準string prefix = strs[0];// 從第二個字符串開始比較for (int i = 1; i < strs.size(); ++i) {int j = 0;// 比較當前前綴和 strs[i] 的公共部分while (j < prefix.size() && j < strs[i].size() && prefix[j] == strs[i][j]) {++j;}// 截斷前綴prefix = prefix.substr(0, j);// 如果公共前綴為空，直接返回if (prefix.empty()) return "";}return prefix;
}// 測試用例
int main() {vector<string> strs1 = {"flower", "flow", "flight"};vector<string> strs2 = {"dog", "racecar", "car"};cout << "示例 1 輸出: " << longestCommonPrefix(strs1) << endl; // 輸出: "fl"cout << "示例 2 輸出: " << longestCommonPrefix(strs2) << endl; // 輸出: ""return 0;
}

上述代碼的運行結果為

可用于提交的代碼

string longestCommonPrefix(vector<string>& strs) {if (strs.empty()) return "";// 取第一個字符串作為基準string prefix = strs[0];// 從第二個字符串開始比較for (int i = 1; i < strs.size(); ++i) {int j = 0;// 比較當前前綴和 strs[i] 的公共部分while (j < prefix.size() && j < strs[i].size() && prefix[j] == strs[i][j]) {++j;}// 截斷前綴prefix = prefix.substr(0, j);// 如果公共前綴為空，直接返回if (prefix.empty()) return "";}return prefix;
}

2 單詞拆分 II

中等 字典樹 單詞拆分

給定一個字符串 $s$ 和一個字符串字典 wordDict ，在字符串 $s$ 中增加空格來構建一個句子，使得句子中所有的單詞都在詞典中。以任意順序 返回所有這些可能的句子。

注意：詞典中的同一個單詞可能在分段中被重復使用多次。

示例輸入輸出 1：
輸入: s = “catsanddog”, wordDict = [“cat”,“cats”,“and”,“sand”,“dog”]
輸出: [“cats and dog”,“cat sand dog”]

示例 2：

輸入: s = “pineapplepenapple”, wordDict = [“apple”,“pen”,“applepen”,“pine”,“pineapple”]
輸出: [“pine apple pen apple”,“pineapple pen apple”,“pine applepen apple”]
解釋: 注意你可以重復使用字典中的單詞。

示例 3：
輸入: s = “catsandog”, wordDict = [“cats”,“dog”,“sand”,“and”,“cat”]
輸出 :[]

思路解析：

1. 由于需要尋找同一個字符串在某個給定字典下所有可能的單詞組合，所以最好是使用遞歸解決
2. 而為了方便搜索，可以將給定字典轉化為無序字典，并使用一個單獨的字典用來存儲已經搜索出的結果
3. 這里的遞歸對象因為是一個字符串，所以可以從左開始搜索，拿到第一個成型的單詞后，將右側的部分作為新的對象，進行遞歸，然后把左側的單詞壓入結果字典中

本地 debug 代碼

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>using namespace std;class Solution {
public:vector<string> wordBreak(string s, vector<string>& wordDict) {unordered_set<string> dict(wordDict.begin(), wordDict.end()); // 初始化無序集合unordered_map<string, vector<string>> memo; // 初始化記憶化搜索return dfs(s, dict, memo);}private:vector<string> dfs(const string& s, unordered_set<string>& dict,unordered_map<string, vector<string>>& memo) {// 因為memo 是空的，所以如果 s 存在于這個空的變量中，它也是空的if (memo.count(s)) return memo[s];// 如果整個輸入都存在于字典中，那直接返回vector<string> result;if (dict.count(s)) {result.push_back(s);}// 針對字符串本身進行搜索for (int i = 1; i < s.size(); ++i) {string left = s.substr(0, i); // 往左搜索，字符的左側部分string right = s.substr(i); // 往右搜索，字符的右側部分if (dict.count(left)) { //如果左側部分存在于字典中vector<string> rightPart = dfs(right, dict, memo); // 遞歸對右側部分進行處理for (const string& sub : rightPart) {result.push_back(left + " " + sub); // 將左側部分和右側部分都壓入到結果中}}}memo[s] = result;return result;}
};void printResults(const std::vector<std::string>& results) {std::cout << "[";for (size_t i = 0; i < results.size(); ++i) {std::cout << "\"" << results[i] << "\"";if (i != results.size() - 1) {std::cout << ",";}}std::cout << "]" << std::endl;
}// 測試用例
int main() {Solution sol;string s1 = "catsanddog";vector<string> wordDict1 = {"cat","cats","and","sand","dog"};string s2 = "pineapplepenapple";vector<string> wordDict2 = {"apple","pen","applepen","pine","pineapple"};string s3 = "catsandog";vector<string> wordDict3 = {"cats","dog","sand","and","cat"};vector<string> results1 = sol.wordBreak(s1, wordDict1);printResults(results1); // 輸出: ["cats and dog","cat sand dog"]vector<string> results2 = sol.wordBreak(s2, wordDict2);printResults(results2); // 輸出: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]vector<string> results3 = sol.wordBreak(s3, wordDict3);printResults(results3); // 輸出: []return 0;
}

上述代碼的運行結果為

可用于提交的代碼

class Solution {
public:vector<string> wordBreak(string s, vector<string>& wordDict) {unordered_set<string> dict(wordDict.begin(), wordDict.end()); // 初始化無序集合unordered_map<string, vector<string>> memo; // 初始化記憶化搜索return dfs(s, dict, memo);}private:vector<string> dfs(const string& s, unordered_set<string>& dict,unordered_map<string, vector<string>>& memo) {// 因為memo 是空的，所以如果 s 存在于這個空的變量中，它也是空的if (memo.count(s)) return memo[s];// 如果整個輸入都存在于字典中，那直接返回vector<string> result;if (dict.count(s)) {result.push_back(s);}// 針對字符串本身進行搜索for (int i = 1; i < s.size(); ++i) {string left = s.substr(0, i); // 往左搜索，字符的左側部分string right = s.substr(i); // 往右搜索，字符的右側部分if (dict.count(left)) { //如果左側部分存在于字典中vector<string> rightPart = dfs(right, dict, memo); // 遞歸對右側部分進行處理for (const string& sub : rightPart) {result.push_back(left + " " + sub); // 將左側部分和右側部分都壓入到結果中}}}memo[s] = result;return result;}
};void printResults(const std::vector<std::string>& results) {std::cout << "[";for (size_t i = 0; i < results.size(); ++i) {std::cout << "\"" << results[i] << "\"";if (i != results.size() - 1) {std::cout << ",";}}std::cout << "]" << std::endl;
}

這里的題目是 leetcode 中的，感興趣的同學們可以去提交下試試，可以直接運行通過，每日二題，努力加油😉！！！