leetcode解题思路分析（九十七）839 - 845 题

本文主要是介绍leetcode解题思路分析（九十七）839 - 845 题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

839. 相似字符串
     给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组？

用并查集的思想，将字符串数组转化为一个图求联通的边的问题

class Solution {
public:vector<int> f;int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);}bool check(const string &a, const string &b, int len) {int num = 0;for (int i = 0; i < len; i++) {if (a[i] != b[i]) {num++;if (num > 2) {return false;}}}return true;}int numSimilarGroups(vector<string> &strs) {int n = strs.size();int m = strs[0].length();f.resize(n);for (int i = 0; i < n; i++) {f[i] = i;}for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {int fi = find(i), fj = find(j);if (fi == fj) {continue;}if (check(strs[i], strs[j], m)) {f[fi] = fj;}}}int ret = 0;for (int i = 0; i < n; i++) {if (f[i] == i) {ret++;}}return ret;}
};

840. 矩阵中的幻方
     3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。给定一个由整数组成的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。

class Solution {
public:int numMagicSquaresInside(vector<vector<int>>& grid) {int ans=0;for(int i=0;i<(int)grid.size()-2;i++){for(int j=0;j<(int)grid[0].size()-2;j++){if(check(i,j,grid))ans++;}}return ans;}bool check(int x0,int y0,vector<vector<int>>&grid){bool one2nine[9];memset(one2nine,0,sizeof(one2nine));for(int i=x0;i<x0+3;i++){for(int j=y0;j<y0+3;j++){if(grid[i][j]==0||grid[i][j]>9)return false;if(one2nine[grid[i][j]-1]==true)return false;one2nine[grid[i][j]-1]=true;}}int add=grid[x0+2][y0]+grid[x0+1][y0+1]+grid[x0][y0+2];for(int i=0,x=x0;i<3;i++,x++){if(grid[x][y0]+grid[x][y0+1]+grid[x][y0+2]!=add)return false;}for(int i=0,y=y0;i<3;i++,y++){if(grid[x0][y]+grid[x0+1][y]+grid[x0+2][y]!=add)return false;}if(grid[x0][y0]+grid[x0+1][y0+1]+grid[x0+2][y0+2]!=add)return false;return true;}
};

841. 钥匙和房间
     有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，…，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，…，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。最初，除 0 号房间外的其余所有房间都被锁住。你可以自由地在房间之间来回走动。如果能进入每个房间返回 true，否则返回 false。

实际就是遍历问题，用DFS或者BFS均可，额外使用一个辅助数组存储标记位从而减小重复

class Solution {
public:bool canVisitAllRooms(vector<vector<int>>& rooms) {int n = rooms.size(), num = 0;vector<int> vis(n);queue<int> que;vis[0] = true;que.emplace(0);while (!que.empty()) {int x = que.front();que.pop();num++;for (auto& it : rooms[x]) {if (!vis[it]) {vis[it] = true;que.emplace(it);}}}return num == n;}
};

842. 将数组拆分成斐波那契序列
     给定一个数字字符串 S，比如 S = “123456579”，我们可以将它分成斐波那契式的序列 [123, 456, 579]。
     形式上，斐波那契式序列是一个非负整数列表 F，且满足：
     0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；
     F.length >= 3；对于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2] 成立。
     另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。
     返回从 S 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。

回溯剪枝

class Solution {
public:vector<int> splitIntoFibonacci(string num) {vector<int> list;backtrack(list, num, num.length(), 0, 0, 0);return list;}bool backtrack(vector<int>& list, string num, int length, int index, long long sum, int prev) {if (index == length) {return list.size() >= 3;}long long curr = 0;for (int i = index; i < length; i++) {if (i > index && num[index] == '0') {break;}curr = curr * 10 + num[i] - '0';if (curr > INT_MAX) {break;}if (list.size() >= 2) {if (curr < sum) {continue;}else if (curr > sum) {break;}}list.push_back(curr);if (backtrack(list, num, length, i + 1, prev + curr, curr)) {return true;}list.pop_back();}return false;}
};

