算法提升——LeetCode123场双周赛总结

周赛题目

三角形类型 II

给你一个下标从0开始长度为3的整数数组nums，需要用它们来构造三角形。

如果一个三角形的所有边长度相等，那么这个三角形称为equilateral。

如果一个三角形恰好有两条边长度相等，那么这个三角形称为isosceles。

如果一个三角形三条边的长度互不相同，那么这个三角形称为scalene。

如果这个数组无法构成一个三角形，请你返回字符串"none"，否则返回一个字符串表示这个三角形的类型。

解题思路

本题是一道简单题，只要是连接构成三角形的要素是任意两边之和大于第三边即可。

class Solution {
    public String triangleType(int[] nums) {
        int a=nums[0];
        int b=nums[1];
        int c=nums[2];
        if (a+b<=c||a+c<=b||b+c<=a){
            return "none";
        }
        if (a==b&&b==c){
            return "equilateral";
        }
        if (a==b||b==c||a==c){
            return "isosceles";
        }
        return "scalene";
    }
}

人员站位的方案数 I

给你一个nx2的二维数组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[i]和points[j]时（i<j)，就只需要关心纵坐标的大小。

固定points[i[，然后枚举points[j]，如果points[j][1]比之前枚举的纵坐标都打，那么矩形中没有其他的点，答案加一。否则不满足。

class Solution {
    public int numberOfPairs(int[][] points) {
        Arrays.sort(points, (p, q) -> p[0] != q[0] ? p[0] - q[0] : q[1] - p[1]);
        int ans = 0;
        for (int i = 0; i < points.length; i++) {
            int y0 = points[i][1];
            int maxY = Integer.MIN_VALUE;
            for (int j = i + 1; j < points.length; j++) {
                int y = points[j][1];
                if (y <= y0 && y > maxY) {
                    maxY = y;
                    ans++;
                }
            }
        }
        return ans;
    }

}

最大好子数组和

给你一个长度为n的数组nums和一个正整数k。

如果nums的一个子数组中，第一个元素和最后一个元素差的绝对值恰好为k，我们称这个子数组为好的。换句话说，如果子数组nums[i…j]满足|nums[i]-nums[j]|==k，那么它是一个好子数组。

请你返回nums中好子数组的最大和，如果没有好子数组，返回0。

解题思路

利用前缀和来解决本题。子数组nums[i…j]的元素和为sum[j+1]-sum[i]

枚举j，找到最小的s[i]，满足nums[i]-nums[j]==k。

class Solution {
    public static long maximumSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long[] pre = new long[n + 1];
        for (int i = 0; i < n; i++) {
            pre[i + 1] = pre[i] + nums[i];
        }
       
        long ans = Long.MIN_VALUE;
        
        Map<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            int last1 = k + x;
            int last2 = x - k;
            if (index.containsKey(last1)) {
                int idx = index.get(last1);
                ans = Math.max(ans, pre[i+1] - pre[idx]);
            }
            if (index.containsKey(last2)) {
                int idx = index.get(last2);
                ans = Math.max(ans, pre[i+1] - pre[idx]);
            }
            if (index.containsKey(x)) {
                int idx = index.get(x);
                long seg = pre[i] - pre[idx];
                if (seg <= 0) {
                    index.put(x, i);
                }
            } else {
                index.put(x, i); 
            }


        }
        return ans == Long.MIN_VALUE ? 0 : ans;
    }
}