Leetcode: Jump Game

June 29, 2015

Problem statement:

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Spent some time to go over the blogs, and found this one with good illustration. So, write some c# code and then get first hand experience. 目标是会写代码, 不一定是最优. 加强C#练习. 把C++, Java的代码改为C#. 从最笨的方法开始.


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

Go through the code practice using C#:
https://github.com/jianminchen/jumpGame/blob/master/Program.cs

Cache design, dynamic programming - matrix region sum

June 25, 2015

Introduction

It is my firs time to read the algorithm and I am so surprised to learn the algorithm. I love the learning and also very happy to read the blog with good and very clear explanation of the algorithm.

Problem statement:

Given the integer matrix, top left and bottom right coordinates of the rectangular region, calculate the region sum.

Here is one of blogs I like to read and share. 

Make it more time efficient

Naive solution, O(n x m) calculation of addition to get the sum. How to get it as O(1) using cache, how big the cache space?

Naive way to design the cache, it takes O( n² x m²) space. The efficient way is O(n x m), using dynamic programming.

Share the practice C# code, here is the link. 

Leetcode: Count Primes

On June 22, 2015

Problem statement:

Count the number of prime numbers less than a non-negative number, n

Hint: The number n could be in the order of 100,000 to 5,000,000.

Read the article to talk about how to improve skills as a programmer, one comment I like most:

http://blog.csdn.net/gsky1986/article/details/46556933

"那你应该可以一眼就看出满世界的博客的算法文章中的纰漏和层次，那你还是有点功力了", 我现在还没有功底, 专心在Leetcode, 专心用C# 语言; 提高提高自己写C#代码水平.

Share the C# code in github:

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

Leetcode question 66: plus one

June 22, 2015

Given a number represented as an array of digits, plus one to the number.

Leetcode: plus one, 喜欢这道题, 看看有哪些解法; 一个个试过来 (6种方法).
Read the web blogs, and then, try different solutions (Six implementations).

practice using C#, the source code on github:

https://github.com/jianminchen/math-plus-one/

https://github.com/jianminchen/Leetcode_C-/blob/master/66PlusOne.cs

Try different solutions through blogs, and then, catch up something interesting; basic programming styles, for loop, while loop, and different ways to check carry, using %, /, ==10, ==9; one problem can be interpreted with different solutions. Fun time to play with source code, and get familiar with basic C# stuff, array, initialization.

Leetcode: word ladder

June 19, 2015

Problem statement:

Word Ladder I

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:

start = "hit"

end = "cog"

dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",

return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

http://bangbingsyb.blogspot.ca/2014/11/leetcode-word-ladder-i-ii.html

http://shanjiaxin.blogspot.ca/2014/04/word-ladder-leetcode.html

读了上面二个网页, 明白如何分析这个问题. 知道是图的问题, 而且是个难题. 觉得很不错, 刷题可以长见识. 知道自己还不会轻松地分析, 或者说, 想明白思路. 先写写代码, 调试几次, 帮助自己理解.

先看第一篇分析:

思路：

LeetCode中为数不多的考图的难题。尽管题目看上去像字符串匹配题，但从“shortest transformation sequence from start to end”还是能透露出一点图论中最短路径题的味道。如何转化？

1. 将每个单词看成图的一个节点。

2. 当单词s1改变一个字符可以变成存在于字典的单词s2时，则s1与s2之间有连接。

3. 给定s1和s2，问题I转化成了求在图中从s1->s2的最短路径长度。而问题II转化为了求所有s1->s2的最短路径。

无论是求最短路径长度还是求所有最短路径，都是用BFS。在BFS中有三个关键步骤需要实现:

1. 如何找到与当前节点相邻的所有节点。

这里可以有两个策略：

(1) 遍历整个字典，将其中每个单词与当前单词比较，判断是否只差一个字符。复杂度为：n*w，n为字典中的单词数量，w为单词长度。

(2) 遍历当前单词的每个字符x，将其改变成a~z中除x外的任意一个，形成一个新的单词，在字典中判断是否存在。复杂度为：26*w，w为单词长度。

这里可以和面试官讨论两种策略的取舍。对于通常的英语单词来说，长度大多小于100，而字典中的单词数则往往是成千上万，所以策略2相对较优。

2. 如何标记一个节点已经被访问过，以避免重复访问。

可以将访问过的单词从字典中删除。

3. 一旦BFS找到目标单词，如何backtracking找回路径？

