100222. Type of Triangle II
给你一个下标从 0 开始长度为 3 的整数数组 nums ，需要用它们来构造三角形。
- 如果一个三角形的所有边长度相等，那么这个三角形称为 equilateral 。
- 如果一个三角形恰好有两条边长度相等，那么这个三角形称为 isosceles 。
- 如果一个三角形三条边的长度互不相同，那么这个三角形称为 scalene 。
如果这个数组无法构成一个三角形，请你返回字符串 "none" ，否则返回一个字符串表示这个三角形的类型。
测试样例：
输入：nums = [3,3,3]
输出："equilateral"
解释：由于三条边长度相等，所以可以构成一个等边三角形，返回 "equilateral" 。
解答：首先注意，需要判断这个数组是否可以构成三角形。其次才是按照要求判断各种类型。
class Solution {
public String triangleType(int[] nums) {
if (!isCanFormTriangle(nums)) {
return "none";
}
if (isAllEqual(nums)) {
return "equilateral";
} else if (isTwoEqual(nums)) {
return "isosceles";
}
return "scalene";
}
private boolean isCanFormTriangle(int[] nums) {
for (int i = 0; i < nums.length; ++i) {
for (int j = i + 1; j < nums.length; ++j) {
for (int k = 0; k < nums.length; ++k) {
if (nums[i] + nums[j] <= nums[k]) {
return false;
}
}
}
}
return true;
}
private boolean isAllEqual(int[] nums) {
for (int i = 0; i < 3; ++i) {
if (nums[i] != nums[0]) {
return false;
}
}
return true;
}
private boolean isTwoEqual(int[] nums) {
for (int i = 0; i < nums.length; ++i) {
for (int j = i + 1; j < nums.length; ++j) {
if (nums[i] == nums[j]) {
return true;
}
}
}
return false;
}
}
100183. Maximum Good Subarray Sum
给你一个长度为 n 的数组 nums 和一个 正 整数 k 。
如果 nums 的一个子数组中，第一个元素和最后一个元素 差的绝对值恰好 为 k ，我们称这个子数组为 好 的。换句话说，如果子数组 nums[i..j] 满足 |nums[i] - nums[j]| == k ，那么它是一个好子数组。
请你返回 nums 中 好 子数组的 最大 和，如果没有好子数组，返回 0 。
测试样例：
输入：nums = [1,2,3,4,5,6], k = 1
输出：11
解释：好子数组中第一个元素和最后一个元素的差的绝对值必须为 1 。好子数组有 [1,2] ，[2,3] ，[3,4] ，[4,5] 和 [5,6] 。最大子数组和为 11 ，对应的子数组为 [5,6] 。
解答：这道题目应该是这次双周赛最无脑的题目了。只要按照要求记录每个数组出现时候的最小前缀和，然后遍历数组的过程中更新HashMap，并寻找最佳值。
class Solution {
public long maximumSubarraySum(int[] nums, int k) {
long sum = 0, res = Long.MIN_VALUE;
HashMap<Integer, Long> mem = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
long curSum = sum + nums[i];
if (mem.containsKey(nums[i] + k)) {
res = Math.max(res, curSum - mem.get(nums[i] + k));
}
if (mem.containsKey(nums[i] - k)) {
res = Math.max(res, curSum - mem.get(nums[i] - k));
}
if (!mem.containsKey(nums[i]) || mem.get(nums[i]) > sum) {
mem.put(nums[i], sum);
}
sum = curSum;
}
return res == Long.MIN_VALUE ? 0 : res;
}
}
100193. Find the Number of Ways to Place People II
给你一个 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) ，小羊肖恩的位置不是在围栏的右下角。
测试样例：
输入：points = [[6,2],[4,4],[2,6]]
输出：2
解释：总共有 2 种方案安排 liupengsay 和小羊肖恩的位置，使得 liupengsay 不会难过：
- liupengsay 站在 (4, 4) ，小羊肖恩站在 (6, 2) 。
- liupengsay 站在 (2, 6) ，小羊肖恩站在 (4, 4) 。
不能安排 liupengsay 站在 (2, 6) 且小羊肖恩站在 (6, 2) ，因为站在 (4, 4) 的人处于围栏内。
解答：这题其实没有7分的难度。如果两个点符合站位要求，那么就要寻找这个围成的区间内是否存在别的点。暴力一点，可以利用排序，保证x升序。接着不断记录加入的y值，依次作为依据判断是否存在额外的点在围城之内。
class Solution {
class SegmentTree {
int[] tree;
int n;
public SegmentTree(int len) {
n = len;
tree = new int[n * 2];
}
void update(int pos) {
pos += n;
tree[pos] += 1;
while (pos > 0) {
int left = pos;
int right = pos;
if (pos % 2 == 0) {
right = pos + 1;
} else {
left = pos - 1;
}
tree[pos / 2] = tree[left] + tree[right];
pos /= 2;
}
}
public int sumRange(int l, int r) {
l += n;
r += n;
int sum = 0;
while (l <= r) {
if ((l % 2) == 1) {
sum += tree[l];
l++;
}
if ((r % 2) == 0) {
sum += tree[r];
r--;
}
l /= 2;
r /= 2;
}
return sum;
}
}
public int numberOfPairs(int[][] points) {
Arrays.sort(points, (a, b) -> (a[0] != b[0] ? (a[0] - b[0]) : (b[1] - a[1])));
Map<Integer, Integer> ySort = sort(points);
int res = 0;
for (int i = 0; i < points.length; ++i) {
SegmentTree tree = new SegmentTree(ySort.size());
int p = ySort.get(points[i][1]);
tree.update(p);
for (int j = i + 1; j < points.length; ++j) {
int t = ySort.get(points[j][1]);
tree.update(t);
if (points[i][1] >= points[j][1] && tree.sumRange(t, p) == 2) {
++res;
}
}
}
return res;
}
private Map<Integer, Integer> sort(int[][] points) {
TreeSet<Integer> set = new TreeSet<>();
for (int[] p : points) {
set.add(p[1]);
}
int pos = 0;
HashMap<Integer, Integer> res = new HashMap<>();
for (int n : set) {
res.put(n, pos++);
}
return res;
}
}