la la la

原题链接 题目描述 给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。 请返回 nums 的动态和。 数据范围 1≤nums.length≤10001 \le nums.length \le 10001≤nums.length≤1000 −106≤nums[i]≤106-10^6 \le nums[i] \le 10^6−106≤nums[i]≤106 样例 输入样例1： nums = [1,2,3,4] 输出样例1： [1,3,6,10] 样例1解释： 动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。 输入样例2： nums = [1,1,1,1,1] 输出样例2： [1,2,3,4,5] 样例2解释： 动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。 输入样例3： nums = [3,1,2,10,1] 输出样例3： [3,4,6,16,17] 思路 前缀和。 代码 C++ class Solution
...

原题链接 题目描述 一家餐厅收到了 nnn 个客人的预约订单。 每个订单都有开始时间和结束时间。 对于每个订单，餐厅有权利接单，也有权利拒单。 接受的订单，两两之间不得有任何时间交集，甚至不得有时刻交集，即如果一个订单的开始时间和另一个订单的结束时间相同，则两订单也不得同时接受。 为了赚更多钱，餐厅需要尽可能多的接单。 请问，餐厅最多可以接多少单？ 输入格式 第一行包含一个整数 nnn。 接下来 nnn 行，每行包含两个整数 l,rl,rl,r，表示一个订单的开始时间和结束时间。 输出格式 输出可以接受的最大订单数量。 数据范围 1≤n≤5×1051≤n≤5×10^51≤n≤5×105, 1≤l≤r≤1091≤l≤r≤10^91≤l≤r≤109 样例 输入样例1： 2 7 11 4 7 输出样例1： 1 输入样例2： 5 1 2 2 3 3 4 4 5 5 6 输出样例2： 3 输入样例3： 6 4 8 1 5 4 7 2 5 1 3 6 8 输出样例3： 2 思路 贪心。 按照结束时间从小到大排序。 当前用餐的开始时间严格大于上一个用餐的结束时间时，答案 +1 ...

原题链接 题目描述 给定一个长度为 nAn_AnA​ 的非降序整数数组 AAA 和一个长度为 nBn_BnB​ 的非降序整数数组 BBB。 请问，能否从 AAA 中挑选 kkk 个数，从 BBB 中挑选 mmm 个数，使得在 AAA 中挑选出的任何数都严格小于在 BBB 中挑选出的任何数。 输入格式 第一行包含两个整数 nA,nBn_A,n_BnA​,nB​。 第二行包含两个整数 k,mk,mk,m。 第三行包含 nAn_AnA​ 个整数 a1,a2,…,anAa_1,a_2,…,a_{nA}a1​,a2​,…,anA​。 第四行包含 nBn_BnB​ 个整数 b1,b2,…,bnBb_1,b_2,…,b_{nB}b1​,b2​,…,bnB​。 输出格式 共一行，能则输出 YES，否则输出 NO。 数据范围 1≤nA,nB≤1051≤nA,nB≤10^51≤nA,nB≤105, 1≤k≤nA1≤k≤n_A1≤k≤nA​, 1≤m≤nB1≤m≤n_B1≤m≤nB​, −109≤ai,bi≤109-10^9≤a_i,b_i≤10^9−109≤ai​,bi​≤109。 保证 AAA ...

原题链接 题目描述 给定一个长度为 nnn 的正整数数组 a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​。 你需要选择其中一个元素，将其移动至数组中的任意位置（也可以留在原位置）。 我们的目标是，在移动元素操作完成以后，将数组分为前后两个非空部分，并使前一部分的各元素之和等于后一部分的各元素之和。 请问，该目标能否达成？ 输入格式 第一行包含整数 TTT，表示共有 TTT 组测试数据。 每组数据第一行包含整数 nnn。 第二行包含 nnn 个整数 a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​。 输出格式 每组数据输出一行结果，目标可以达成，则输出 YES，否则输出 NO。 数据范围 1≤T≤201≤T≤201≤T≤20, 1≤n≤1051≤n≤10^51≤n≤105, 1≤ai≤1091≤a_i≤10^91≤ai​≤109。 同一测试点内所有 nnn 的和不超过 10510^5105。 样例 输入样例： 3 3 1 3 2 5 1 2 3 4 5 5 2 2 3 4 5 输出样例： YES NO YES 思路 能否达 ...

原题链接 题目描述 一个正整数 xxx 被称为一个可爱数当且仅当不存在任何正整数 a>1a>1a>1 满足 a2a^2a2 是 xxx 的约数。 给定一个正整数 nnn，请计算并输出 nnn 的所有约数中，属于可爱数的最大约数。 输入格式 第一行包含整数 TTT，表示共有 TTT 组测试数据。 每组数据占一行，包含一个整数 nnn。 输出格式 每组数据输出一行结果。 数据范围 1≤T≤101≤T≤101≤T≤10, 1≤n≤10121≤n≤10^{12}1≤n≤1012 样例 输入样例： 2 10 12 输出样例： 10 6 思路 任意正整数 mmm 都可以分解质因数成 m=p1α1p2α2⋯pkαkm = p^{\alpha_1}_1p^{\alpha_2}_2 \cdots p^{\alpha_k}_km=p1α1​​p2α2​​⋯pkαk​​ 。 可爱数 aaa 同样的可以被分解质因数成 a=p1β1p2β2⋯pkβka = p^{\beta_1}_1p^{\beta_2}_2 \cdots p^{\beta_k}_ka=p1β1​​p2β2​​ ...