再看第二篇分析:

/**

* Solution: Graph BFS

* 这道题想明白后非常简单，其实就是求最短路径问题，自然是BFS方法，其实问题可以用Graph来很好的解释。

* 顶点是每个字符串，如果相差一个字符，我们就可以连一条边，

* 一个字符串的边的数量最大值可能是 25 * L. 然后连线，形成Graph, 这样就是start - end的最短路径问题.

* 每次我们可以从start 出发，找adjacent string, 然后 enqueue, 下次再遍历下一层，这样第一次到end的时候，shortest = length + 1.

*

* 这题目的特点:

* 1. dict来代替BFS 中 visited 标记，直接remove from dict 就代表遍历过了 或者 不存在

* 2. 都小写字母, 字符串长度固定. 问题简单化(如果不固定，就不是只换一个char这种简单情形了，会复杂的多，跟这题也会大不相同)

*

* Time Complexity. 有点不太确定

* 最差情况: 对于每一个词, 查询应该是26*wordLength. 然后一直遍历完所有dict才找到答案. O(dict.size * 26*wordLength)

* Space 只需要一个Queue 存储邻接点，最大是dict的size, 因为dict不会是规模的，所以算是O(1)

*/

大概知道了解决方案，练习写代码．

Share C# code on github:

https://github.com/jianminchen/word-ladder-I/blob/master/Program.cs

Leetcode: string function atoi

June 18, 2015

Figure out how people are smart to get organized. The following blog is well organized.

http://pisxw.com/tag/#blog

atoi function blog:

http://blog.csdn.net/ljiabin/article/details/40508889

http://blog.csdn.net/ithomer/article/details/8800530

http://blog.csdn.net/column/details/leetcode-solutions.html

interesting stuff:

http://hihocoder.com/services/campus-recruitment

Share C# practice:

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

Leetcode 72: edit distance

June 16, 2015

Problem statement:

72. Edit Distance 

Code study: 

One solution in Chinese, blog is here written by FightForYouDream. 

Stanford lecture note about edit distance, the pdf file is here. 

Write down the feeling after the practice:

It is a two dimension dynamic programming. It took me a few hours to understand the algorithm. After a few month, I may totally forget the algorithm.

这个算法是2 dimensional dynamic programming. 读了好几个小时, 练习了代码, 理解了算法; 可能过几个月全忘了. 代码有一段容易出错,

Share the C# code, code is here. 

Follow up 

May 5, 2017

Review the algorithm after mocking experience on this algorithm in May 4, 2017. 

Leetcode 226: invert a binary tree

Invert a binary tree

http://www.wengweitao.com/leetcode-invert-binary-tree.html

http://mojijs.com/2015/06/196603/index.html

Binary tree upside down 

http://bangbingsyb.blogspot.ca/2014/11/leetcode-binary-tree-upside-down.html

Github source code:

https://github.com/jianminchen/leetcode-tree/

June 15, 2015

Write C# code 

/**
         * Latest update: on June 16, 2015
         * Leetcode: 
         * Invert a binary tree
         * Reference: 
         * http://www.zhihu.com/question/31202353
         * 
         * 7 lines of code - using recursion
         */
        public static Node invertBinaryTree(Node root)
        {
            if (root == null)
                return null;

            Node temp = root.left;
            root.left = root.right;
            root.right = temp;

            invertBinaryTree(root.left);
            invertBinaryTree(root.right);

            return root; 
        }

        /**
         * Latest update: on June 16, 2015
         * Leetcode: Invert a binary tree
         * using iterative solution 
         */
        public static Node invertBinaryTreeIterative(Node root)
        {
            if (root == null)
                return null;

            Queue q = new Queue();
            q.Enqueue(root);

            /*
             * consider the queue: 
             */
            while (q.Count > 0)
            {
                Node nd = (Node)q.Dequeue();

                Node tmp = nd.left;
                nd.left = nd.right;
                nd.right = tmp;

                if (nd.left != null)
                    q.Enqueue(nd.left);
                if (nd.right != null)
                    q.Enqueue(nd.right); 
            }

            return root; 
        }

Leetcode 5: longest palindromic substring

Problem statement:

Given a string S, find the longest palindromic substring in S.

June 15, 2015

Websites to read:

http://www.programcreek.com/2013/12/leetcode-solution-of-longest-palindromic-substring-java/

