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

Commitc25465e

Browse files
author
luzhipeng
committed
1 parent71ecc82 commitc25465e

11 files changed

+325
-320
lines changed

‎README.en.md

Lines changed: 7 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -128,7 +128,7 @@ The data structures mainly includes:
128128
-[0055.jump-game](./problems/55.jump-game.md) 🆕
129129
-[0062.unique-paths](./problems/62.unique-paths.md)🆕
130130
-[0075.sort-colors](./problems/75.sort-colors.md)
131-
-[0078.subsets](./problems/78.subsets.md)🆕
131+
-[0078.subsets](./problems/78.subsets.md)
132132
-[0086.partition-list](./problems/86.partition-list.md)
133133
-[0090.subsets-ii](./problems/90.subsets-ii.md)
134134
-[0091.decode-ways](./problems/91.decode-ways.md) 🆕
@@ -142,21 +142,23 @@ The data structures mainly includes:
142142
-[0152.maximum-product-subarray](./problems/152.maximum-product-subarray.md) 🆕
143143
-[0199.binary-tree-right-side-view](./problems/199.binary-tree-right-side-view.md)
144144
-[0201.bitwise-and-of-numbers-range](./problems/201.bitwise-and-of-numbers-range.md)
145-
-[0208.implement-trie-prefix-tree](./problems/208.implement-trie-prefix-tree.md) 🆕
145+
-[0208.implement-trie-prefix-tree](./problems/208.implement-trie-prefix-tree.md)
146146
-[0209.minimum-size-subarray-sum](./problems/209.minimum-size-subarray-sum.md) 🖊
147-
-[0236.lowest-common-ancestor-of-a-binary-tree](./problems/236.lowest-common-ancestor-of-a-binary-tree.md)🆕
147+
-[0236.lowest-common-ancestor-of-a-binary-tree](./problems/236.lowest-common-ancestor-of-a-binary-tree.md)
148148
-[0238.product-of-array-except-self](./problems/238.product-of-array-except-self.md) 🆕
149149
-[0240.search-a-2-d-matrix-ii](./problems/240.search-a-2-d-matrix-ii.md)
150150
-[0279.perfect-squares](./problems/279.perfect-squares.md)
151151
-[0309.best-time-to-buy-and-sell-stock-with-cooldown](./problems/309.best-time-to-buy-and-sell-stock-with-cooldown.md) 🆕
152152
-[0322.coin-change](./problems/322.coin-change.md)
153-
-[0334.increasing-triplet-subsequence](./problems/334.increasing-triplet-subsequence.md)
154153
-[0328.odd-even-linked-list](./problems/328.odd-even-linked-list.md)
154+
-[0334.increasing-triplet-subsequence](./problems/334.increasing-triplet-subsequence.md)
155+
-[0365.water-and-jug-problem](./problems/365.water-and-jug-problem.md) 🆕
155156
-[0416.partition-equal-subset-sum](./problems/416.partition-equal-subset-sum.md)
156157
-[0445.add-two-numbers-ii](./problems/445.add-two-numbers-ii.md)
157158
-[0454.4-sum-ii](./problems/454.4-sum-ii.md) 🆕
158-
-[0494.target-sum](./problems/494.target-sum.md) 🆕
159+
-[0494.target-sum](./problems/494.target-sum.md)
159160
-[0518.coin-change-2](./problems/518.coin-change-2.md)
161+
-[0609.find-duplicate-file-in-system](./problems/609.find-duplicate-file-in-system.md) 🆕
160162
-[0875.koko-eating-bananas](./problems/875.koko-eating-bananas.md)
161163
-[0877.stone-game](./problems/877.stone-game.md)
162164
-[0887.super-egg-drop](./problems/887.super-egg-drop.md)
@@ -204,16 +206,6 @@ Latest updated flashcards (only lists the front page):
204206

205207
###Future Plans
206208

207-
-[0494.target-sum](./todo/494.target-sum.js)
208-
209-
-[0609.find-duplicate-file-in-system](./todo/609.find-duplicate-file-in-system.js)
210-
211-
-[0010.regular-expression-matching](./todo/10.regular-expression-matching.js)
212-
213-
-[0309.best-time-to-buy-and-sell-stock-with-cooldown](./todo/309.best-time-to-buy-and-sell-stock-with-cooldown.js)
214-
215-
-[0365.water-and-jug-problem](./todo/365.water-and-jug-problem.js)
216-
217209
-[Complete Anki Flashcards](./assets/anki/)
218210

219211
-[Collection of String Problem](./todo/str/)

‎README.md

