Skip to content

Commit f0a58b6

Browse files
awangdevawangdev
committed
.
1 parent d70ff0b commit f0a58b6

8 files changed

+590
-990
lines changed

‎Java/Delete Digits.java

100644100755
Lines changed: 14 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,11 @@
1+
M
2+
3+
数位靠前的，权值更大. 所以硬来把靠前的相对更大的（跟following digit相比）去掉。
4+
5+
```
16
/*
2-
Given string A representative a positive integer which has N digits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer.
7+
Given string A representative a positive integer which has N digits, remove any k digits of the number,
8+
the remaining digits are arranged according to the original order to become a new positive integer.
39
410
Find the smallest integer after remove k digits.
511
@@ -13,6 +19,10 @@
1319
Tags Expand
1420
Greedy LintCode Copyright
1521
22+
*/
23+
24+
/*
25+
1626
Attempt2,Thoughts:
1727
loop k times: each interation, find one digit to remove
1828
Rules: want to remove whatever digit at A[i] that's A[i] > A[i+1].
@@ -21,14 +31,9 @@ Well... thinking straight (attempt2) seems much easier to understand and to code
2131
2232
Note:
2333
remember to remove the prefixing 0's
24-
*/
2534
35+
*/
2636
public class Solution {
27-
/**
28-
*@param A: A positive integer which has N digits, A is a string.
29-
*@param k: Remove k digits.
30-
*@return: A string
31-
*/
3237
public String DeleteDigits(String A, int k) {
3338
if (A == null || A.length() == 0 || k == 0) {
3439
return A;
@@ -112,3 +117,5 @@ public static String DeleteDigits(String A, int k) {
112117
}
113118

114119
}
120+
121+
```

‎Java/Delete Node in the Middle of Singly Linked List.java

100644100755
Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,8 @@
1+
E
2+
3+
Just do it. Link curr.next to curr.next.next
4+
5+
```
16
/*
27
Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.
38
@@ -32,9 +37,11 @@ public class Solution {
3237
*/
3338
public void deleteNode(ListNode node) {
3439
if (node == null) {
35-
return;
40+
return;
3641
}
3742
node.val = node.next.val;
3843
node.next = node.next.next;
3944
}
4045
}
46+
47+
```

‎Java/Distinct Subsequences.java

