101 lines
2.2 KiB
Markdown
101 lines
2.2 KiB
Markdown
## 每日一题 - 593. 有效的正方形
|
||
|
||
### 信息卡片
|
||
|
||
- 时间：2019-06-08
|
||
- 题目链接：https://leetcode.com/problems/top-k-frequent-elements/description/
|
||
- tag：`Hash Table` `Heap`
|
||
|
||
### 题目描述
|
||
|
||
```
|
||
Given a non-empty array of integers, return the k most frequent elements.
|
||
|
||
Example 1:
|
||
|
||
Input: nums = [1,1,1,2,2,3], k = 2
|
||
Output: [1,2]
|
||
|
||
Example 2:
|
||
|
||
|
||
Input: nums = [1], k = 1
|
||
Output: [1]
|
||
|
||
Note:
|
||
|
||
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
|
||
Your algorithm's time complexity must be better than O(n log n), where n is
|
||
the array's size.
|
||
```
|
||
|
||
|
||
|
||
### 参考答案
|
||
|
||
模仿 [@raof01](https://github.com/raof01) 的思路写的JS代码，
|
||
|
||
基本思路就是： 证明四个角都是直角， 而证明直角的方式就是边长关系。
|
||
|
||
四个点一共有六个连接的线段，其中两个是对角线，另外四个是边。
|
||
|
||
对于直角来说，满足“a * a + b * b = c * c”, 由于是正方形，所以a = b， 因此c就等于
|
||
2 * a * a , 其中a为边长，c就是对角线的长度。
|
||
|
||
|
||
我们分别计算出距离的平方，如果有四个相同，另外两个相同。 且二者的关系可以满足直角，那么他就有四个直角，他就是一个正方形
|
||
|
||
```js
|
||
/*
|
||
* @lc app=leetcode id=593 lang=javascript
|
||
*
|
||
* [593] Valid Square
|
||
*/
|
||
function square(p1, p2) {
|
||
const deltaX = p1[0] - p2[0];
|
||
const deltaY = p1[1] - p2[1];
|
||
|
||
return deltaX * deltaX + deltaY * deltaY;
|
||
}
|
||
/**
|
||
* @param {number[]} p1
|
||
* @param {number[]} p2
|
||
* @param {number[]} p3
|
||
* @param {number[]} p4
|
||
* @return {boolean}
|
||
*/
|
||
var validSquare = function (p1, p2, p3, p4) {
|
||
// 证明四个角都是直角
|
||
// 证明直角的方式就是边长关系
|
||
const squares = [
|
||
square(p1, p2),
|
||
square(p1, p3),
|
||
square(p1, p4),
|
||
square(p2, p3),
|
||
square(p2, p4),
|
||
square(p3, p4)
|
||
];
|
||
let cnt1 = 0;
|
||
let cnt2 = 0;
|
||
let sum = 0;
|
||
|
||
for(let i = 0; i < squares.length; i++) {
|
||
sum += squares[i];
|
||
}
|
||
|
||
for(let i = 0; i < squares.length; i++) {
|
||
if (sum === 8 * squares[i]) {
|
||
cnt1++;
|
||
} else if(sum === 4 * squares[i]) {
|
||
cnt2++;
|
||
}
|
||
}
|
||
|
||
return cnt1 === 4 && cnt2 ===2;
|
||
|
||
}
|
||
```
|
||
### 其他优秀解答
|
||
|
||
暂无
|