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;
|
|||
|
|
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
### 其他优秀解答
|
|||
|
|
|
|||
|
|
暂无
|