力扣8.27

本文主要是介绍力扣8.27，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

433.最小基因变化

题目

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 ‘T’ 之一。

假设我们需要调查从基因序列 start 变为end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。
另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

数据范围

start.length == 8
end.length == 8
0 <= bank.length <= 10
bank[i].length == 8
start、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 <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、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;}
};