一、100222. 三角形类型 II
1、原题链接
2、题目描述
3、思路分析
4、代码详解
二、100194. 人员站位的方案数 I
1、原题链接
2、题目描述
3、思路分析
4、代码详解
三、100183. 最大好子数组和
1、原题链接
2、题目描述
3、思路分析
4、代码详解
四、100193. 人员站位的方案数 II
1、原题链接
2、题目描述
3、思路分析
4、代码详解
一、100222. 三角形类型 II
1、原题链接
三角形类型 II - 力扣 (LeetCode) 竞赛
2、题目描述
给你一个下标从 0 开始长度为 3 的整数数组 nums ，需要用它们来构造三角形。
- 如果一个三角形的所有边长度相等，那么这个三角形称为 equilateral 。
- 如果一个三角形恰好有两条边长度相等，那么这个三角形称为 isosceles 。
- 如果一个三角形三条边的长度互不相同，那么这个三角形称为 scalene 。
如果这个数组无法构成一个三角形，请你返回字符串 "none" ，否则返回一个字符串表示这个三角形的类型。
3、思路分析
签到题，没什么说的
复制的时候多了个空格，喜提WA
时间复杂度：O(1) 空间复杂度：O(1)
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、原题链接
人员站位的方案数 I - 力扣 (LeetCode) 竞赛
2、题目描述
给你一个 n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [xi, yi] 。
我们定义 x 轴的正方向为 右 （x 轴递增的方向），x 轴的负方向为 左 （x 轴递减的方向）。类似的，我们定义 y 轴的正方向为 上 （y 轴递增的方向），y 轴的负方向为 下 （y 轴递减的方向）。
你需要安排这 n 个人的站位，这 n 个人中包括 liupengsay 和小羊肖恩 。你需要确保每个点处 恰好 有 一个 人。同时，liupengsay 想跟小羊肖恩单独玩耍，所以 liupengsay 会以 liupengsay 的坐标为 左上角 ，小羊肖恩的坐标为 右下角 建立一个矩形的围栏（注意，围栏可能 不 包含任何区域，也就是说围栏可能是一条线段）。如果围栏的 内部 或者 边缘 上有任何其他人，liupengsay 都会难过。
请你在确保 liupengsay 不会 难过的前提下，返回 liupengsay 和小羊肖恩可以选择的 点对 数目。
注意，liupengsay 建立的围栏必须确保 liupengsay 的位置是矩形的左上角，小羊肖恩的位置是矩形的右下角。比方说，以 (1, 1) ，(1, 3) ，(3, 1) 和 (3, 3) 为矩形的四个角，给定下图的两个输入，liupengsay 都不能建立围栏，原因如下：
- 图一中，liupengsay 在 (3, 3) 且小羊肖恩在 (1, 1) ，liupengsay 的位置不是左上角且小羊肖恩的位置不是右下角。
- 图二中，liupengsay 在 (1, 3) 且小羊肖恩在 (1, 1) ，小羊肖恩的位置不是在围栏的右下角。
3、思路分析
二维偏序问题
他这个坐标太烦人了，我把它转了一下
将坐标转换为以左上角为源点，x轴往下延伸，y轴往右延伸
这样有什么好处呢？我们按x坐标升序排序，x相同就按y升序排序
然后我们遍历坐标数组，每个元素右边的所有满足纵坐标大于自己的坐标都有机会配对，因为排序后x坐标已经满足了，只用看y坐标
那么对于那些可能的坐标如何进一步判断配对呢？只要二者围成的区域内没有别的点即可
这个时候我们坐标变换的好处就体现出来了，我们可以通过二维前缀和来判断区域内是否有别的点（不变换也能求前缀和，但是容易写错）
只要区域和为2（即只有配对的两个点），我们答案计数+1
时间复杂度：O(N^2) 空间复杂度：O(U^2)，U为坐标最大值
4、代码详解
class Solution { public: typedef vector vi; int g[55][55]; int numberOfPairs(vector &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]
