LeetCode 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：

输出：0

解释：

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

示例 2：

输出：2

解释：

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

示例 3：

输出：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\ne 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++

/** @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++ —— 原始版本（思考过程）可跳过

/** @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"
#endifclass Solution {
private:inline bool check(vector<vector<int>>& points, int i, int j) {  // 易错点3：单独的(i, j)也要checkif (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

'''
Author: LetMeFly
Date: 2025-09-02 13:08:07
LastEditors: LetMeFly.xyz
LastEditTime: 2025-09-02 18:47:49
'''
from typing import Listclass 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 = 0n = len(points)self.points = pointsfor i in range(n):for j in range(n):if i == j:continueif not self.check2(i, j):continuecan = Truefor k in range(n):if k == i or k == j:continueif not self.check3(i, j, k):can = Falsebreakans += canreturn ans

Go

/** @Author: LetMeFly* @Date: 2025-09-02 13:08:07* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-09-02 18:53:07*/
package mainfunc 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 := truefor k := range points {if k == i || k == j {continue}if !check3_3025(points, i, j, k) {can = falsebreak}}if can {ans++}}}return
}

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

千篇源码题解已开源