LeetCode第 123 场双周赛个人题解

给你一个下标从 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<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、原题链接

最大好子数组和 – 力扣 (LeetCode) 竞赛

2、题目描述

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

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

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

3、思路分析

一眼哈希，我们预处理前缀和pre[]，开一个哈希表记录每个数字上一次最小前缀出现位置

我们遍历数组，对于nums[i]，如果前面出现过nums[i] – k 或者nums[i] + k，那么我们就维护好子数组和最大值

然后就要维护nums[i]在哈希表中存储的下标了

如果哈希表中没有nums[i]，直接插入

如果已经存在hash[nums[i]] = j，如果pre[i] < pre[j]，我们就将j替换为i

时间复杂度：O(N) 空间复杂度：O(N)

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、题目描述

给你一个 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、思路分析

第二题我们的做法是O(N^2)的时间复杂度，本题1e3的数据量照样能过

但是由于这次坐标范围太大了，所以我们要对坐标进行离散化，其它操作一样

时间复杂度：O(N^2) 空间复杂度：O(U^2)，U为坐标最大值

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;
    }
};