Skip to content

Commit cb16d94

Browse files
tg123tg123
committed
commit changes to gh-pages aug 28
1 parent 8073930 commit cb16d94

File tree

4 files changed

+209
-9
lines changed

4 files changed

+209
-9
lines changed

‎_includes/_root/distinct-subsequences/README.md

+192-2
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

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

10-
throw new RuntimeException();
19+
throw new RuntimeException();
1120
}
12-
}
21+
}

‎distinct-subsequences/index.md

+2-1
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

+1-1
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)