3025.人员站位的方案数 I：既然是I，那就先暴力吧（三层循环）

【LetMeFly】3025.人员站位的方案数 I：既然是I，那就先暴力吧（三层循环）

力扣题目链接：https://leetcode.cn/problems/find-the-number-of-ways-to-place-people-i/

给你一个  n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [xi, yi] 。

 

计算点对 (A, B) 的数量，其中

  • A 在 B 的左上角，并且
  • 它们形成的长方形中（或直线上）没有其它点（包括边界）。

返回数量。

 

示例 1：

输入：points = [[1,1],[2,2],[3,3]]

输出：0

解释：

没有办法选择 A 和 B，使得 A 在 B 的左上角。

示例 2：

输入：points = [[6,2],[4,4],[2,6]]

输出：2

解释：

  • 左边的是点对 (points[1], points[0])，其中 points[1] 在 points[0] 的左上角，并且形成的长方形内部是空的。
  • 中间的是点对 (points[2], points[1])，和左边的一样是合法的点对。
  • 右边的是点对 (points[2], points[0])，其中 points[2] 在 points[0] 的左上角，但 points[1] 在长方形内部，所以不是一个合法的点对。

示例 3：

输入：points = [[3,1],[1,3],[1,1]]

输出：2

解释：

  • 左边的是点对 (points[2], points[0])，其中 points[2] 在 points[0] 的左上角并且在它们形成的直线上没有其它点。注意两个点形成一条线的情况是合法的。
  • 中间的是点对 (points[1], points[2])，和左边一样也是合法的点对。
  • 右边的是点对 (points[1], points[0])，它不是合法的点对，因为 points[2] 在长方形的边上。

 

提示：

  • 2 <= n <= 50
  • points[i].length == 2
  • 0 <= points[i][0], points[i][1] <= 50
  • points[i] 点对两两不同。

解题方法：三层循环模拟

第一层循环使用$i$和$j$分别枚举每个点，如果$i\neq j$并且$points[i]$在$points[j]$的左上方，则继续：

第三层循环使用$k$再次枚举每个点，枚举之前使用一个变量$can=true$。如果$points[k]$在$points[i]$和$points[j]$的中间，则令$can=false$并退出第三层循环。

如果第三层循环没有将$can$设置为$false$，则答案数量加一。

  • 时间复杂度$O(len(points)^3)$
  • 空间复杂度$O(1)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
 * @Author: LetMeFly
 * @Date: 2025-09-02 13:08:07
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-09-02 13:51:14
 * @Description: rewrite from 0
 */
class Solution {
private:
    inline bool check(vector<vector<int>>& points, int i, int j) {
        return i != j && points[i][0] <= points[j][0] && points[i][1] >= points[j][1];
    }

    inline bool check(vector<vector<int>>& points, int i, int j, int k) {
        return !(points[i][0] <= points[k][0] && points[k][0] <= points[j][0]
              && points[i][1] >= points[k][1] && points[k][1] >= points[j][1]);
    }
public:
    int numberOfPairs(vector<vector<int>>& points) {
        int ans = 0;
        for (int i = 0; i < points.size(); i++) {
            for (int j = 0; j < points.size(); j++) {
                if (!check(points, i, j)) {
                    continue;
                }
                bool can = true;
                for (int k = 0; k < points.size(); k++) {
                    if (k == i || k == j) {
                        continue;
                    }
                    if (!check(points, i, j, k)) {
                        can = false;
                        break;
                    }
                }
                ans += can;
            }
        }
        return ans;
    }
};

C++ —— 原始版本（思考过程）可跳过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/*
 * @Author: LetMeFly
 * @Date: 2025-09-02 13:08:07
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-09-02 13:45:45
 */
#if defined(_WIN32) || defined(__APPLE__)
#include "_[1,2]toVector.h"
#endif