Lines changed: 7 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -116,7 +116,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
116116
-[0002. Add Two Numbers](./problems/2.addTwoNumbers.md)
117117
-[0003. Longest Substring Without Repeating Characters](./problems/3.longestSubstringWithoutRepeatingCharacters.md)
118118
-[0011.container-with-most-water](./problems/11.container-with-most-water.md)
119-
-[0015.3-sum](./problems/15.3-sum.md) 🆕
119+
-[0015.3-sum](./problems/15.3-sum.md)
120120
-[0019. Remove Nth Node From End of List](./problems/19.removeNthNodeFromEndofList.md)
121121
-[0024. Swap Nodes In Pairs](./problems/24.swapNodesInPairs.md)
122122
-[0039.combination-sum](./problems/39.combination-sum.md)
@@ -126,7 +126,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
126126
-[0055.jump-game](./problems/55.jump-game.md) 🆕
127127
-[0062.unique-paths](./problems/62.unique-paths.md)🆕
128128
-[0075.sort-colors](./problems/75.sort-colors.md)
129-
-[0078.subsets](./problems/78.subsets.md) 🆕
129+
-[0078.subsets](./problems/78.subsets.md)
130130
-[0086.partition-list](./problems/86.partition-list.md)
131131
-[0090.subsets-ii](./problems/90.subsets-ii.md)
132132
-[0091.decode-ways](./problems/91.decode-ways.md) 🆕
@@ -140,21 +140,23 @@ leetcode 题解，记录自己的 leetcode 解题之路。
140140
-[0152.maximum-product-subarray](./problems/152.maximum-product-subarray.md) 🆕
141141
-[0199.binary-tree-right-side-view](./problems/199.binary-tree-right-side-view.md)
142142
-[0201.bitwise-and-of-numbers-range](./problems/201.bitwise-and-of-numbers-range.md)
143-
-[0208.implement-trie-prefix-tree](./problems/208.implement-trie-prefix-tree.md) 🆕
143+
-[0208.implement-trie-prefix-tree](./problems/208.implement-trie-prefix-tree.md)
144144
-[0209.minimum-size-subarray-sum](./problems/209.minimum-size-subarray-sum.md) 🖊
145145
-[0236.lowest-common-ancestor-of-a-binary-tree](./problems/236.lowest-common-ancestor-of-a-binary-tree.md)🆕
146146
-[0238.product-of-array-except-self](./problems/238.product-of-array-except-self.md) 🆕
147147
-[0240.search-a-2-d-matrix-ii](./problems/240.search-a-2-d-matrix-ii.md)
148148
-[0279.perfect-squares](./problems/279.perfect-squares.md)
149149
-[0309.best-time-to-buy-and-sell-stock-with-cooldown](./problems/309.best-time-to-buy-and-sell-stock-with-cooldown.md) 🆕
150150
-[0322.coin-change](./problems/322.coin-change.md)
151-
-[0334.increasing-triplet-subsequence](./problems/334.increasing-triplet-subsequence.md)
152151
-[0328.odd-even-linked-list](./problems/328.odd-even-linked-list.md)
152+
-[0334.increasing-triplet-subsequence](./problems/334.increasing-triplet-subsequence.md)
153+
-[0365.water-and-jug-problem](./problems/365.water-and-jug-problem.md) 🆕
153154
-[0416.partition-equal-subset-sum](./problems/416.partition-equal-subset-sum.md)
154155
-[0445.add-two-numbers-ii](./problems/445.add-two-numbers-ii.md)
155156
-[0454.4-sum-ii](./problems/454.4-sum-ii.md) 🆕
156-
-[0494.target-sum](./problems/494.target-sum.md) 🆕
157+
-[0494.target-sum](./problems/494.target-sum.md)
157158
-[0518.coin-change-2](./problems/518.coin-change-2.md)
159+
-[0609.find-duplicate-file-in-system](./problems/609.find-duplicate-file-in-system.md) 🆕
158160
-[0875.koko-eating-bananas](./problems/875.koko-eating-bananas.md)
159161
-[0877.stone-game](./problems/877.stone-game.md)
160162
-[0887.super-egg-drop](./problems/887.super-egg-drop.md)
@@ -200,16 +202,6 @@ anki - 文件 - 导入 - 下拉格式选择“打包的 anki集合”，然后
200202

201203
###计划
202204

203-
-[0494.target-sum](./todo/494.target-sum.js)
204-
205-
-[0609.find-duplicate-file-in-system](./todo/609.find-duplicate-file-in-system.js)
206-
207-
-[0010.regular-expression-matching](./todo/10.regular-expression-matching.js)
208-
209-
-[0309.best-time-to-buy-and-sell-stock-with-cooldown](./todo/309.best-time-to-buy-and-sell-stock-with-cooldown.js)
210-
211-
-[0365.water-and-jug-problem](./todo/365.water-and-jug-problem.js)
212-
213205
-[anki 卡片 完善](./assets/anki/)
214206

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

