leetcode解题思路分析（一百零二）874

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

模拟行走机器人
机器人在一个无限大小的 XY 网格平面上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ：
-2 ：向左转 90 度
-1 ：向右转 90 度
1 <= x <= 9 ：向前移动 x 个单位长度
在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点 obstacles[i] = (xi, yi) 。
机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，但仍然可以继续尝试进行该路线的其余部分。返回从原点到机器人所有经过的路径点（坐标为整数）的最大欧式距离的平方。（即，如果距离为 5 ，则返回 25 ）

没什么好说的，按顺序走就完事了

class Solution {
public:int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {int dx[4] = {0, 1, 0, -1};int dy[4] = {1, 0, -1, 0};int x = 0, y = 0, di = 0;unordered_set<pair<int, int>, pair_hash> obstacleSet;for (vector<int> obstacle: obstacles)obstacleSet.insert(make_pair(obstacle[0], obstacle[1]));int ans = 0;for (int cmd: commands) {if (cmd == -2)di = (di + 3) % 4;else if (cmd == -1)di = (di + 1) % 4;else {for (int k = 0; k < cmd; ++k) {int nx = x + dx[di];int ny = y + dy[di];if (obstacleSet.find(make_pair(nx, ny)) == obstacleSet.end()) {x = nx;y = ny;ans = max(ans, x*x + y*y);}}}}return ans;}private:struct pair_hash{template <class T1, class T2>std::size_t operator () (std::pair<T1, T2> const &pair) const{std::size_t h1 = std::hash<T1>()(pair.first);std::size_t h2 = std::hash<T2>()(pair.second);return h1 ^ h2;}};
};

爱吃香蕉的珂珂
珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

二分法不断试探

class Solution {
public:int minEatingSpeed(vector<int>& piles, int H) {int lo = 1, hi = pow(10, 9);while (lo < hi) {int mi = lo + (hi - lo) / 2;if (!possible(piles, H, mi))lo = mi + 1;elsehi = mi;}return lo;}// Can Koko eat all bananas in H hours with eating speed K?bool possible(vector<int>& piles, int H, int K) {int time = 0;for (int p: piles)time += (p - 1) / K + 1;return time <= H;}
};

链表的中间结点
给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

快慢指针基础题

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* middleNode(ListNode* head) {ListNode *pSlow, *pFast;pSlow = head;pFast = head;while (pFast != NULL && pFast->next != NULL){pSlow = pSlow->next;pFast = pFast->next;if (pFast){pFast = pFast->next;}}return pSlow;}
};

石子游戏
Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有正整数颗石子，数目为 piles[i] 。游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。Alice 和 Bob 轮流进行，Alice 先开始。每回合，玩家从行的开始或结束处取走整堆石头。这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false

作为先手的Alice 可以在第一次取走石子时就决定取走哪一组的石子，并全程取走同一组的石子。既然如此，Alice 是否有必胜策略？
答案是肯定的。将石子分成两组之后，可以计算出每一组的石子数量，同时知道哪一组的石子数量更多。Alice 只要选择取走数量更多的一组石子即可。因此，Alice 总是可以赢得比赛。

class Solution {
public:bool stoneGame(vector<int>& piles) {return true;}
};

第 N 个神奇数字
如果正整数可以被 A 或 B 整除，那么它是神奇的。返回第 N 个神奇数字。由于答案可能非常大，返回它模 10^9 + 7 的结果。

先求出最大公倍数L，然后对于任意的x，小于等于x的神奇数字的个数必然是x/A + x/B - x/L，根据二分法查找即可

class Solution {
public:int nthMagicalNumber(int N, int A, int B) {int MOD = 1e9 + 7;int L = A / gcd(A, B) * B;long lo = 0;long hi = (long) 1e15;while (lo < hi) {long mi = lo + (hi - lo) / 2;// If there are not enough magic numbers below mi...if (mi / A + mi / B - mi / L < N)lo = mi + 1;elsehi = mi;}return (int) (lo % MOD);}int gcd(int x, int y) {if (x == 0) return y;return gcd(y % x, x);}
};

盈利计划
集团里有 n 名员工，他们可以完成各种各样的工作创造利润。第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。工作的任何至少产生 minProfit 利润的子集称为盈利计划。并且工作的成员总数最多为 n 。有多少种计划可以选择？因为答案很大，所以返回结果模 10^9 + 7 的值。

动态规划求解

class Solution {
public:int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));for (int i = 0; i <= n; i++) {dp[i][0] = 1;}int len = group.size(), MOD = (int)1e9 + 7;for (int i = 1; i <= len; i++) {int members = group[i - 1], earn = profit[i - 1];for (int j = n; j >= members; j--) {for (int k = minProfit; k >= 0; k--) {dp[j][k] = (dp[j][k] + dp[j - members][max(0, k - earn)]) % MOD;}}}return dp[n][minProfit];}
};

索引处的解码字符串
给定一个编码字符串 S。请你找出解码字符串并将其写入磁带。解码时，从编码字符串中每次读取一个字符，并采取以下步骤：
如果所读的字符是字母，则将该字母写在磁带上。
如果所读的字符是数字（例如 d），则整个当前磁带总共会被重复写 d-1 次。
现在，对于给定的编码字符串 S 和索引 K，查找并返回解码字符串中的第 K 个字母。

首先，找出解码字符串的长度。之后，我们将逆向工作，跟踪 size：解析符号 S[0], S[1], …, S[i] 后解码字符串的长度。如果我们看到一个数字 S [i]，则表示在解析 S [0]，S [1]，…，S [i-1] 之后解码字符串的大小将是 size / Integer(S[i])。否则，将是 size - 1。

class Solution {
public:string decodeAtIndex(string S, int K) {long size = 0;int N = S.size();// Find size = length of decoded stringfor (int i = 0; i < N; ++i) {if (isdigit(S[i]))size *= S[i] - '0';elsesize++;}for (int i = N-1; i >=0; --i) {K %= size;if (K == 0 && isalpha(S[i]))return (string) "" + S[i];if (isdigit(S[i]))size /= S[i] - '0';elsesize--;}return "";}
};