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

Commitb159f16

Browse files
author
luzhipeng
committed
feat: 修改azl397985856#209azl397985856#279， 增加todo
1 parent3f8598e commitb159f16

8 files changed

+217
-15
lines changed

‎README.md

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -118,9 +118,9 @@ leetcode 题解，记录自己的 leetcode 解题之路。
118118
-[199.binary-tree-right-side-view](./problems/199.binary-tree-right-side-view.md)
119119
-[201.bitwise-and-of-numbers-range](./problems/201.bitwise-and-of-numbers-range.md)
120120
- 🆕[208.implement-trie-prefix-tree](./problems/208.implement-trie-prefix-tree.md)
121-
-[209.minimum-size-subarray-sum](./problems/209.minimum-size-subarray-sum.md)
121+
-🖊[209.minimum-size-subarray-sum](./problems/209.minimum-size-subarray-sum.md)
122122
-[240.search-a-2-d-matrix-ii](./problems/240.search-a-2-d-matrix-ii.md)
123-
-[279.perfect-squares](./problems/279.perfect-squares.md)
123+
-🖊[279.perfect-squares](./problems/279.perfect-squares.md)
124124
-[322.coin-change](./problems/322.coin-change.md)
125125
-[328.odd-even-linked-list](./problems/328.odd-even-linked-list.md)
126126
-[416.partition-equal-subset-sum](./problems/416.partition-equal-subset-sum.md)
@@ -169,9 +169,9 @@ anki - 文件 - 导入 - 下拉格式选择“打包的 anki集合”，然后
169169

170170
-[365.water-and-jug-problem](./todo/365.water-and-jug-problem.js)
171171

172-
- anki 卡片 完善
172+
-[anki 卡片 完善](./assets/anki/)
173173

174-
- 字符串类问题汇总
174+
-[字符串类问题汇总](./todo/str/)
175175

176176
##交流群
177177

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
<mxfile modified="2019-04-24T03:55:11.597Z" host="www.draw.io" agent="Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/73.0.3683.86 Safari/537.36" etag="RuhMS0eC7MZ-eP7ukQ4K" version="10.6.3" type="device"><diagram id="2aZ_QtbOp8G18H4-aLN5" name="第 1 页">7ZpBb5swGIZ/DcdF2AYDxzZttsMqTcqh2mlywAFUwBScJemvnymGBOyknZYQouWU8NkY87yfzWuMgabp5mtB8uiJBTQxoBlsDPRgQAiQ54qfKrKtIw4GdSAs4kBW2gXm8RuVQVNGV3FAy05FzljC47wb9FmWUZ93YqQo2LpbbcmS7lVzElIlMPdJokaf44BHddSFzi7+jcZh1FwZYK8uSUlTWd5JGZGArfdC6NFA04IxXv9LN1OaVPAaLvV5swOlbccKmvHPnOA7L7Nis9g+/bRfnk3ivr3O11/kbfwmyUresOws3zYECrbKAlo1Agx0v45iTuc58avStdBcxCKeJrK45AV7oVOWsOL9bOQ5D6bjiBJ5IVpwujl4B6DlIhKKspTyYiuqyBNcSVKmkicP1ztdAJaxaE8TR8aITIWwbXhHS/yRwP4CHlDgHaNnfkzvBIy8LiNgqpBsDSP7XIygwghdnBGwRgYJKZDA5SGNLZOsEY42OLZMshVI1uUhjS2T8AjnJDS2THIVSI4CSdwuP/b8z1gmat4v4yTphUgSh5k49AUeKuL3FbxY2K47WZDGQVBdRou+K86SZVwaR2jL4z0HMpthE+LTqGSbPZWArahkaVSC51LJU1Ryj6TyPxm4gJRR28oJWPbcHHBVlO0qYBg7Zyow8bXABMjp0Gzp7ptjGw1JU3XHDeDrw4kcTXKag+JUjbQ6H4+UJuzNmpajSU7dtHk+mqpP8q6GZjOMJU0bq7k58DpYNVRXk5sIdHMTY01uDvsYUt/JJDQLq87cqWZ+HBaso8oHfsw076czeBr1cFe89glzKTsGVNfcaqeuMf5v7UBv5CHzwl4aqGb6NvA+KZ6lWa4OKh5Uzftt5B0Sr3GzjXjehUceVNcKN/EO2T/kTrry2ZqNkGHlU9cmrXzwJt/Rl6FY89pjWPHUzQdFsnbrskPO/MCzL1zbsqtKCVnQ5AcrYx4zrX7fexUWjHOWagTmLNflgehfXnU13YTVLvQkLX1CJwHNC+oTToNJzkpR89f7hnAvt0RHl65PfV+TB0EsGpB9Ktmq0ucUOWD13vViB040azhPkwaWfa40ULdXDIgTLqkY1Q57Awy/rqpNa4ECEeyaC3c/hMPqN42z5nTRnbqFuuQ2H3TfKKNeLthnm8zF4e5rg/eyvW820OMf</diagram></mxfile>
Loading

