Skip to content

Commit 540738b

Browse files
haoelhaoel
committed
Add comments to explain the solutions
1 parent 55b0a2b commit 540738b

File tree

14 files changed

+212
-34
lines changed

14 files changed

+212
-34
lines changed

‎src/editDistance/editDistance.cpp

Lines changed: 64 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -22,29 +22,87 @@
2222
#include <algorithm>
2323
using namespace std;
2424

25+
26+
/*
27+
* Dynamic Programming
28+
*
29+
* Definitaion
30+
*
31+
* m[i][j] is minimal distance from word1[0..i] to word2[0..j]
32+
*
33+
* So,
34+
*
35+
* 1) if word1[i] == word2[j], then m[i][j] == m[i-1][j-1].
36+
*
37+
* 2) if word1[i] != word2[j], then we need to find which one below is minimal:
38+
*
39+
* min( m[i-1][j-1], m[i-1][j], m[i][j-1] )
40+
*
41+
* and +1 - current char need be changed.
42+
*
43+
* Let's take a look m[1][2] : "a" => "ab"
44+
*
45+
* +---+ +---+
46+
* ''=> a | 1 | | 2 | '' => ab
47+
* +---+ +---+
48+
*
49+
* +---+ +---+
50+
* a => a | 0 | | 1 | a => ab
51+
* +---+ +---+
52+
*
53+
* To know the minimal distance `a => ab`, we can get it from one of the following cases:
54+
*
55+
* 1) delete the last char in word1, minDistance( '' => ab ) + 1
56+
* 2) delete the last char in word2, minDistance( a => a ) + 1
57+
* 3) change the last char, minDistance( '' => a ) + 1
58+
*
59+
*
60+
* For Example:
61+
*
62+
* word1="abb", word2="abccb"
63+
*
64+
* 1) Initialize the DP matrix as below:
65+
*
66+
* "" a b c c b
67+
* "" 0 1 2 3 4 5
68+
* a 1
69+
* b 2
70+
* b 3
71+
*
72+
* 2) Dynamic Programming
73+
*
74+
* "" a b c c b
75+
* "" 0 1 2 3 4 5
76+
* a 1 0 1 2 3 4
77+
* b 2 1 0 1 2 3
78+
* b 3 2 1 1 1 2
79+
*
80+
*/
81+
int min(int x, int y, int z) {
82+
return std::min(x, std::min(y,z));
83+
}
84+
2585
int minDistance(string word1, string word2) {
2686
int n1 = word1.size();
2787
int n2 = word2.size();
2888
if (n1==0) return n2;
2989
if (n2==0) return n1;
30-
vector< vector<int> > m(n1+1);
90+
vector< vector<int> > m(n1+1, vector<int>(n2+1));
3191
for(int i=0; i<m.size(); i++){
32-
vector<int> r(n2+1);
33-
r[0] = i;
34-
m[i] = r;
92+
m[i][0] = i;
3593
}
3694
for (int i=0; i<m[0].size(); i++) {
3795
m[0][i]=i;
3896
}
3997

4098
//Dynamic Programming
99+
int row, col;
41100
for (row=1; row<m.size(); row++) {
42101
for(col=1; col<m[row].size(); col++){
43102
if (word1[row-1] == word2[col-1] ){
44103
m[row][col] = m[row-1][col-1];
45104
}else{
46-
int minValue = min(m[row-1][col-1], m[row-1][col]);
47-
minValue = min(minValue, m[row][col-1]);
105+
int minValue = min(m[row-1][col-1], m[row-1][col], m[row][col-1]);
48106
m[row][col] = minValue + 1;
49107
}
50108
}

‎src/firstMissingPositive/firstMissingPositive.cpp

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,22 @@ using namespace std;
2121

2222
#define INT_MAX 2147483647
2323

24+
/*
25+
* The idea is simple:
26+
*
27+
* 1) put all of number into a map.
28+
* 2) for each number a[i] in array, remove its continous number in the map
29+
* 2.1) remove ... a[i]-3, a[i]-2, a[i]-1, a[i]
30+
* 2.2) remove a[i]+1, a[i]+2, a[i]+3,...
31+
* 3) during the removeing process, if some number cannot be found, which means it's missed.
32+
*
33+
* considering a case [-2, -1, 4,5,6],
34+
* [-2, -1] => missed 0
35+
* [4,5,6] => missed 3
36+
*
37+
* However, we missed 1, so, we have to add dummy number 0 whatever.
38+
*
39+
*/
2440
int firstMissingPositive(int A[], int n) {
2541
map<int, int> cache;
2642
for(int i=0; i<n; i++){
@@ -47,12 +63,14 @@ int firstMissingPositive(int A[], int n) {
4763
}
4864

4965
int num ;
66+
// remove the ... x-3, x-2, x-1, x
5067
for( num=x; cache.find(num)!=cache.end(); num--){
5168
cache.erase(cache.find(num));
5269
}
5370
if ( num>0 && num < miss ){
5471
miss = num;
5572
}
73+
// remove the x+1, x+2, x+3 ...
5674
for ( num=x+1; cache.find(num)!=cache.end(); num++){
5775
cache.erase(cache.find(num));
5876
}

‎src/insertInterval/insertInterval.cpp

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -31,6 +31,7 @@ struct Interval {
3131
Interval(int s, int e) : start(s), end(e) {}
3232
};
3333

34+
//Two factors sorting [start:end]
3435
bool compare(const Interval& lhs, const Interval& rhs){
3536
return (lhs.start==rhs.start) ? lhs.end < rhs.end : lhs.start < rhs.start;
3637
}
@@ -40,10 +41,12 @@ vector<Interval> merge(vector<Interval> &intervals) {
4041
vector<Interval> result;
4142

4243
if (intervals.size() <= 0) return result;
43-
44+
//sort the inervals. Note: using the customized comparing function.
4445
sort(intervals.begin(), intervals.end(), compare);
4546
for(int i=0; i<intervals.size(); i++) {
4647
int size = result.size();
48+
// if the current intervals[i] is overlapped with previous interval.
49+
// merge them together
4750
if( size>0 && result[size-1].end >= intervals[i].start) {
4851
result[size-1].end = max(result[size-1].end, intervals[i].end);
4952
}else{
@@ -54,6 +57,7 @@ vector<Interval> merge(vector<Interval> &intervals) {
5457
return result;
5558
}
5659

60+
//just reuse the solution of "Merge Intervals", quite straight forward
5761
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
5862

5963
intervals.push_back(newInterval);

‎src/jumpGame/jumpGame.II.cpp

Lines changed: 12 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@
2222
#include <iostream>
2323
using namespace std;
2424

25+
//Acutally, using the Greedy algorithm can have the answer
2526
int jump(int A[], int n) {
2627
if (n<=1) return 0;
2728

@@ -36,9 +37,10 @@ int jump(int A[], int n) {
3637
if (coverPos >= n-1){
3738
return steps;
3839
}
40+
//Greedy: find the next place which can have biggest distance
3941
int nextPos=0;
4042
int maxDistance=0;
41-
for(int j=i+1; j<=A[i]+i; j++){
43+
for(int j=i+1; j<=coverPos; j++){
4244
if ( A[j]+j > maxDistance ) {
4345
maxDistance = A[j]+j;
4446
nextPos = j;
@@ -59,7 +61,7 @@ void printArray(int a[], int n){
5961
}
6062
int main()
6163
{
62-
#define TEST(a) printArray(a, sizeof(a)/sizeof(int)); cout<<jump(a, sizeof(a)/sizeof(int))<<endl;
64+
#define TEST(a) printArray(a, sizeof(a)/sizeof(a[0])); cout<<jump(a, sizeof(a)/sizeof(a[0]))<<endl;
6365

6466
int a1[]={0};
6567
TEST(a1);
@@ -76,5 +78,13 @@ int main()
7678
int a5[]={1,2,3};
7779
TEST(a5);
7880

81+
// 0 -> 1 -> 4 -> end
82+
int a6[]={2,3,1,1,4,0,1};
83+
TEST(a6);
84+
85+
// 0 -> 1 -> 3 -> end
86+
int a7[]={2,3,1,2,0,1};
87+
TEST(a7);
88+
7989
return 0;
8090
}

‎src/jumpGame/jumpGame.cpp

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,9 @@ class Solution {
2323
bool canJump(int A[], int n) {
2424
if (n<=0) return false;
2525

26+
// the basic idea is traverse array, maintain the most far can go
2627
int coverPos=0;
28+
// the condition i<=coverPos means traverse all of covered position
2729
for(int i=0; i<=coverPos && i<n; i++){
2830

2931
if (coverPos < A[i] + i){

‎src/mergeIntervals/mergeIntervals.cpp

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@ struct Interval {
2525
Interval(int s, int e) : start(s), end(e) {}
2626
};
2727

28+
//Two factos sorting [start:end]
2829
bool compare(const Interval& lhs, const Interval& rhs){
2930
return (lhs.start==rhs.start) ? lhs.end < rhs.end : lhs.start < rhs.start;
3031
}
@@ -34,10 +35,12 @@ vector<Interval> merge(vector<Interval> &intervals) {
3435
vector<Interval> result;
3536

3637
if (intervals.size() <= 0) return result;
37-
38+
//sort the inervals. Note: using the customized comparing function.
3839
sort(intervals.begin(), intervals.end(), compare);
3940
for(int i=0; i<intervals.size(); i++) {
4041
int size = result.size();
42+
// if the current intervals[i] is overlapped with previous interval.
43+
// merge them together
4144
if( size>0 && result[size-1].end >= intervals[i].start) {
4245
result[size-1].end = max(result[size-1].end, intervals[i].end);
4346
}else{

‎src/nQueens/nQueuens.II.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -31,7 +31,7 @@ int totalNQueens(int n) {
3131
return result;
3232
}
3333

34-
34+
// the solution is same as the "N Queens" problem.
3535
void solveNQueensRecursive(int n, int currentRow, vector<int>& solution, int& result) {
3636

3737
for (int i = 0; i < n; i++) {

‎src/nQueens/nQueuens.cpp

Lines changed: 20 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -50,34 +50,40 @@ vector< vector<string> > solveNQueens(int n) {
5050
return result;
5151
}
5252

53-
53+
//The following recursion is easy to understand. Nothing's tricky.
54+
// 1) recursively find all of possible columns row by row.
55+
// 2) solution[] array only stores the columns index. `solution[row] = col;`
5456
void solveNQueensRecursive(int n, int currentRow, vector<int>& solution, vector< vector<string> >& result) {
57+
//if no more row need to do, shape the result
5558
if (currentRow == n){
5659
vector<string> s;
57-
for (int i = 0; i < n; i++) {
58-
string row;
59-
for (int j = 0; j < n; j++) {
60-
if ( solution[i]== j ) {
61-
row += "Q";
62-
}else{
63-
row += ".";
64-
}
60+
for (int row = 0; row < n; row++) {
61+
string sRow;
62+
for (int col = 0; col < n; col++) {
63+
sRow = sRow + (solution[row] == col ? "Q" :"." );
6564
}
66-
s.push_back(row);
65+
s.push_back(sRow);
6766
}
6867
result.push_back(s);
6968
return;
7069
}
7170

72-
for (int i = 0; i < n; i++) {
73-
if (isValid(i, currentRow, solution) ) {
74-
solution[currentRow] = i;
71+
//for each column
72+
for (int col = 0; col < n; col++) {
73+
//if the current column is valid
74+
if (isValid(col, currentRow, solution) ) {
75+
//place the Queue
76+
solution[currentRow] = col;
77+
//recursively put the Queen in next row
7578
solveNQueensRecursive(n, currentRow+1, solution, result);
7679
}
7780
}
7881
}
7982

80-
83+
//Attempting to put the Queen into [row, col], check it is valid or not
84+
//Notes:
85+
// 1) we just checking the Column not Row, because the row cannot be conflicted
86+
// 2) to check the diagonal, we just check |x'-x| == |y'-y|, (x',y') is a Queen will be placed
8187
bool isValid(int attemptedColumn, int attemptedRow, vector<int> &queenInColumn) {
8288

8389
for(int i=0; i<attemptedRow; i++) {

‎src/permutations/permutations.II.cpp

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,9 @@
2121
#include <algorithm>
2222
using namespace std;
2323

24+
// To deal with the duplication number, we need do those modifications:
25+
// 1) sort the array [pos..n].
26+
// 2) skip the same number.
2427
vector<vector<int> > permute(vector<int> &num) {
2528

2629
vector<vector<int> > vv;

‎src/permutations/permutations.cpp

Lines changed: 32 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,37 @@ using namespace std;
2828
{ 3 1 2 }
2929
*/
3030

31+
/*
32+
* The algroithm - Take each element in array to the first place.
33+
*
34+
* For example:
35+
*
36+
* 0) initalization
37+
*
38+
* pos = 0
39+
* [1, 2, 3]
40+
*
41+
* 1) take each element into the first place,
42+
*
43+
* pos = 1
44+
* [1, 2, 3] ==> [2, 1, 3] , [3, 1, 2]
45+
*
46+
* then we have total 3 answers
47+
* [1, 2, 3], [2, 1, 3] , [3, 1, 2]
48+
*
49+
* 2) take each element into the "first place" -- pos
50+
*
51+
* pos = 2
52+
* [1, 2, 3] ==> [1, 3, 2]
53+
* [2, 1, 3] ==> [2, 3, 1]
54+
* [3, 1, 2] ==> [3, 2, 1]
55+
*
56+
* then we have total 6 answers
57+
* [1, 2, 3], [2, 1, 3] , [3, 1, 2], [1, 3, 2], [2, 3, 1], [3, 2, 1]
58+
*
59+
* 3) pos = 3 which greater than length of array, return.
60+
*
61+
*/
3162
vector<vector<int> > permute(vector<int> &num) {
3263

3364
vector<vector<int> > vv;
@@ -41,7 +72,7 @@ vector<vector<int> > permute(vector<int> &num) {
4172
while(pos<num.size()-1){
4273
int size = vv.size();
4374
for(int i=0; i<size; i++){
44-
//take each number to the first
75+
//take each number to the first place
4576
for (int j=pos+1; j<vv[i].size(); j++) {
4677
vector<int> v = vv[i];
4778
int t = v[j];

‎src/searchInRotatedSortedArray/searchInRotatedSortedArray.II.cpp

Lines changed: 11 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,16 @@
1313
*
1414
**********************************************************************************/
1515

16+
// Using the same idea "Search in Rotated Sorted Array"
17+
// but need be very careful about the following cases:
18+
// [3,3,3,4,5,6,3,3]
19+
// [3,3,3,3,1,3]
20+
// After split, you don't know which part is rotated and which part is not.
21+
// So, you have to skip the ducplication
22+
// [3,3,3,4,5,6,3,3]
23+
// ^ ^
24+
// [3,3,3,3,1,3]
25+
// ^ ^
1626
class Solution {
1727
public:
1828
bool search(int A[], int n, int key) {
@@ -28,8 +38,7 @@ class Solution {
2838
return false;
2939
}
3040

31-
//if dupilicates, them binary search the duplication
32-
41+
//if dupilicates, remove the duplication
3342
while (low < high && A[low]==A[high]){
3443
low++;
3544
}

0 commit comments

Comments
 (0)