class Solution {
private:
    inline bool check(vector<vector<int>>& points, int i, int j) {  // 易错点3：单独的(i, j)也要check
        if (points[i][0] > points[j][0] || points[i][1] < points[j][1]) {  // 易错点1：注意这里纵坐标大于等于才合法
            return false;
        }
        return true;
    }
    inline bool check(vector<vector<int>>& points, int i, int j, int k) {
        if (points[i][0] <= points[k][0] && points[k][0] <= points[j][0] && points[i][1] >= points[k][1] && points[k][1] >= points[j][1]) {
            return false;
        }
        return true;
    }
public:
    int numberOfPairs(vector<vector<int>>& points) {
        int ans = 0;
        for (int i = 0; i < points.size(); i++) {
            for (int j = 0; j < points.size(); j++) {
                if (i == j) {
                    continue;
                }
                if (!check(points, i, j)) {
                    continue;
                }
                bool can = true;  // 易错点2：有一个k导致不符就不符
                for (int k = 0; k < points.size(); k++) {
                    if (k == i || k == j) {
                        continue;
                    }
                    if (!check(points, i, j, k)) {
                        can = false;
                        break;
                    }
                }
                ans += can;
            }
        }
        return ans;
    }
};

#if defined(_WIN32) || defined(__APPLE__)
/*
[[1,1],[2,2],[3,3]]

0
*/
/*
[[0,0],[0,3]]

1
*/
/*
[[6,2],[4,4],[2,6]]

(2,1) (1, 0)

2
*/
/*
[[0,0],[0,3]]

1
*/
int main() {
    string s;
    while (cin >> s) {
        vector<vector<int>> v = stringToVectorVector(s);
        Solution sol;
        cout << sol.numberOfPairs(v) << endl;
    }
    return 0;
}
#endif

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
'''
Author: LetMeFly
Date: 2025-09-02 13:08:07
LastEditors: LetMeFly.xyz
LastEditTime: 2025-09-02 18:47:49
'''
from typing import List

class Solution:
    def check2(self, i: int, j: int) -> bool:
        return self.points[i][0] <= self.points[j][0] and self.points[i][1] >= self.points[j][1]
    
    def check3(self, i: int, j: int, k: int) -> bool:
        return not (self.points[i][0] <= self.points[k][0] <= self.points[j][0] and self.points[i][1] >= self.points[k][1] >= self.points[j][1])
    
    def numberOfPairs(self, points: List[List[int]]) -> int:
        ans = 0
        n = len(points)
        self.points = points
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                if not self.check2(i, j):
                    continue
                can = True
                for k in range(n):
                    if k == i or k == j:
                        continue
                    if not self.check3(i, j, k):
                        can = False
                        break
                ans += can
        return ans

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
 * @Author: LetMeFly
 * @Date: 2025-09-02 13:08:07
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-09-02 18:53:07
 */
package main

func check2_3025(points [][]int, i, j int) bool {
    return points[i][0] <= points[j][0] && points[i][1] >= points[j][1]
}

func check3_3025(points [][]int, i, j, k int) bool {
    return !(points[i][0] <= points[k][0] && points[k][0] <= points[j][0] &&
             points[i][1] >= points[k][1] && points[k][1] >= points[j][1])
}

func numberOfPairs(points [][]int) (ans int) {
    for i := range points {
        for j := range points {
            if i == j {
                continue
            }
            if !check2_3025(points, i, j) {
                continue
            }
            can := true
            for k := range points {
                if k == i || k == j {
                    continue
                }
                if !check3_3025(points, i, j, k) {
                    can = false
                    break
                }
            }
            if can {
                ans++
            }
        }
    }
    return
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源

题解 > LeetCode
#题解 #中等 #数学 #数组 #排序 #LeetCode #几何 #枚举
3025.人员站位的方案数 I：既然是I，那就先暴力吧（三层循环）
https://blog.letmefly.xyz/2025/09/02/LeetCode 3025.人员站位的方案数I/
作者
发布于
2025年9月2日
许可协议