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

2024-09-05 04:48
文章标签 leetcode 874 880 一百零二 解题 思路 分析

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

  1. 模拟行走机器人
    机器人在一个无限大小的 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;}};
};
  1. 爱吃香蕉的珂珂
    珂珂喜欢吃香蕉。这里有 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;}
};
  1. 链表的中间结点
    给定一个头结点为 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;}
};
  1. 石子游戏
    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;}
};
  1. 第 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);}
};
  1. 盈利计划
    集团里有 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];}
};
  1. 索引处的解码字符串
    给定一个编码字符串 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 "";}
};

这篇关于leetcode解题思路分析（一百零二）874 - 880 题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1137994。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

引言 随着时间的发展，大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用，随着人们期望的不断增加，目标也发生了巨大的变化。在短短的几个月的时间里，人们对大模型的认识已经从对其zero-shot能力感到惊讶，转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构（例如Transformer）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...
SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

查看原文>>>全流程SWAP农业模型数据制备、敏感性分析及气候变化影响实践技术应用 SWAP模型是由荷兰瓦赫宁根大学开发的先进农作物模型，它综合考虑了土壤-水分-大气以及植被间的相互作用；是一种描述作物生长过程的一种机理性作物生长模型。它不但运用Richard方程，使其能够精确的模拟土壤中水分的运动，而且耦合了WOFOST作物模型使作物的生长描述更为科学。 本文让更多的科研人员和农业工作者
阅读更多...
MOLE 2.5 分析分子通道和孔隙

MOLE 2.5 分析分子通道和孔隙

软件介绍 生物大分子通道和孔隙在生物学中发挥着重要作用，例如在分子识别和酶底物特异性方面。 我们介绍了一种名为 MOLE 2.5 的高级软件工具，该工具旨在分析分子通道和孔隙。 与其他可用软件工具的基准测试表明，MOLE 2.5 相比更快、更强大、功能更丰富。作为一项新功能，MOLE 2.5 可以估算已识别通道的物理化学性质。 软件下载 https://pan.quark.cn/s/57
阅读更多...
leetcode-24Swap Nodes in Pairs

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L
阅读更多...
leetcode-23Merge k Sorted Lists

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists
阅读更多...
衡石分析平台使用手册-单机安装及启动

衡石分析平台使用手册-单机安装及启动

单机安装及启动​ 本文讲述如何在单机环境下进行 HENGSHI SENSE 安装的操作过程。 在安装前请确认网络环境，如果是隔离环境，无法连接互联网时，请先按照 离线环境安装依赖的指导进行依赖包的安装，然后按照本文的指导继续操作。如果网络环境可以连接互联网，请直接按照本文的指导进行安装。 准备工作​ 请参考安装环境文档准备安装环境。 配置用户与安装目录。 在操作前请检查您是否有 sud
阅读更多...
线性因子模型 - 独立分量分析（ICA）篇

线性因子模型 - 独立分量分析（ICA）篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型，它们通过引入潜变量（ latent variables \text{latent variables} latent variables）来更好地表征数据。其中，独立分量分析（ ICA \text{ICA} ICA）作为线性因子模型的一种，以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2