[Algorithm][综合训练][数组中两个字符串的最小距离][Fibonacci数列][单词搜索]详细讲解

---

1.数组中两个字符串的最小距离

1.题目链接

• 数组中两个字符串的最小距离

---

2.算法原理详解 && 代码实现

• 自己的版本：85% 贪心
  • 错误原因：这样贪心只是一直在往后找两组可能的新的str来更新最小值，但是前面仍然有可能存在最优解的情况
  • 错误版本

    #include <iostream>
    #include <vector>
    #include <string>
    #include <cstdlib>
    #include <climits>
    using namespace std;int main()
    {int n = 0;string str1, str2;cin >> n >> str1 >> str2;vector<string> strs(n);for(int i = 0; i < n; i++){cin >> strs[i];}if(str1.empty() && str2.empty()){cout << -1 << endl;return 0;}// 双指针int p1 = 0, p2 = 0, ret1 = 0, ret2 = 0, minDist = INT_MAX;bool flag1 = false, flag2 = false;while(p1 < n && p2 < n){// 找str1while(p1 < n){if(strs[p1] == str1){flag1 = true;ret1 = p1++;break;}p1++;}// 找str2while(p2 < n){if(strs[p2] == str2){flag2 = true;ret2 = p2++;break;}p2++;}if(flag1 && flag2){minDist = min(minDist, abs(ret1 - ret2));}}cout << (minDist == INT_MAX ? -1 : minDist) << endl;return 0;
    }
    

  • 纠正：每次找到一个str就应该更新一次minDist，而不是等两个查找str都跑完再更新

    #include <iostream>
    #include <vector>
    #include <string>
    #include <cstdlib>
    #include <climits>
    using namespace std;int main()
    {int n = 0;string str1, str2;cin >> n >> str1 >> str2;vector<string> strs(n);for (int i = 0; i < n; i++){cin >> strs[i];}if (str1.empty() && str2.empty()){cout << -1 << endl;return 0;}// 双指针int p1 = 0, p2 = 0, ret1 = 0, ret2 = 0, minDist = INT_MAX;bool flag1 = false, flag2 = false;while (p1 < n || p2 < n){// 找str1while (p1 < n){if (strs[p1] == str1){flag1 = true;ret1 = p1++;break;}p1++;}if (flag1 && flag2){minDist = min(minDist, abs(ret1 - ret2));}// 找str2while (p2 < n){if (strs[p2] == str2){flag2 = true;ret2 = p2++;break;}p2++;}if (flag1 && flag2){minDist = min(minDist, abs(ret1 - ret2));}}cout << (minDist == INT_MAX ? -1 : minDist) << endl;return 0;
    }
    

• 优化版本：贪心(预处理) --> 用几个变量去标记目前已经发现的值

  #include <iostream>
  #include <string>
  using namespace std;int main()
  {int n = 0;string str1, str2, str; // str用于优化空间，没必要用一个vector存储cin >> n >> str1 >> str2;int prev1 = -1, prev2 = -1, ret = 0x3f3f3f3f;for(int i = 0; i < n; i++) // 用i去同时探寻str1和str2{cin >> str;if(str == str1) // 去前面找最近的str2{if(prev2 != -1){ret = min(ret, i - prev2);}prev1 = i;}else if(str == str2) // 去前面找最近的str1{if(prev1 != -1){ret = min(ret, i - prev1);}prev2 e= i;}}cout << (ret == 0x3f3f3f3f ? -1 : ret) << endl;return 0;
  }
  

---

2.Fibonacci数列

1.题目链接

• Fibonacci数列

---

2.算法原理详解 && 代码实现

• 自己的版本：

  #include <iostream>
  #include <vector>
  using namespace std;int main()
  {int n = 0;cin >> n;// 动态规划计算Fibvector<int> fib(2, 0);fib[0] = 0, fib[1] = 1;int i = 2;while(true){fib.push_back(fib[i - 1] + fib[i - 2]);if(fib[i++] > n){break;}}int prevDist = n - fib[i - 2], nextDist = fib[i - 1] - n;cout <<  (prevDist < nextDist ? prevDist : nextDist) << endl;return 0;
  }
  

• 优化版本：相较自己的版本进行了空间优化

  #include <iostream>
  using namespace std;int main()
  {int n = 0;cin >> n;int a = 0, b = 1, c = 1;while(n > c){a = b;b = c;c = a + b;}cout << min(c - n, n - b);return 0;
  }
  

---

3.单词搜索

1.题目链接

• 单词搜索

---

2.算法原理详解 && 代码实现

• 自己的版本：纯暴搜，因为超时而64.25%

  class Solution
  {int n = 0, m = 0;int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};vector<vector<bool>> visit;string _word, path;bool exist(vector<string>& board, string word){n = board.size(), m = board[0].size();visit.resize(n, vector<bool>(m, false));_word = word;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){path += board[i][j];visit[i][j] = true;if(DFS(board, i, j)){return true;}path.pop_back(); // 回溯visit[i][j] = false;}}return false;}bool DFS(vector<string>& board, int row, int col){if(path == _word){return true;}for(int k = 0; k < 4; k++){int i = row + dx[k], j = col + dy[k];if(i < n && i >= 0 && j < m && j >= 0 && !visit[i][j]){visit[i][j] = true;path += board[i][j];if(DFS(board, i, j)){return true;}// 回溯visit[i][j] = false;path.pop_back();}}return false;}
  };
  

• 优化版本：相较于自己的版本，做了剪枝和空间优化

  class Solution
  {int n = 0, m = 0;vector<vector<bool>> visit;int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};
  public:bool exist(vector<string>& board, string word){n = board.size(), m = board[0].size();visit.resize(n, vector<bool>(m, false));for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(board[i][j] == word[0]) // 剪枝{if(DFS(board, i, j, word, 0)){return true;}}}}return false;}bool DFS(vector<string>& board, int i, int j, string& word, int pos){if(pos == word.size() - 1){return true;}visit[i][j] = true;for(int k = 0; k < 4; k++){int a = i + dx[k], b = j + dy[k];if(a >= 0 && a < n && b >= 0 && b < m && !visit[a][b] && board[a][b] == word[pos + 1]) // 剪枝{if(DFS(board, a, b, word, pos + 1)){return true;}}}visit[i][j] = false;return false;}
  };
  

---