https://yanbxice.wordpress.com/2015/05/31/leetcode-longest-palindromic-substring/

题目分析很透彻, 很有帮助! 

https://leetcodenotes.wordpress.com/tag/palindrome/

C# code on github:

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

https://github.com/jianminchen/Leetcode_C-/blob/master/5LongestPalindromicSubstring.cs
https://github.com/jianminchen/Leetcode_C-/blob/master/5LongestPalindromic_B.cs

January 2, 2016

Review the algorithm. 

Leetcode question: 5. Longest Palindromic Substring

https://github.com/jianminchen/Leetcode_C-/blob/master/5LongestPalindromicSubstring.cs

January 13, 2016

Read the blog: 

http://blog.csdn.net/linhuanmars/article/details/20888595
http://blog.csdn.net/linhuanmars/article/details/22777711

Please read 5-6 solution about this leetcode question, and then, collect all the wisdom. Try to have nice memory about the solution, some fun experience; therefore, it will be a quick and fun time to solve the similar problems in the future.

Do not rush to finish more leetcode questions. Try to focus on simple problems.

There are 5 solutions discussed in the following blog, most important is to give overview of 5 analysis, what is brute force solution - time, space complexity.

One way to make review more fun is to read more than 10 - 20 solutions, and know all the ideas out there, and then, write some code; Reading is most important to help understand algorithms, through a simple problem, common interview question.

http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-i.html

4 solutions in the above blog

one optimal solution - linear time solution in the following blog:
http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

This blog is in Chinese. Excellent! Try to summary a few tips to come out linear time optimal solution! Do something to get more involved.

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

spent 10 minutes to read the article,
https://www.akalin.com/longest-palindrome-linear-time

Read the blog:
http://www.acmerblog.com/leetcode-longest-palindromic-substring-5356.html

6th solution, a suffix tree solution:
http://www.allisons.org/ll/AlgDS/Tree/Suffix/

January 7, 2017
3 code reviews:
Longest palindrome string - best review - no raw loop.

Leetcode 54: Spiral Matrix | Code review | 2015 - 2023 | Long journey

June 11, 2015

Problem Statement

Recursive solution

The first study code is here. The second is here.

Iterative solution

The first study code is here. The second one is here. 

C# code to pass Leetcode online judge:

Julia's C# code practice in 2015

Follow up 

May 23, 2017

C# practice passes all test case. The code is here. Put one row and one column checking inside the for loop statement. Code is here.

Feb. 13, 2018

It is the early day I started to write coding blog to document my code practice. At that time, I was so shy and also afraid to write down my thinking process. I do not know myself even it is just three years ago.

I just wrote down two sentences, even the sentence is not complete. I chose to study two solutions and then I practiced one of them.

One thing I can tell now is that I did not pay attention to myself, how I think as a programmer, most likely I thought that coding is more important and also challenge.

The blogs I chose in 2015

Those algorithm blogs are well-written. I am surprised that I did not practice one by one in 2015.

The recursive solution is saved in the gist. Here is the link.
The solution based on directions is saved in the gist. Here is the link.
The solution based on directions and range is here.

Follow up 

July 4, 2023

I am so lucky to have chance to prepare for another phone screen from Meta in short future. I have chance to review my work history on this algorithm. 

Leetcode: Power(x,n)

June 10, 2015

This question is most popular question in terms of my personal experience.

http://fisherlei.blogspot.ca/2012/12/leetcode-powx-n.html

http://fisherlei.blogspot.ca/2012/12/leetcode-powx-n.html

http://yucoding.blogspot.ca/2013/03/leetcode-question-74-powxn.html

best blog I have seen:

power(x,n)

http://rleetcode.blogspot.ca/2014/02/powx-n-java.html

http://www.lilongdream.com/

http://www.lilongdream.com/2014/04/10/94.html

http://www.shuatiblog.com/blog/categories/leetcode/

check this blog and ensure that it makes good sense to read it.

http://www.shuatiblog.com/blog/2014/05/28/Best-Time-to-Buy-and-Sell-Stock-III/

http://codingtnnd.blogspot.ca/2014/09/powx-n-leetcode.html

Share C# code: 

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

Read blogs and study

June 10 2015

Came cross this blog, and chose to read 10 leetcode solutions to expedite my practice on leetcode questions. Took more than 6 months, a lot of questions are new to me. So, jump into 10-20 questions new first time:

Iterative tree travesal

Palindrome number

gas station

Leetcode: strstr function

