冬令时个人打卡贴

上个月才开始刷题，觉得每日打卡互相加米的氛围很好，甚至眼熟了不少互相加米的小伙伴，可惜现在不允许打卡贴了，其实感觉每日打卡还是很激励自己每天至少做一点题的
刚下了一些高频题，那接下来就继续刷高频叭

Day 18
不愧是你 高频题 果然有些做过了 如果是一个月内做过的我就不再做一次了

973. K Closest Points to Origin

比较decent的做法是重写priority queue的比较器，然后queue里存的是以distance增长排序的{distance,point} pair
但是我偷懒了所以我就直接用把distance压入priority queue，同时以distance为key建立一个map，value存的是同一个distance的那些点的下标，当然也可以直接存点，我不过是省一点点空间
然后提取K个点的时候，考虑到有可能第k个是存在于某一个vector的中间，所以我同时count要返回的vector大小，一旦已经有k个点了，就停下

415. Add strings

虽然说是easy，但是写起来也不是特别短，从后往前加，记录进位即可

199. Binary Tree Right Side View

其实我挺喜欢BFS的，整体就是一个queue+while就能解决的
每次记录queue的大小，于是知道当前行有多少个node，根据这个大小把当前行的left,right都压入queue中
因为是right side view，所以把每一行结尾的那个值sum起来

211. Design Add and Search Word

终于写了Trio，之前只是看了下Trio的数据结构
感觉写得不是特别decent但是过了诶嘿嘿
数据结构就是一棵树，每个节点存一个letter以及是否是单词(ending with this letter)
不论是add还是search都牵扯到深度遍历树的操作
add的话就是找是否存在，存在就继续往下走，不存在就开始添加结点
search的话，针对非dot就是一样地操作，dot就得遍历当前所有的子node，于是我这里就用递归了，然后如果已经验证到最后一个letter了，那就要判断isWord，我这儿写得就很啰嗦
优化的话做了个从map到vector的优化，存孩子们的时候，因为已知letter一共就26个(a-z)，所以可以预设26个TrioNode，确实快了些

124. Binary Tree Maximum

首先是递归
然后最大和是全局的，所以我用了一个引用参数方便全局比较
每次计算包含当前节点的最大和，也就是root, root+left, root+right, root+left+right，以此和全局最大和比较
每次返回的是以当前节点为起始点的最大path，于是这个结果才能和parent node相连

就酱

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 19 Daily+高频

Daily是指针的插入排序，就直接做了插入，如果借助map可能可以二分，不确定是不是这样所以有些结果更快

用一个preHead这样可以处理头部插入
每次插入要确保有一个指针指向当前指针的next，用来遍历
然后被插入后的prev和next之间的关联都要构建上

543. Diameter of BT

前几天做过一个path sum的，一个思路，只是这个更简单因为只有正数

636. Exclusive Time of Functions

题目描述里写了stack了，所以就是用stack
一个stack记录function id，如果有新的function就直接压
一个stack记录时间，如果有新的function就计算当前function的delta time，然后pop这个timestamp
如果pop了function，则根据是否存在旧的function来resume，resume的方式就是push一个当前的timestamp

76. Minimum Window Substring

不知道为什么写出来不是最快的，时间分析依然是O(N+M)
我的做法是先找到一个满足要求的，然后sliding window，每次往后移动，发现有目标letter的子集shift start index,确实不是最优
之前看的最优的是每次有了一个满足的，就从前shift，直到不能shift，于是由这么一个不满足条件的string开始拓展end index，直到发现下一个满足要求的
emmm 尝试了从map改到vector， 确实快了
感觉这个题得再写一遍，至少看思路上能不能把我的两个for block变成一个

349. Intersection of two arrays

这个简单，第一次做了仨循环 O(M+N+M)，第二次减少了一次循环，但时间上差距不大

Day 20. Daily + 高频，哎 这pe选票

Daily 1446. Consecutive char

最长连续同一字符，easy

215. Kth largest element

刷了一个月题觉得这个就是明朗的priority_queue
所以同时尝试了非priority_queue的写法，或者说感觉自己并不能把最小化堆默出来
自己的写法就是先放k个，进行排序klogk，然后二分插入

173. BST

本质就是inorder
solution里那个只插入left child，然后next的时候再进行剩余步骤的遍历，感觉更严格地控制了S(N)

767. reorg string

隔着插入高频letter
一个map统计
一个map排序高频
然后隔着插入

140. word break

还是先写了个TLE的，感觉在做了一遍纯单词检测后，整理单词位句子的部分依然没有做到最优
一年前写的是这个

top-down的递归，但是每次把已经成为句子的vec<string>以首尾index为key存起来作为memo
还是应该看看人家的写法因为我的不够快，感觉这个key太局限，可能有些重复判定

加油

Day 21 Daily only

Day 22 Daily + high freq Qs

1217. Minimum Cost to Move Chips to The Same Position

Don't get it. It is really easy

98. Validate Binary Search Tree

pass a range to each recursion function call.
Check if the left son is btw [small, root] or the right son is btw root, small]
Then recursively check left son and right son.

1004. Max Consecutive Ones III

Counting 1s all the time
Using a sliding window to see how many 1s we have
Flip 0 to 1 when K is > 0

528. Random Pick with Weight

calculate an accumulated sum array for preparation
get the random number between 0 and sum-1
use binary search to see where the random number should fall regarding the accumulated array

Fighting

Day 23 Daily + high freq

1283. Find the smallest divisor

did not get the question until I see an explanation. I am kinda not familiar with the word divisor.
Once I got the point, so it is a math+binary search question.
Let's find the boundary first, the smallest one is sum/threshold and the largest one is the max(nums[i]).
Then let's calculate the result to see where to shift.
Typically nmax * long,

419 Battleships in a board

did not come up up with a solution without changing the original board
I've to change the board content when I find a new battleship.
The solution is smart, detect if this is a "start" of a battle ship and then count # of start

463. Island Perimeter

quite straightforward. subtract by the # of neighbors.

50.Pow(x,y)

keep memo the results of n=2^int until n is larger than required.
then use another loop to multiplies the result from memo.

200. Number os islands
I still need to change the original board.
"visit" the cell if it is part of the island we found. Recursively change the neighbors on 4 directions.

keep fighting.

Why my replies got deleted????
Day 23

Day 24. Only daily today

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