April 26, 2015
Problem statement:
Finding the Minimum Window in S which Contains All Elements from T
Introduction
I tried to solve one algorithm in 5 days in a row from January 28 to February 3 in 2015, every two hours after 6 PM in a week. But I could not do it successfully.
The algorithm is called find smallest substring containing unique keys. At that time, I did not have the peer to talk to, and I came home after the full time work, I wrote the code on the paper, 2 hours each time from Monday to Friday.
I wrote on papers, page by page. I tried so many times but there is always new issues coming out. It is the first time I learned that there is brute force solution, and time complexity can be analyzed using kind of mathematics.
The idea to solve the solution is to use slide window and also keep the minimum time complexity by tracking the unique keys inside the slide window by maintaining a variable.
从2015年1月28到2月3日, 每天二小时, 总共14个小时, 我练习写这个算法。
最优解是用O(N)的时间, N是字符串的长度。
从一个简单的例子, 开始分析。
最优解是用O(N)的时间, N是字符串的长度。
从一个简单的例子, 开始分析。
比如, abc 是要寻找的字符, 另外一个字符是 abbca; 如何从abbc, 找到 bca?
最笨的方法, 就是起点有多少选项, 终点有多少选项， 时间复杂度就是O(N2)。
最笨的方法, 就是起点有多少选项, 终点有多少选项， 时间复杂度就是O(N2)。
最笨的方法就是O(N x N), 想要最优, 只能走一遍, 二个指针, 起点, 终点, 如何移动, 保证起点移动是在O(N)的算法中, 终点的也在. 设计中小心不要移太多.
Follow up after 10 days
on June 5, 2015
Algorithm blog in Chinese, with good example and illustration of the algorithm. Blog link is here.
Write down the notes in the above blog and pay attention to the thinking process. Here is the gist.
Follow up after 24 months
April 9, 2017Follow up Feb 5 2018
One thing I like to do is to read the above blog in Chinese, and then make notes more readable, and then go over the source code as well. Save notes and code as two gists, and later I will write a C# solution based on the source code.Write down the notes in the above blog and pay attention to the thinking process. Here is the gist.
No comments:
Post a Comment