字符串接龍
110. 字符串接龍 (kamacoder.com)
主要參考代碼隨想錄?代碼隨想錄 (programmercarl.com)
目標：得到從beginStr轉變為endStr所需的最少步數
過程：每次變換一個字母，每次變換的結果要在strList中。
對于一個圖來說，相當于我們有1個起點beginStr和一個終點endStr，以及strList中的N個字符串，然后我們需要找到路徑來使得beginStr變成endStr，將beginStr連接到endStr的路徑即為變化的過程，我們要最小化這個過程。
這里有兩個問題：
- 圖中的線是如何連在一起的。
- 如何確定當前路徑最短。
對于線的連接，我們注意到每次只能變換一個字符，即我們需要判斷是一個目標字符串與源字符串是否相差一個字符，若相差一個字符，則他們之間是連通的。
而判斷路徑最短，考慮使用廣度優先算法，只要搜索到了結果，那得到的一定是最短路徑，此外，注意這里計算的最短路徑不是線的數目，而是節點的數目。
代碼隨想錄里有兩個點能方便計算：一是無向圖需要標志位，來標記節點是否走過，使用set來檢查字符串是否出現在字符串集合中較快。二是利用哈希表來映射字符串和路徑長度。
具體代碼如下，和代碼隨想錄中結果一樣。
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <queue>
using namespace std;int main(){int N;cin>>N; // 輸入字符串數量 Nunordered_set<string> strSet; // 創建一個無序集合存儲所有字符串string beginStr, endStr, str;cin >> beginStr >>endStr; // 輸入起始字符串和目標字符串for(int i = 0; i < N; i++){cin>>str; // 輸入 N 個字符串strSet.insert(str); // 將字符串插入集合}unordered_map<string , int> visitMap; // 創建一個無序映射記錄字符串和對應的路徑長度queue<string> Queue; // 創建一個隊列用于 BFSQueue.push(beginStr); // 將起始字符串入隊列visitMap.insert(pair<string,int>(beginStr, 1)); // 起始字符串路徑長度為 1while(!Queue.empty()){ // 當隊列不為空時進行 BFSstring word = Queue.front(); // 獲取隊列首部的字符串Queue.pop();int path = visitMap[word]; // 獲取該字符串的路徑長度for(int i = 0;i < word.size();i++){ // 遍歷字符串的每個字符string newWord = word; // 創建一個新字符串，用于修改字符for(int j = 0; j < 26; j++){ // 遍歷 'a' 到 'z'，ASCII碼newWord[i] = 'a' + j; // 修改字符串的一個字符if(newWord == endStr){ // 如果新字符串是目標字符串cout<<path + 1<<endl; // 輸出路徑長度并結束程序return 0;}if(strSet.find(newWord)!= strSet.end() && visitMap.find(newWord) == visitMap.end()){// 如果新字符串在集合中且未被訪問過visitMap.insert(pair<string,int>(newWord,path + 1)); // 記錄新字符串和路徑長度Queue.push(newWord); // 將新字符串入隊列}}}}cout<< 0 <<endl; // 如果沒有找到路徑，輸出 0return 0;
}
對每個字符串，長度定位L，在BFS的過程中，每個字符串都可能被訪問一次，每個源字符串的每個字符都有修改的可能，共有26*L次操作，由于每個字符串只被訪問一次，因此總的時間復雜度為O(N*26*L)。
對空間復雜度，主要需要一個集合、一個哈希表及一個隊列，空間復雜度都為O(N*L)，總體空間復雜度為O(N*L)。
有向圖的完全可達性
用廣度優先搜索，對1的每個可達點進行遍歷，并將可達點加入set，最后判斷set的長度是否等于節點數即可。
#include <iostream>
#include <vector>
#include <unordered_set>
#include<queue>
using namespace std;int main(){int N,K;cin>>N>>K; // 輸入節點總數 N 和邊的總數 Kvector<vector<int>> dirgraph(K,vector<int>(2,0)); // 創建一個二維向量，用于存儲有向圖的邊for(int i = 0 ; i < K; i++){cin>>dirgraph[i][0]>>dirgraph[i][1]; // 輸入每條邊的起始節點和終止節點}unordered_set<int> visited; // 創建一個無序集合，用于存儲已訪問的節點visited.insert(1); // 將起始節點 1 加入已訪問集合queue<int> Queue; // 創建一個隊列，用于 BFSQueue.push(1); // 將起始節點 1 加入隊列while(!Queue.empty()){ // 當隊列不為空時進行 BFSint x = Queue.front(); // 獲取隊列首部的節點Queue.pop(); // 出隊列for(int i = 0; i < K;i++){ // 遍歷所有的邊if(dirgraph[i][0] == x && visited.find(dirgraph[i][1]) == visited.end()) {// 如果邊的起始節點是 x 并且終止節點未被訪問過visited.insert(dirgraph[i][1]); // 將終止節點加入已訪問集合Queue.push(dirgraph[i][1]); // 將終止節點加入隊列}}}if(visited.size()==N) // 如果已訪問的節點數等于總節點數cout<<1<<endl;else{ // 否則cout<<-1<<endl;}return 0;
}
算法的時間復雜度為O(N*K),空間復雜度為O(N+K)。
島嶼的周長
emmm，想了半天dfs和bfs，發現并不需要。。。
代碼隨想錄 (programmercarl.com)
遍歷每一個空格，遇到島嶼就計算其上下左右的領域情況，若上下左右為0或超出區域，則是一條邊。遍歷完所有的空格和每個空格的領域，即得到結果。
#include <iostream>
#include <vector>
using namespace std;int result = 0; // 定義一個全局變量，用于存儲島嶼周長int main() {int N,M;cin>>N>>M; // 輸入網格的行數 N 和列數 Mvector<vector<int>> graph(N,vector<int>(M)); // 創建一個 N 行 M 列的二維向量，用于存儲網格for(int i = 0; i < N; i++) // 遍歷網格的每一行for (int j = 0; j < M; j++) // 遍歷網格的每一列cin >> graph[i][j]; // 輸入網格的值for(int i = 0; i < N; i++){ // 遍歷網格的每一行for(int j = 0; j < M; j++){ // 遍歷網格的每一列if(graph[i][j] == 1){ // 如果當前單元格是土地if((i + 1) == N || graph[i+1][j] == 0) // 如果下方是網格邊緣或水result++; // 結果計數器加 1if((i - 1) == -1 || graph[i-1][j] == 0) // 如果上方是網格邊緣或水result++; // 結果計數器加 1if(j + 1 == M || graph[i][j + 1] == 0) // 如果右方是網格邊緣或水result++; // 結果計數器加 1if(j - 1 == -1 || graph[i][j - 1] == 0) // 如果左方是網格邊緣或水result++; // 結果計數器加 1}}}cout<<result<<endl; // 輸出島嶼周長return 0;
}
算法的時間復雜度為O(4*N*M)，空間復雜度為O(1)。
