我要评论目录
一、100222. 三角形类型 ii
1、原题链接
2、题目描述
3、思路分析
签到题，没什么说的
复制的时候多了个空格，喜提wa
4、代码详解
class solution:
def triangletype(self, nums: list[int]) -> str:
a, b, c = nums[0], nums[1], nums[2]
if a + b > c and a + c > b and b + c > a:
if a == b == c:
return "equilateral"
if a == b or a == c or b == c:
return "isosceles"
return "scalene"
else:
return "none"二、100194. 人员站位的方案数 i
1、原题链接
2、题目描述
3、思路分析
二维偏序问题
他这个坐标太烦人了，我把它转了一下
将坐标转换为以左上角为源点，x轴往下延伸，y轴往右延伸
这样有什么好处呢？我们按x坐标升序排序，x相同就按y升序排序
然后我们遍历坐标数组，每个元素右边的所有满足纵坐标大于自己的坐标都有机会配对，因为排序后x坐标已经满足了，只用看y坐标
那么对于那些可能的坐标如何进一步判断配对呢？只要二者围成的区域内没有别的点即可
这个时候我们坐标变换的好处就体现出来了，我们可以通过二维前缀和来判断区域内是否有别的点（不变换也能求前缀和，但是容易写错）
只要区域和为2（即只有配对的两个点），我们答案计数+1
4、代码详解
class solution
{
public:
typedef vector<int> vi;
int g[55][55];
int numberofpairs(vector<vector<int>> &p)
{
memset(g, 0, sizeof(g));
int ret = 0, n = p.size();
for (auto &x : p){
int a = x[0] + 1, b = x[1] + 1;
g[x[0] = 52 - b][x[1] = a] = 1;
}
sort(p.begin(), p.end(), [&](vi &x, vi &y)
{
if(x[0] != y[0])
return x[0] < y[0];
return x[1] < y[1]; });
for (int i = 1; i <= 51; i++)
for (int j = 1; j <= 51; j++)
g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
for (int i = 0; i < n; i++)
{
int a = p[i][0], b = p[i][1];
for (int j = i + 1; j < n; j++)
{
int x = p[j][0], y = p[j][1];
if (y >= b && g[x][y] - g[x][b - 1] - g[a - 1][y] + g[a - 1][b - 1] == 2)
ret++;
}
}
return ret;
}
};三、100183. 最大好子数组和
1、原题链接
2、题目描述
3、思路分析
一眼哈希，我们预处理前缀和pre[]，开一个哈希表记录每个数字上一次最小前缀出现位置
我们遍历数组，对于nums[i]，如果前面出现过nums[i] - k 或者nums[i] + k，那么我们就维护好子数组和最大值
然后就要维护nums[i]在哈希表中存储的下标了
如果哈希表中没有nums[i]，直接插入
如果已经存在hash[nums[i]] = j，如果pre[i] < pre[j]，我们就将j替换为i
4、代码详解
class solution
{
public:
long long maximumsubarraysum(vector<int> &nums, int k)
{
int n = nums.size();
unordered_map<int, int> mp;
vector<long long> pre(n + 1);
for (int i = 1; i <= n; i++)
pre[i] = pre[i - 1] + nums[i - 1];
long long ret = -1e15;
for (int i = 0; i < n; i++)
{
if (mp.count(nums[i] - k))
{
ret = max(ret, pre[i + 1] - pre[mp[nums[i] - k]]);
}
if (mp.count(k + nums[i]))
{
ret = max(ret, pre[i + 1] - pre[mp[k + nums[i]]]);
}
if (!mp.count(nums[i]))
mp[nums[i]] = i;
else if(pre[i] < pre[mp[nums[i]]]) mp[nums[i]] = i;
}
return ret == -1e15 ? 0 : ret;
}
};四、100193. 人员站位的方案数 ii
1、原题链接
人员站位的方案数 ii - 力扣 (leetcode) 竞赛
2、题目描述
3、思路分析
第二题我们的做法是o(n^2)的时间复杂度，本题1e3的数据量照样能过
但是由于这次坐标范围太大了，所以我们要对坐标进行离散化，其它操作一样
4、代码详解
class solution
{
public:
typedef vector<int> vi;
int g[1010][1010], ax[1010], ay[1010], nx, ny;
int numberofpairs(vector<vector<int>> &p)
{
memset(g, 0, sizeof(g));
int ret = 0, n = p.size();
for (int i = 0; i < n; i++)
ax[i] = p[i][0], ay[i] = p[i][1];
sort(ax, ax + n), sort(ay, ay + n);
nx = unique(ax, ax + n) - ax, ny = unique(ay, ay + n) - ay;
for (auto &x : p)
{
int a = lower_bound(ax, ax + nx, x[0]) - ax + 1, b = lower_bound(ay, ay + ny, x[1]) - ay + 1;
g[x[0] = 1005 - b][x[1] = a] = 1;
}
sort(p.begin(), p.end(), [&](vi &x, vi &y)
{
if(x[0] != y[0])
return x[0] < y[0];
return x[1] < y[1]; });
for (int i = 1; i <= 1005; i++)
for (int j = 1; j <= 1005; j++)
g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
for (int i = 0; i < n; i++)
{
int a = p[i][0], b = p[i][1];
for (int j = i + 1; j < n; j++)
{
int x = p[j][0], y = p[j][1];
if (y >= b && g[x][y] - g[x][b - 1] - g[a - 1][y] + g[a - 1][b - 1] == 2)
ret++;
}
}
return ret;
}
};
发表评论