May 26, 2016
Reverse Shuffle Merge - Problem statement:
Use test case: "abcacb" to explain the solution:
int[] add = new int[26],
int[] skip = new int[26]
a - 0, b - 1, c -2
add[0] = 1, add[1] = 1, add[2] = 1,
skip[0] = 1, skip[1] = 1, skip[1] =1,
Find smallest lexical string.
reverse input char one by one:
push b into stack,
'c' > ''b', then, push c into stack
stack:
c
b
Now, a is scanned, 'a' < stack.peek() = 'c', skip[2] = 1 > 0,
backtracking, pop c out of stack, skip[2] = 0
Now, 'a' < stack.peek() = 'b', skip[1] = 1 > 0,
backtracking, pop b out of stack, then adjust skip[1] = 0
add[0] > 0, push a into stack, add[0] = 0,
next, c is scanned, cannot skip, push into stack,
next, b is scanned, cannot skip, push into stack,
next, a is scanned, skip a.
stack.ToArray(), keep stack iterator order, "bca",
Array.Reverse(stack.ToArray()) -> "acb"
Lexical smallest string.
warmup practice:
Second practice:
so many bugs in second practice:
1. confused on skip, add array --, ++; line 71, line 80 did the opposite.
2. string reverse, char[], string, Array.Reverse etc. lookup
3. add one more test case: "abcacb",
b in stack, c in stack, then, run into a, pop up c, and pop up b, let 'a' in the stack. Two in row pop up in stack. While loop is tested on line 64 - 67.
4. while statement from line 64 - 67, fix compile error.
both are ok to compile:
(char)stack.Peek() > runner)
(char)stack.Peek() - runner > 0)
Third practice:
The code passes HackerRank online test cases as well.
A few good changes:
1. add comment from line 67 - line 72, test case: "abcacb",
use test case, stack top -'c' is removed, help to ensure the code is correct.
2. line 73, avoid bug to overwrite the variable runner, create a new variable called backTracked.
https://gist.github.com/jianminchen/8e2c28262dd3d13c4db856feaed5603e
Fourth practice:
1. create a new function getIndex - on line 100 - 103
2. after reading through the code, still missed a bug in writing - on line 55; debug the code and find
the result of first test case "abcacb" should be "acb", but it was "bca".
Julia examined line by line, but still missed the bug on line 55.
https://gist.github.com/jianminchen/7572e92ea48211d3d05c557d97601dbf
Read C# string constructor char[]: spend 10 - 20 minutes to read all constructors of string in C#.
https://msdn.microsoft.com/en-us/library/aa331865(v=vs.71).aspx
No comments:
Post a Comment