福建省建设监理公司网站,做网站的linux程序代码,谷歌优化seo,wordpress手机端如何前言 执手看歌敲金钗#xff0c;笑语落珠明眸睐。 忽然蝴蝶春风满#xff0c;焉教冷镜瘦朱颜。 整体评价
T3是基于map的前缀和的变形题#xff0c;T4是二维偏序的一道应用题。
题外话#xff0c;力扣还是实现N久之前的承诺了#xff0c;命名权奖励#xff0c;赞一个。 …前言 执手看歌敲金钗笑语落珠明眸睐。 忽然蝴蝶春风满焉教冷镜瘦朱颜。 整体评价
T3是基于map的前缀和的变形题T4是二维偏序的一道应用题。
题外话力扣还是实现N久之前的承诺了命名权奖励赞一个。 T1. 三角形类型 II
思路: 模拟
class Solution {public String triangleType(int[] nums) {// 先判合法性Arrays.sort(nums);if (nums[0] nums[1] nums[2]) return none;if (nums[0] nums[1] nums[1] nums[2]) {return equilateral;} else if (nums[0] nums[1] || nums[1] nums[2]) {return isosceles;} else {return scalene;}}
}T2. 人员站位的方案数 I
和T4一起讲 T3. 最大好子数组和
思路: 基于map的前缀和应用
这边需要以值作为key, value为最小的前缀和(需向前偏移一位)
更新的时候需要分类讨论v为当前值 v − k v - k v−k v k v k vk
class Solution {public long maximumSubarraySum(int[] nums, int k) {long inf Long.MIN_VALUE / 10;long res inf;// 维护最小的前缀和MapLong, Long minMap new HashMap();long acc 0;for (int i 0; i nums.length; i) {long v nums[i];acc v;if (minMap.containsKey(v - k)) {res Math.max(acc - minMap.get(v - k), res);}if (minMap.containsKey(v k)) {res Math.max(acc - minMap.get(v k), res);}// 更新if (!minMap.containsKey(v) || acc - v minMap.get(v)) {minMap.put(v, acc - v);}}return res inf ? 0 : res;}}T4. 人员站位的方案数 II
思路: 二维偏序 枚举
对于偏序题一般先固定一个维度
先按x坐标从小到大排序再按照y坐标从大到小排序
因为题目指定左上角右下角
然后枚举左右端点check是否满足需求即可。
在枚举的过程中可以引入 单调队列优化 单调队列优化 单调队列优化
实际上只要维护最接近左端点y坐标(严格小于等于)的单变量即可, 递增状态
这样整个时间复杂度可以降为
排序 O ( n l o g n ) O(nlogn) O(nlogn)枚举左右端点 O ( n 2 ) O(n^2) O(n2)
最终为 O ( n 2 ) O(n^2) O(n2)
class Solution {public int numberOfPairs(int[][] points) {// 按x从小到大按y从大到小Arrays.sort(points, Comparator.comparingInt((int[] p) - p[0]).thenComparingInt(p - -p[1]));int res 0;int n points.length;for (int i 0; i n; i) {// 维护最接近左端点y值的值(严格小于等于)int nearest Integer.MIN_VALUE;for (int j i 1; j n; j) {if (points[j][1] points[i][1]) {if (points[j][1] nearest) {res;nearest points[j][1];}}}}return res;}
}离散化二维前缀和 (补充)
这个解法应该更加的直观
class Solution {// 离散化MapInteger, Integer discrete(ListInteger ps) {TreeSetInteger range new TreeSet(ps);MapInteger, Integer ids new HashMap();int ptr 0;for (var k: range) {ids.put(k, ptr);}return ids;}public int numberOfPairs(int[][] points) {int n points.length;int res 0;MapInteger, Integer xs discrete(Arrays.stream(points).map(p - p[0]).collect(Collectors.toList()));MapInteger, Integer ys discrete(Arrays.stream(points).map(p - p[1]).collect(Collectors.toList()));int h ys.size(), w xs.size();int[][] area new int[h][w];for (int[] p: points) {area[ys.get(p[1])][xs.get(p[0])] 1;}int[][] pre new int[h 1][w 1];for (int i 0; i h; i) {for (int j 0; j w; j) {pre[i 1][j 1] pre[i 1][j] pre[i][j 1] - pre[i][j] area[i][j];}}for (int i 0; i n; i) {for (int j 0; j n; j) {if (i j) continue;if (points[i][0] points[j][0] points[i][1] points[j][1]) {int ty ys.get(points[i][1]), by ys.get(points[j][1]);int tx xs.get(points[j][0]), bx xs.get(points[i][0]);int s pre[ty 1][tx 1] - pre[ty 1][bx] - pre[by][tx 1] pre[by][bx];if (s 2) {res ;}}}}return res;}
} 写在最后
