Skip to content

Commit f786039

Browse files
author
luzhipeng
committed
合并
2 parents e6ae6c7 + ad0fadf commit f786039

32 files changed

+1432
-78
lines changed

‎README.en.md

Lines changed: 9 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,8 @@
11
# LeetCode
2-
2+
[![Travis](https://img.shields.io/badge/language-C++-green.svg)]()
3+
[![Travis](https://img.shields.io/badge/language-JavaScript-yellow.svg)]()
4+
[![Travis](https://img.shields.io/badge/language-Python-red.svg)]()
5+
[![Travis](https://img.shields.io/badge/language-Java-blue.svg)]()
36
![Total visitor](https://visitor-count-badge.herokuapp.com/total.svg?repo_id=azl397985856.leetcode)
47
![Visitors in today](https://visitor-count-badge.herokuapp.com/today.svg?repo_id=azl397985856.leetcode)
58
> since 2019-09-03 19:40
@@ -13,7 +16,7 @@
1316
This essay records the course of and my emotion to this project from initialisation to 10,000 stars.
1417
[Milestone for 10,000+ stars](./thanksGiving.md)
1518

16-
If you are interested in this project, do not mean your star. This project will be supported for a long enough time by the comminity. Thanks for every audience and contributor.
19+
If you are interested in this project, **do not mean your star**. This project will be **supported for a long enough time** by the comminity. Thanks for every audience and contributor.
1720

1821
## Introduction
1922

@@ -107,7 +110,7 @@ The data structures mainly includes:
107110

108111
### Solutions to LeetCode Classic Problems
109112

110-
> Here only lists some representative problems but not all.
113+
> Here only lists some **representative problems** but not all.
111114
112115
#### Easy
113116

@@ -158,7 +161,7 @@ The data structures mainly includes:
158161
- [0046.permutations](./problems/46.permutations.md)
159162
- [0047.permutations-ii](./problems/47.permutations-ii.md)
160163
- [0048.rotate-image](./problems/48.rotate-image.md)
161-
- [0049.group-anagrams](./problems/49.group-anagrams.md)
164+
- [0049.group-anagrams](./problems/49.group-anagrams.md)
162165
- [0055.jump-game](./problems/55.jump-game.md)
163166
- [0056.merge-intervals](./problems/56.merge-intervals.md)
164167
- [0062.unique-paths](./problems/62.unique-paths.md )
@@ -183,7 +186,7 @@ The data structures mainly includes:
183186
- [0150.evaluate-reverse-polish-notation](./problems/150.evaluate-reverse-polish-notation.md)
184187
- [0152.maximum-product-subarray](./problems/152.maximum-product-subarray.md)
185188
- [0199.binary-tree-right-side-view](./problems/199.binary-tree-right-side-view.md)
186-
- [0200.number-of-islands](./problems/200.number-of-islands.md) 🆕
189+
- [0200.number-of-islands](./problems/200.number-of-islands.md) 🆕
187190
- [0201.bitwise-and-of-numbers-range](./problems/201.bitwise-and-of-numbers-range.md)
188191
- [0208.implement-trie-prefix-tree](./problems/208.implement-trie-prefix-tree.md)
189192
- [0209.minimum-size-subarray-sum](./problems/209.minimum-size-subarray-sum.md)
@@ -214,6 +217,7 @@ The data structures mainly includes:
214217
- [0877.stone-game](./problems/877.stone-game.md)
215218
- [0887.super-egg-drop](./problems/887.super-egg-drop.md)
216219
- [0900.rle-iterator](./problems/900.rle-iterator.md)
220+
- [0912.sort-an-array](./problems/912.sort-an-array.md) 🆕
217221
- [1031.maximum-sum-of-two-non-overlapping-subarrays](./problems/1031.maximum-sum-of-two-non-overlapping-subarrays.md)
218222
- [1218.longest-arithmetic-subsequence-of-given-difference.md](./problems/1218.longest-arithmetic-subsequence-of-given-difference.md) 🆕
219223

‎README.md

Lines changed: 16 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,9 @@
11
# LeetCode
22

3+
[![Travis](https://img.shields.io/badge/language-C++-green.svg)]()
4+
[![Travis](https://img.shields.io/badge/language-JavaScript-yellow.svg)]()
5+
[![Travis](https://img.shields.io/badge/language-Python-red.svg)]()
6+
[![Travis](https://img.shields.io/badge/language-Java-blue.svg)]()
37
![历史共访问次数](https://visitor-count-badge.herokuapp.com/total.svg?repo_id=azl397985856.leetcode)
48
![今天被访问次数](https://visitor-count-badge.herokuapp.com/today.svg?repo_id=azl397985856.leetcode)
59

@@ -12,13 +16,13 @@
1216
![leetcode.jpeg](./assets/leetcode.jpeg)
1317

1418
这个是我写的[纪念项目 Star 突破 1W 的一个短文](./thanksGiving.md)， 记录了项目的"兴起"之路, 大家有兴趣可以看一下，
15-
如果对这个项目感兴趣，请点击一下Star， 项目会长久更新，感谢大家的支持。
19+
如果对这个项目感兴趣，请**点击一下Star**， 项目会**持续更新**，感谢大家的支持。
1620

1721
## 介绍
1822

1923
leetcode 题解，记录自己的 leetcode 解题之路。
2024

21-
本仓库目前分为五个部分：
25+
本仓库目前分为**五个**部分：
2226

2327
- 第一个部分是 leetcode 经典题目的解析，包括思路，关键点和具体的代码实现。
2428

@@ -34,18 +38,12 @@ leetcode 题解，记录自己的 leetcode 解题之路。
3438
3539
## 关于我
3640

37-
我是一个对技术充满兴趣的程序员, 擅长前端工程化，前端性能优化，前端标准化等。
41+
擅长前端工程化，前端性能优化，前端标准化等，做过.net， 搞过Java，现在是一名前端工程师，我的个人博客：https://lucifer.ren/blog/
3842

39-
做过.net， 搞过Java，现在是一名前端工程师。
43+
我经常会在开源社区进行一些输出和分享，比较受欢迎的有[宇宙最强的前端面试指南](https://github.com/azl397985856/fe-interview)
44+
和[我的第一本小书](https://github.com/azl397985856/automate-everything)。目前本人正在写一本关于《leetcode题解》的实体书，因此可能更新会比较慢，如果有人想要做些贡献或者合作的也可以直接用下面的邮箱联系我。
4045

41-
除了我的本职工作外，我会在开源社区进行一些输出和分享，比较受欢迎的有[宇宙最强的前端面试指南](https://github.com/azl397985856/fe-interview)
42-
和[我的第一本小书](https://github.com/azl397985856/automate-everything)
43-
44-
目前本人正在写一本关于《leetcode题解》的实体书，因此可能更新会比较慢，
45-
如果有人想要做些贡献或者合作的也可以直接用下面的邮箱联系我。
46-
47-
另外如果大家需要内推的可以找我，我这里有包括阿里，腾讯，头条，网易等很多公司的朋友。
48-
有需要可以直接群里联系我，或者发送到我的个人邮箱 [azl397985856@gmail.com]。
46+
另外如果大家需要内推的可以找我，我这里有包括阿里，腾讯，头条，网易等很多公司的朋友。有需要可以直接群里联系我，或者发送到我的个人邮箱 [azl397985856@gmail.com]。
4947

5048
## 食用指南
5149

@@ -120,7 +118,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
120118

121119
### leetcode 经典题目的解析
122120

123-
> 这里仅列举具有代表性题目，并不是全部题目
121+
> 这里仅列举具有**代表性题目**，并不是全部题目
124122
125123
#### 简单难度
126124

@@ -227,8 +225,10 @@ leetcode 题解，记录自己的 leetcode 解题之路。
227225
- [0877.stone-game](./problems/877.stone-game.md)
228226
- [0887.super-egg-drop](./problems/887.super-egg-drop.md)
229227
- [0900.rle-iterator](./problems/900.rle-iterator.md)
228+
- [0912.sort-an-array](./problems/912.sort-an-array.md) 🆕
230229
- [1031.maximum-sum-of-two-non-overlapping-subarrays](./problems/1031.maximum-sum-of-two-non-overlapping-subarrays.md)
231230
- [1218.longest-arithmetic-subsequence-of-given-difference.md](./problems/1218.longest-arithmetic-subsequence-of-given-difference.md) 🆕
231+
232232
#### 困难难度
233233

234234
- [0004.median-of-two-sorted-array](./problems/4.median-of-two-sorted-array.md) 🆕
@@ -300,16 +300,13 @@ anki - 文件 - 导入 - 下拉格式选择“打包的 anki集合”，然后
300300

301301
## 关注我
302302

303-
最近我重新整理了下自己的公众号，并且我还给他换了一个名字`脑洞前端`，它是一个帮助你打开大前端新世界大门的钥匙🔑，在这里你可以听到新奇的观点，看到一些技术尝新，还会收到系统性总结和思考。
304-
305-
由于微信`一个自然人只能有一个订阅号`的限制, 现在我也会放一些leetcode题解在这个号上面，
306-
后期考虑出一个leetcode模块或者想办法开另外一个公众号。
303+
我重新整理了下自己的公众号，并且我还给它换了一个名字`脑洞前端`，它是一个帮助你打开大前端新世界大门的钥匙 🔑，在这里你可以听到新奇的观点，看到一些技术尝新，还会收到系统性总结和思考。
307304

308305
在这里我会尽量通过图的形式来阐述一些概念和逻辑，帮助大家快速理解，图解是我的目标。
309306

310-
之后我的文章同步到微信公众号 `脑洞前端` ，您可以关注获取最新的文章，或者和我进行交流。
307+
之后我的文章会同步到微信公众号 `脑洞前端` ，你可以关注获取最新的文章，并和我进行交流。
311308

312-
另外你可以回复leetcode拉你进微信群，如果想加入qq群，请回复qq。
309+
另外你可以回复大前端进大前端微信交流群， 回复 leetcode 拉你进 leetcode 微信群，如果想加入 qq 群，请回复 qq。
313310

314311

315312
<img width="300" src="./assets/gongzhonghao.jpeg">

‎assets/drawio/912.sort-an-array.drawio

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
<mxfile modified="2019-09-14T09:21:59.588Z" host="www.draw.io" agent="Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/76.0.3809.132 Safari/537.36" etag="pFvn7xNMapLTBJD5jPEq" version="11.2.8" type="device" pages="1"><diagram id="tFO1_1GZ6p5RLwFWiUon" name="第 1 页">7Zxdb6M4FIZ/TS4Tgc1HuEyyzaxWWmlHlWZ2584b3AQNwalxmmR+/ZhgoHBIp2FIcCX3og3HcBz8vLY5x6YjvNgeP3Gy2/zNQhqPkBUeR/iPEUIBtuXvzHDKDY7n54Y1j8LcZFeGx+gHVUZLWfdRSNPaiYKxWES7unHFkoSuRM1GOGeH+mlPLK7XuiNrCgyPKxJD69coFJvcOkV+Zf+TRutNUbPtBXnJlhQnqztJNyRkh1cm/DDCC86YyD9tjwsaZ21XtEt+3fJCafnFOE3Eey6YfVvG/y7/+0K+zl9Ou2/T57+eP4+VlxcS79UNu+rbilPRBJztk5BmXuwRnh82kaCPO7LKSg+SubRtxDZWxU8sEYqi7anjBYsZP/vCy+XUsixpj8n/NJ4zHlJeFCcskZfN1zFJM2jZWUzWE4lMOtPsMBWcfS85oNLyqoLg/CNL1I1RLujxYovZJQepX8q2VPCTPEVdgKZefonSrqdIHiohuMq0eaWBwkaU9Nal44qO/KAAXQELAVi2gVXAwlgvWNjAegOWZj3LAbCQgVXAcjTrWS6AZRlYJSzNepZnYF2G5WrWs4K7wwqCxeKjwHJrrMoIZShYRf2GVhst29INFwy1DK4Kl3a9CwZbt34k/EC4mpHx8LhguGVwXYyNh8cFA65bR8cfCZd2vQuGXJPJBACTdyzqVOrNpBr6KYrjhonE0TqRhyvZQlTa51n7RSsSz1TBNgrDrJpWGVRCsRocX6kCW2+oosG7jxGymO9Lhi5g6LQwRDdj6AOGI+TFGbB0R5IaSe95n2Wlz801Ts/tN5Mn2N7uWBXKT+vs79i1sohL+ZLfLXeXFxqNXBFRBLCb31ci01tJxDkPjkYi1z8XF0O/LhpBMOrsUSNTo5EOGvF00wgMdfvRiJll+ojVBpcHDK37kYdt5NEh2HBszeQBQ/l+5IGMPDrII9BNHjB10I88sJFHh+VG7UYPmKroRx6OkUcHeQS6PXvA9eh+5OEaeXRIgDi6yQMmycwi3cWNQIPnpRFMWBlcF7cCDY8L7i8xqz4XNwMNjgvDVJ9Z9XmboQd2nUyHndAwzLWYEbLC5TmadTmY+zC4Sly+rRsumIswuCpc2vWum+UGzNJVTwPw0AEgvlV+wKyAdx70A80kcquNNGYfTeeJRjeJwEAXAKRJOMveT85IZK0YrS4+CbQ3p3rPpT6p47ZJfbmcu37V1jQErzz/sqXfOWVzGhMRvdTdtzWvquEfFsmKq8Umqx4C4ymuu0jZnq+ouqqC9GtHqOFIEL6mAjg60y5v+zfeJ2zbJaOBAEKSbspHUe3V0NjX0l0NTUf3VkPbfhijhuvU4NjWxG3owemmhxZXyLmvImBaxijiakV4Tm+KgK7urYi2XS9GEdcpwrV7en4Aju49Y7RtcjFquFINfk/PD8DRvdUA81aRDMKOQBJaB4WoRYT+w8x7aMlUjn4/KGy+W6F61FAhoQMTSyvZasIwfD9DNPArVA7M/CT7bWoQvrX7HNXHTn9ohnDLSGCjScq4GJNkTDgnp0tAdaLo3JeiW6foYJhhw1YAOfrXc5SH1T/Fy6fQ6j8L4oef</diagram></mxfile>

‎assets/problems/912.sort-an-array-1.png

48.5 KB
Loading

‎assets/problems/912.sort-an-array-2.png

38.3 KB
Loading

‎daily/2019-08-19.md

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
## 每日一题 - 593. 有效的正方形
2+
3+
### 信息卡片
4+
5+
- 时间：2019-06-08
6+
- 题目链接：https://leetcode.com/problems/top-k-frequent-elements/description/
7+
- tag：`Hash Table` `Heap`
8+
9+
### 题目描述
10+
11+
```
12+
Given a non-empty array of integers, return the k most frequent elements.
13+
14+
Example 1:
15+
16+
Input: nums = [1,1,1,2,2,3], k = 2
17+
Output: [1,2]
18+
19+
Example 2:
20+
21+
22+
Input: nums = [1], k = 1
23+
Output: [1]
24+
25+
Note:
26+
27+
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
28+
Your algorithm's time complexity must be better than O(n log n), where n is
29+
the array's size.
30+
```
31+
32+
33+
34+
### 参考答案
35+
36+
模仿 [@raof01](https://github.com/raof01) 的思路写的JS代码，
37+
38+
基本思路就是： 证明四个角都是直角， 而证明直角的方式就是边长关系。
39+
40+
四个点一共有六个连接的线段，其中两个是对角线，另外四个是边。
41+
42+
对于直角来说，满足“a * a + b * b = c * c”, 由于是正方形，所以a = b， 因此c就等于
43+
2 * a * a , 其中a为边长，c就是对角线的长度。
44+
45+
46+
我们分别计算出距离的平方，如果有四个相同，另外两个相同。 且二者的关系可以满足直角，那么他就有四个直角，他就是一个正方形
47+
48+
```js
49+
/*
50+
* @lc app=leetcode id=593 lang=javascript
51+
*
52+
* [593] Valid Square
53+
*/
54+
function square(p1, p2) {
55+
const deltaX = p1[0] - p2[0];
56+
const deltaY = p1[1] - p2[1];
57+
58+
return deltaX * deltaX + deltaY * deltaY;
59+
}
60+
/**
61+
* @param {number[]} p1
62+
* @param {number[]} p2
63+
* @param {number[]} p3
64+
* @param {number[]} p4
65+
* @return {boolean}
66+
*/
67+
var validSquare = function (p1, p2, p3, p4) {
68+
// 证明四个角都是直角
69+
// 证明直角的方式就是边长关系
70+
const squares = [
71+
square(p1, p2),
72+
square(p1, p3),
73+
square(p1, p4),
74+
square(p2, p3),
75+
square(p2, p4),
76+
square(p3, p4)
77+
];
78+
let cnt1 = 0;
79+
let cnt2 = 0;
80+
let sum = 0;
81+
82+
for(let i = 0; i < squares.length; i++) {
83+
sum += squares[i];
84+
}
85+
86+
for(let i = 0; i < squares.length; i++) {
87+
if (sum === 8 * squares[i]) {
88+
cnt1++;
89+
} else if(sum === 4 * squares[i]) {
90+
cnt2++;
91+
}
92+
}
93+
94+
return cnt1 === 4 && cnt2 ===2;
95+
96+
}
97+
```
98+
### 其他优秀解答
99+
100+
暂无

‎daily/2019-08-21.md

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
# 毎日一题 - 桶中取黑白球
2+
3+
## 信息卡片
4+
5+
* 时间：2019-08-21
6+
* tag：`Math` `位运算`
7+
## 题目描述
8+
```
9+
有一个桶，里面有白球，黑球各100个，你必须用以下规则将球取出来：
10+
- 每次从桶里取两个球
11+
- 如果两个球是相同的颜色，那么再放一个黑球
12+
- 如果两个球是不同的颜色，那么再放一个白球。
13+
问：最后一个球是黑球的概率是多少？
14+
```
15+
16+
## 参考答案
17+
18+
### 1. 数学分析原问题
19+
20+
首先我们来仔细读题看看我们有哪些知道的信息：
21+
22+
- 不管什么情况，每次球的总数减1；
23+
- 两黑：黑球-1，白球0；
24+
- 两白：黑球+1，白球-2；
25+
- 一黑一白：黑球-1，白球0；
26+
- 最后两球只要不是一黑一白，最后一球都是黑；
27+
28+
初始状态是100个黑球和100个白球，从上面三个状态可知道，黑球要么+1要么-1，而白球要么不变要么-2；在198次取球后，我们可知剩余两个球，现在假设剩余的两球为一黑一白，可以证明这是不存在的。
29+
30+
因为白球下降是以2的倍数下降，不可能从100下降至1,；故剩余两球肯定不是一黑一白的情况，那么最后一球的情况必然为黑。
31+
32+
33+
### 2. 原问题拓展（n个黑球和m个白球）
34+
35+
在n+m-2次取球后，剩余两个球。
36+
37+
由于我们知道白球数下降是以2的倍数下降，如果m为偶数的话，是不可能下降至1；即同上1，最后一球必为黑球。如果m为奇数的话，最后必然是k黑1白（k>=1），显然对于任意的k，要么剩余全是黑球，要么黑球不断减1，最后变为1黑1白。全黑和1黑1白最后的结果都是剩余一个白球。
38+
39+
得出结论，最后一球结果无关黑球数量（n>=0）,仅与白球数量m有关。
40+
41+
- 如果白球m为奇数，最后一球必然白；
42+
- 如果白球m为偶数，最后一球必然黑；
43+
44+
### 3. 抽象为数学模型，严格证明
45+
46+
不妨设黑球为0，白球为1；
47+
48+
- 两黑：F(0,0) = 0；表示两个黑球生一黑；
49+
- 两白：F(1,1) = 0；表示两个白球生一黑；
50+
- 一黑一白：F(0,1) = 0；表示一个黑球一个白球生一白；
51+
52+
仔细观察就会发现这个函数F就是XOR（异或）；
53+
54+
那么m个黑球和n个白球，就抽象为m个0和n个1作异或的结果；而且我们可知异或满足结合律和交换律（证明略，最简单的证明方法枚举）。
55+
56+
那么问题就很简单，对于任意多0，异或结果依然是0，所以对于任意多1，只需要考虑1个数的奇偶性就可判断最后剩余1个1还是0个1；
57+
58+
结论同2：
59+
60+
- 1（白球）的个数奇数，最后异或结果为1；
61+
- 1（白球）的个数偶数，最后异或结果为0；
62+
63+
64+
## 优秀解答
65+
66+
>暂缺

0 commit comments

Comments
 (0)