100644100755
Lines changed: 57 additions & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,14 @@
1+
H
2+
3+
Not Done
4+
5+
```
16
/*
27
Given a string S and a string T, count the number of distinct subsequences of T in S.
38
4-
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
9+
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none)
10+
of the characters without disturbing the relative positions of the remaining characters.
11+
(ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
512
613
Example
714
Given S = "rabbbit", T = "rabbit", return 3.
@@ -18,29 +25,29 @@ Do it in O(n2) time and O(n) memory.
1825
Attempt2:
1926
Use DP. Okay, first I had no idea how to start, but here is a reference: http://blog.csdn.net/abcbc/article/details/8978146
2027
First of all, Map out the number of existance of T in S in a 2D map:
21-
0 1 2 3 4 5 6 7
22-
---------------
23-
r a b b b i t
24-
0| 1 1 1 1 1 1 1 1
25-
1| r 0 1 1 1 1 1 1 1
26-
2| a 0 0 1 1 1 1 1 1
27-
3| b 0 0 0 1 2 3 3 3
28-
4| b 0 0 0 0 1 3 3 3
29-
5| i 0 0 0 0 0 0 3 3
30-
6| t 0 0 0 0 0 0 0 3
28+
0 1 2 3 4 5 6 7
29+
---------------
30+
r a b b b i t
31+
0| 1 1 1 1 1 1 1 1
32+
1| r 0 1 1 1 1 1 1 1
33+
2| a 0 0 1 1 1 1 1 1
34+
3| b 0 0 0 1 2 3 3 3
35+
4| b 0 0 0 0 1 3 3 3
36+
5| i 0 0 0 0 0 0 3 3
37+
6| t 0 0 0 0 0 0 0 3
3138
3239
Use DP[T][S]. We realize:
3340
1.DP[0][0] == 1; //Both null can be a match
3441
2.DP[0][1 ~ S.length - 1] = 1;//First fow, when T=="", whatever S will have 1 subsequence: ""
3542
3.DP[1 ~ T.length][0] = 0;// First column, when S=="", whatever T will not be subsequence of S == ""
3643
4.When looking at each row and filling out the pixels, we realize when T exist in S[a~b], it will surely exist in S[a~b+1], taht is:
37-
Step1: DP[i][j] is at least equal to DP[i][j - 1];//DP[i][j] is always based on DP[i][j-1], so DP[i][j] = DP[i][j+1] + something
38-
Step2: So, what's that 'something' in step1? For example, look at T[3] == 'b' against S[0 ~ 3]:
39-
S[0 ~ 3] has 1 'b' at S[3], and also, T[0~3] == S[0~3], that's a perfect match. SO DP[3][3] = 1
40-
S[0 ~ 4] has 2 'b' at S[3] and S[4]. Now imagine we pick either S[3] or S[4] to genreate T[0~3] out of S[0~4]: we have 2 possibilities.D[3][4] = 2
41-
Consider: D[i][j] means we picked S[j]; in our S[0 ~ 4] case, that means we picked S[4] but skipped S[3], though S[3] still counts towards another situation where we skipped S[4].
42-
After all, we will count whatever that we skipped into our current DP[i][j], that is DP[i][j] += T[i - 1] == S[j - 1] ? DP[i - 1][j - 1] : 0;
43-
Conclusion: while we for-looping through each row, if we find out S[j] and S[j - 1] both equals to T[i - 1], we want to make sure we count D[i - 1][j -1]'s previous records in!
44+
Step1: DP[i][j] is at least equal to DP[i][j - 1];//DP[i][j] is always based on DP[i][j-1], so DP[i][j] = DP[i][j+1] + something
45+
Step2: So, what's that 'something' in step1? For example, look at T[3] == 'b' against S[0 ~ 3]:
46+
S[0 ~ 3] has 1 'b' at S[3], and also, T[0~3] == S[0~3], that's a perfect match. SO DP[3][3] = 1
47+
S[0 ~ 4] has 2 'b' at S[3] and S[4]. Now imagine we pick either S[3] or S[4] to genreate T[0~3] out of S[0~4]: we have 2 possibilities.D[3][4] = 2
48+
Consider: D[i][j] means we picked S[j]; in our S[0 ~ 4] case, that means we picked S[4] but skipped S[3], though S[3] still counts towards another situation where we skipped S[4].
49+
After all, we will count whatever that we skipped into our current DP[i][j], that is DP[i][j] += T[i - 1] == S[j - 1] ? DP[i - 1][j - 1] : 0;
50+
Conclusion: while we for-looping through each row, if we find out S[j] and S[j - 1] both equals to T[i - 1], we want to make sure we count D[i - 1][j -1]'s previous records in!
4451
4552
Note:
4653
In double for loop, set i,j <= xxxx.length(), since we've increased the 2D array by 1 block on row and col.
@@ -53,23 +60,23 @@ public class Solution {
5360
* @return: Count the number of distinct subsequences
5461
*/
5562
public int numDistinct(String S, String T) {
56-
int[][] DP = new int[T.length() + 1][S.length() + 1];
57-
DP[0][0] = 1;
58-
for(int i = 1; i < S.length(); i++) {
59-
DP[0][i] = 1;
60-
}
61-
for (int i = 1; i < T.length(); i++) {
62-
DP[i][0] = 0;
63-
}
64-
for (int i = 1; i <= T.length(); i++) {
65-
for (int j = 1; j <= S.length(); j++){
66-
DP[i][j] = DP[i][j - 1];
67-
if (T.charAt(i - 1) == S.charAt(j - 1)) {
68-
DP[i][j] += DP[i - 1][j - 1];
69-
}
70-
}
71-
}
72-
return DP[T.length()][S.length()];
63+
int[][] DP = new int[T.length() + 1][S.length() + 1];
64+
DP[0][0] = 1;
65+
for(int i = 1; i < S.length(); i++) {
66+
DP[0][i] = 1;
67+
}
68+
for (int i = 1; i < T.length(); i++) {
69+
DP[i][0] = 0;
70+
}
71+
for (int i = 1; i <= T.length(); i++) {
72+
for (int j = 1; j <= S.length(); j++){
73+
DP[i][j] = DP[i][j - 1];
74+
if (T.charAt(i - 1) == S.charAt(j - 1)) {
75+
DP[i][j] += DP[i - 1][j - 1];
76+
}
77+
}
78+
}
79+
return DP[T.length()][S.length()];
7380
}
7481
}
7582

@@ -81,19 +88,19 @@ public int numDistinct(String S, String T) {
8188
*/
8289
public class Solution {
8390
public int numDistinct(String S, String T) {
84-
if (S.length() == 0) {
85-
return T.length() == 0 ? 1 : 0;
86-
}
87-
if (T.length() == 0) {
88-
return 1;
89-
}
90-
int count = 0;
91-
for (int i = 0; i < S.length(); i++) {
92-
if (S.charAt(i) == T.charAt(0)) {
93-
count += numDistinct(S.substring(i + 1), T.substring(1));
94-
}
95-
}
96-
return count;
91+
if (S.length() == 0) {
92+
return T.length() == 0 ? 1 : 0;
93+
}
94+
if (T.length() == 0) {
95+
return 1;
96+
}
97+
int count = 0;
98+
for (int i = 0; i < S.length(); i++) {
99+
if (S.charAt(i) == T.charAt(0)) {
100+
count += numDistinct(S.substring(i + 1), T.substring(1));
101+
}
102+
}
103+
return count;
97104
}
98105
}
99106

@@ -107,4 +114,5 @@ public int numDistinct(String S, String T) {
107114
However, time cost on this:
108115
For example I have n missing chars from S.length == m. so I have (m + 1) places where i can insert the n chars. Then it's a mCn problem. This goes up to m!, too much. Not applicapable.
109116
110-
*/
117+
*/
118+
```

‎Java/Easy Reverse Linked List.java

Lines changed: 0 additions & 61 deletions
This file was deleted.

‎Java/Edit Distance.java

100644100755
Lines changed: 9 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,11 @@
1+
M
2+
3+
Not Done
4+
5+
```
16
/*
2-
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
7+
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2.
8+
(each operation is counted as 1 step.)
39
410
You have the following 3 operations permitted on a word:
511
@@ -27,10 +33,6 @@ DP[i][j] means the steps (edit distance) to take to transfer word1[0 ~ i] to wor
2733

2834

2935
public class Solution {
30-
/**
31-
* @param word1 & word2: Two string.
32-
* @return: The minimum number of steps.
33-
*/
3436
public int minDistance(String word1, String word2) {
3537
if (word1 == null && word2 != null) {
3638
return word2.length();
@@ -56,3 +58,5 @@ public int minDistance(String word1, String word2) {
5658
return DP[word1.length()][word2.length()];
5759
}
5860
}
61+
62+
```

0 commit comments

Comments
 (0)