Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit808d840

Browse files
author
luzhipeng
committed
feat: 更新题目 169,226,240,887
1 parent524a101 commit808d840

13 files changed

+487
-197
lines changed

‎README.md

Lines changed: 15 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,7 @@ leetcode 题解，记录自己的 leecode 解题之路。
1818
1919
##食用指南
2020

21-
-经典题目的解析的目录部分，前面有🆕的代表是最新更新的
21+
-对于最近添加的部分， 前面会有 🆕 标注
2222
- 对于最近更新的部分， 前面会有 🖊 标注
2323
- 将来会在这里更新anki卡片
2424
- 这里有一份leetcode官方账号在知乎上给出的一个《互联网公司最常见的面试算法题有哪些？》的答案，我这里尽量去覆盖回答中的题目和知识点
@@ -66,21 +66,25 @@ leetcode 题解，记录自己的 leecode 解题之路。
6666

6767
-[20. Valid Parentheses](./problems/validParentheses.md)
6868
-[26.remove-duplicates-from-sorted-array](./problems/26.remove-duplicates-from-sorted-array.md)
69-
-[206.reverse-linked-list](./problems/206.reverse-linked-list.md)
7069
-[136.single-number](./problems/136.single-number.md)
7170
-[167.two-sum-ii-input-array-is-sorted](./problems/167.two-sum-ii-input-array-is-sorted.md)
71+
- 🆕[169.majority-element](./problems/169.majority-element.md)
72+
-[190.reverse-bits](./problems/190.reverse-bits.md)
73+
-[191.number-of-1-bits](./problems/191.number-of-1-bits.md)
7274
-[203.remove-linked-list-elements](./problems/203.remove-linked-list-elements.md)
75+
-[206.reverse-linked-list](./problems/206.reverse-linked-list.md)
7376
-[219.contains-duplicate-ii](./problems/219.contains-duplicate-ii.md)
77+
- 🆕[226.invert-binary-tree](./problems/226.invert-binary-tree.md)
7478
-[283.move-zeroes](./problems/283.move-zeroes.md)
7579
-[349.intersection-of-two-arrays](./problems/349.intersection-of-two-arrays.md)
76-
-[190.reverse-bits](./problems/190.reverse-bits.md)
77-
-[191.number-of-1-bits](./problems/191.number-of-1-bits.md)
80+
7881

7982
####中等难度
8083

8184
-[2. Add Two Numbers](./problems/addTwoNumbers.md)
8285
-[3. Longest Substring Without Repeating Characters](./problems/longestSubstringWithoutRepeatingCharacters.md)
8386
-[5. Longest Palindromic Substring](./problems/longestPalindromicSubstring.md)
87+
- 🆕[11.container-with-most-water](./problems/11.container-with-most-water.md)
8488
-[19. Remove Nth Node From End of List](./problems/removeNthNodeFromEndofList.md)
8589
-[24. Swap Nodes In Pairs](./problems/swapNodesInPairs.md)
8690
-[75.sort-colors.md](./problems/75.sort-colors.md)
@@ -91,18 +95,19 @@ leetcode 题解，记录自己的 leecode 解题之路。
9195
-[103.binary-tree-zigzag-level-order-traversal](./problems/103.binary-tree-zigzag-level-order-traversal.md)
9296
-[144.binary-tree-preorder-traversal](./problems/144.binary-tree-preorder-traversal.md)
9397
-[150.evaluate-reverse-polish-notation](./problems/150.evaluate-reverse-polish-notation.md)
94-
-[328.odd-even-linked-list](./problems/328.odd-even-linked-list.md)
95-
-[445.add-two-numbers-ii](./problems/445.add-two-numbers-ii.md)
96-
-[877.stone-game](./problems/877.stone-game.md)
97-
-[279.perfect-squares](./problems/279.perfect-squares.md)
9898
-[199.binary-tree-right-side-view](./problems/199.binary-tree-right-side-view.md)
9999
-[201.bitwise-and-of-numbers-range](./problems/201.bitwise-and-of-numbers-range.md)
100100
-[209.minimum-size-subarray-sum](./problems/209.minimum-size-subarray-sum.md)
101-
-[900.rle-iterator](./problems/900.rle-iterator.md)
101+
- 🆕[240.search-a-2-d-matrix-ii](./problems/240.search-a-2-d-matrix-ii.md)
102+
-[279.perfect-squares](./problems/279.perfect-squares.md)
102103
-[322.coin-change](./problems/322.coin-change.md)
104+
-[328.odd-even-linked-list](./problems/328.odd-even-linked-list.md)
105+
-[445.add-two-numbers-ii](./problems/445.add-two-numbers-ii.md)
103106
-[518.coin-change-2](./problems/518.coin-change-2.md)
104-
- 🆕[11.container-with-most-water](./problems/11.container-with-most-water.md)
105107
- 🆕[875.koko-eating-bananas](./problems/875.koko-eating-bananas.md)
108+
-[877.stone-game](./problems/877.stone-game.md)
109+
- 🆕[887.super-egg-drop](./problems/887.super-egg-drop.md)
110+
-[900.rle-iterator](./problems/900.rle-iterator.md)
106111

