Leetcode 239: sliding window maximum

August 7, 2015

Julia spent 20-30 minutes to think about solution first, and read the following blogs, write some code as well. She practised three time using C# and here are the details.

C# practices

Here are 3 practice Julia did using LinkedList, List and SortedList. 

1. C# LinkedList

C# code implementation

2. C# List<int>

C# practice code

3. C# SortedList

C# practice code

More detail

Double ended queue is implemented using C# LinkedList class, here is Julia's C# practice code: C# code implementation

Julia chose to study the blog on Leetcode: sliding window maximum

C# code implementation (C# does not have deque class, so using C# List<int>, 

convert Python code implementation to C#, time limit exceeded)

Good workout on C# List<int>, Julia experienced different style on removing head element if out of sliding window. 

C# practice code 

Julia chose to read the blog on geekforgeek.com called "maximum of all subarrays of size k". 

Method A: naive solution, time complexity O(nw)
C# practice code is here. 

Method B: using Self-Balancing Tree (Time complexity: O(nk), need to write c# code)

C# practice code is here. 

4. blog:

http://yuanhsh.iteye.com/blog/2190852

http://n00tc0d3r.blogspot.ca/2013/04/sliding-window-maximum.html

Good comment about Deque:

We can use a Deque which allow insertions/deletions on both ends. For a Deque implemented by Circular Array/Buffer or Double Linked List, the basic insert/delete operations run in constant time.

discussion of using heap: 

 The first thought might be heap.

By maintaining a heap for all numbers in the window can give us a O(nlogw)-time solution, where

• building up a heap for initial window takes time O(wlogw)
• when window moves to the next number, each insertion and deletion take time O(logw) and there are n-w moves in total.
• after updating the heap, findMax only takes time O(1) since we know the top of heap is the largest.
•  

So, if w << n, the performance of this solution is good, close to O(n); but if w is not that small, say w = n/3 or n/4, the running time goes up to O(nlogn).

5. blog:   C++ code 

using C++ multiset in the above solution, so try to convert it to C# class using SortedList

C# practice code

6. blog:
http://www.mamicode.com/info-detail-927510.html

Convert Java Script code to C#; I spent over 12 months to try to be expert on Java Script, so much fun to read the Java Script code again, and enjoyed the blog about the analysis. 

Others:
https://github.com/jianminchen/slidingWindowMaximum/blob/master/slidingWindowMaximu5.cs

http://www.cnblogs.com/grandyang/p/4656517.html

http://techinpad.blogspot.ca/2015/05/lintcodeleetcode-sliding-window-maximum.html

Leetcode Question No 70: climbing stairs

July 28, 2015

Problem statement:

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

The problem is most popular question in the algorithm, so I do like to spend time to find out all sorts of solution, and get myself comfortable to all kinds of ideas, and figure out which one is best, and all concerns we can have in the discussion of climbing stairs:

1. Recursion solution vs. DP problem solution (Dynamic Programming solution)

2. Time complexity solution: O(2^n) vs O(n) solution

3. The space O(N) vs O(1), in other words: array of N or 2 variable, and another tmp variable

4. The base case discussion: f(0) = 1 or f(0) =1, math question?

5. Math formula - closed form solution vs DP problem solution
6. Use Memoization DP vs. no memoization DP
7. Programming skills, how to make code easy to follow, more readable, more abstract. 

The investment of time on the problem is well done. Go over 16 implementation one by one using C# programming language. 

C# code:

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

其实, 我觉得题目越容易, 越值得投入时间去学习; 看看大家有没有不同的理解, 打开思路; 如果自己没有训练过这道题, 可能会紧张; 即使训练过, 但是, 有的想法, 可能自己从来没有思考过, 一时还不能判断好坏, 但是, 多看网上的博客, 向每一个人取取经. 谦虚, 才能有提高.

我编网站后台, C#程序自己写; 自己训练的题目太少; 这次选择用Leetcode来提高C#编程, 又可以提高算法和数据结构的知识, 网站后台靠平时训练.  

January 3, 2016

Review the leetcode question 70, climbing stairs. 

Read the blog:

http://blog.csdn.net/kenden23/article/details/17377869
http://yucoding.blogspot.ca/2012/12/leetcode-question-15-climbing-stairs.html

http://www.cnblogs.com/springfor/p/3886576.html

http://www.cnblogs.com/springfor/p/3886576.html

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

https://github.com/zwxxx/LeetCode/blob/master/Climbing_Stairs.cpp