前言说实话，陌陌这次的笔试真的真的让人感觉到了原来我真的会点东西啊，废话不多说，直接上题目。
对了，前提需要说一下，代码为核心代码模式，且需要将结果设为result，最终函数返回1，后续会人工判卷（有一说一我自己是觉得人工判卷相对来说会比系统自动要好一些，最起码有主观看法）。
寻找支配点P为给定的二维平面整数点集。定义P中某点x，如果x满足P中任意点都不在x的右上方区域内（横纵坐标都大于x），则称其为一个支配点。
如下图所示，蓝色点位该点集中的支配点集合
寻找支配点
请实现代码，找到给定的人以及和P中的所有支配点并输出。（所有点的横纵坐标不重复）
输入：二维数组，表示点集P
输出：二维数组，n个支配点的点集Q
示例：
输入 P=[[1, 2], [5, 3], [4, 6], [7, 5], [9, 0]]
输出 [[4, 6], [7, 5], [9, 0]]
代码1234567891011from typing import Listclass Solution: def main(self , P: List[List[int]]) -> int: P.sort(key = lambda p: (-p[0], p[1])) result = [] max_y = 1 for x, y in P: if y > max_y: result.append([x, y]) self.result = result return 1
非极大值抑制非极大值抑制（Non-Maximum Suppression，NMS）是一种用于目标检测的算法，旨在从多个重叠的候选框中选择出最优的框。其基本思想是抑制那些不是局部最大值的元素，从而减少冗余的检测结果。
NMS的工作原理
局部最大搜索：NMS算法通过对候选框的得分进行排序，选择得分最高的框作为参考框。
计算重叠度：对于其他候选框，计算它们与当前参考框的重叠度（交并比，IoU）。如果某个候选框的IoU大于设定的阈值（通常在0.3到0.5之间），则认为它与参考框指向同一目标，因而将其剔除。
重复过程：从剩余的候选框中再次选择得分最高的框，重复上述步骤，直到没有候选框可以被剔除为止。
NMS在计算机视觉领域的应用非常广泛，包括视频目标跟踪、数据挖掘、3D重建和目标识别等
(以上资料来源于网络)
输入：
boxes为二维数组，其中每个元素是一维数组[x1, y1, x2, y2]，分别表示框的左上角和右下角坐标。scores是一个一维数组，每个元素表示每个框的置信度。两个的元素个数是相互对应的，iou_threshold表示用于移除重叠框的交并比阈值。
输出：
一个一维数组，表示所有留下框在原始列表中的下表，按照从小到大排序。
提示：
框面积计算公式为（y2 - y1) * (x2 - x1)
交并比的计算公式为：两框的交集面积除以并集面积
示例：
输入：
boxes = [[x11, y11, x21, y21], [x12, y12, x22, y22], [x13, y13, x23, y23]], scores = [0.75, 0.7, 0.8], iou_threshold = 0.7
输出：
[0, 2]
1234567891011121314151617181920212223242526272829class Solution: def main(self, boxes: List[List[int]], sorces: List[float], iou_threshold: float) -> int: def calculate_iou(box1, box2): x1 = max(box1[0], box2[0]) y1 = max(box1[1], box2[1]) x2 = min(box1[2], box2[2]) y2 = min(box1[3], box2[3]) intersection = max(0, x2 - x1) * max(0, y2 - y1) area1 = (box1[2] - box1[0]) * (box1[3] - box1[1]) area2 = (box2[2] - box2[0]) * (box2[3] - box2[1]) union = area1 + area2 - intersection return intersection / union if union > 0 else 0 n = len(boxes) indices = list(range(n)) indices.sort(key = lambda i: sorces[i], reverse = True) result = [] while indices: idx = indices[0] result.append(idx) indices = indices[1:] indices = [i for i in indices if calculate_iou(boxes[idx], boxes[0]) <= iou_threshold] result.sort() result = result return 1
序列置换给一个长度为N（N<1000）的正整数序列（1~N），我们称之为A。将上述序列随机重新排列后的序列称之为B序列。使用B序列作为一个置换，来对A序列进行操作。置换是指将A序列中的第B[i]个元素，挪到第i个位置。请实现一个函数，输入将A序列置换K次之后的序列。注意K可能会非常大($K < 10^8$)
输入：A序列、B序列以及K
输出：置换后序列
示例：
输入：
A = [1, 2, 3], B = [3, 1, 2], k = 2
输出：[2, 3, 1]
说明：
A序列经过B序列置换后变为312，再经过231
Q1：请简述算法思路和时间空间复杂度
Q2：编程实现
123456789101112131415161718class Solution: def main(self, A: List[int], B: List[int], k: int) -> int: n = len(A) result = [0] * n visited = [False] * n for i in range(n): if not visited[i]: cycle = [] j = i while not visited[j]: visited[j] = True cycle.append(j) j = B[j] - 1 cycle_length = len(cycle) for m in range(cycle_length): result[cycle[(m + K) % cycle_length]] = A[cycle[m]] return 1
思路
构建循环：遍历A的每个元素，使用i作为索引如果没有被访问则从这里开始，沿着B数组定义的置换元素构建一个置换循环。使用cycle记录循环中给所有元素的索引
处理置换循环：遍历cycle，记长度为cycle_length，对每个元素都置换到新位置，位置是计算得出的
时间复杂度时间复杂度O(n)，空间复杂度O(n)
后记这次的题相对来说其实属于easy和medium范畴了。但是由于没有设定结果所以也没办法看自己最终能够通过多少，不过我的思路应该是大差不差的，如果有什么问题还请大家在评论里指出，啾咪💞