‎problems/209.minimum-size-subarray-sum.md

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -21,11 +21,13 @@ If you have figured out the O(n) solution, try coding another solution of which
2121

2222
用滑动窗口来记录序列， 每当滑动窗口中的 sum 超过 s， 就去更新最小值，并根据先进先出的原则更新滑动窗口，直至 sum 刚好小于 s
2323

24+
![209.minimum-size-subarray-sum](../assets/problems/209.minimum-size-subarray-sum.png)
25+
2426
>这道题目和 leetcode 3 号题目有点像，都可以用滑动窗口的思路来解决
2527
2628
##关键点
2729

28-
- 滑动窗口简化操作
30+
- 滑动窗口简化操作(滑窗口适合用于求解这种要求`连续`的题目)
2931

3032
##代码
3133

‎problems/279.perfect-squares.md

Lines changed: 69 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,16 +1,16 @@
11
##题目地址
2+
23
https://leetcode.com/problems/perfect-squares/description/
34

45
##题目描述
56

6-
77
```
88
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
99
1010
Example 1:
1111
1212
Input: n = 12
13-
Output: 3
13+
Output: 3
1414
Explanation: 12 = 4 + 4 + 4.
1515
Example 2:
1616
@@ -23,19 +23,66 @@ Explanation: 13 = 4 + 9.
2323
##思路
2424

2525
直接递归处理即可，但是这种暴力的解法很容易超时。如果你把递归的过程化成一棵树的话（其实就是递归树），
26-
可以看出中间有很多重复的计算。
26+
可以看出中间有很多重复的计算。
2727

2828
如果能将重复的计算缓存下来，说不定能够解决时间复杂度太高的问题。
2929

3030
>递归对内存的要求也很高， 如果数字非常大，也会面临爆栈的风险，将递归转化为循环可以解决。
3131
32-
如果使用DP，其实本质上和递归 + 缓存 差不多。
32+
递归 + 缓存的方式代码如下：
33+
34+
```js
35+
constmapper= {};
36+
37+
functiond(n,level) {
38+
if (n===0)return level;
39+
40+
let i=1;
41+
constarr= [];
42+
43+
while (n- i* i>=0) {
44+
consthit= mapper[n- i* i];
45+
if (hit) {
46+
arr.push(hit+ level);
47+
}else {
48+
constdepth=d(n- i* i, level+1)- level;
49+
mapper[n- i* i]= depth;
50+
arr.push(depth+ level);
51+
}
52+
i++;
53+
}
54+
55+
returnMath.min(...arr);
56+
}
57+
/**
58+
*@param{number}n
59+
*@return{number}
60+
*/
61+
varnumSquares=function(n) {
62+
returnd(n,0);
63+
};
64+
```
65+
66+
如果使用 DP，其实本质上和递归 + 缓存 差不多。
67+
68+
DP 的代码见代码区。
3369

3470
##关键点解析
3571

3672
- 如果用递归 + 缓存， 缓存的设计很重要
37-
我的做法是key就是n，value是以n为起点，到达底端的深度。
38-
下次取出缓存的时候用当前的level + 存的深度 就是我们想要的level.
73+
我的做法是 key 就是 n，value 是以 n 为起点，到达底端的深度。
74+
下次取出缓存的时候用当前的 level + 存的深度 就是我们想要的 level.
75+
76+
- 使用递归的核心点还是选和不选的问题
77+
78+
```js
79+
for (let i=1; i<= n; i++) {
80+
for (let j=1; j* j<= i; j++) {
81+
// 选（dp[i]） 还是 不选（dp[i - j * j]）
82+
dp[i]=Math.min(dp[i], dp[i- j* j]+1);
83+
}
84+
}
85+
```
3986

4087
##代码
4188

@@ -74,13 +121,12 @@ Explanation: 13 = 4 + 9.
74121
constmapper= {};
75122

76123
functiond(n,level) {
77-
78-
if (n===0)return level;
124+
if (n===0)return level;
79125

80126
let i=1;
81127
constarr= [];
82128

83-
while(n- i* i>=0) {
129+
while(n- i* i>=0) {
84130
consthit= mapper[n- i* i];
85131
if (hit) {
86132
arr.push(hit+ level);
@@ -99,6 +145,19 @@ function d(n, level) {
99145
*@return{number}
100146
*/
101147
varnumSquares=function(n) {
102-
returnd(n,0);
148+
if (n<=0) {
149+
return0;
150+
}
151+
152+
constdp=Array(n+1).fill(Number.MAX_VALUE);
153+
dp[0]=0;
154+
for (let i=1; i<= n; i++) {
155+
for (let j=1; j* j<= i; j++) {
156+
// 选（dp[i]） 还是 不选（dp[i - j * j]）
157+
dp[i]=Math.min(dp[i], dp[i- j* j]+1);
158+
}
159+
}
160+
161+
return dp[n];
103162
};
104163
```
Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
/*
2+
*@lc app=leetcode id=239 lang=javascript
3+
*
4+
* [239] Sliding Window Maximum
5+
*
6+
* https://leetcode.com/problems/sliding-window-maximum/description/
7+
*
8+
* algorithms
9+
* Hard (37.22%)
10+
* Total Accepted: 150.8K
11+
* Total Submissions: 399.5K
12+
* Testcase Example: '[1,3,-1,-3,5,3,6,7]\n3'
13+
*
14+
* Given an array nums, there is a sliding window of size k which is moving
15+
* from the very left of the array to the very right. You can only see the k
16+
* numbers in the window. Each time the sliding window moves right by one
17+
* position. Return the max sliding window.
18+
*
19+
* Example:
20+
*
21+
*
22+
* Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
23+
* Output: [3,3,5,5,6,7]
24+
* Explanation:
25+
*
26+
* Window position Max
27+
* --------------- -----
28+
* [1 3 -1] -3 5 3 6 7 3
29+
* ⁠1 [3 -1 -3] 5 3 6 7 3
30+
* ⁠1 3 [-1 -3 5] 3 6 7 5
31+
* ⁠1 3 -1 [-3 5 3] 6 7 5
32+
* ⁠1 3 -1 -3 [5 3 6] 7 6
33+
* ⁠1 3 -1 -3 5 [3 6 7] 7
34+
*
35+
*
36+
* Note:
37+
* You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty
38+
* array.
39+
*
40+
* Follow up:
41+
* Could you solve it in linear time?
42+
*/
43+
/**
44+
*@param {number[]} nums
45+
*@param {number} k
46+
*@return {number[]}
47+
*/
48+
varmaxSlidingWindow=function(nums,k){
49+
// bad 时间复杂度O(n^2)
50+
if(nums.length===0||k===0)return[];
51+
letslideWindow=[];
52+
constret=[];
53+
for(leti=0;i<nums.length-k+1;i++){
54+
for(letj=0;j<k;j++){
55+
slideWindow.push(nums[i+j]);
56+
}
57+
ret.push(Math.max(...slideWindow));
58+
slideWindow=[];
59+
}
60+
returnret;
61+
// 双端队列优化时间复杂度
62+
};