‎backlog/326.power-of-three.js

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -46,6 +46,7 @@
4646
*@return {boolean}
4747
*/
4848
varisPowerOfThree=function(n){
49+
// tag: 数论
4950
// let i = 0;
5051
// while(Math.pow(3, i) < n) {
5152
// i++;
@@ -55,3 +56,4 @@ var isPowerOfThree = function(n) {
5556
// 巧用整除
5657
returnn>0&&Math.pow(3,19)%n===0;
5758
};
59+
// 扩展： 这个方法可以扩展到任意质数，合数则不行

‎problems/365.water-and-jug-problem.md

Lines changed: 123 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,123 @@
1+
2+
##题目地址
3+
https://leetcode.com/problems/water-and-jug-problem/description/
4+
5+
##题目描述
6+
7+
```
8+
You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.
9+
10+
If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.
11+
12+
Operations allowed:
13+
14+
Fill any of the jugs completely with water.
15+
Empty any of the jugs.
16+
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.
17+
Example 1: (From the famous "Die Hard" example)
18+
19+
Input: x = 3, y = 5, z = 4
20+
Output: True
21+
Example 2:
22+
23+
Input: x = 2, y = 6, z = 5
24+
Output: False
25+
26+
```
27+
28+
##思路
29+
30+
这是一道关于`数论`的题目，确切地说是关于`裴蜀定理`（英语：Bézout's identity）的题目。
31+
32+
摘自wiki的定义：
33+
34+
```
35+
对任意两个整数 a、b，设 d是它们的最大公约数。那么关于未知数 x和 y的线性丢番图方程（称为裴蜀等式）：
36+
37+
ax+by=m
38+
39+
有整数解 (x,y) 当且仅当 m是 d的整数倍。裴蜀等式有解时必然有无穷多个解。
40+
41+
```
42+
43+
因此这道题可以完全转化为`裴蜀定理`。
44+
45+
##关键点解析
46+
47+
- 数论
48+
- 裴蜀定理
49+
50+
##代码
51+
```js
52+
53+
54+
/*
55+
* @lc app=leetcode id=365 lang=javascript
56+
*
57+
* [365] Water and Jug Problem
58+
*
59+
* https://leetcode.com/problems/water-and-jug-problem/description/
60+
*
61+
* algorithms
62+
* Medium (28.76%)
63+
* Total Accepted: 27K
64+
* Total Submissions: 93.7K
65+
* Testcase Example: '3\n5\n4'
66+
*
67+
* You are given two jugs with capacities x and y litres. There is an infinite
68+
* amount of water supply available. You need to determine whether it is
69+
* possible to measure exactly z litres using these two jugs.
70+
*
71+
* If z liters of water is measurable, you must have z liters of water
72+
* contained within one or both buckets by the end.
73+
*
74+
* Operations allowed:
75+
*
76+
*
77+
* Fill any of the jugs completely with water.
78+
* Empty any of the jugs.
79+
* Pour water from one jug into another till the other jug is completely full
80+
* or the first jug itself is empty.
81+
*
82+
*
83+
* Example 1: (From the famous "Die Hard" example)
84+
*
85+
*
86+
* Input: x = 3, y = 5, z = 4
87+
* Output: True
88+
*
89+
*
90+
* Example 2:
91+
*
92+
*
93+
* Input: x = 2, y = 6, z = 5
94+
* Output: False
95+
*
96+
*/
97+
/**
98+
*@param{number}x
99+
*@param{number}y
100+
*@param{number}z
101+
*@return{boolean}
102+
*/
103+
varcanMeasureWater=function(x,y,z) {
104+
if (x+ y< z)returnfalse;
105+
106+
if (z===0)returntrue;
107+
108+
if (x===0)return y=== z;
109+
110+
if (y===0)return x=== z;
111+
112+
functionGCD(a,b) {
113+
let min=Math.min(a, b);
114+
while (min) {
115+
if (a% min===0&& b% min===0)return min;
116+
min--;
117+
}
118+
return1;
119+
}
120+
121+
return z%GCD(x, y)===0;
122+
};
123+
```

‎problems/494.target-sum.md

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -54,7 +54,7 @@ target的总数一共有多少种，这是一道我们之前做过的题目，
5454
##关键点解析
5555

5656
- 对元素进行分组，分组的依据是符号， 是`+` 或者`-`
57-
- 通过数学公式推导可以简化我们的求解过程，这需要一点`数学知识和数学意志`
57+
- 通过数学公式推导可以简化我们的求解过程，这需要一点`数学知识和数学意识`
5858

5959
##代码
6060
```js
@@ -132,3 +132,7 @@ var findTargetSumWays = function(nums, S) {
132132
returnsumCount(nums, (S+ sum)>>1);
133133
};
134134
```
135+
136+
##扩展
137+
138+
如果这道题目并没有限定所有的元素以及target都是正数怎么办？

0 commit comments

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