wordpress 文章路径,富阳网站seo价格,魔改wordpress主题,电话销售网站建设话术文章目录 149. 直线上最多的点数题目链接标签思路总体思路如何判断 一个点 在 由两点确定的直线 上 代码 347. 前 K 个高频元素题目链接标签思路代码 31. 下一个排列题目链接标签思路代码 149. 直线上最多的点数
题目链接
149. 直线上最多的点数
标签
几何 数组 哈希表 数学… 文章目录 149. 直线上最多的点数题目链接标签思路总体思路如何判断 一个点 在 由两点确定的直线 上 代码 347. 前 K 个高频元素题目链接标签思路代码 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−x2y2−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) { // 如果点的数量小于等于 2return n; // 则直接返回点的数量即可}int res 0; // 保存结果for (int i 0; i n; i) {int[] p1 points[i]; // 第一个点for (int j i 1; j n; j) {int[] p2 points[j]; // 第二个点int deltaX p1[0] - p2[0]; // p1 和 p2 的横坐标的差值int deltaY p1[1] - p2[1]; // p1 和 p2 的纵坐标的差值// 统计有多少个点位于 p1 与 p2 所确定的直线上初始值为 2 表示 p1 和 p2 位于这条直线上int cnt 2;for (int k j 1; k n; k) {int[] p3 points[k]; // 第三个点// 如果 p3 在 p1, p2 所确定的直线上则点数加一if ((p3[1] - p2[1]) * deltaX (p3[0] - p2[0]) * 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 为元素出现的次数MapInteger, Integer cnt new HashMap(nums.length);for (int num : nums) {cnt.put(num, cnt.getOrDefault(num, 0) 1);}// 小顶堆元素出现的次数越少越靠近顶部。存放着数组中频率前 k 高的元素// 在 int[] 中存放了 2 个值第一个值表示 元素的值第二个值表示 元素出现的次数PriorityQueueint[] pq new PriorityQueue((p1, p2) - p1[1] - p2[1]);for (Map.EntryInteger, 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()[1]) {// 此时元素个数等于 k 个如果 当前元素的出现次数 大于 堆顶元素的出现次数pq.poll(); // 则移除堆顶元素pq.offer(new int[]{num, count}); // 将当前元素放入堆中}}// 构造结果数组并返回int[] res new int[k];for (int i 0; i k; i) {res[i] pq.poll()[0];}return res;}
}31. 下一个排列
题目链接
31. 下一个排列
标签
数组 双指针
思路
本题是 纯技巧题只要会这个技巧便能解决本题如果不会最好将其 背 下来。这个技巧分为如下三步 寻找 在数组中从右向左寻找 小于它右边的数 的数将其称为 逆数。例如 [1, 2, 5, 4, 6, 3] 中的 4。如果在数组中找到了 逆数那么从 最后一个数 到 逆数 的下一个数寻找一个 比 逆数 大 的数将其称为 大数。例如 [1, 2, 5, 4, 6, 3] 中的 6。 交换如果能找到 大数则交换这两个数。反转 如果在数组中找到了 逆数则将 逆数 的下一个数 到 最后一个数 的范围内的所有数进行反转操作。如果在数组中没有找到 逆数则将整个数组都进行反转操作。 如果很难理解这个技巧不妨来看看这个例子至少知道它可以使用
对于数组 [1, 2, 5, 4, 6, 3]
-----------------------------------
寻找逆数和比逆数大的数分别用 i, j 指向
[1, 2, 5, 4, 6, 3]^ ^i j
-----------------------------------
交换 i, j 指向的数
[1, 2, 5, 6, 4, 3]^i
-----------------------------------
反转 i 1 之后的部分
[1, 2, 5, 6, 3, 4]代码
class Solution {public void nextPermutation(int[] nums) {final int n nums.length;// 从右往左扫描直到找到一个 比它右边的数小的 数int i n - 2;while (i 0 nums[i] nums[i 1]) {i--;}// 如果在数组中找到了逆数if (i 0) {// 则 在 索引为 i 1 的数 到 最后一个数 的范围内寻找一个比逆数大的数int j n - 1;while (j i nums[i] nums[j]) {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[i];nums[i] nums[j];nums[j] 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--;}}
}
