LeetCode 149, 347, 31
149. 直线上最多的点数标题链接
149. 直线上最多的点数
标签
多少 数组 哈希表 数学
思路
总体思路
本题是一道 数学题，可以采取 暴力 的方式：
[*]先 罗列所有由两点连接而成的直线，即 罗列任意两个点 计算其所在直线。
[*]然后再 罗列所有点，统计 每条直线上的点的数量 的最大值。
可以轻微对这种方式进行优化：
[*]将第一步中的 罗列任意两个点 改为 罗列 任意点 和 其之后的所有点。防止 计算完点 A A A 和点 B B B 所在直线上的点的数量之后，再计算点 B B B 和点 A A A 所在直线上的点的数量 如许的重复计算。
[*]将第二步中的 罗列所有点 改为 罗列 第一步罗列的两个点之后的 所有点。制止了重复计算。
如何判断 一个点 在 由两点确定的直线 上
接下来就需要思量如何判断一个点 在 由两点确定的直线 上，其实并不难，既然已经罗列出两个点 P 1 ( x 1 , y 1 ) , P 2 ( x 2 , y 2 ) P_1(x_1, y_1), P_2(x_2, y_2) P1(x1,y1),P2(x2,y2)，对于第三个点 P 3 ( x 3 , y 3 ) P_3(x_3, y_3) P3(x3,y3)，只要 第一个点 和 第二个点 所确定直线的斜率 与 第二个点 和 第三个点 所确定直线的斜率 雷同，则点 P 3 P_3 P3 在直线 P 1 P 2 P_1P_2 P1P2 上。斜率雷同可以表现如下：
x 1 − x 2 y 1 − y 2 = x 2 − x 3 y 2 − y 3 \frac{x_1 - x_2}{y_1 - y_2} = \frac{x_2 - x_3}{y_2 - y_3} y1−y2x1−x2=y2−y3x2−x3
但是，在程序中无法使用 int, double 表现分数，如果强行使用，则会造成一定的精度丧失，导致结果错误。以是思量 将 除法 酿成 乘法，斜率雷同表现如下：
( y 2 − y 3 ) ( x 1 − x 2 ) = ( x 2 − x 3 ) ( y 1 − y 2 ) (y_2 - y_3) (x_1 - x_2) = (x_2 - x_3) (y_1 - y_2) (y2−y3)(x1−x2)=(x2−x3)(y1−y2)
确定第三个点是否在直线上时，需要多次使用 ( x 1 − x 2 ) (x_1 - x_2) (x1−x2) 和 ( y 1 − y 2 ) (y_1 - y_2) (y1−y2)，以是用变量来纪录它们： Δ x = ( x 1 − x 2 ) , Δ y = ( y 1 − y 2 ) \Delta x = (x_1 - x_2), \Delta y = (y_1 - y_2) Δx=(x1−x2),Δy=(y1−y2)，斜率雷同表现如下：
( y 2 − y 3 ) Δ x = ( x 2 − x 3 ) Δ y (y_2 - y_3) \Delta x = (x_2 - x_3) \Delta y (y2−y3)Δx=(x2−x3)Δy
代码
class Solution {
public int maxPoints(int[][] points) {
int n = points.length; // 获取数组中点的数量
if (n <= 2) { // 如果点的数量小于等于 2
return n; // 则直接返回点的数量即可
}
int res = 0; // 保存结果
for (int i = 0; i < n; i++) {
int[] p1 = points; // 第一个点
for (int j = i + 1; j < n; j++) {
int[] p2 = points; // 第二个点
int deltaX = p1 - p2; // p1 和 p2 的横坐标的差值
int deltaY = p1 - p2; // p1 和 p2 的纵坐标的差值
// 统计有多少个点位于 p1 与 p2 所确定的直线上，初始值为 2 表示 p1 和 p2 位于这条直线上
int cnt = 2;
for (int k = j + 1; k < n; k++) {
int[] p3 = points; // 第三个点
// 如果 p3 在 p1, p2 所确定的直线上，则点数加一
if ((p3 - p2) * deltaX == (p3 - p2) * deltaY) {
cnt++;
}
}
res = Math.max(res, cnt); // 更新最大值
}
}
return res;
}
}
347. 前 K 个高频元素
标题链接
347. 前 K 个高频元素
标签
数组 哈希表 分治 桶排序 计数 快速选择 排序 堆（优先队列）
思路
本题可以使用 优先队列，和 LeetCode 215. 数组中的第K个最大元素 很相似，都使用 小顶堆 来存放数组中优先级前 K 高的元素，不外本题中元素的优先级不是元素的值，而是元素的出现次数。
本题直接使用 Java 中的 PriorityQueue 优先队列，（用一个长度为 2 的数组作为范例参数）保存元素的值和出现次数。此外，需要在构造器中传入一个 比力器，定义优先队列内部存储的数据如何进行比力。
代码
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 统计每个元素出现的次数，key 为元素的值，value 为元素出现的次数
Map<Integer, Integer> cnt = new HashMap<>(nums.length);
for (int num : nums) {
cnt.put(num, cnt.getOrDefault(num, 0) + 1);
}
// 小顶堆，元素出现的次数越少，越靠近顶部。存放着数组中频率前 k 高的元素
// 在 int[] 中存放了 2 个值，第一个值表示 元素的值，第二个值表示 元素出现的次数
PriorityQueue<int[]> pq = new PriorityQueue<>((p1, p2) -> p1 - p2);
for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) { // 构建小顶堆
int num = entry.getKey(), count = entry.getValue();
if (pq.size() < k) { // 如果小顶堆中的元素少于 k 个
pq.offer(new int[]{num, count}); // 则给其中添加元素
} else if (count > pq.peek()) {
// 此时元素个数等于 k 个，如果 当前元素的出现次数 大于 堆顶元素的出现次数
pq.poll(); // 则移除堆顶元素
pq.offer(new int[]{num, count}); // 将当前元素放入堆中
}
}
// 构造结果数组并返回
int[] res = new int;
for (int i = 0; i < k; i++) {
res = pq.poll();
}
return res;
}
}
31. 下一个排列
标题链接
31. 下一个排列
标签
数组 双指针
思路
本题是 纯技巧题，只要会这个技巧便能解决本题，如果不会，最好将其 背 下来。这个技巧分为如下三步：
[*]寻找：
[*]在数组中，从右向左寻找 小于它右边的数 的数，将其称为 逆数。例如 中的 4。
[*]如果在数组中找到了 逆数，那么从 末了一个数 到 逆数 的下一个数，寻找一个 比 逆数 大 的数，将其称为 大数。例如 中的 6。
[*]互换：如果能找到 大数，则互换这两个数。
[*]反转：
[*]如果在数组中找到了 逆数，则将 逆数 的下一个数 到 末了一个数 的范围内的所有数进行反转操作。
[*]如果在数组中没有找到 逆数，则将整个数组都进行反转操作。
如果很难理解这个技巧，不妨来看看这个例子，至少知道它可以使用：
对于数组
-----------------------------------
寻找逆数和比逆数大的数，分别用 i, j 指向：
^^
ij
-----------------------------------
交换 i, j 指向的数：
^
i
-----------------------------------
反转 i + 1 之后的部分：
代码
class Solution {
public void nextPermutation(int[] nums) {
final int n = nums.length;
// 从右往左扫描，直到找到一个 比它右边的数小的 数
int i = n - 2;
while (i >= 0 && nums >= nums) {
i--;
}
// 如果在数组中找到了逆数
if (i >= 0) {
// 则 在 索引为 i + 1 的数 到 最后一个数 的范围内，寻找一个比逆数大的数
int j = n - 1;
while (j > i && nums >= nums) {
j--;
}
// 交换它们
swap(nums, i, j);
}
// 反转 i + 1 之后的部分
reverse(nums, i + 1);
}
// 交换 nums 中索引 i, j 指向的元素
private void swap(int[] nums, int i, int j) {
int temp= nums;
nums = nums;
nums = temp;
}
// 从 start 开始反转 nums 数组
private void reverse(int[] nums, int start) {
int left = start, right = nums.length - 1;
while (left < right) {
swap(nums, left, right);
left++;
right--;
}
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]