力扣8.27
433.最小基因变化
题目
基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 ‘T’ 之一。
假设我们需要调查从基因序列 start 变为end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
- 例如，
"AACCGGTT" --> "AACCGGTA"就是一次基因变化。
另有一个基因库bank记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库bank中）
给你两个基因序列 start 和 end ，以及一个基因库bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。
注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
数据范围
start.length == 8end.length == 80 <= bank.length <= 10bank[i].length == 8start、end和bank[i]仅由字符['A', 'C', 'G', 'T']组成
分析
bfs，向bank中的字符串转移，写个函数判断两个字符串之间不同字符个数
代码
class Solution {
public:struct node_ {string s;int times;};map<string, bool> vis;int calDiffuse(string a, string b) {int cnt = 0;for(int i = 0; i < a.size(); i ++ ) {if(a[i] != b[i]) {cnt ++ ;}}return cnt;}int bfs(string s, string t, vector<string>& bank) {for(int i = 0; i < bank.size(); i ++ ) {vis[bank[i]] = false;}queue<node_> q;q.push({s, 0});vis[s] = true;while(q.size()) {auto now = q.front();q.pop();if(now.s == t) {return now.times;}for(int i = 0; i < bank.size(); i ++ ) {if(vis[bank[i]] == true) continue;if(calDiffuse(bank[i], now.s) != 1) continue;vis[bank[i]] = true;q.push({bank[i], now.times + 1});}}return -1;}int minMutation(string startGene, string endGene, vector<string>& bank) {return bfs(startGene, endGene, bank);}
};
127.单词接龙
题目
字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
- 每一对相邻的单词只差一个字母。
- 对于
1 <= i <= k时，每个si都在wordList中。注意，beginWord不需要在wordList中。 sk == endWord
给你两个单词beginWord和endWord和一个字典wordList，返回 从beginWord到endWord的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回0。
数据范围
1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord、endWord和wordList[i]由小写英文字母组成beginWord != endWord- wordList 中的所有字符串 互不相同
分析
乍一看，这道题和上面那题思路一样，但稍微分析一下就可以知道，普通的bfs肯定会超时，所以需要采用双向广搜，但本题我才用的是另一种做法。这道题的字符串间的转换关系可以看作顶点之间连边，因此可以考虑建图然后跑最短路。给每个字符串映射一个id，然后建图，最暴力的建图方法是遍历wordList的所有点，然后向其他所有点连边，但这样显然会超时，因此考虑别的建图方法。我们可以考虑使用虚拟顶点，对于字符串a，都可以有b转换过来(这里b和a只相差一个字符串)，例如fib可以由*ib、f*b和fi*转移过来，而*ib又可以转换到tib等，这样就可以通过建虚拟点大大降低建图复杂度，唯一需要注意的是，在最终计算答案时，由于我们是通过fib->*ib->tib这种方式得到目标字符串的，而实际只需要从fib->tib，花费多了一倍，需要除以2，再者，对于fib->tib，实际长度应该要加上fib，因此最后结果还需要加1，然后按照bfs的常规流程跑就行了。
代码
class Solution {
public:const static int N = 5e5;struct node_ {int id;int times;};bool vis[N];unordered_map<string, int> id;vector<vector<int>> mp;int idx = 0;void addPoint(string s) {if(id.find(s) != id.end()) return ;id[s] = idx ++ ;mp.emplace_back();}void addEdge(string s1, string s2) {auto id1 = id[s1];auto id2 = id[s2];mp[id1].push_back(id2);mp[id2].push_back(id1);}void addVirtual(string s) {addPoint(s);string tmps = s;for(int i = 0; i < s.size(); i ++ ) {char tmp = s[i];s[i] = '*';addPoint(s);addEdge(s, tmps);s[i] = tmp;}}void init(string s, string t, vector<string>& wordList) {for(int i = 0; i < wordList.size(); i ++ ) {addVirtual(wordList[i]);}addVirtual(s);addVirtual(t);}int bfs(string s, string t) {queue<node_> q;q.push({id[s], 0});vis[id[s]] = true;while(q.size()) {auto now = q.front();q.pop();if(now.id == id[t]) {return now.times / 2 + 1;}for(auto k : mp[now.id]) {if(vis[k]) continue;vis[k] = true;q.push({k, now.times + 1});}}return 0;}int ladderLength(string beginWord, string endWord, vector<string>& wordList) {init(beginWord, endWord, wordList);bool flag = false;for(int i = 0; i < wordList.size(); i ++ ) {if(wordList[i] == endWord) flag = true;}if(!flag) return 0;return bfs(beginWord, endWord);}
};
77.组合
题目
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
数据范围
1 <= n <= 20- `1 <= k <= n
分析
普通dfs
代码
class Solution {
public:const static int N = 25;int a[N];vector<vector<int>> res;bool vis[N];void dfs(int t, int n, int k) {if(t > k) {vector<int> tmp;for(int i = 1; i <= k; i ++ ) {tmp.push_back(a[i]);}res.push_back(tmp);return ;}for(int i = max(a[t - 1], 1); i <= n; i ++ ) {if(vis[i]) continue;vis[i] = true;a[t] = i;dfs(t + 1, n, k);vis[i] = false;}}vector<vector<int>> combine(int n, int k) {dfs(1, n, k);return res;}
};