冬令时个人打卡贴

yt.sssun 发表于 2020-11-08 01:25:54
同从每月刷题打卡贴过来。没有帖子了好不适应，于是我也自己开了一贴自行记录。楼主加油。 (P.S. 发现好像这个贴不能给点赞加大米。。。所以是因为刷题打卡贴大家大米涨的太快影响卖会员的业绩了嘛）

我发现连回帖都没有提醒的 可能这个版直接禁止了加米等一系列操作 其实非常讽刺
你也加油(๑•̀ㅂ•́)و✧

Day 25 Daily + freq

Daily 563. Binary Tree Tile

Calculate the sum first recursively. (DFS)
Calculate the diff btw left child and right child and add it to global result. (DFS)

227. Basic Calculator II

General using the stack idea.
I have one stack for numbers and the other one for operators
If it is + or -, I push to the stack, if it is * or /, I retrieve top from stack of numbers and calculate the result.
Second pass is to calculate the result of + and -.

The code could be briefer like treating + and - as sign of numbers directly. So we only have * and / operators and just do the calculation. Lastly calculate the numbers in the stack so we only need one stack then.

162. Find Peak Element

Even watch the MIT video I still did not get why the binary search idea is correct.

529. Minesweeper

Love minesweeper!
Basically recursion.
figure out the neighbours when itself is 'B' aka '0' mines around.

32. Longest Valid Parentheses

I have "left view" and "right view" in my mind.
so first run from left to right to see if ( is more than ), keep going until the end of the string so we have a couple of range that # of ( is larger than # of right.
Next, do the reversed thing to each range so the range of range should have equal # of left and right.
I store the number of each range by map. Other data structures are fine too.

Keep going!

Day 25 Daily + freq

Daily 563. Binary Tree Tile

Calculate the sum first recursively. (DFS)
Calculate the diff btw left child and right child and add it to global result. (DFS)

227. Basic Calculator II

General using the stack idea.
I have one stack for numbers and the other one for operators
If it is + or -, I push to the stack, if it is * or /, I retrieve top from stack of numbers and calculate the result.
Second pass is to calculate the result of + and -.

The code could be briefer like treating + and - as sign of numbers directly. So we only have * and / operators and just do the calculation. Lastly calculate the numbers in the stack so we only need one stack then.

162. Find Peak Element

Even watch the MIT video I still did not get why the binary search idea is correct.

529. Minesweeper

Love minesweeper!
Basically recursion.
figure out the neighbours when itself is 'B' aka '0' mines around.

32. Longest Valid Parentheses

I have "left view" and "right view" in my mind.
so first run from left to right to see if ( is more than ), keep going until the end of the string so we have a couple of range that # of ( is larger than # of right.
Next, do the reversed thing to each range so the range of range should have equal # of left and right.
I store the number of each range by map. Other data structures are fine too.

Keep going!

Day 25 Daily + freq
Why my replies require review?

Day 26 Daily + High Freq

Daily 1026. Max diff btw ancestor and the current node

Very typical recursion + tree question

347. Top K Freq Elements

I am using the classic map + priority_queue solution.
Need to figure out how to do quick selection here.

692. Top K Freq Words

Very similar to the last question. I used the same solution and adjust based on the details of the question
Same. Need to figure out the quick selection solution. Partial sorting is important.

515. Find Largest Values

Row scan. Tree+queue

1.Two sum

Don't know why the time becomes so high after one year.

Keep fighting.

Day 27 Daily + high freq
Did pony.ai interview x 2 tonight.
Don't have time to push my projects...

Daily. 832. Flipping an image

one-pass for loop is enough
Don't really understand the meaning of such questions...

No. 977 Squares of a sorted array

Kinda construct a merge sort case.
Find the min absolute value first, I can find that via binary search but I did not realize during coding.
One array is [min] - end and the other is [min] - start. Calculate the abs and choose which to add for each turn.
Process the remaining array items

No.540 Single Element in an array

Binary search.
The condition is to compare it to its "pair", pair is the following item if even, or previous item if odd.
If it is not the same, means the single item exists before index, otherwise after.
Compare current with prev and next to see if this is the item directly.

No.78 Subsets

Like permutation.
do it one by one.
For each newly coming item, we can add such item to all previous results, and just itself. This forms a new result for next item to use.

No.239 Sliding WIndow Maximum

I've written a slow result using priority_queue.
I've pushed value to a priority queue for the coming items.
For leaving items, I push to another priority queue, and
I pop the top of the second queue if it is equal to the first queue, aka the result for that window is changing. Keep doing this until not equal or the second queue is empty.
nlogn I think

Then I checked the discussion. Smart solution is using deque. Kinda they compare the lastly pushed value with the new item to ensure the queue is descending.
So the first item is the result for such sliding window.
Moreover, when an item leaves the window, check if it is top and remove if true.

Decent.

Keep fighting.

Day 28. Daily Only. Pony ai has been processed to the maybe last interview (with manager...)
FB may provide STE (compared to FTE quq)

Day 29. Daily only

Day 30 Daily + high freq

Daily. populating next right

row scan. I've done much faster than last year haha

350. Intersection of Two Arrays

map solution is feasible for all kinds with T(n) = O(n)
considering if both are sorted. It is still O(n) actually.

257. Binary Tree paths

Very typical recursion (DFS)

207. Course Schedule

Topological sort
My solution is slow and I realized that instead of manipulating containers/vectors, adding if clause after reducing the indegree to see if such is a candidate for indegree=0 is better

622. Design circular queue

Record two pointers to know where is the start and where is the end. Instead, I use an end pointer and track the read size of the queue.

Keep fighting.

Why deleted my day 30???
Ridiculous

Daily 31