Julia's coding blog - Practice makes perfect

From January 2015, she started to practice leetcode questions; she trains herself to stay focus, develops "muscle" memory when she practices those questions one by one. 2015年初, Julia开始参与做Leetcode, 开通自己第一个博客. 刷Leet code的题目, 她看了很多的代码, 每个人那学一点, 也开通Github, 发表自己的代码, 尝试写自己的一些体会. She learns from her favorite sports – tennis, 10,000 serves practice builds up good memory for a great serve. Just keep going. Hard work beats talent when talent fails to work hard.

Thursday, July 23, 2015

Leetcode 102: Binary tree level order traversal

July 23, 2015

Problem statement:

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

写代码发现很多问题. 程序要多写, 多练. 背算法可能也是一个途径. 从C++代码, 转化成C#, 犯了几个错. 一下学习到很多C#知识, 感觉不错! 练习6种方法.

1. Solution 1: (push extra null node in the queue to divide level)

Read the blog:

https://github.com/xiaoxq/leetcode-cpp/blob/master/src/BinaryTreeLevelOrderTraversal.cpp

convert it to C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal.cs

C# code passing leetcode online judge:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal2.cs

Solution 2: (using 3 variables to help queue to do BFS algorithm)

blog:

http://fisherlei.blogspot.ca/2013/01/leetcode-binary-tree-level-order.html

C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal3.cs

Solution 3: DFS algorithm:

blog:

http://fisherlei.blogspot.ca/2013/01/leetcode-binary-tree-level-order.html

C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal4.cs

Solution 4: using two containers for current level, next level

blog:

http://bangbingsyb.blogspot.ca/2014/11/leetcode-binary-tree-level-order.html

C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal5.cs

Solution 5: one queue and iteratively solution (单个queue的迭代解法)
blog:

http://bangbingsyb.blogspot.ca/2014/11/leetcode-binary-tree-level-order.html

C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal6.cs

Solution 6: one queue and extra node null into queue to mark end of level

blog:

http://bangbingsyb.blogspot.ca/2014/11/leetcode-binary-tree-level-order.html

C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal7.cs

Blogs to read:

1. http://www.jiuzhang.com/solutions/binary-tree-level-order-traversal-ii/

2. http://siddontang.gitbooks.io/leetcode-solution/content/tree/binary_tree_level_order_traversal.html

3. http://blog.csdn.net/ljphhj/article/details/22428939

Sunday, July 19, 2015

Leetcode 37: Sudoku Solver

July 19, 2015

Problem statement:

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

Solution 1:

Great blog to read:

http://blog.csdn.net/fightforyourdream/article/details/16916985

And then, start to implement the solution using C# code:

https://github.com/jianminchen/sudokuSolver/blob/master/Program.cs

Solution 2:

Read the blog,
http://blog.csdn.net/linhuanmars/article/details/20748761

and then, implement the solution using c# code:

https://github.com/jianminchen/sudokuSolver/blob/master/Program2.cs

