目录
1502. 判断能否形成等差数列
给你一个数字数组 arr 。
如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。
如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。
示例 1：
输入：arr = [3,5,1]
输出：true
解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。
示例 2：
输入：arr = [1,2,4]
输出：false
解释：无法通过重新排序得到等差数列。
提示：
2 <= arr.length <= 1000
-10^6 <= arr[i] <= 10^6
class Solution {
public:
bool canMakeArithmeticProgression(vector<int>& arr) {
sort(arr.begin(), arr.end());
int k = arr[1] - arr[0];
for(int i = 2; i < arr.size(); i++)if (arr[i] - arr[i - 1] - k)return false;
return true;
}
};1503. 所有蚂蚁掉下来前的最后一刻
1504. 统计全 1 子矩形
1506. 找到 N 叉树的根节点 待更新
待更新
1510. 石子游戏 IV
1512. 好数对的数目
给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
返回好数对的数目。
示例 1：
输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
示例 2：
输入：nums = [1,1,1,1]
输出：6
解释：数组中的每组数字都是好数对示例 3：
输入：nums = [1,2,3]
输出：0
提示：
1 <= nums.length <= 1001 <= nums[i] <= 100
class Solution {
public:
int numIdenticalPairs(vector<int>& nums) {
int ans=0;
for(int i=0;i<nums.size();i++)for(int j=i+1;j<nums.size();j++)ans+=(nums[i]==nums[j]);
return ans;
}
};1513. 仅含 1 的子串数
给你一个二进制字符串 s（仅由 '0' 和 '1' 组成的字符串）。
返回所有字符都为 1 的子字符串的数目。
由于答案可能很大，请你将它对 10^9 + 7 取模后返回。
示例 1：
输入：s = "0110111"
输出：9
解释：共有 9 个子字符串仅由 '1' 组成
"1" -> 5 次
"11" -> 3 次
"111" -> 1 次示例 2：
输入：s = "101"
输出：2
解释：子字符串 "1" 在 s 中共出现 2 次
示例 3：
输入：s = "111111"
输出：21
解释：每个子字符串都仅由 '1' 组成
示例 4：
输入：s = "000"
输出：0
提示：
s[i] == '0'或s[i] == '1'1 <= s.length <= 10^5
class Solution {
public:
int numSub(string s) {
int len=0,ans=0;
for(int i=0;i<s.length();i++)
{
if(s[i]-'0')len++;
else len=0;
ans+=len,ans%=1000000007;
}
return ans;
}
};1518. 换水问题
1522. N 叉树的直径
1535. 找出数组游戏的赢家
给你一个由 不同 整数组成的整数数组 arr 和一个整数 k 。
每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的胜利并保留在位置 0 ，较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的 赢家 。
返回赢得比赛的整数。
题目数据 保证 游戏存在赢家。
示例 1：
输入：arr = [2,1,3,5,4,6,7], k = 2 输出：5 解释：一起看一下本场游戏每回合的情况：
因此将进行 4 回合比赛，其中 5 是赢家，因为它连胜 2 回合。
示例 2：
输入：arr = [3,2,1], k = 10 输出：3 解释：3 将会在前 10 个回合中连续获胜。
示例 3：
输入：arr = [1,9,8,2,3,7,6,4,5], k = 7 输出：9
示例 4：
输入：arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000 输出：99
提示：
2 <= arr.length <= 10^51 <= arr[i] <= 10^6arr所含的整数 各不相同 。1 <= k <= 10^9
class Solution {
public:
int getWinner(vector<int>& arr, int k) {
int a=arr[0],b;
map<int,int>m;
for(int i=1;i<arr.size();i++){
b=arr[i];
if(a<b)a^=b^=a^=b;
if(++m[a]==k)return a;
}
return a;
}
};1542. 找出最长的超赞子字符串
1547. 切棍子的最小成本
有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：
给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。
你可以按顺序完成切割，也可以根据需要更改切割的顺序。
每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。
返回切棍子的 最小总成本 。
示例 1：
输入：n = 7, cuts = [1,3,4,5] 输出：16 解释：按 [1, 3, 4, 5] 的顺序切割的情况如下所示：
第一次切割长度为 7 的棍子，成本为 7 。第二次切割长度为 6 的棍子（即第一次切割得到的第二根棍子），第三次切割为长度 4 的棍子，最后切割长度为 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。 而将切割顺序重新排列为 [3, 5, 1, 4] 后，总成本 = 16（如示例图中 7 + 4 + 3 + 2 = 16）。
示例 2：
输入：n = 9, cuts = [5,6,1,4,2] 输出：22 解释：如果按给定的顺序切割，则总成本为 25 。总成本 <= 25 的切割顺序很多，例如，[4, 6, 5, 2, 1] 的总成本 = 22，是所有可能方案中成本最小的。
提示：
2 <= n <= 10^61 <= cuts.length <= min(n - 1, 100)1 <= cuts[i] <= n - 1cuts数组中的所有整数都 互不相同
int listt[105];
int sum[105][105];
int f(int start, int end)
{
if (sum[start][end] >= 0)return sum[start][end];
if (start == end)return 0;
if (start + 1 == end)return listt[start] + listt[end];
long long min = 10000000000, temp;
for (int i = start; i < end; i++)
{
temp = f(start, i) + f(i + 1, end);
if (min>temp)min = temp;
}
for (int i = start; i <= end; i++)min += listt[i];
sum[start][end] = min;
return min;
}
class Solution {
public:
int minCost(int n, vector<int>& cuts) {
sort(cuts.begin(),cuts.end());
listt[1] = cuts[0];
for (int i = 1; i < cuts.size(); i++) listt[i+1] = cuts[i]-cuts[i-1];
listt[cuts.size()+1] = n-cuts[cuts.size()-1];
memset(sum, -1, sizeof(sum));
return f(1, cuts.size()+1);
}
};1553. 吃掉 N 个橘子的最少天数
1554. 只有一个不同字符的字符串
1559. 二维网格图中探测环
1561. 你可以获得的最大硬币数目
1563. 石子游戏 V
1568. 使陆地分离的最少天数
1569. 将子数组重新排序得到同一个二叉搜索树的方案数
1572. 矩阵对角线元素的和
给你一个正方形矩阵 mat，请你返回矩阵对角线元素的和。
请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。
示例 1：
输入：mat = [[1,2,3], [4,5,6], [7,8,9]] 输出：25 解释：对角线的和为：1 + 5 + 9 + 3 + 7 = 25 请注意，元素 mat[1][1] = 5 只会被计算一次。
示例 2：
输入：mat = [[1,1,1,1], [1,1,1,1], [1,1,1,1], [1,1,1,1]] 输出：8
示例 3：
输入：mat = [[5]] 输出：5
提示：
n == mat.length == mat[i].length1 <= n <= 1001 <= mat[i][j] <= 100
class Solution {
public:
int diagonalSum(vector<vector<int>>& mat) {
int s = 0, size = mat.size();
for (int i = 0; i < size; i++)s += mat[i][i] + mat[i][mat.size() - 1 - i];
return s - (size & 1)* mat[size >> 1][size >> 1];
}
};
扫一扫
3291
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