原题链接 题目描述 给定一个 n×nn×nn×n 的 010101 矩阵。 你可以选择若干列（也可以不选），并将这些列上的所有元素进行变换（111 变 000，000 变 111）。 你的目标是使得矩阵中有尽可能多的行满足：一行中的所有元素都为 111。 输出可以得到的满足条件的行的最大数量。 输入格式 第一行包含整数 nnn。 接下来 nnn 行，每行包含一个长度为 nnn 的 010101 字符串，表示整个矩阵。 输出格式 输出可以得到的满足条件的行的最大数量。 数据范围 1≤n≤1001≤n≤1001≤n≤100 样例 输入样例1： 4 0101 1000 1111 0101 输出样例1： 2 输入样例2： 3 111 111 111 输出样例2： 3 思路 可以发现，不同的字符串不可能在同样的操作下同时变为全 111 字符串。所以只要找出出现次数最多的字符串，将这个类串中的 000 改为 111 即可。 代码 C++ #include <iostream> #include <unordered_map> using names ...

原题链接 题目描述 你在进行一个简化版的吃豆人游戏。你从 [0,0][0, 0][0,0] 点开始出发，你的目的地是 target=[xtarget,ytarget]target = [x_{target}, y_{target}]target=[xtarget​,ytarget​] 。地图上有一些阻碍者，以数组 ghosts 给出，第 i 个阻碍者从 ghosts[i]=[xi,yi]ghosts[i] = [x_i, y_i]ghosts[i]=[xi​,yi​] 出发。所有输入均为 整数坐标 。 每一回合，你和阻碍者们可以同时向东，西，南，北四个方向移动，每次可以移动到距离原位置 111 个单位 的新位置。当然，也可以选择 不动 。所有动作 同时 发生。 如果你可以在任何阻碍者抓住你 之前 到达目的地（阻碍者可以采取任意行动方式），则被视为逃脱成功。如果你和阻碍者同时到达了一个位置（包括目的地）都不算是逃脱成功。 只有在你有可能成功逃脱时，输出 true ；否则，输出 false。 数据范围 1≤ghosts.length≤1001 \le ghosts.length \le ...

原题链接 题目描述 给你一个字符数组 charscharschars ，请使用下述算法压缩： 从一个空字符串 sss 开始。对于 charscharschars 中的每组 连续重复字符 ： 如果这一组长度为 111 ，则将字符追加到 sss 中。 否则，需要向 sss 追加字符，后跟这一组的长度。 压缩后得到的字符串 sss 不应该直接返回，需要转储到字符数组 charscharschars 中。需要注意的是，如果组长度为 101010 或 101010 以上，则在 charscharschars 数组中会被拆分为多个字符。 请在修改完输入数组后，返回该数组的新长度。 你必须设计并实现一个只使用常量额外空间的算法来解决此问题。 数据范围 1≤chars.length≤20001 \le chars.length \le 20001≤chars.length≤2000 chars[i] 可以是小写英文字母、大写英文字母、数字或符号 样例 输入样例1： chars = ["a","a","b","b& ...

原题链接 题目描述 一天可以被分为 nnn 个时段。 一个工人的每日工作安排可以用一个长度为 nnn 的 010101 序列 a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​ 来表示。 aia_iai​ 为 000 表示第 iii 个时间段是工作时间，aia_iai​ 为 111 表示第 iii 个时间段是休息时间。 工人日复一日的严格按照这个工作安排来进行工作和休息。 请问，工人的最长连续休息时间有多长（单位：时段）？ 注意，连续休息时间可能跨天。 保证工人至少在一个时间段处于工作状态。 输入格式 第一行包含整数 TTT，表示共有 TTT 组测试数据。 每组数据第一行包含整数 nnn。 第二行包含 nnn 个整数 a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​。 输出格式 每组数据输出一行结果，表示最长连续休息时间。 数据范围 1≤T≤101≤T≤101≤T≤10, 1≤n≤2×1051≤n≤2×10^51≤n≤2×105, 0≤ai≤10≤a_i≤10≤ai​≤1, 同一测试点内所有 nnn 的和不超过 2×1052×10^ ...

原题链接 题目描述 给定一个长度为 nnn 的正整数数组 a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​。 你可以任意改变其中任意元素的值。 但是，改变后的元素的值仍需是正整数。 将一个元素的值从 aaa 变为 bbb 所需要付出的代价为 ∣a−b∣|a-b|∣a−b∣。 对于一个正整数 ttt，如果 ∣ai−t∣≤1|a_i-t|≤1∣ai​−t∣≤1，则称第 ii 个元素能够与 ttt 匹配。 现在，请你指定一个正整数 ttt，并且用最小的代价修改整个数组，使得数组中所有元素都能够与 ttt 匹配。 指定的 ttt 不同，所需付出的最小代价也可能不同。 请你合理选择正整数 ttt，目标是让所需付出的最小代价尽可能小。 输入格式 第一行包含整数 TTT，表示共有 TTT 组测试数据。 每组数据第一行包含整数 nnn。 第二行包含 nnn 个整数 a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​。 输出格式 每组数据输出一行结果，首先输出你选择的正整数 ttt，然后输出使得数组中所有元素都能够与 ttt 匹配，所需付出的最小代价。 ...