June 10, 2015

http://blog.csdn.net/linhuanmars/article/details/20276833

http://zjalgorithm.blogspot.ca/2014/12/leetcode-in-java-implement-strstr.html

Understand the Boyer-Moore Algorithm using test cases

Try to pass online judge

C# code:

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

Microsoft phone screen | Binary Tree: Write a function to return count of nodes in binary tree which has only one child.

June 8, 2015

我最喜欢的一道算法题目, 我写了七八行.　你准备了几行?　

去年我才知道这道题可以用二行代码. 2014年七月, 第一次世界上最强的算法高手耐心地开导我, 教会我如何优化代码的, argue, change, using logic reasoning and try to make it minimal. 假想代码bug, 开始改; 然后, 试图解释清楚, 自己的想法.

讨论的要点:
1. Local variable in each recursive function
2. Redundancy code
3. If statement, how many if statement in the function
4. How to argue that the code will not have bugs? Can you simplify the code?
5. Make the code simple as possible, no way to hide any bugs
6. Base case discussion
7. Discussion if null checking is needed to call the function.
8. Use a global variable to store the count.
9. Function arguments - what arguments are needed.

2015年初, 决定从Java Script 学习, 转到算法, C#, Leetcode;  先练习最基本的问题.

Github for source code:

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

只有一个孩子, 可以表示为一句话:　 (node.left!=null) != (node.right!=null)

Follow up

Feb. 15, 2019
Here is the link of my practice.

Follow up 

Nov. 1, 2023

I remembered that I had a phone screen from Microsoft. The interviewer was a principle engineer from Microsoft, and he coached me through the phone screen interview how to write an elegant solution using two lines of code. 

Actually I spent near 30 minutes to work with him, and I tried to write a broken solution. 

Leetcode: Largest rectangle in histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

June 8, 2015

My favorite websites about this problem:

http://fisherlei.blogspot.ca/2012/12/leetcode-largest-rectangle-in-histogram.html

我喜欢这个题解, 从最笨的方法到最优的方法, 都解答一遍. 我用C#也来做一遍.

http://siddontang.gitbooks.io/leetcode-solution/content/array/largest_rectangle_in_histogram.html

Here is my practice:

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

June 30, 2015
Totally forget the problem, and then, need second round study.
Read the blog:
http://segmentfault.com/a/1190000002673098

Leetcode: review time

June 8, 2015

Learning to write code is kind of tough process. Mental part, I am still very weak in the challenges. So, train myself to be a talent programmer, take leetcode questions as my projects to stay focus. The benefit of practising leetcode question is to allow myself to expose top talent programmers in China. So, reading time again for those leetcode questions, 5 -10 questions to review, and then, learn. 每一个程序员有强有弱, 看代码能够看出一些细节来. 感觉感觉, 多读一些题解.

https://www.gitbook.com/book/siddontang/leetcode-solution/details

http://siddontang.gitbooks.io/leetcode-solution/content/array/maximal_rectangle.html

http://siddontang.gitbooks.io/leetcode-solution/content/array/search_a_2d_matrix.html

http://siddontang.gitbooks.io/leetcode-solution/content/array/largest_rectangle_in_histogram.html

http://siddontang.gitbooks.io/leetcode-solution/content/dynamic_programming/best_time_to_buy_and_sell_stock.html

Leetcode: Candy

Problem statement:

There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements:

1. Each child must have at least one candy.
2. Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

June 8, 2015

Read the websites in my favorite orders:

1. http://fisherlei.blogspot.ca/2013/11/leetcode-candy-solution.html

2. http://www.programcreek.com/2014/03/leetcode-candy-java/

3. http://blog.csdn.net/linhuanmars/article/details/21424783

4. http://www.cnblogs.com/lichen782/p/4300325.html

5. http://siddontang.gitbooks.io/leetcode-solution/content/greedy/candy.html

Analysis from website 2

This problem can be solved in O(n) time.

We can always assign a neighbor with 1 more if the neighbor has higher a rating value. However, to get the minimum total number, we should always start adding 1s in the ascending order. We can solve this problem by scanning the array from both sides. First, scan the array from left to right, and assign values for all the ascending pairs. Then scan from right to left and assign values to descending pairs.

This problem is similar to Trapping Rain Water.

Most important, play with code; Spent 30 minutes to work on the coding using C# (change from Java code on webpage 2), and also, the code passes leetcode online judge.

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