107112
####困难难度
108113

@@ -124,22 +129,14 @@ TODO
124129

125130
###计划
126131

127-
[226.invert-binary-tree]
128-
129132
[494.target-sum]
130133

131134
[88.merge-sorted-array]
132135

133136
[139.word-break]
134137

135-
[169.majority-element]
136-
137-
[240.search-a-2-d-matrix-ii]
138-
139138
[416.partition-equal-subset-sum]
140139

141140
[609.find-duplicate-file-in-system]
142141

143-
[887.super-egg-drop]
144-
145142
anki 卡片
61.4 KB
Loading
47.5 KB
Loading
27.6 KB
Loading
67.6 KB
Loading

‎problems/169.majority-element.md

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
2+
##题目地址
3+
https://leetcode.com/problems/majority-element/description/
4+
5+
##题目描述
6+
7+
```
8+
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
9+
10+
You may assume that the array is non-empty and the majority element always exist in the array.
11+
12+
Example 1:
13+
14+
Input: [3,2,3]
15+
Output: 3
16+
Example 2:
17+
18+
Input: [2,2,1,1,1,2,2]
19+
Output: 2
20+
21+
```
22+
23+
##思路
24+
25+
符合直觉的做法是利用额外的空间去记录每个元素出现的次数，并用一个单独的变量记录当前出现次数最多的元素。
26+
27+
但是这种做法空间复杂度较高，有没有可能进行优化呢？ 答案就是用"投票算法"。
28+
29+
投票算法的原理是通过不断消除不同元素直到没有不同元素，剩下的元素就是我们要找的元素。
30+
31+
![169.majority-element](../assets/problems/169.majority-element.png)
32+
33+
##关键点解析
34+
35+
- 投票算法
36+
37+
38+
##代码
39+
40+
```js
41+
42+
43+
/*
44+
* @lc app=leetcode id=169 lang=javascript
45+
*
46+
* [169] Majority Element
47+
*
48+
* https://leetcode.com/problems/majority-element/description/
49+
*
50+
* algorithms
51+
* Easy (51.62%)
52+
* Total Accepted: 365.6K
53+
* Total Submissions: 702.5K
54+
* Testcase Example: '[3,2,3]'
55+
*
56+
* Given an array of size n, find the majority element. The majority element is
57+
* the element that appears more than ⌊ n/2 ⌋ times.
58+
*
59+
* You may assume that the array is non-empty and the majority element always
60+
* exist in the array.
61+
*
62+
* Example 1:
63+
*
64+
*
65+
* Input: [3,2,3]
66+
* Output: 3
67+
*
68+
* Example 2:
69+
*
70+
*
71+
* Input: [2,2,1,1,1,2,2]
72+
* Output: 2
73+
*
74+
*
75+
*/
76+
/**
77+
*@param{number[]}nums
78+
*@return{number}
79+
*/
80+
varmajorityElement=function(nums) {
81+
let count=1;
82+
let majority= nums[0];
83+
for(let i=1; i<nums.length; i++) {
84+
if (count===0) {
85+
majority= nums[i];
86+
}
87+
if (nums[i]=== majority) {
88+
count++;
89+
}else {
90+
count--;
91+
}
92+
}
93+
return majority;
94+
};
95+
```
96+

