力扣OJ（3x）LCP

目录

LCP 01. 猜数字

LCP 02. 分式化简

LCP 06. 拿硬币

LCP 07. 传递信息

LCP 11. 期望个数统计

LCP 14. 切分数组

LCP 17. 速算机器人

LCP 18. 早餐组合

LCP 23. 魔术排列

LCP 24. 数字游戏

LCP 26. 导航装置

LCP 30. 魔塔游戏

LCP 33. 蓄水

LCP 41. 黑白翻转棋

LCP 48. 无限棋局

LCP 50. 宝石补给

LCP 54. 夺回据点

LCP 62. 交通枢纽

---

LCP 01. 猜数字

小A 和 小B 在玩猜数字。小B 每次从 1, 2, 3 中随机选择一个，小A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏，请返回 小A 猜对了几次？

输入的guess数组为 小A 每次的猜测，answer数组为 小B 每次的选择。guess和answer的长度都等于3。

示例 1：

输入：guess = [1,2,3], answer = [1,2,3]
输出：3
解释：小A 每次都猜对了。
示例 2：

输入：guess = [2,2,3], answer = [3,2,1]
输出：1
解释：小A 只猜对了第二次。
 

限制：

guess 的长度 = 3
answer 的长度 = 3
guess 的元素取值为 {1, 2, 3} 之一。
answer 的元素取值为 {1, 2, 3} 之一。

class Solution:def game(self, guess: List[int], answer: List[int]) -> int:ans=0for i in range(len(guess)):if(guess[i]==answer[i]):ans+=1return ans

LCP 02. 分式化简

有一个同学在学习分式。他需要将一个连分数化成最简分数，你能帮助他吗？

连分数是形如上图的分式。在本题中，所有系数都是大于等于0的整数。

输入的cont代表连分数的系数（cont[0]代表上图的a0，以此类推）。返回一个长度为2的数组[n, m]，使得连分数的值等于n / m，且n, m最大公约数为1。

示例 1：

输入：cont = [3, 2, 0, 2]
输出：[13, 4]
解释：原连分数等价于3 + (1 / (2 + (1 / (0 + 1 / 2))))。注意[26, 8], [-13, -4]都不是正确答案。
示例 2：

输入：cont = [0, 0, 3]
输出：[3, 1]
解释：如果答案是整数，令分母为1即可。
 

限制：

cont[i] >= 0
1 <= cont的长度 <= 10
cont最后一个元素不等于0
答案的n, m的取值都能被32位int整型存下（即不超过2 ^ 31 - 1）。

class Solution:def fraction(self, cont: List[int]) -> List[int]:if len(cont) == 1:return [cont[0], 1]x = cont[0]cont.pop(0)a = self.fraction(cont)return [x * a[0] + a[1], a[0]]

LCP 06. 拿硬币

桌上有 n 堆力扣币，每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数。

示例 1：

输入：[4,2,1]

输出：4

解释：第一堆力扣币最少需要拿 2 次，第二堆最少需要拿 1 次，第三堆最少需要拿 1 次，总共 4 次即可拿完。

示例 2：

输入：[2,3,10]

输出：8

限制：

1 <= n <= 4
1 <= coins[i] <= 10

class Solution:def minCount(self, coins: List[int]) -> int:ans=0for i in range(len(coins)):ans+=(coins[i]+coins[i]%2)/2return int(ans)

LCP 07. 传递信息

小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：

1. 有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0
2. 每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。
3. 每轮信息必须需要传递给另一个人，且信息可重复经过同一个人

给定总玩家数 n，以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。

示例 1：

输入：n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3

输出：3

解释：信息从小 A 编号 0 处开始，经 3 轮传递，到达编号 4。共有 3 种方案，分别是 0->2->0->4， 0->2->1->4， 0->2->3->4。

示例 2：

输入：n = 3, relation = [[0,2],[2,1]], k = 2

输出：0

解释：信息不能从小 A 处经过 2 轮传递到编号 2

限制：

• 2 <= n <= 10
• 1 <= k <= 5
• 1 <= relation.length <= 90, 且 relation[i].length == 2
• 0 <= relation[i][0],relation[i][1] < n 且 relation[i][0] != relation[i][1]

class Solution {
public:int numWays(int n, vector<vector<int>>& r, int k) {vector<int>ans(n,0);map<int, vector<int>>m;for (auto ri : r)m[ri[0]].push_back(ri[1]);ans[0] = 1;while (k--) {vector<int>t(n,0);for (int i=0;i<n;i++){for (auto x : m[i])t[x] += ans[i];}ans = t;}return ans[n - 1];}
};

LCP 11. 期望个数统计