Solution 3: (good workout on C# KeyValuePair class)

and then, convert C++ code to C# code from the blog:
https://github.com/yinlinglin/LeetCode/blob/master/SudokuSolver.h

Excellent code in C++, using class for node on the board. Learn a few things, fun to play with the code

C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program3.cs

solution 4:
https://github.com/jianminchen/sudokuSolver/blob/master/Program4.cs
source code from the blog:
https://github.com/xiaoxq/leetcode-cpp/blob/master/src/SudokuSolver.cpp

Solution 5:
read the blog: (Good coding! practice more based on this blog)
https://github.com/zwxxx/LeetCode/blob/master/Sudoku_Solver.cpp

and convert the C++ code to C# code, (great workout on C# LinkedList for blank nodes)

https://github.com/jianminchen/sudokuSolver/blob/master/Program5.cs

Solution 6:
read the blog:
http://shanjiaxin.blogspot.ca/2014/04/sudoku-solver-leetcode.html

and convert Java code to C# code, great workout on C# and logic checking "return false"

https://github.com/jianminchen/sudokuSolver/blob/master/Program6.cs

Solution 7:
blog:
http://www.jiuzhang.com/solutions/sudoku-solver/
C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program7.cs

Solution 8:
Thanks for the blog's highlight line of code on back tracking; finally, I got it! My logic thinking has flaws on back tracking; extra backtracking is not a good. Minimize the back tracking, only do it when "return false". It makes sense to do that.

blog:
http://bangbingsyb.blogspot.ca/2014/11/leetcode-valid-sudoku-sudoku-solver.html
C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program8.cs

Solution 9:
blog:
http://www.cnblogs.com/TenosDoIt/p/3800485.html

C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program9.cs

Solution 10:
blog: (Excellent implementation! no extra line or number in the code! Best for memorization! Go through other solutions later. )
https://github.com/rffffffff007/leetcode/blob/master/Sudoku%20Solver.java

C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program10.cs

算法理解了, 代码可以记住了; 开始看不同的题解, 看看高手的代码; 从不同的题解中, 模仿模仿! 像打网球, 多接触不同的打法, 开阔眼界; 接着看这道题的题解. 试着从不同角度看一个问题, 多练习改代码; 看自己能不能有自己的看法, 去尝试一点更改, 玩一点花样; 增加练习C#编程的机会.

Also, the code written has been work on readability, learned through my favorite book reading:
http://shop.oreilly.com/product/9780596802301.do

Those favorite rules I like to learn, pick up and follow:
Big fan of DRY (Do not repeat yourself) principle, do one thing a time, break giant expression, using explaining variable or summary variable, and abstract the thing to a function, extract a subproblem to a function. The code is also modified to fit into short memory, less mental baggage to read through.

Read solutions:

https://github.com/jordandong/myleetcodes/blob/master/SudokuSolver.cpp

https://github.com/Sayericplz/myleetcode/blob/master/isValidSudoku.cpp

BFS, using queue - try to convert it to C#
http://yucoding.blogspot.ca/2013/12/leetcode-question-sudoku-solver.html

Leetcode: maximal rectangle

July 19, 2015

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

http://www.aiuxian.com/article/p-389634.html

http://www.cnblogs.com/lichen782/p/leetcode_maximal_rectangle.html

Fully understand the problem and solution, and then, spend some time to convert java code to C# code; and then, play with code, and see if I can improve the code.

Thursday, July 16, 2015

leetcode: longest substring without repeating characters

July 16, 2015

Problem statement:

Longest Substring Without Repeating Characters

Read the blog:

http://blog.csdn.net/fightforyourdream/article/details/17860983

这算法写了很多次, 时间太长, 半年前, 有一次写了二个小时, 写不下去, 想法不好, 没有办法收场; 接着, 又写了四天, 每天二小时, 把上次代码拿出来看, 有什么问题, 改写. 过后想, 这样学习, 时间是浪费的, 打的是疲劳站; 工作中没有这么复杂的问题, 解决问题, 一定要评估复杂程度.

改变学习方式, 看以上的网页, 看Java的代码, 改写C#; 然后, 增加一些测试的内容, 帮助自己记忆算法的主要思想, 然后, 再改写; 用最简化的测试案例手工检测代码. 二三个小时搞定, 比半年前写的C#简单很多.

关键是用别人的想法, 又加快改写代码的速度, 改写后的代码更方便自己记忆. 这算法用移动窗口, 所以, 在代码中定义窗口起点, 长度, 什么时候决定更新窗口起点; 用一个数组(256字符)记录每个字符上次所在的位置, 然后, 对当前点, 窗口最右点, 判断是在窗口中出现没有; 间接判断, 看上次的位置在滑动窗口外还是里面.

学习别人的代码, 又练习自己改写代码, 写测试的内容, 多练习总是有新的体会.

Julia发现改写代码, 从其他语言到C#, 让她有机会快速练习写代码, 学习C#语言; 同时, 体会和其他语言的不同, 开阔眼界; 读的再多, 想法很好, 不会写代码实现, 或超过时间范围, 或写起来头痛, 太多错误, 都通过Leetcode训练, 有所提高.

Share C# code:

https://github.com/jianminchen/BinaryTreeMaxPathSum/blob/master/longestSubstringWithoutRepeatingChars.cs

First blog about the same problem:

http://juliachencoding.blogspot.ca/2015/06/longest-substring-without-repeating.html

"撑死胆大的,饿死胆小的. ", 虽然是个歇后语, 但是, 这道题目, 如果只考虑抽象思维, Hashset, 不具体讨论256字符等具体内容, 确实可以10 - 15分钟写出代码. 这是Julia练习的代码, 在第一次训练几个月之后.

https://github.com/jianminchen/Leetcode_C-/blob/master/3LongestSubstringWithoutRepeating.cs

leetcode Question No 132: palindrome 2

July 16, 2015

Problem statement:

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Read the blogs:

http://blog.csdn.net/fightforyourdream/article/details/17730939

Share C# code:

https://github.com/jianminchen/palindromeII/blob/master/Program.cs

January 2, 2016
Review the source code, and try to figure out the algorithm.

Monday, July 13, 2015

Leetcode: study time

July 14, 2015

做Leetcode题目需要选择自己熟悉的编程语言; 正好, 想提高C#的编程, 看C++的代码, 改写C#; 从Java 代码改写成C#. 现在, 题目还有很多没有看过, 想法都没有, 还会紧张. 所以, 尝试看一个人的博客, 选十几个没有做过的问题, 在几个小时内读一遍.

今天就读下面博客:

http://blog.csdn.net/fightforyourdream/article/category/1350225

http://www.lifeincode.net/category/programming/

Leetcode: study time

July 13, 2015

Choose to read blogs with code using Java programming language. 很多题是第一次接触.

http://yyeclipse.blogspot.ca/2012/11/leetcode-populating-next-right-pointers.html

http://yyeclipse.blogspot.ca/2012/11/leetcode-set-matrix-zeroes.html

http://yyeclipse.blogspot.ca/2012/11/solving-maximal-rectangle-problem-based.html

http://yyeclipse.blogspot.ca/2013/01/leetcode-generate-parentheses.html

The majority vote ( more than n/3 element in an array, go through the array once or twice, get the number)

http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

The maximum rectangle problem:

http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529?pgno=1

The longest increasing subsequence:

http://www.felix021.com/blog/read.php?1587

http://yyeclipse.blogspot.ca/2013/02/notes-on-lcs-lis-and-related-problems.html

Microsoft interview question:

http://yyeclipse.blogspot.ca/2013/02/two-equal-sized-subsets-partition.html

Review strstr leetcode question: (KMP, Boyer-Moore, Rabin-Karp algorithm)

http://yyeclipse.blogspot.ca/2013/02/leetcode-implement-strstr-string.html

DP problem: leetcode question

http://yyeclipse.blogspot.ca/2013/03/leetcode-palindrome-partition-ii.html

http://www.geeksforgeeks.org/dynamic-programming-set-17-palindrome-partitioning/

http://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/

Thursday, July 9, 2015

ITInt5: Excel columns to integer

July 8, 2015

Problem statement:

链接: http://www.itint5.com/oj/#23
问题:
Excel中的行列数用A~Z 26个字母表示，A, B, C, D, …, Z, AA, AB, …, AZ, BA, BB, …
分别表示10进制数1, 2, 3, 4, …, 26, 27, 28, …, 52, 53, 54…。
请实现2个函数decToExcel和excelToDec，将10进制数转换为Excel数，以及将Excel数转换为10进制数。

Share C# code for the practice:

https://github.com/jianminchen/ExcelColumnStrToInt/blob/master/Program.cs

ITInt5: Arithmetic Expression Evaluation

July 9, 2015

Read blogs:

给定一个表达式字符串，其中只包含非负整数，加法，减法以及乘法符号，例如7+345+2+4-3-1。请写程序计算该表达式的值。提示：可以尝试使用递归算法，程序将非常简洁易写，很适用于面试场合。

https://github.com/AnnieKim/ITint5/blob/master/026_%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.cpp

https://github.com/jordandong/myITint5/blob/master/26_Evaluation.cpp

Monday, July 6, 2015

Leetcode Question No. 53: Maximum subarray sum

July 6, 2015

problem statement:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Study the code:
http://joycelearning.blogspot.ca/2013/10/leetcode-maximum-subarray.html

C# code:

https://github.com/jianminchen/MaximumSubArray/blob/master/Program.cs

https://github.com/jianminchen/MaximumSubArray_Space/blob/master/Program.cs

ITInt5: maximum boxes

July 6, 2015

Problem statement:

Link: http://www.itint5.com/oj/#34

问题:

有n块积木，每块积木有体积vol和重量weight两个属性，用二元组(vol, weight)表示。

积木需要搭成竖直的塔状，上面积木的体积和重量必须都比它下面的积木小。问最多可以搭多少个积木。

样例：

有7个积木boxes:

[(65, 100), (70, 150), (56, 90), (75, 190), (60, 95), (68, 110), (80, 12)]

最多可以搭6个积木，从上到下分别为：

(56, 90), (60, 95), (65, 100), (68, 110), (70, 150), (75, 190)

所以函数应该返回6。

题目来源：CRACKING THE CODING INTERVIEW 9.7

Solution: 先按照vol进行排序，题目就变成了根据weight寻找最长严格递增子序列。

Share C# practice:

https://github.com/jianminchen/MaxBoxes/blob/master/Program.cs

ITINT5: tree maximum path sum (I)

July 6, 2015

Problem statement:

链接: http://www.itint5.com/oj/#13

问题:

给定一棵树的根结点，树中每个结点都包含一个整数值val。

我们知道树中任意2个结点之间都存在唯一的一条路径，路径值为路径上所有结点值之和。

请计算最大的路径值（允许路径为空）。

样例：

-10

/ | \

2 3 4

/ \

5 -1

-1

最大的路径值为13，相应的路径为5到6之间的路径。

扩展：此题算法也可用来解决另一个非常常见的面试题“树的直径”（求树中任意两结点路径的长度的最大值）。

可以认为树中每个结点的val值为1，那么求最长路径相当于求路径值最大的路径。

Solution: LeetCode中Binary Tree Maximum Path Sum的扩展，这里是树，而非二叉树。

Share C# code:

https://github.com/jianminchen/TreeMaxPathSum/blob/master/Program.cs

February 3, 2016

work on Leetcode question 124: Binary Tree Maximum Path Sum

Leetcode: word search

July 6, 2015

Problem statement:

Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

The problem can be solved using backtracking, recursive solution.

Share C# implementation:

https://github.com/jianminchen/wordSearch-/blob/master/Program.cs

Sunday, July 5, 2015

Leetcode: good blogs to follow

July 5, 2015,

Went through 6 months training on C# using leetcode, learned a lot. So, next two blogs to read:

https://github.com/yinlinglin/LeetCode

https://github.com/xiaoxq/cracking-the-coding-interview-v4-cpp

Read the blog, and transfer C++ to C# code. So, she can learn C#, and also know the difference between C++ and C#.

https://github.com/xiaoxq/leetcode-cpp

https://github.com/Sayericplz/myleetcode

Another good blog to read:

https://github.com/zwxxx/LeetCode

Code in java:
https://github.com/patrickyao1988/LeetCode-Java

https://github.com/wuhanyu/leetC2013

Saturday, July 4, 2015

Leetcode 124: Maximum binary tree path sum

July 4, 2015

Problem statement:

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:

Given the below binary tree,

/ \

2 3

Return 6.

Blogs to read:

http://blog.unieagle.net/2012/12/09/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Abinary-tree-maximum-path-sum/

http://shanjiaxin.blogspot.ca/2014/02/binary-tree-maximum-path-sum-leetcode.html

http://bangbingsyb.blogspot.ca/2014/11/leetcode-binary-tree-maximum-path-sum.html

http://jane4532.blogspot.ca/2013/09/binary-tree-maximum-path-sumleetcode.html

原来这讲解很清楚:

http://www.cnblogs.com/yuzhangcmu/p/4172855.html

The best readable code, and perfect to follow for this problem:

https://github.com/xiaoxq/leetcode-cpp/blob/master/src/BinaryTreeMaximumPathSum.cpp

Julia's C# practice.

https://github.com/jianminchen/BinaryTreeMaxPathSum/blob/master/Program.cs

https://github.com/jianminchen/Leetcode_C-/blob/master/124BinaryTreeMaximumPathSum.cs

Extension problem:

https://github.com/AnnieKim/ITint5/blob/master/013_%E6%A0%91%E4%B8%AD%E6%9C%80%E5%A4%A7%E8%B7%AF%E5%BE%84%E5%92%8C.cpp

February 3, 2016

Review the algorithm, need to figure out how to make this algorithm easy to remember, recall, write without a bug.

Good analysis from the blog (http://www.cnblogs.com/yuzhangcmu/p/4172855.html):

计算树的最长path有2种情况：

1. 通过根的path.

(1)如果左子树从左树根到任何一个Node的path大于零，可以链到root上

(2)如果右子树从右树根到任何一个Node的path大于零，可以链到root上

2. 不通过根的path. 这个可以取左子树及右子树的path的最大值。

所以创建一个inner class:

记录2个值：

1. 本树的最大path。

2. 本树从根节点出发到任何一个节点的最大path.

注意，当root == null,以上2个值都要置为Integer_MIN_VALUE; 因为没有节点可取的时候，是不存在solution的。以免干扰递归的计算

http://www.cnblogs.com/yuzhangcmu/p/4172855.html

Practice using this class as return type:

private class ResultType {

int singlePath;

int maxPath;

ResultType(int singlePath, int maxPath) {

this.singlePath = singlePath;

this.maxPath = maxPath;

}

Friday, July 3, 2015

ITint5 - questions

July 3, 2015

Went through the first 10 questions from the blogs:

Stumble on most questions:

https://github.com/AnnieKim/ITint5/blob/master/004_%E7%BB%9F%E8%AE%A1%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%BB%93%E7%82%B9%E6%95%B0.cpp

Need to practice this question using C#, excellent question. Do not think clearly about height calculation, left side height vs right side height, which is the complete the tree.

Another one,

https://github.com/AnnieKim/ITint5/blob/master/008_%E6%9C%80%E5%A4%A7%E8%BF%9E%E7%BB%AD%E5%AD%90%E6%AE%B5%E5%92%8C.cpp

how to come out the best solution? Naive solution is O(N^2), start point and end point, each has n choices; so, let us try O(n) solution. Go through one loop, maybe multiple times. How many variables, ...stumble on easy question.

And then, how to extend the problem: if the start point can connect end point, like a ring. Stumble on this problem, so, take easy step, first, ask myself, what is the case no ring? And then, what is connection between two of them. Clever solution.

https://github.com/AnnieKim/ITint5/blob/master/009_%E7%8E%AF%E5%BD%A2%E6%9C%80%E5%A4%A7%E8%BF%9E%E7%BB%AD%E5%AD%90%E6%AE%B5%E5%92%8C_%E8%A7%A3%E6%B3%952.cpp

Topological order learning:

First time read it about this ordering - topological order

https://github.com/AnnieKim/ITint5/blob/master/010_%E4%BB%BB%E5%8A%A1%E8%B0%83%E5%BA%A6.cpp

http://www.cnblogs.com/skywang12345/p/3711494.html

One comment is that she needs to go through quick learning through problems, 10 problems a time; pick up something, like a hint, and then, know how to expand her knowledge.

Leetcode: Add Binary

July 3, 2015

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

work on programming using C#; find great code to convert it from C++ to C#, know the difference.

https://github.com/jianminchen/addBinary/blob/master/Program.cs