‎todo/226.invert-binary-tree.jsrenamed to‎problems/226.invert-binary-tree.md

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,46 @@
1+
2+
##题目地址
3+
https://leetcode.com/problems/invert-binary-tree/description/
4+
5+
##题目描述
6+
7+
```
8+
Invert a binary tree.
9+
10+
Example:
11+
12+
Input:
13+
14+
4
15+
/ \
16+
2 7
17+
/ \ / \
18+
1 3 6 9
19+
Output:
20+
21+
4
22+
/ \
23+
7 2
24+
/ \ / \
25+
9 6 3 1
26+
Trivia:
27+
This problem was inspired by this original tweet by Max Howell:
28+
29+
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.
30+
```
31+
32+
##思路
33+
遍历树（随便怎么遍历），然后将左右子树交换位置。
34+
##关键点解析
35+
36+
- 递归简化操作
37+
- 如果树很高，建议使用栈来代替递归
38+
- 这道题目对顺序没要求的，因此队列数组操作都是一样的，无任何区别
39+
40+
##代码
41+
42+
```js
43+
144
/*
245
* @lc app=leetcode id=226 lang=javascript
346
*
@@ -78,3 +121,4 @@ var invertTree = function(root) {
78121
}
79122
return root;
80123
};
124+
```
Lines changed: 116 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,116 @@
1+
2+
##题目地址
3+
https://leetcode.com/problems/search-a-2d-matrix-ii/description/
4+
5+
##题目描述
6+
7+
```
8+
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
9+
10+
Integers in each row are sorted in ascending from left to right.
11+
Integers in each column are sorted in ascending from top to bottom.
12+
Example:
13+
14+
Consider the following matrix:
15+
16+
[
17+
[1, 4, 7, 11, 15],
18+
[2, 5, 8, 12, 19],
19+
[3, 6, 9, 16, 22],
20+
[10, 13, 14, 17, 24],
21+
[18, 21, 23, 26, 30]
22+
]
23+
Given target = 5, return true.
24+
25+
Given target = 20, return false.
26+
27+
```
28+
29+
##思路
30+
31+
符合直觉的做法是两层循环遍历，时间复杂度是O(m * n),
32+
有没有时间复杂度更好的做法呢？ 答案是有，那就是充分运用矩阵的特性（横向纵向都递增），
33+
我们可以从角落（左下或者右上）开始遍历，这样时间复杂度是O(m + n).
34+
35+
![240.search-a-2-d-matrix-ii](../assets/problems/240.search-a-2-d-matrix-ii.png)
36+
37+
其中蓝色代表我们选择的起点元素， 红色代表目标元素。
38+
39+
##关键点解析
40+
41+
- 从角落开始遍历，利用递增的特性简化时间复杂度
42+
43+
44+
##代码
45+
46+
```js
47+
48+
/*
49+
* @lc app=leetcode id=240 lang=javascript
50+
*
51+
* [240] Search a 2D Matrix II
52+
*
53+
* https://leetcode.com/problems/search-a-2d-matrix-ii/description/
54+
*
55+
* algorithms
56+
* Medium (40.30%)
57+
* Total Accepted: 170K
58+
* Total Submissions: 419.1K
59+
* Testcase Example: '[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]\n5'
60+
*
61+
* Write an efficient algorithm that searches for a value in an m x n matrix.
62+
* This matrix has the following properties:
63+
*
64+
*
65+
* Integers in each row are sorted in ascending from left to right.
66+
* Integers in each column are sorted in ascending from top to bottom.
67+
*
68+
*
69+
* Example:
70+
*
71+
* Consider the following matrix:
72+
*
73+
*
74+
* [
75+
* ⁠ [1, 4, 7, 11, 15],
76+
* ⁠ [2, 5, 8, 12, 19],
77+
* ⁠ [3, 6, 9, 16, 22],
78+
* ⁠ [10, 13, 14, 17, 24],
79+
* ⁠ [18, 21, 23, 26, 30]
80+
* ]
81+
*
82+
*
83+
* Given target = 5, return true.
84+
*
85+
* Given target = 20, return false.
86+
*
87+
*/
88+
/**
89+
*@param{number[][]}matrix
90+
*@param{number}target
91+
*@return{boolean}
92+
*/
93+
varsearchMatrix=function(matrix,target) {
94+
if (!matrix||matrix.length===0)return0;
95+
96+
let colIndex=0;
97+
let rowIndex=matrix.length-1;
98+
while(rowIndex>0&& target< matrix[rowIndex][colIndex]) {
99+
rowIndex--;
100+
}
101+
102+
while(colIndex< matrix[0].length) {
103+
if (target=== matrix[rowIndex][colIndex])returntrue;
104+
if (target> matrix[rowIndex][colIndex]) {
105+
colIndex++;
106+
}elseif (rowIndex>0){
107+
rowIndex--;
108+
}else {
109+
returnfalse;
110+
}
111+
}
112+
113+
returnfalse;
114+
};
115+
```
116+

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp