February 8, 2016
Wiggle Sort
Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....
Julia figured out the easy way to do it, O(n) time, O(1) space. So motivated. Next time, think about algorithm by yourself, start from brute force, and then, work towards requirement - efficient solution.
https://segmentfault.com/a/1190000003783283
public class Solution {
public void wiggleSort(int[] nums) {
for(int i = 1; i < nums.length; i++){
// 需要交换的情况：奇数时nums[i] < nums[i - 1]或偶数时nums[i] > nums[i - 1]
if((i % 2 == 1 && nums[i] < nums[i-1]) || (i % 2 == 0 && nums[i] > nums[i-1])){
int tmp = nums[i-1];
nums[i-1] = nums[i];
nums[i] = tmp;
}
}
}
}
To be continued.
Monday, February 8, 2016
Leetcode 319: Bulb Switch
February 8, 2016
319 Bulb Switch
http://www.cnblogs.com/grandyang/p/5100098.html
Analysis from the above blog:
319 Bulb Switch
http://www.cnblogs.com/grandyang/p/5100098.html
Analysis from the above blog:
那么我们来看这道题吧，还是先枚举个小例子来分析下，比如只有5个灯泡的情况，'X'表示亮，‘√’表示灭，如下所示：
初始状态： X X X X X
第一次： √ √ √ √ √
第二次： √ X √ X √
第三次： √ X X X √
第四次： √ X X √ √
第五次： √ X X √ X
那么最后我们发现五次遍历后，只有1号和4号锁是亮的，而且很巧的是它们都是平方数，是巧合吗，还是其中有什么玄机。我们仔细想想，对于第n个灯泡，只有当次数是n的因子的之后，才能改变灯泡的状态，即n能被当前次数整除，比如当n为36时，它的因数有(1,36), (2,18), (3,12), (4,9), (6,6), 可以看到前四个括号里成对出现的因数各不相同，括号中前面的数改变了灯泡状态，后面的数又变回去了，等于锁的状态没有发生变化，只有最后那个(6,6)，在次数6的时候改变了一次状态，没有对应其它的状态能将其变回去了，所以锁就一直是打开状态的。所以所有平方数都有这么一个相等的因数对，即所有平方数的灯泡都将会是打开的状态。
那么问题就简化为了求1到n之间完全平方数的个数，我们可以用force brute来比较从1开始的完全平方数和n的大小
To be continued.
To be continued.
Leetcode 322: Coin Change
February 8, 2016
Julia likes to build a good fun memory about dynamic programming design, coding experience. Let this one - coin change build up good memory about Dynamic Programming.
322 Coin change
http://www.cnblogs.com/grandyang/p/5138186.html
Julia likes to build a good fun memory about dynamic programming design, coding experience. Let this one - coin change build up good memory about Dynamic Programming.
322 Coin change
http://www.cnblogs.com/grandyang/p/5138186.html
这道题只让我们求出最小的那种，对于求极值问题，我们还是主要考虑动态规划Dynamic Programming来做，我们维护一个一维动态数组dp，其中dp[i]表示钱数为i时的最小硬币数的找零，递推式为：
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
其中coins[j]为第j个硬币，而i - coins[j]为钱数i减去其中一个硬币的值，剩余的钱数在dp数组中找到值，然后加1和当前dp数组中的值做比较，取较小的那个更新dp数组
To be continued.
Sunday, February 7, 2016
Leetcode 318: Maximum Product of Word Length
February 7, 2016
There are a several of stages to go through on Leetcode 318 problem solving today.
10 minutes to read question and think about solution, confused about requirement(以为包括子字符串) ->
20 minutes to read blogs to understand solutions ->
10 minutes to know the detail to implement (1) ->
20 minutes to implement without bugs (2) ->
10 minutes to implement with more clear code with bugs (3) ->
10 minutes debug to read code again, debugging to pinpoint bug ->
60 minutes to work on a better idea - optimal idea (5) ->
work on exceeded time issues (20 minutes, instead of 60+ minutes) (6)
Action items:
1. Always work on coding, using Visual Studio. Try to improve coding.
Leetcode 318: Maximum Product of Word Length
Given a string array
https://www.hrwhisper.me/leetcode-maximum-product-of-word-lengths/
Solution 1:
Solution 2:
There are a several of stages to go through on Leetcode 318 problem solving today.
10 minutes to read question and think about solution, confused about requirement(以为包括子字符串) ->
20 minutes to read blogs to understand solutions ->
10 minutes to know the detail to implement (1) ->
20 minutes to implement without bugs (2) ->
10 minutes to implement with more clear code with bugs (3) ->
10 minutes debug to read code again, debugging to pinpoint bug ->
60 minutes to work on a better idea - optimal idea (5) ->
work on exceeded time issues (20 minutes, instead of 60+ minutes) (6)
Action items:
1. Always work on coding, using Visual Studio. Try to improve coding.
Leetcode 318: Maximum Product of Word Length
Given a string array
words, find the maximum value of length(word[i]) * length(word[j])where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.https://www.hrwhisper.me/leetcode-maximum-product-of-word-lengths/
Solution 1:
直接看看每个字符串都包括了哪个字符，然后一一枚举是否有交集：
- 有交集，则乘积为0
- 无交集，乘积为 words[i].length() * words[j].length()
Julia's practice:
其实因为全部都是小写的字母，用int 就可以存储每一位的信息。这就是位运算
- elements[i] |= 1 << (words[i][j] – ‘a’); //把words[i][j] 在26字母中的出现的次序变为1
- elements[i] & elements[j] // 判断是否有交集只需要两个数 按位 与 （AND）运算即可
http://www.cnblogs.com/onlyac/p/5155881.html
在一个字符串组成的数组words中，找出max{Length(words[i]) * Length(words[j]) },其中words[i]和words[j]中没有相同的字母，在这里字符串由小写字母a-z组成的。
对于这道题目我们统计下words[i]的小写字母a-z是否存在，然后枚举words[i]和words[j]，找出max{Length(words[i]) * Length(words[j]) }。
小写字母a-z是26位，一般统计是否存在我们要申请一个bool flg[26]这样的数组，但是我们在这里用int代替，int是32位可以替代flg数组，用 与（&），或（1），以及向左移位（<<）就能完成。如“abcd” 的int值为 0000 0000 0000 0000 0000 0000 0000 1111，“wxyz” 的int值为 1111 0000 0000 0000 0000 0000 0000 0000，这样两个进行与（&）得到0， 如果有相同的字母则不是0。
Here is julia's practice:
https://github.com/jianminchen/Leetcode_C-/blob/master/318MaximumProductOfWordLength_B.cs
Read the webpage about precedence and order of evaluation:
https://msdn.microsoft.com/en-us/library/2bxt6kc4.aspx
Solution 3:
Just for fun, write another version of bit manipulation implementation, but Julia created 3 bugs in the row before she writes a correct version.
Instead of using two words do not contain same char,
if ((s1 & s2) == 0) return true;
she tried to write a version to check any char from a to z, one by one check version:
https://github.com/jianminchen/Leetcode_C-/blob/master/318MaximumProductOfWordLength_C.cs
Design takes practice. She thought about and then wrote, and then failed 3 times!
https://github.com/jianminchen/Leetcode_C-/blob/master/318MaximumProductOfWordLength_B.cs
Read the webpage about precedence and order of evaluation:
https://msdn.microsoft.com/en-us/library/2bxt6kc4.aspx
Solution 3:
Just for fun, write another version of bit manipulation implementation, but Julia created 3 bugs in the row before she writes a correct version.
Instead of using two words do not contain same char,
if ((s1 & s2) == 0) return true;
she tried to write a version to check any char from a to z, one by one check version:
https://github.com/jianminchen/Leetcode_C-/blob/master/318MaximumProductOfWordLength_C.cs
Design takes practice. She thought about and then wrote, and then failed 3 times!
Sunday - Reading time (2)
February 7, 2016
Favorite time to read, learn and understand business world. Have some coaches. Today, Julia writes down another 10 rules to success, Marcus Lemonis.
Marcus Lemonis
https://www.youtube.com/watch?v=Ty0L1rkjl5w
1. Make business plan
get a piece of paper, write down the idea, and get feedback:
Here is my product and service.
Here is how I attack the market.
Here is how I beat the competition.
Here is how I learn from my competitors.
Here is I take from my customers.
Here is the people I need to surround myself with.
Answer those questions.
2. Have enough working capital
3. Create a to do list for tomorrow
Good habit to follow -
Write down a list to complete at night, and complete it before noon. Afternoon, maybe, a wild wild west.
What you have to do, house keeping.
4. Take care of your employees
Take care of your employees - they will put customers first.
5. Have the knowledge
Follow the passion. Work for other for a while. Better have a partner.
6. Constantly reinvent yourself
Bold step, no matter how old you are. As an entrepreneur.
End up like Sears, not existing any more. Not evolving, will die.
7. Always stay one step ahead
8. Stick to the grind
Business owner, team member.
9. Push through the fear of failure
Fear of failure - cannot ignore them, admit my vulnerability when he turns old around 40s years old.
10. Stand out
Favorite time to read, learn and understand business world. Have some coaches. Today, Julia writes down another 10 rules to success, Marcus Lemonis.
Marcus Lemonis
https://www.youtube.com/watch?v=Ty0L1rkjl5w
1. Make business plan
get a piece of paper, write down the idea, and get feedback:
Here is my product and service.
Here is how I attack the market.
Here is how I beat the competition.
Here is how I learn from my competitors.
Here is I take from my customers.
Here is the people I need to surround myself with.
Answer those questions.
2. Have enough working capital
3. Create a to do list for tomorrow
Good habit to follow -
Write down a list to complete at night, and complete it before noon. Afternoon, maybe, a wild wild west.
What you have to do, house keeping.
4. Take care of your employees
Take care of your employees - they will put customers first.
5. Have the knowledge
Follow the passion. Work for other for a while. Better have a partner.
6. Constantly reinvent yourself
Bold step, no matter how old you are. As an entrepreneur.
End up like Sears, not existing any more. Not evolving, will die.
7. Always stay one step ahead
8. Stick to the grind
Business owner, team member.
9. Push through the fear of failure
Fear of failure - cannot ignore them, admit my vulnerability when he turns old around 40s years old.
10. Stand out
Sunday - Reading time - Career Advice
February 7, 2016
Working on Leetcode algorithm, Julia took so many breaks when she worked on 5 Leetcode questions on Feb. 6 evening, she found out that she needs to build up mental toughness on the problem solving - using algorithm/ data structure. She wonders why she needs to read something not meaningful while solving those problems, why the algorithm cannot be nature in her life.
So, she turns to advice from her favorite politician, Mitt Romney's top 10 rules for success, a Havard graduate's advice this Sunday.
https://en.wikipedia.org/wiki/Mitt_Romney
1. Have clear objectives -
Write down clear objectives.
What is my objective to work on Leetcode algorithms?
1. Constant Reinvent herself - as a software programmer.
2.
3.
2. Stop thinking, start doing
3. Failures are inevitable
4. Have a life coach
5. Do what you enjoy
More detail: English major -> business school -> Law degree (Havard law school)
Do what you enjoy -> not lead more money
6. Launch out into the deep
Master teaches Peter how to fish (Luke 5:4 “Put out into deep water, and let down the nets for a catch.” )
Metaphor for the life, do not live in shallow, live in deep. Educate you, service others
7. Keep your life in perspective
Perspective is good friend. Find ways in perspective.
Do not study on Sunday. Personal time.
Do not work at home. Devote time to the family. Really focus on the importance things of life.
8. Devote time for family
9. Do your present job well
Secret to the advancement.
10. Your choices shape the lives of other people
And then, spent half hour to read the article. Great time to read. Julia found out that so many interesting things to read in the article, she started to find the joy of life - reading, expand the knowledge, and know the world: education, father and son, and career advice from the father, and many more.
https://en.wikipedia.org/wiki/Mitt_Romney
Working on Leetcode algorithm, Julia took so many breaks when she worked on 5 Leetcode questions on Feb. 6 evening, she found out that she needs to build up mental toughness on the problem solving - using algorithm/ data structure. She wonders why she needs to read something not meaningful while solving those problems, why the algorithm cannot be nature in her life.
So, she turns to advice from her favorite politician, Mitt Romney's top 10 rules for success, a Havard graduate's advice this Sunday.
https://en.wikipedia.org/wiki/Mitt_Romney
1. Have clear objectives -
Write down clear objectives.
What is my objective to work on Leetcode algorithms?
1. Constant Reinvent herself - as a software programmer.
2.
3.
2. Stop thinking, start doing
3. Failures are inevitable
4. Have a life coach
5. Do what you enjoy
More detail: English major -> business school -> Law degree (Havard law school)
Do what you enjoy -> not lead more money
6. Launch out into the deep
Master teaches Peter how to fish (Luke 5:4 “Put out into deep water, and let down the nets for a catch.” )
Metaphor for the life, do not live in shallow, live in deep. Educate you, service others
7. Keep your life in perspective
Perspective is good friend. Find ways in perspective.
Do not study on Sunday. Personal time.
Do not work at home. Devote time to the family. Really focus on the importance things of life.
8. Devote time for family
9. Do your present job well
Secret to the advancement.
10. Your choices shape the lives of other people
And then, spent half hour to read the article. Great time to read. Julia found out that so many interesting things to read in the article, she started to find the joy of life - reading, expand the knowledge, and know the world: education, father and son, and career advice from the father, and many more.
https://en.wikipedia.org/wiki/Mitt_Romney
Friday, February 5, 2016
Do not complain - a tip worthy to share
February 5, 2016
Chinese new year is coming in 2 days. And then, spent a few hours to watch videos about Canadian immigrant story.
"Do not complain", the video about Robert Herjavec, a Canadian story, an immigrant story.
https://www.youtube.com/watch?v=u5uD62Plakg
https://www.youtube.com/watch?v=-s9qJ7ATP7w
https://www.youtube.com/watch?v=sYprh2qkeDY
1. Be great on one thing
2. Never complain (Never complain, no one cares.
short story: Appreciate the opportunity. The father was laid off from sweeping the floor job, did not take unemployment pay when Robert tried to fill the form for his dad, his father did not want anything from the Canada which gives him opportunity. 20 dollars his dad came to Canada with wife and son, taking a boat with a suitcase)
3. Just keep going
4. Create value for your customers
5. Become the person others want to know
6. Listen to yourself
7. Leave your emotions out of it
8. Be able to adapt
9. Find what makes you tick
10. You are in control of everything
Robert Herjavec: The will to win
https://www.youtube.com/watch?v=7GxQ9KoaUJ0
Do not classify people loser. People give up, being a loser. Being a winner is easy, being a loser, keep going. Everything can go, go wrong for me.
Mental strength. Train for marathon for 20 days. The way you gain confidence, you just do it.
Just do it. You gain confidence by your experience.
If you are successful, money will follow.
Be efficient. Adaptability. If you are dropped in jungle, you will survive.
With kindness - kills the competition
https://www.youtube.com/watch?v=M9Mf2s4OJSU
Love tech industry - every 3 years it reinvents itself.
What is the purpose of business? Create customer, create value for them. ( Julia's still thinking about it)
Leave emotion out of it. Be angry, make bad decisions.
Listening - what people try to say to you.
Let go - success is not good at everything. Find thing you are good at. Let go others. The world will reward you with very narrow knowledge.
Be world class on one thing. Do not worry about your weakness.
The minute you find that you are successful, it is the end of it. Keep going. Be master everything you choose, react with.
Conclusion:
Do not complain how time-consuming to improve skills by working on Leetcode algorithms.
Try to stay calm when performing algorithms. Do not give in nervousness.
Be mental toughness on problem solving. Always focus on current problem. Not worry about next one, or other thing. Try to do small, simple, stupid things first, see if it leads an idea or solution, and then, try to improve, and optimize it if need.
Chinese new year is coming in 2 days. And then, spent a few hours to watch videos about Canadian immigrant story.
"Do not complain", the video about Robert Herjavec, a Canadian story, an immigrant story.
https://www.youtube.com/watch?v=u5uD62Plakg
https://www.youtube.com/watch?v=-s9qJ7ATP7w
https://www.youtube.com/watch?v=sYprh2qkeDY
1. Be great on one thing
2. Never complain (Never complain, no one cares.
short story: Appreciate the opportunity. The father was laid off from sweeping the floor job, did not take unemployment pay when Robert tried to fill the form for his dad, his father did not want anything from the Canada which gives him opportunity. 20 dollars his dad came to Canada with wife and son, taking a boat with a suitcase)
3. Just keep going
4. Create value for your customers
5. Become the person others want to know
6. Listen to yourself
7. Leave your emotions out of it
8. Be able to adapt
9. Find what makes you tick
10. You are in control of everything
Robert Herjavec: The will to win
https://www.youtube.com/watch?v=7GxQ9KoaUJ0
Do not classify people loser. People give up, being a loser. Being a winner is easy, being a loser, keep going. Everything can go, go wrong for me.
Mental strength. Train for marathon for 20 days. The way you gain confidence, you just do it.
Just do it. You gain confidence by your experience.
If you are successful, money will follow.
Be efficient. Adaptability. If you are dropped in jungle, you will survive.
With kindness - kills the competition
https://www.youtube.com/watch?v=M9Mf2s4OJSU
Love tech industry - every 3 years it reinvents itself.
What is the purpose of business? Create customer, create value for them. ( Julia's still thinking about it)
Leave emotion out of it. Be angry, make bad decisions.
Listening - what people try to say to you.
Let go - success is not good at everything. Find thing you are good at. Let go others. The world will reward you with very narrow knowledge.
Be world class on one thing. Do not worry about your weakness.
The minute you find that you are successful, it is the end of it. Keep going. Be master everything you choose, react with.
Conclusion:
Do not complain how time-consuming to improve skills by working on Leetcode algorithms.
Try to stay calm when performing algorithms. Do not give in nervousness.
Be mental toughness on problem solving. Always focus on current problem. Not worry about next one, or other thing. Try to do small, simple, stupid things first, see if it leads an idea or solution, and then, try to improve, and optimize it if need.
Netflix company culture - take some notes
February 5, 2016
Netflix culture - Julia likes to write down and then think about them.
http://www.fastcompany.com/3056187/the-future-of-work/the-woman-who-created-netflixs-enviable-company-culture?partner=cnnmoney&linkId=21014664#1
Netflix culture: Freedom & Responsibility
Enron, whose leader went to jail, and which went bankrupt from fraud, had these values displayed in their lobby:
Integrity
Communication
Respect
Excellence
The actual company values,
as opposed to the nice-sounding values, are shown by who gets rewarded, promoted, or let go
Actual company values are the behavior and skills that are valued in fellow employees.
At Netflix, we particularly value the following nine behaviors and skills in our colleagues...
... meaning we hire and promote people who demonstrate these nine
Judgement
You make wise decisions (people, technical, business, and creative) despite ambiguity
You identity root cause, and get beyond treating symptoms
You think strategically, and can articulate what you are, and are not, trying to do
You smartly separate what must be done well now, and what can be improved later
Communication
You listen well, instead of reacting fast, so you can better understand
You are concise and articulate in speech and writing
You treat people with respect independent of their status or disagreement with you
You maintain calm poise in stressful situations
Impact
You accomplish amazing amounts of important work
You demonstrate consistently strong performance so colleagues can rely upon you
You focus on great values rather than on process
You exhibit bias-to-action, and avoid analysis-paralysis
Curiosity
You learn rapidly and eagerly
You seek to understand our strategy, market, customers, and suppliers
You are broadly knowledgeable about business, technology and entertainment
You contribute effectively outside of your specialty
Innovation
You re-conceptualize issues to discover practical solutions to hard problems
You challenge prevailing assumptions when warranted, and suggest better approaches
You create new ideas that prove useful
You keep us nimble by minimizing complexity and finding time to simplify
Courage
You say what you think even if it is controversial
You make tough decisions without agonizing
You take smart risks
You question actions inconsistent with our values
Passion
You inspire others with thirst for excellence
You care intensely about Netflix's success
You celebrate wins
You are tenacious
Honesty
You are known for candor and directness
You are non-political when you disagree with others
You only say things about fellow employees you will say to their face
You are quick to admit mistakes
Selflessness
You seek what is best for Netflix, rather than best for yourself or your group
You are ego-less when searching for the best ideas
You make time to help colleagues
You share information openly and proactively
Loyalty is Good
Loyalty is good as a stabilizer
People who have been stars for us, and hit a bad patch, get a near term pass because we think they are likely to become stars for us again
Hard Work - Not Relevant
We don't measure people by how many hours they work or how much they are in the office
We do care about accomplishing great work
Sustained B-level performance, despite "A for effort", generates a generous severance package, with respect
Sustained A-level performance, despite minimal effort, is rewarded with more responsibility and great pay
Brilliant Jerks
Some companies tolerate them
For us, cost to effective teamwork is too high
Diverse styles are fine - as long as person embodies the 9 values.
The Rare Responsible Person
Self motivating
Self aware
Self disciplined
Self improving
Acts like a leader
Doesn't wait to be told what to do
Picks up the trash lying on the floor
Responsible People
Thrive on Freedom, and are worthy of Freedom
http://www.ted.com/watch/ted-institute/ted-bcg/patty-mccord-lessons-from-a-silicon-valley-maverick
Netflix culture - Julia likes to write down and then think about them.
http://www.fastcompany.com/3056187/the-future-of-work/the-woman-who-created-netflixs-enviable-company-culture?partner=cnnmoney&linkId=21014664#1
Netflix culture: Freedom & Responsibility
Enron, whose leader went to jail, and which went bankrupt from fraud, had these values displayed in their lobby:
Integrity
Communication
Respect
Excellence
The actual company values,
as opposed to the nice-sounding values, are shown by who gets rewarded, promoted, or let go
Actual company values are the behavior and skills that are valued in fellow employees.
At Netflix, we particularly value the following nine behaviors and skills in our colleagues...
... meaning we hire and promote people who demonstrate these nine
Judgement
You make wise decisions (people, technical, business, and creative) despite ambiguity
You identity root cause, and get beyond treating symptoms
You think strategically, and can articulate what you are, and are not, trying to do
You smartly separate what must be done well now, and what can be improved later
Communication
You listen well, instead of reacting fast, so you can better understand
You are concise and articulate in speech and writing
You treat people with respect independent of their status or disagreement with you
You maintain calm poise in stressful situations
Impact
You accomplish amazing amounts of important work
You demonstrate consistently strong performance so colleagues can rely upon you
You focus on great values rather than on process
You exhibit bias-to-action, and avoid analysis-paralysis
Curiosity
You learn rapidly and eagerly
You seek to understand our strategy, market, customers, and suppliers
You are broadly knowledgeable about business, technology and entertainment
You contribute effectively outside of your specialty
Innovation
You re-conceptualize issues to discover practical solutions to hard problems
You challenge prevailing assumptions when warranted, and suggest better approaches
You create new ideas that prove useful
You keep us nimble by minimizing complexity and finding time to simplify
Courage
You say what you think even if it is controversial
You make tough decisions without agonizing
You take smart risks
You question actions inconsistent with our values
Passion
You inspire others with thirst for excellence
You care intensely about Netflix's success
You celebrate wins
You are tenacious
Honesty
You are known for candor and directness
You are non-political when you disagree with others
You only say things about fellow employees you will say to their face
You are quick to admit mistakes
Selflessness
You seek what is best for Netflix, rather than best for yourself or your group
You are ego-less when searching for the best ideas
You make time to help colleagues
You share information openly and proactively
Loyalty is Good
Loyalty is good as a stabilizer
People who have been stars for us, and hit a bad patch, get a near term pass because we think they are likely to become stars for us again
Hard Work - Not Relevant
We don't measure people by how many hours they work or how much they are in the office
We do care about accomplishing great work
Sustained B-level performance, despite "A for effort", generates a generous severance package, with respect
Sustained A-level performance, despite minimal effort, is rewarded with more responsibility and great pay
Brilliant Jerks
Some companies tolerate them
For us, cost to effective teamwork is too high
Diverse styles are fine - as long as person embodies the 9 values.
The Rare Responsible Person
Self motivating
Self aware
Self disciplined
Self improving
Acts like a leader
Doesn't wait to be told what to do
Picks up the trash lying on the floor
Responsible People
Thrive on Freedom, and are worthy of Freedom
http://www.ted.com/watch/ted-institute/ted-bcg/patty-mccord-lessons-from-a-silicon-valley-maverick
Wednesday, February 3, 2016
Algorithm: reading blog
February 2, 2016
Think about learning Python today, since Julia likes to read Python code and get some great ideas in the code. She starts to read the blogs from Leetcode question 331 to 1 in descending order.
As a programmer, she spent over 6 months to learn Javascript in 2014, and then she loves to read Javascript code now. So, spend 10 - 20 minutes a day to learn Python, one day she will love to read Python code.
Here is the blog she starts to read.
http://bookshadow.com/leetcode/
https://www.hrwhisper.me/leetcode-algorithm-solution/
http://www.cnblogs.com/grandyang/p/4606334.html
http://www.cnblogs.com/EdwardLiu/tag/Leetcode/
http://www.jiuzhang.com/problem/
Here is the log of her reading:
Feb. 3, 2016
Leetcode: 331, 330, 329, 328, 327, 326
331. Verify Preorder serialization of a Binary Tree
idea: Use stack
330. Patching Array
Read the blog, understand the idea:
https://leetcode.com/discuss/82822/solution-explanation
329. Longest Increasing Path in a matrix
idea: go through each node in the matrix, BFS search, and get minimum one;
328. Odd Even Linked List (Easy)
Julia's comment: think about O(N) space solution first (using array, and then, easy to go through), and then, work on O(1) space solution, the following blog helps:
http://www.cnblogs.com/EdwardLiu/p/5138199.html
Feb. 4, 2016
327 Count of Range Sum
Still confused about the question, the example is also hard to understand.
324. Wiggle Sort II
Julia figured out the easy way to do it, O(n) time, O(1) space. So motivated. Next time, think about algorithm by yourself, start from brute force, and then, work towards requirement - efficient solution.
https://segmentfault.com/a/1190000003783283
public class Solution { public void wiggleSort(int[] nums) { for(int i = 1; i < nums.length; i++){ // 需要交换的情况：奇数时nums[i] < nums[i - 1]或偶数时nums[i] > nums[i - 1] if((i % 2 == 1 && nums[i] < nums[i-1]) || (i % 2 == 0 && nums[i] > nums[i-1])){ int tmp = nums[i-1]; nums[i-1] = nums[i]; nums[i] = tmp; } } } }
322 Coin change
http://www.cnblogs.com/grandyang/p/5138186.html
319 Bulb Switch
http://www.cnblogs.com/grandyang/p/5100098.html
Analysis from the above blog:
February 7, 2-16
Please understand the question, if the problem is too complex, then the understanding may not be not correct.
Leetcode 318: Maximum Product of Word Length
Given a string array
https://www.hrwhisper.me/leetcode-maximum-product-of-word-lengths/
Solution 1:
http://www.cnblogs.com/onlyac/p/5155881.html
Think about learning Python today, since Julia likes to read Python code and get some great ideas in the code. She starts to read the blogs from Leetcode question 331 to 1 in descending order.
As a programmer, she spent over 6 months to learn Javascript in 2014, and then she loves to read Javascript code now. So, spend 10 - 20 minutes a day to learn Python, one day she will love to read Python code.
Here is the blog she starts to read.
http://bookshadow.com/leetcode/
https://www.hrwhisper.me/leetcode-algorithm-solution/
http://www.cnblogs.com/grandyang/p/4606334.html
http://www.cnblogs.com/EdwardLiu/tag/Leetcode/
http://www.jiuzhang.com/problem/
Here is the log of her reading:
Feb. 3, 2016
Leetcode: 331, 330, 329, 328, 327, 326
331. Verify Preorder serialization of a Binary Tree
idea: Use stack
330. Patching Array
Read the blog, understand the idea:
https://leetcode.com/discuss/82822/solution-explanation
329. Longest Increasing Path in a matrix
idea: go through each node in the matrix, BFS search, and get minimum one;
328. Odd Even Linked List (Easy)
Julia's comment: think about O(N) space solution first (using array, and then, easy to go through), and then, work on O(1) space solution, the following blog helps:
http://www.cnblogs.com/EdwardLiu/p/5138199.html
Feb. 4, 2016
327 Count of Range Sum
Still confused about the question, the example is also hard to understand.
324. Wiggle Sort II
Julia figured out the easy way to do it, O(n) time, O(1) space. So motivated. Next time, think about algorithm by yourself, start from brute force, and then, work towards requirement - efficient solution.
https://segmentfault.com/a/1190000003783283
public class Solution { public void wiggleSort(int[] nums) { for(int i = 1; i < nums.length; i++){ // 需要交换的情况：奇数时nums[i] < nums[i - 1]或偶数时nums[i] > nums[i - 1] if((i % 2 == 1 && nums[i] < nums[i-1]) || (i % 2 == 0 && nums[i] > nums[i-1])){ int tmp = nums[i-1]; nums[i-1] = nums[i]; nums[i] = tmp; } } } }
322 Coin change
http://www.cnblogs.com/grandyang/p/5138186.html
这道题只让我们求出最小的那种，对于求极值问题，我们还是主要考虑动态规划Dynamic Programming来做，我们维护一个一维动态数组dp，其中dp[i]表示钱数为i时的最小硬币数的找零，递推式为：
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
其中coins[j]为第j个硬币，而i - coins[j]为钱数i减去其中一个硬币的值，剩余的钱数在dp数组中找到值，然后加1和当前dp数组中的值做比较，取较小的那个更新dp数组
321. Find Maximum number
https://www.hrwhisper.me/leetcode-create-maximum-number/319 Bulb Switch
http://www.cnblogs.com/grandyang/p/5100098.html
Analysis from the above blog:
那么我们来看这道题吧，还是先枚举个小例子来分析下，比如只有5个灯泡的情况，'X'表示亮，‘√’表示灭，如下所示：
初始状态： X X X X X
第一次： √ √ √ √ √
第二次： √ X √ X √
第三次： √ X X X √
第四次： √ X X √ √
第五次： √ X X √ X
那么最后我们发现五次遍历后，只有1号和4号锁是亮的，而且很巧的是它们都是平方数，是巧合吗，还是其中有什么玄机。我们仔细想想，对于第n个灯泡，只有当次数是n的因子的之后，才能改变灯泡的状态，即n能被当前次数整除，比如当n为36时，它的因数有(1,36), (2,18), (3,12), (4,9), (6,6), 可以看到前四个括号里成对出现的因数各不相同，括号中前面的数改变了灯泡状态，后面的数又变回去了，等于锁的状态没有发生变化，只有最后那个(6,6)，在次数6的时候改变了一次状态，没有对应其它的状态能将其变回去了，所以锁就一直是打开状态的。所以所有平方数都有这么一个相等的因数对，即所有平方数的灯泡都将会是打开的状态。
那么问题就简化为了求1到n之间完全平方数的个数，我们可以用force brute来比较从1开始的完全平方数和n的大小
Please understand the question, if the problem is too complex, then the understanding may not be not correct.
Leetcode 318: Maximum Product of Word Length
Given a string array
words, find the maximum value of length(word[i]) * length(word[j])where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.https://www.hrwhisper.me/leetcode-maximum-product-of-word-lengths/
Solution 1:
直接看看每个字符串都包括了哪个字符，然后一一枚举是否有交集：
- 有交集，则乘积为0
- 无交集，乘积为 words[i].length() * words[j].length()
其实因为全部都是小写的字母，用int 就可以存储每一位的信息。这就是位运算
- elements[i] |= 1 << (words[i][j] – ‘a’); //把words[i][j] 在26字母中的出现的次序变为1
- elements[i] & elements[j] // 判断是否有交集只需要两个数 按位 与 （AND）运算即可
http://www.cnblogs.com/onlyac/p/5155881.html
在一个字符串组成的数组words中，找出max{Length(words[i]) * Length(words[j]) },其中words[i]和words[j]中没有相同的字母，在这里字符串由小写字母a-z组成的。
对于这道题目我们统计下words[i]的小写字母a-z是否存在，然后枚举words[i]和words[j]，找出max{Length(words[i]) * Length(words[j]) }。
小写字母a-z是26位，一般统计是否存在我们要申请一个bool flg[26]这样的数组，但是我们在这里用int代替，int是32位可以替代flg数组，用 与（&），或（1），以及向左移位（<<）就能完成。如“abcd” 的int值为 0000 0000 0000 0000 0000 0000 0000 1111，“wxyz” 的int值为 1111 0000 0000 0000 0000 0000 0000 0000，这样两个进行与（&）得到0， 如果有相同的字母则不是0。
Algorithm: Count the number of palindromes in a string
Count the number of
palindromes in a string
January 28, 2016
Write down ideas:
1. First of all, do not count duplicate.
2. Brute force solution:
any substring of O(N^2) substrings to see if it is a palindrome;
Add the substring of palindrome to a hashset if it is not in the hashset.
And return the length of hashset
3. Use recursive solution - using subproblem to solve. Cannot filter out duplicate - not good
4. Better solution - use center point of string - 2n + 1, and then, go over each one, add all palindromes substring.
Requirement: write a C# code in 10 minutes for the solution, using brute force one.
https://github.com/jianminchen/AlgorithmsPractice/blob/master/NumberOfDistinctPalindromes.cs
Tuesday, February 2, 2016
Algorithm: Merge two sorted singly linked list
February 2, 2016
Always work on simple problem. Enjoy the practice. Recursive function design is most important one.
recursive solution:
http://stackoverflow.com/questions/10707352/interview-merging-two-sorted-singly-linked-list
Itearative solution:
http://stackoverflow.com/questions/10707352/interview-merging-two-sorted-singly-linked-list
http://www.geeksforgeeks.org/merge-two-sorted-linked-lists/
Julia's practice:
Recursive solution:
https://github.com/jianminchen/AlgorithmsPractice/blob/master/MergeTwoSortedSinglyLinkedList.cs
Always work on simple problem. Enjoy the practice. Recursive function design is most important one.
recursive solution:
http://stackoverflow.com/questions/10707352/interview-merging-two-sorted-singly-linked-list
Itearative solution:
http://stackoverflow.com/questions/10707352/interview-merging-two-sorted-singly-linked-list
http://www.geeksforgeeks.org/merge-two-sorted-linked-lists/
Julia's practice:
Recursive solution:
https://github.com/jianminchen/AlgorithmsPractice/blob/master/MergeTwoSortedSinglyLinkedList.cs
quicksort: a practice makes difference
February 2, 2016
Introduction
Julia likes to work on basic things on algorithm problem solving, like brute force solution, recursive function design, divide and conquer solution, partitioning; So, she can write code everyday on algorithm.
Review the quicksort algorithm, and then, practice using C# programming language. So many times Julia went through the review of quick sort algorithm, but to write it in less than 10 minutes, without a bug, without stress, takes more dedicated effort - maybe write a blog to share will help.
Julia likes to rewrite the above paragraph in April 9, 2018.
Quicksort warmup
First review the blog - the quick algorithm written in Java programming language. Julia must like the idea of choosing pivot value - "// simple version - pick the right most value as the pivot ". As a sports programmer, Julia knows that the power of using a simple test case, she likes to do it here.
Let us describe how quick sort works: - explain it using 5 minutes - 10 minutes to write the code
1. First, using partition, and then, divide and conquer, use recursive function calls to solve the problem.
Most important technique, is to design a partition - 2-way partition, how to design the partition, choose pivot point, and how to do partition step by step.
Let us work on a simple example and have discussion, show the procedure of partition.
Let us say that array 1, 2, 3, 4, 5, 6, sorted, and then we like to derive the above sorted array using this one, 1, 3, 2, 5, 4, 6.
One of ideas to choose pivot position, is to choose last number in the array. For the example, choose last one in the array, 6, the position of pivot point, left side <= 6, right side > 6. So, do you see the problem, 6 is not ideal case. No swap, second partition with 0 values; in other words, all values go to first partition.
Two way partition
Let us work on another order: 1, 6, 2, 5, 4, 3,
1. Choose pivot value - last element in the array, value 3
2. Work on partition the array, left partition <= 3, right partition > 3
3. Two partitions are 1, 2, 6, 5, 4, 3
1. Choose pivot value - last element in the array, value 3
2. Work on partition the array, left partition <= 3, right partition > 3
3. Two partitions are 1, 2, 6, 5, 4, 3
4. Put the pivot point in-between, 1, 2, 3, 6, 5, 4
5. Divide and conquer, solve two small subproblems, use recursive call.
5. Divide and conquer, solve two small subproblems, use recursive call.
Use a diagram to show progress:
The easy way to remember is to find right partition's start position.
Two way partition - test case
1, 2, 6, 5, 4, 3 -> move pivot value 3 between two partitions
1, 2, 3, 6, 5, 4
Step by step,
first, after partitioning, the array is the following:
1, 2, 6, 5, 4, 3
so right side partition starting from array's index value 2 to 4, values are highlighted in background color of green.
Left side partition:
1 2
left partition, array's index is from 0 to 1.
Right side partition - start and end position.
6 5 4
right partition, array's index is from 2 to 4.
And then the pivot value 3 is inserted in-between left partition and right partition.
1, 2, 3, 6, 5, 4
Let us recap what we practice here, go over a simple test case, and then choose a pivot value, and then partition, divide and conquer, go to solve two small problems using recursive calls.
Julia's practice:
Quick sort algorithm writing in C# - less than 20 minutes (18 minutes to write the code with comments)
Quicksort Lecture Study
Julia, spend one hours to read the webpage, and enjoy the great lecture. Reading is much important than coding. And then, work on some questions in the lecture.
princeton lecture notes
Questions and Answers
February 3, 2016
After reading her favourite lecture notes, Julia likes to respond something to entertain quicksort algorithm practice, put something together with her own thinking based on discussion from reading material:
Fact 1:
Q1. Quick sort algorithm will work even in worst case, no dead loop. Why?
Arguments:
1. Each recursive function, at least one value is resolved, no more work for the value. That is pivot point. So, at most, each recursive call solves one value, n recursive call will solve all n values in the array. Is it fun to design the algorithm? Yes.
Q2. Quicksort function design - only solve one value to position correctly, in the whole array. This is not efficient?
Arguments:
1. This is the fact. And it works fine. And if you remember that, you can write a quick sort algorithm in less than 5 minutes.
2. So, position one value, partition array into two sections.
Q3. Partition can use different strategies, only important and should work on more is to find one, work out as fast as you can. And make it easy to remember. What is your advice?
Advice:
Choose last one in the array as a pivot point, and then, find the partition - swap and maintain a partition (each value in the partition > pivot value) just on right side of array. Use two pointers to find the partition two values - start, end position.
Q4. Is this algorithm using in-place without extra space?
Answer:
Yes, the answer is staying in the original array, no extra space (O(1), not O(n)). So, array is used to store result, only swap two nodes' value if need.
Facts: at most how many swap? it depends. O(n^2)
How many recursive calls? n
Because it is using in-place, the quicksort function design takes 3 input arguments, original array, start, end.
If you cannot come out best design using in-place, you may need extra time.
Feb. 4, 2016 Q5. Work on Leetcode - partition list
86. Partition list
http://www.cnblogs.com/springfor/p/3862392.html
328. Odd Even Linked List
Follow up after 9 months
Nov. 24, 2016
Review the code review about quick sort.
Answer the question, link is here.
Follow up after 13 months
March 14, 2017
1. Read all algorithms in the blog, the blogger got Google and Linkedin offer. The algorithms may be a good study material for Julia.
2. Practice one more time, C# code. Add test case for partition method and quicksort method.
Subscribe to:
Posts (Atom)