leetcode解题思路分析（九十八）846 - 852 题

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

846. 一手顺子
     爱丽丝有一手（hand）由整数数组给定的牌。 现在她想把牌重新排列成组，使得每个组的大小都是 W，且由 W 张连续的牌组成。如果她可以完成分组就返回 true，否则返回 false。

记录每个牌是否用过，排序后依次找即可

class Solution {
public:bool isNStraightHand(vector<int>& hand, int groupSize) {int len = hand.size();// 两种特例if(len % groupSize != 0) return false; // 不能整除 直接返回falseif(groupSize == 1) return true; // groupSize为1 直接返回true// 排序sort(hand.begin(),hand.end());// 记录数组元素是否被用过vector<int> used(len,false);// i为第一个指针 遍历hand数组 for(int i=0;i<len;i++){// 元素已被使用则跳过if(used[i]) continue;// 剩下的牌数量不足以构成一个新的Wif(i>len-groupSize) return false;// 取use[i]为这一手牌中的第一张牌 并记录该牌已被使用int cur = hand[i];            used[i] = true;int tar = cur + 1; // tar为下一张需要找到的牌int end = cur + groupSize - 1;// end为这一手牌中的最后一张牌for(int j=i+1;j<len;j++){if(used[j]) continue; // 若已被用过 则跳过if(hand[j]>tar) return false;// hand[j]>tar 说明缺少需要的牌else if(hand[j]==tar){// hand[j]==tar 说明已找到下一张需要的牌used[j] = true;if(hand[j]==end)break; // 已找到end这张牌 跳出循环 重新开始找新的一组牌// 还未到end 继续找下一个tarelse tar++;}}}return true;}
};

847. 访问所有节点的最短路径
     存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号。给你一个数组 graph 表示这个图。其中，graph[i] 是一个列表，由所有与节点 i 直接相连的节点组成。返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边

采用BFS+状态压缩得解

class Solution {
public:int shortestPathLength(vector<vector<int>>& graph) {int n = graph.size();// 1.初始化队列及标记数组，存入起点queue< tuple<int, int, int> > q; // 三个属性分别为 idx, mask, distvector<vector<bool>> vis(n, vector<bool>(1 << n)); // 节点编号及当前状态for(int i = 0; i < n; i++) {q.push({i, 1 << i, 0}); // 存入起点，起始距离0，标记vis[i][1 << i] = true;}// 开始搜索while(!q.empty()) {auto [cur, mask, dist] = q.front(); // 弹出队头元素q.pop();// 找到答案，返回结果if(mask == (1 << n) - 1) return dist;// 扩展for(int x : graph[cur]) {int nextmask = mask | (1 << x);if(!vis[x][nextmask]) {q.push({x, nextmask, dist + 1});vis[x][nextmask] = true;}}}return 0;}
};

848. 字母移位
     有一个由小写字母组成的字符串 S，和一个整数数组 shifts。我们将字母表中的下一个字母称为原字母的 移位（由于字母表是环绕的， ‘z’ 将会变成 ‘a’）。例如·，shift(‘a’) = ‘b’， shift(‘t’) = ‘u’,， 以及 shift(‘z’) = ‘a’。对于每个 shifts[i] = x ， 我们会将 S 中的前 i+1 个字母移位 x 次。返回将所有这些移位都应用到 S 后最终得到的字符串。

前缀和的使用

class Solution {
public:string shiftingLetters(string s, vector<int>& shifts) {vector<int>presum;long long sumall=shifts.back();presum.push_back(sumall);reverse(shifts.begin(),shifts.end());for(int i=1;i<shifts.size();i++){sumall%=26;sumall+=shifts[i];sumall%=26;presum.push_back(sumall);}reverse(presum.begin(),presum.end());//cout<<presum[2]<<endl;for(int i=0;i<s.size();i++){int inter=presum[i]%26;int index=s[i]-'a';s[i]=(inter+index)%26+'a';}return s;}
};

849. 到最近的人的最大距离
     给你一个数组 seats 表示一排座位，其中 seats[i] = 1 代表有人坐在第 i 个座位上，seats[i] = 0 代表座位 i 上是空的（下标从 0 开始）。至少有一个空座位，且至少有一人已经坐在座位上。亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。返回他到离他最近的人的最大距离。

双指针滑动解题

class Solution {
public:int maxDistToClosest(vector<int>& seats) {int pre = -1;   //上一个已坐位置，初始值为-1int maxdis = 0; //两个已坐位置间的最大长度int n = seats.size();for (int i = 0; i < n; i++) {if (seats[i] == 1) {    //已坐座位//第一个已坐座位if (pre == -1) {maxdis = i * 2;}else if (i - pre > 1) {maxdis = max(maxdis, i - pre - 1);}pre = i;    //更新pre}//非已坐座位且是最后一个座位else if (i == n - 1) {maxdis = max(maxdis, 2 * (i - pre));}}return maxdis - maxdis / 2; //离他最近的人的最大距离为maxdis - maxdis / 2}
};

850. 矩形面积2
     我们给出了一个（轴对齐的）矩形列表 rectangles 。 对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐标，（x2，y2）是该矩形右上角的坐标。找出平面中所有矩形叠加覆盖后的总面积。 由于答案可能太大，请返回它对 10 ^ 9 + 7 取模的结果。

线性扫描

class Solution 
{
private:const static int MOD = 1e9 + 7;const static int OPEN = 0;const static int CLOSE = 1;// 计算宽度：其实就是不断累加更大的x的差值即可int QueryWidth(multiset<pair<int,int>>& activate){int res = 0;int maxX = -1;for (auto [x1, x2] : activate){maxX = max(maxX, x1);// 如果x变大了，则计算差值累加更大的宽度res += max(0, x2 - maxX);// 不断更新最大xmaxX = max(maxX, x2);}return res;}public:int rectangleArea(vector<vector<int>>& rectangles) {vector<vector<int>> rec;for (auto v: rectangles){rec.push_back({v[1], OPEN, v[0], v[2]});rec.push_back({v[3], CLOSE, v[0], v[2]});}// 排序从下到上来扫描sort(rec.begin(), rec.end());// 存储面积和int res = 0;// 初始化第一个y的位置int lastY = rec[0][0];// 当前需要计算的面积横坐标 [x1,x2]// 扫描过程中 对于每次OPEN则插入，CLOSE则删除multiset<pair<int,int>> activate;for (const vector<int> r : rec){int y = r[0];int state = r[1];int x1 = r[2];int x2 = r[3];// 累加面积res = (res + (long long)QueryWidth(activate)*(y-lastY)) % MOD;// 更新上一个y坐标lastY = y;// 对于每次OPEN则插入，CLOSE则删除if (state == OPEN){activate.insert({x1, x2});}else{activate.erase(activate.find(pair<int,int>{x1, x2}) );}}return res;}
};

851. 喧闹和富有
     在一组 N 个人（编号为 0, 1, 2, …, N-1）中，每个人都有不同数目的钱，以及不同程度的安静（quietness）。为了方便起见，我们将编号为 x 的人简称为 "person x "。如果能够肯定 person x 比 person y 更有钱的话，我们会说 richer[i] = [x, y] 。注意 richer 可能只是有效观察的一个子集。另外，如果 person x 的安静程度为 q ，我们会说 quiet[x] = q 。现在，返回答案 answer ，其中 answer[x] = y 的前提是，在所有拥有的钱不少于 person x 的人中，person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。

根据有钱程度进行排序，然后再比较安静值得出最终解。

class Solution {
public:vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {int n = quiet.size();vector<vector<int>> g(n);//有向图,富的指向穷的vector<int> indegree(n, 0);//入度for(auto& r : richer){g[r[0]].push_back(r[1]);indegree[r[1]]++;}queue<int> q;//点的idvector<int> ans(n, -1);for(int i = 0; i< n; i++)ans[i] = i;//初始化最安静的是自己for(int i = 0; i < n; i++){if(indegree[i] == 0){q.push(i);//最富裕的人，入度为0}}while(!q.empty()){int id = q.front();//人的idint q_val = quiet[ans[id]];//到他这为止，最安静的人的安静值q.pop();for(auto nt : g[id])//跟他连接的人（比他穷）{if(q_val < quiet[ans[nt]])//比 nt 更安静的人是 ans[nt], 其安静值没有q_val小ans[nt] = ans[id];if(--indegree[nt] == 0)q.push(nt);}}return ans;}
};

852. 山脉数组的峰顶索引
     符合下列属性的数组 arr 称为 山脉数组 ：
     arr.length >= 3
     存在 i（0 < i < arr.length - 1）使得：
     arr[0] < arr[1] < … arr[i-1] < arr[i]
     arr[i] > arr[i+1] > … > arr[arr.length - 1]
     给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。

二分查找

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int size = arr.size();int left = 0, right = size, mid = 0, ret = 0;while (left < right){mid = (left + right) / 2;if (arr[mid] > arr[mid + 1]){if (arr[mid] > arr[mid - 1]){ret = mid;break;}right = mid;continue;}else{left = mid;}}return ret;}
};

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

---