843. 猜猜这个单词
     这个问题是 LeetCode 平台新增的交互式问题 。我们给出了一个由一些独特的单词组成的单词列表，每个单词都是 6 个字母长，并且这个列表中的一个单词将被选作秘密。你可以调用 master.guess(word) 来猜单词。你所猜的单词应当是存在于原列表并且由 6 个小写字母组成的类型字符串。此函数将会返回一个整型数字，表示你的猜测与秘密单词的准确匹配（值和位置同时匹配）的数目。此外，如果你的猜测不在给定的单词列表中，它将返回 -1。对于每个测试用例，你有 10 次机会来猜出这个单词。当所有调用都结束时，如果您对 master.guess 的调用不超过 10 次，并且至少有一次猜到秘密，那么您将通过该测试用例。除了下面示例给出的测试用例外，还会有 5 个额外的测试用例，每个单词列表中将会有 100 个单词。这些测试用例中的每个单词的字母都是从 ‘a’ 到 ‘z’ 中随机选取的，并且保证给定单词列表中的每个单词都是唯一的。

极小化的思路
第一次随机取一个单词
按照返回的match，下一个查找match数量一样的单词，构成单词组
按照单词组里随机取单次，如果没完全匹配且未超过10次则重复步骤2,否则结束

/*** // This is the Master's API interface.* // You should not implement it, or speculate about its implementation* class Master {*   public:*     int guess(string word);* };*/
/*** // This is the Master's API interface.* // You should not implement it, or speculate about its implementation* class Master {*   public:*     int guess(string word);* };*/
class Solution {
private:int NumMatched(const string& a, const string& b){int res = 0;for (int i = 0; i < 6; ++i){res += a[i] == b[i];}return res;}public:void findSecretWord(vector<string>& wordlist, Master& master) {if (wordlist.empty()){return;}int n = wordlist.size();int w = wordlist[0].size();// match预先计算int matches[n][n];memset(matches, 0x3f3f3f3, sizeof(matches));for (int i = 0; i < n; ++i){for (int j = i; j < n; ++j){if (i != j){matches[i][j] = NumMatched(wordlist[i], wordlist[j]);matches[j][i] = matches[i][j];}else{matches[i][j] = w;}// cout << i<<","<<j << " " << matches[i][j] << endl;}}vector<int> guessList(n, 0);for (int i = 0; i < n ; ++i){guessList[i] = i;}int lastNum = 0;vector<int> guessList2;for (int i = 0; i < 10; ++i){if (guessList.empty()){return;}// int curr = guessList[rand()%guessList.size()];int curr = guessList[guessList.size()/2];int currMatch = master.guess(wordlist[curr]);// cout << wordlist[curr] << " " << currMatch << endl;//  已经猜中则返回if (currMatch == w){return;}guessList2.clear();for (int j : guessList){if (matches[curr][j] == currMatch){guessList2.push_back(j);}}guessList.swap(guessList2);}return;}
};

844. 比较含退格的字符串
     给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。如果相等，返回 true ；否则，返回 false 。注意：如果对空文本输入退格字符，文本继续为空。

逆序指针滑动即可

class Solution {
public:bool backspaceCompare(string S, string T) {int i = S.length() - 1, j = T.length() - 1;int skipS = 0, skipT = 0;while (i >= 0 || j >= 0) {while (i >= 0) {if (S[i] == '#') {skipS++, i--;} else if (skipS > 0) {skipS--, i--;} else {break;}}while (j >= 0) {if (T[j] == '#') {skipT++, j--;} else if (skipT > 0) {skipT--, j--;} else {break;}}if (i >= 0 && j >= 0) {if (S[i] != T[j]) {return false;}} else {if (i >= 0 || j >= 0) {return false;}}i--, j--;}return true;}
};

845. 数组中的最长山脉
     我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：B.length >= 3存在 0 < i < B.length - 1 使得 B[0] < B[1] < … B[i-1] < B[i] > B[i+1] > … > B[B.length - 1]（注意：B 可以是 A 的任意子数组，包括整个数组 A。）给出一个整数数组 A，返回最长 “山脉” 的长度。如果不含有 “山脉” 则返回 0。

双指针滑动

class Solution {
public:int longestMountain(vector<int>& arr) {int n = arr.size();int ans = 0;int left = 0;while (left + 2 < n) {int right = left + 1;if (arr[left] < arr[left + 1]) {while (right + 1 < n && arr[right] < arr[right + 1]) {++right;}if (right < n - 1 && arr[right] > arr[right + 1]) {while (right + 1 < n && arr[right] > arr[right + 1]) {++right;}ans = max(ans, right - left + 1);}else {++right;}}left = right;}return ans;}
};

这篇关于leetcode解题思路分析（九十七）839 - 845 题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---