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

Commitcb16d94

Browse files
committed
commit changes to gh-pages aug 28
1 parent8073930 commitcb16d94

File tree

4 files changed

+209
-9
lines changed

4 files changed

+209
-9
lines changed
Lines changed: 192 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,194 @@
1+
##Guessing
2+
3+
Lets start with`rabbbit` and`rabbit`.
4+
5+
To make the problem easier, start from one char,`distinct subsequences` of`rabbbit` and`r`.
6+
7+
`distinct subsequences` below, by eyeball:
8+
9+
*`r` and`r` has 1`distinct subsequences`
10+
*`a` and`r` has 0`distinct subsequences`
11+
12+
These two are easy to be understood.
13+
14+
*`ra` and`r` has 1`distinct subsequences`
15+
*`rab` and`r` has 1`distinct subsequences`
16+
*`rabbbbbbbbbbbb` and`r` has 1`distinct subsequences`
17+
18+
These three show that`r` plus any junk chars will not change`distinct subsequences`
19+
20+
*`rr` and`r` has 2`distinct subsequences`
21+
*`rar` and`r` has 2`distinct subsequences`
22+
*`rara` and`r` has 2`distinct subsequences`
23+
*`rarar` and`r` has 3`distinct subsequences`
24+
25+
`rar` and`r` is same as`rr` and`r`, because`a` there has nothing to do with the number of`distinct subsequences`, it is a junk like above.
26+
27+
In another word,`rar` and`r` can be converted to`ra` +`r` and`r`, that is`1 + 1`.
28+
29+
###Put them into table
30+
31+
the value`P[i][j]` means that`S[0..i]` and`T[0..j]` has`P[i][j]``distinct subsequences`.
32+
33+
the table with only one char
34+
35+
```
36+
+---+---+---+---+---+---+---+---+
37+
| | r | a | b | b | b | i | t |
38+
+---+---+---+---+---+---+---+---+
39+
| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
40+
+---+---+---+---+---+---+---+---+
41+
```
42+
43+
Enlarge the table
44+
45+
46+
```
47+
+---+---+---+---+---+---+---+---+
48+
| | r | a | b | b | b | i | t |
49+
+---+---+---+---+---+---+---+---+
50+
| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
51+
+---+---+---+---+---+---+---+---+
52+
| a | | | | | | | |
53+
+---+---+---+---+---+---+---+---+
54+
| b | | | | | | | |
55+
+---+---+---+---+---+---+---+---+
56+
| b | | | | | | | |
57+
+---+---+---+---+---+---+---+---+
58+
| i | | | | | | | |
59+
+---+---+---+---+---+---+---+---+
60+
| t | | | | | | | |
61+
+---+---+---+---+---+---+---+---+
62+
```
63+
64+
Some grids here are easy to be filled, the grids which`j > i`.
65+
That is, T is longer than S, there will be no`distinct subsequences`.
66+
67+
```
68+
+---+---+---+---+---+---+---+---+
69+
| | r | a | b | b | b | i | t |
70+
+---+---+---+---+---+---+---+---+
71+
| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
72+
+---+---+---+---+---+---+---+---+
73+
| a | 0 | | | | | | |
74+
+---+---+---+---+---+---+---+---+
75+
| b | 0 | 0 | | | | | |
76+
+---+---+---+---+---+---+---+---+
77+
| b | 0 | 0 | 0 | | | | |
78+
+---+---+---+---+---+---+---+---+
79+
| i | 0 | 0 | 0 | 0 | | | |
80+
+---+---+---+---+---+---+---+---+
81+
| t | 0 | 0 | 0 | 0 | 0 | | |
82+
+---+---+---+---+---+---+---+---+
83+
```
84+
85+
`j == i` grids are easy too, the S and T must be the same if it wants to have 1`distinct subsequences`.
86+
87+
```
88+
+---+---+---+---+---+---+---+---+
89+
| | r | a | b | b | b | i | t |
90+
+---+---+---+---+---+---+---+---+
91+
| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
92+
+---+---+---+---+---+---+---+---+
93+
| a | 0 | 1 | | | | | |
94+
+---+---+---+---+---+---+---+---+
95+
| b | 0 | 0 | 1 | | | | |
96+
+---+---+---+---+---+---+---+---+
97+
| b | 0 | 0 | 0 | 1 | | | |
98+
+---+---+---+---+---+---+---+---+
99+
| i | 0 | 0 | 0 | 0 | 0 | | |
100+
+---+---+---+---+---+---+---+---+
101+
| t | 0 | 0 | 0 | 0 | 0 | 0 | |
102+
+---+---+---+---+---+---+---+---+
103+
```
104+
105+
This pictrue is just encouraging you, as there is only a few grids left to be filled.
106+
107+
###`rab` and`ra`
108+
109+
This problem looks familiar. It is the`ra` and`r`.
110+
111+
as`b` is a junk char,`rab` should have the same number as`ra` and`ra`.
112+
113+
Then the table is like
114+
115+
```
116+
+---+---+---+---+---+---+---+---+
117+
| | r | a | b | b | b | i | t |
118+
+---+---+---+---+---+---+---+---+
119+
| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
120+
+---+---+---+---+---+---+---+---+
121+
| a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
122+
+---+---+---+---+---+---+---+---+
123+
| b | 0 | 0 | 1 | | | | |
124+
+---+---+---+---+---+---+---+---+
125+
| b | 0 | 0 | 0 | 1 | | | |
126+
+---+---+---+---+---+---+---+---+
127+
| i | 0 | 0 | 0 | 0 | 0 | | |
128+
+---+---+---+---+---+---+---+---+
129+
| t | 0 | 0 | 0 | 0 | 0 | 0 | |
130+
+---+---+---+---+---+---+---+---+
131+
```
132+
133+
###`rabb` and`rab`
134+
135+
This time, add a new`b` to both`rab` and`ra`.
136+
137+
####Use the new`b` in subsequences
138+
139+
This time they have same letter,`b` , at the end. It is not a junk.
140+
141+
This time, remove`b` from both S and T, then they become`rab` and`ra`.
142+
143+
that is, this will take`rab` and`ra``distinct subsequences`.
144+
145+
####Dont use the new`b`
146+
147+
Treat`b` as junk, it has`rab` and`rab``distinct subsequences`.
148+
149+
150+
####Sum up two choices
151+
152+
Use or not will result two set of`distinct subsequences`, so sum them up.
153+
154+
`rabb` and`rab` =`rab` and`ra` +`rab` and`rab`.
155+
156+
```
157+
+---+---+---+---+---+---+---+---+
158+
| | r | a | b | b | b | i | t |
159+
+---+---+---+---+---+---+---+---+
160+
| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
161+
+---+---+---+---+---+---+---+---+
162+
| a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
163+
+---+---+---+---+---+---+---+---+
164+
| b | 0 | 0 | 1 | 2 | | | |
165+
+---+---+---+---+---+---+---+---+
166+
| b | 0 | 0 | 0 | 1 | | | |
167+
+---+---+---+---+---+---+---+---+
168+
| i | 0 | 0 | 0 | 0 | 0 | | |
169+
+---+---+---+---+---+---+---+---+
170+
| t | 0 | 0 | 0 | 0 | 0 | 0 | |
171+
+---+---+---+---+---+---+---+---+
172+
```
173+
174+
##General form
175+
176+
the grid`P[i][j]` has 1 choice when`S[i] != T[j]`, this only adds some junk chars.
177+
178+
```
179+
P[i][j] = P[i - 1][j]
180+
```
181+
182+
the grid`P[i][j]` has 2 choice when`S[i] == T[j]`
183+
184+
```
185+
P[i][j] =
186+
P[i - 1][j] // adds as junk chars.
187+
+
188+
P[i - 1][j - 1] // use the new char in the new subsequence
189+
190+
```
191+
192+
Fill up the table and the bottom right grid is the answer.
1193