某互联网公司一年一度的春招开始了，一共有 n 名面试者入选。每名面试者都会提交一份简历，公司会根据提供的简历资料产生一个预估的能力值，数值越大代表越有可能通过面试。

小 A 和小 B 负责审核面试者，他们均有所有面试者的简历，并且将各自根据面试者能力值从大到小的顺序浏览。由于简历事先被打乱过，能力值相同的简历的出现顺序是从它们的全排列中等可能地取一个。现在给定 n 名面试者的能力值 scores，设 X 代表小 A 和小 B 的浏览顺序中出现在同一位置的简历数，求 X 的期望。

提示：离散的非负随机变量的期望计算公式为 。在本题中，由于 X 的取值为 0 到 n 之间，期望计算公式可以是 。

示例 1：

输入：scores = [1,2,3]

输出：3

解释：由于面试者能力值互不相同，小 A 和小 B 的浏览顺序一定是相同的。X的期望是 3 。

示例 2：

输入：scores = [1,1]

输出：1

解释：设两位面试者的编号为 0, 1。由于他们的能力值都是 1，小 A 和小 B 的浏览顺序都为从全排列 [[0,1],[1,0]] 中等可能地取一个。如果小 A 和小 B 的浏览顺序都是 [0,1] 或者 [1,0] ，那么出现在同一位置的简历数为 2 ，否则是 0 。所以 X 的期望是 (2+0+2+0) * 1/4 = 1

示例 3：

输入：scores = [1,1,2]

输出：2

限制：

1 <= scores.length <= 10^5
0 <= scores[i] <= 10^6

class Solution:def expectNumber(self, scores: List[int]) -> int:scores=sorted(scores)x=-1ans = 0for i in range(len(scores)):if scores[i] != x:ans+=1x=scores[i]return ans

LCP 14. 切分数组

螺旋归纳

LCP 17. 速算机器人

小扣在秋日市集发现了一款速算机器人。店家对机器人说出两个数字（记作 x 和 y），请小扣说出计算指令：

"A" 运算：使 x = 2 * x + y；
"B" 运算：使 y = 2 * y + x。
在本次游戏中，店家说出的数字为 x = 1 和 y = 0，小扣说出的计算指令记作仅由大写字母 A、B 组成的字符串 s，字符串中字符的顺序表示计算顺序，请返回最终 x 与 y 的和为多少。

示例 1：

输入：s = "AB"

输出：4

解释：
经过一次 A 运算后，x = 2, y = 0。
再经过一次 B 运算，x = 2, y = 2。
最终 x 与 y 之和为 4。

提示：

0 <= s.length <= 10
s 由 'A' 和 'B' 组成

class Solution:def calculate(self, s: str) -> int:x=1y=0for i in range(len(s)):if s[i]=='A':x+=x+yelse:y+=x+yreturn x+y

LCP 18. 早餐组合

小扣在秋日市集选择了一家早餐摊位，一维整型数组 staple 中记录了每种主食的价格，一维整型数组 drinks 中记录了每种饮料的价格。小扣的计划选择一份主食和一款饮料，且花费不超过 x 元。请返回小扣共有多少种购买方案。

注意：答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1

示例 1：

输入：staple = [10,20,5], drinks = [5,5,2], x = 15

输出：6

解释：小扣有 6 种购买方案，所选主食与所选饮料在数组中对应的下标分别是：
第 1 种方案：staple[0] + drinks[0] = 10 + 5 = 15；
第 2 种方案：staple[0] + drinks[1] = 10 + 5 = 15；
第 3 种方案：staple[0] + drinks[2] = 10 + 2 = 12；
第 4 种方案：staple[2] + drinks[0] = 5 + 5 = 10；
第 5 种方案：staple[2] + drinks[1] = 5 + 5 = 10；
第 6 种方案：staple[2] + drinks[2] = 5 + 2 = 7。

示例 2：

输入：staple = [2,1,1], drinks = [8,9,5,1], x = 9

输出：8

解释：小扣有 8 种购买方案，所选主食与所选饮料在数组中对应的下标分别是：
第 1 种方案：staple[0] + drinks[2] = 2 + 5 = 7；
第 2 种方案：staple[0] + drinks[3] = 2 + 1 = 3；
第 3 种方案：staple[1] + drinks[0] = 1 + 8 = 9；
第 4 种方案：staple[1] + drinks[2] = 1 + 5 = 6；
第 5 种方案：staple[1] + drinks[3] = 1 + 1 = 2；
第 6 种方案：staple[2] + drinks[0] = 1 + 8 = 9；
第 7 种方案：staple[2] + drinks[2] = 1 + 5 = 6；
第 8 种方案：staple[2] + drinks[3] = 1 + 1 = 2；

提示：

