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

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

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, 

  1 

 /  \ 

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; } Read more blogs: http://buttercola.blogspot.ca/2014/08/leetcode-binary-tree-maximum-path-sum.html Discussion of global variable - max value - Julia likes the discussion  https://leetcode.com/discuss/14190/accepted-short-solution-in-java

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

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.