2-
##TODO
3-
* write down thinking
4194

‎_includes/_root/two-sum/Solution.java

Lines changed: 14 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,21 @@
11
publicclassSolution {
22
publicint[]twoSum(int[]numbers,inttarget) {
3-
// Note: The Solution object is instantiated only once and is reused by each test case.
3+
4+
HashMap<Integer,Integer>m =newHashMap<Integer,Integer>();
5+
6+
for(inti =0;i <numbers.length;i++){
7+
m.put(target -numbers[i],i);
8+
}
9+
410
for(inti =0;i <numbers.length;i++){
5-
for(intj =i +1 ;j <numbers.length;j++){
6-
if (numbers[i] +numbers[j] ==target)returnnewint[]{i +1,j +1};
11+
12+
Integerv =m.get(numbers[i]);
13+
14+
if(v !=null &&v !=i){
15+
returnnewint[]{i +1,v +1};
716
}
817
}
918

10-
thrownewRuntimeException();
19+
thrownewRuntimeException();
1120
}
12-
}
21+
}

‎distinct-subsequences/index.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,8 @@
11
---
22
layout:solution
33
title:Distinct Subsequences
4-
date:2014-07-23 02:42:48 +0800
4+
date:2014-08-28 01:16:24 +0800
5+
eaten:true
56
---
67
{% assign leetcode_name = {{page.path | remove: '/index.md'}} %}
78
{% assign leetcode_readme = {{leetcode_name | append: '/README.md' | prepend: '_root/' }} %}

‎two-sum/index.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
---
22
layout:solution
33
title:Two Sum
4-
date:2014-07-31 12:15:46 +0800
4+
date:2014-08-27 11:53:26 +0800
55
eaten:true
66
---
77
{% assign leetcode_name = {{page.path | remove: '/index.md'}} %}

0 commit comments

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