1 <= staple.length <= 10^5
1 <= drinks.length <= 10^5
1 <= staple[i],drinks[i] <= 10^5
1 <= x <= 2*10^5

class Solution:def breakfastNumber(self, s: List[int], d: List[int], x: int) -> int:s=sorted(s)d=sorted(d)j=len(d)-1ans=0for i in range(len(s)):while j>=0 and s[i]+d[j]>x:j-=1ans+=j+1return ans%1000000007

LCP 23. 魔术排列

rust

LCP 24. 数字游戏

优先队列

LCP 26. 导航装置

二叉树

LCP 30. 魔塔游戏

优先队列

LCP 33. 蓄水

给定 N 个无限容量且初始均空的水缸，每个水缸配有一个水桶用来打水，第 i 个水缸配备的水桶容量记作 bucket[i]。小扣有以下两种操作：

• 升级水桶：选择任意一个水桶，使其容量增加为 bucket[i]+1
• 蓄水：将全部水桶接满水，倒入各自对应的水缸

每个水缸对应最低蓄水量记作 vat[i]，返回小扣至少需要多少次操作可以完成所有水缸蓄水要求。

注意：实际蓄水量 达到或超过 最低蓄水量，即完成蓄水要求。

示例 1：

输入：bucket = [1,3], vat = [6,8]

输出：4

解释： 第 1 次操作升级 bucket[0]； 第 2 ~ 4 次操作均选择蓄水，即可完成蓄水要求。

示例 2：

输入：bucket = [9,0,1], vat = [0,2,2]

输出：3

解释： 第 1 次操作均选择升级 bucket[1] 第 2~3 次操作选择蓄水，即可完成蓄水要求。

提示：

• 1 <= bucket.length == vat.length <= 100
• 0 <= bucket[i], vat[i] <= 10^4

class Solution {
public:int storeWater(vector<int>& bucket, vector<int>& vat) {bool flag=true;for(int i=0;i<vat.size();i++){if(vat[i])flag=false;}if(flag)return 0;int ans=1234567;for(int i=1;i<10000;i++)ans=min(ans,i+storeWater(bucket,vat,i));return ans;}int storeWater(vector<int>& bucket, vector<int>& vat,int n) {int s=0;for(int i=0;i<vat.size();i++){s+=max((vat[i]+n-1)/n-bucket[i],0);}return s;}
};

LCP 41. 黑白翻转棋

在 n*m 大小的棋盘中，有黑白两种棋子，黑棋记作字母 "X", 白棋记作字母 "O"，空余位置记作 "."。当落下的棋子与其他相同颜色的棋子在行、列或对角线完全包围（中间不存在空白位置）另一种颜色的棋子，则可以翻转这些棋子的颜色。

「力扣挑战赛」黑白翻转棋项目中，将提供给选手一个未形成可翻转棋子的棋盘残局，其状态记作 chessboard。若下一步可放置一枚黑棋，请问选手最多能翻转多少枚白棋。

注意：

若翻转白棋成黑棋后，棋盘上仍存在可以翻转的白棋，将可以 继续 翻转白棋
输入数据保证初始棋盘状态无可以翻转的棋子且存在空余位置
示例 1：

输入：chessboard = ["....X.","....X.","XOOO..","......","......"]

输出：3

解释：
可以选择下在 [2,4] 处，能够翻转白方三枚棋子。

示例 2：

输入：chessboard = [".X.",".O.","XO."]

输出：2

解释：
可以选择下在 [2,2] 处，能够翻转白方两枚棋子。

示例 3：

输入：chessboard = [".......",".......",".......","X......",".O.....","..O....","....OOX"]

输出：4

解释：
可以选择下在 [6,3] 处，能够翻转白方四枚棋子。

提示：

1 <= chessboard.length, chessboard[i].length <= 8
chessboard[i] 仅包含 "."、"O" 和 "X"

class Solution {
public:int flipChess(vector<string> ch, int r, int c) {const vector<int> dx8{ 0,0,1,-1,1,1,-1,-1 };const vector<int> dy8{ 1,-1,0,0 ,1,-1,1,-1 };queue<int>q;q.push(r * 100 + c);int ans = 0;while (!q.empty()) {for (int i = 0; i < 8; i++) {r = q.front() / 100, c = q.front() % 100;int dr = dx8[i], dc = dy8[i];queue<int>q2;r += dr, c += dc;while (r >= 0 && r < ch.size() && c >= 0 && c < ch[0].length()) {if (ch[r][c] == 'X') {while (!q2.empty()) {q.push(q2.front());ch[q2.front() / 100][q2.front() % 100] = 'X';q2.pop();ans++;}break;}if (ch[r][c] == '.')break;q2.push(r * 100 + c);r += dr, c += dc;}}q.pop();}return ans;}int flipChess(vector<string>& chessboard) {int ans = 0;for (int i = 0; i < chessboard.size(); i++) {for (int j = 0; j < chessboard[0].size(); j++) {if (chessboard[i][j] == '.')ans = max(ans, flipChess(chessboard, i, j));}}return ans;}
};