‎todo/str/214.shortest-palindrome.js

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
/*
2+
*@lc app=leetcode id=214 lang=javascript
3+
*
4+
* [214] Shortest Palindrome
5+
*
6+
* https://leetcode.com/problems/shortest-palindrome/description/
7+
*
8+
* algorithms
9+
* Hard (27.15%)
10+
* Total Accepted: 73.1K
11+
* Total Submissions: 266.3K
12+
* Testcase Example: '"aacecaaa"'
13+
*
14+
* Given a string s, you are allowed to convert it to a palindrome by adding
15+
* characters in front of it. Find and return the shortest palindrome you can
16+
* find by performing this transformation.
17+
*
18+
* Example 1:
19+
*
20+
*
21+
* Input: "aacecaaa"
22+
* Output: "aaacecaaa"
23+
*
24+
*
25+
* Example 2:
26+
*
27+
*
28+
* Input: "abcd"
29+
* Output: "dcbabcd"
30+
*/
31+
/**
32+
*@param {string} s
33+
*@return {string}
34+
*/
35+
varshortestPalindrome=function(s){
36+
37+
};
38+
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
/*
2+
*@lc app=leetcode id=5 lang=javascript
3+
*
4+
* [5] Longest Palindromic Substring
5+
*
6+
* https://leetcode.com/problems/longest-palindromic-substring/description/
7+
*
8+
* algorithms
9+
* Medium (26.70%)
10+
* Total Accepted: 525K
11+
* Total Submissions: 1.9M
12+
* Testcase Example: '"babad"'
13+
*
14+
* Given a string s, find the longest palindromic substring in s. You may
15+
* assume that the maximum length of s is 1000.
16+
*
17+
* Example 1:
18+
*
19+
*
20+
* Input: "babad"
21+
* Output: "bab"
22+
* Note: "aba" is also a valid answer.
23+
*
24+
*
25+
* Example 2:
26+
*
27+
*
28+
* Input: "cbbd"
29+
* Output: "bb"
30+
*
31+
*
32+
*/
33+
/**
34+
*@param {string} s
35+
*@return {string}
36+
*/
37+
varlongestPalindrome=function(s){
38+
39+
};
40+

0 commit comments

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