LCP 48. 无限棋局

五子棋

LCP 50. 宝石补给

欢迎各位勇者来到力扣新手村，在开始试炼之前，请各位勇者先进行「宝石补给」。

每位勇者初始都拥有一些能量宝石， gem[i] 表示第 i 位勇者的宝石数量。现在这些勇者们进行了一系列的赠送，operations[j] = [x, y] 表示在第 j 次的赠送中 第 x 位勇者将自己一半的宝石（需向下取整）赠送给第 y 位勇者。

在完成所有的赠送后，请找到拥有最多宝石的勇者和拥有最少宝石的勇者，并返回他们二者的宝石数量之差。

注意：

• 赠送将按顺序逐步进行。

示例 1：

输入：gem = [3,1,2], operations = [[0,2],[2,1],[2,0]]

输出：2

解释： 第 1 次操作，勇者 0 将一半的宝石赠送给勇者 2， gem = [2,1,3] 第 2 次操作，勇者 2 将一半的宝石赠送给勇者 1， gem = [2,2,2] 第 3 次操作，勇者 2 将一半的宝石赠送给勇者 0， gem = [3,2,1] 返回 3 - 1 = 2

示例 2：

输入：gem = [100,0,50,100], operations = [[0,2],[0,1],[3,0],[3,0]]

输出：75

解释： 第 1 次操作，勇者 0 将一半的宝石赠送给勇者 2， gem = [50,0,100,100] 第 2 次操作，勇者 0 将一半的宝石赠送给勇者 1， gem = [25,25,100,100] 第 3 次操作，勇者 3 将一半的宝石赠送给勇者 0， gem = [75,25,100,50] 第 4 次操作，勇者 3 将一半的宝石赠送给勇者 0， gem = [100,25,100,25] 返回 100 - 25 = 75

示例 3：

输入：gem = [0,0,0,0], operations = [[1,2],[3,1],[1,2]]

输出：0

提示：

• 2 <= gem.length <= 10^3
• 0 <= gem[i] <= 10^3
• 0 <= operations.length <= 10^4
• operations[i].length == 2
• 0 <= operations[i][0], operations[i][1] < gem.length

class Solution {
public:int giveGem(vector<int>& gem, vector<vector<int>>& operations) {for (auto p : operations) {int x = gem[p[0]] / 2;gem[p[0]] -= x, gem[p[1]] += x;}int a = gem[0], b = gem[0];for (auto x : gem)a = min(a, x), b = max(b, x);return b - a;}
};

LCP 54. 夺回据点

图的连通分量

LCP 62. 交通枢纽

rust 图论

力扣会员题
前3070题（目前所有）已分类，非纯数字题没有会员题

C++

尝试过：

3018

没做：

在本地

SQL

尝试过：512 534 1194 1308 1322 1336 1364 1369 1384 1412

没做：

569 571 574 578 579 580 597 603 612 613 614 615 618

1069 1076 1077 1082 1083 1097 1098 1107 1112 1113 1126 1127 1132 1142 1149 1159 1173  1205 1212 1225 1241 1264 1270 

1421 1435 1440 1445 1454 1459 1468 1479 1495

1501 1511 1532 1543 1549 1555 1565 1571 1596 1607 1613 1623 1635 1645 1651 1677  1699

1709 1715 1747 1767 1777 1783

1809  1811 1821 1831 1841 1843 1853 1867 1875 1892

1917 1919 1939 1949 1951 1972 1988 1990

2004 2010 2020 2026 2041 2051 2066 2072  2082 2084

2112 2118 2142 2153 2159 2173 2175 2199

2205  2228 2230 2238 2252 2253 2292 2298 2308 2314 2324 2329 2339 2346 2362 2372 2377 2388  2394 2474 2480 2494 2504 2668 2669 2686 2687 2688 2701 

2720 2738 2752 2783 2793 2820 2837 2853 2854 2893

2922 2978 2984 2985 2986   2987  2988  2989 2990 2991 2993 2994 2995

3050 3051 3052 3053 3054 3055 3056 3057 3058 3059 3060  3061

JS

没做：

2628 2632 2633 2636 2675 2676 2690 2691 2692

2700 2754 2755 2756 2757 2758 2759 2774 2775 2776 2777 2794 2795 2796 2797

2803 2804 2805 2821 2822 2823

非会员题

尝试过

1157 1505 2276  面试16.13

待提交