7月缺米的来刷题/Mock interview活动

慕容清 发表于 2020-07-04 07:11:53
打卡第三天

打卡第四天

leetcode*6 做了链表的几道新题还复习了几道之前做过的题目
92.reverse linked list ii: recursive还是用了基本的reverse linked list 的操作。如果初始节点对应位置为0，那么直接就reverse节点直到相应的位置。如果不是，那么当前节点cur对应保留，对cur.next进行recursive，同时m- -，n- -。
如果是iterative, 需要考虑corner case, 是否是从头进行反转，还是从中间的某个节点进行反转，可能出现空指针的情况。
21.merge two sorted list: 同样recursive，进行比较head节点的值，值较小保留，对head.next再次进行迭代。基本的base case就是其中一个为null，返回另一个。
Iterative: 引入dummy head。
86.partition list. Iterative的做法同样是引入dummy head, 存储两个linked list，之后再将这两个list进行合并，注意存储large节点的list最后节点要保证large.next = null, 否则会出现cycle。
143.reorder list: 主要是之前几道题目的整合：快慢指针找到中间节点，之后将后半部分进行reverse，然后将前后两部分进行整合。
141.linked list cycle: 判断是否有循环，直接进行快慢指针的判断，如果有循环的话，快指针套圈慢指针，两者总会相遇。否则快指针会先到终点。
142.linked list cycle ii: 利用cycle的性质以及快慢指针。

今天还是刷array的题

第5天打卡：
今天刷了3题。

Group Sold Products By The Date
Count Submatrices With All Ones
Hamming Distance

Count Submatrices With All Ones 还需要再花一些时间看最优解。

Jun 5 打卡第4天，7道题
1504. Count Submatrices With All Ones, contest没做出的原因没有想到m*n的形状如何被计算；再加一层循环k进行sum的遍历就可以计算进来这种形状的；
211. Maximal Square, DP，三个方向取最小值可以确定是否构成一个square；
461. Hamming Distance, Brian Kernighan’s Algorithm计算count of 1；每次只考虑最右边的1，计算loop的次数即可；
85. Maximal Rectangle, 第一种解法类似于周赛第三题，TC: O(m^2n);  morrischen解法是从某个点基于此时的高度往左右延伸，最大的矩形一定包含在内；
84. Largest Rectangle in Histogram, brute force , Divide conquer; 可以用stack做，类似于积雨水？也有在某个点向左右延伸的解法。

第二天打卡，复习并新刷了两道题， 逐渐有点感觉了。

今天三题，达成！！

7.5  zszszszszszszszszszszszs

7.5打卡，
做了三个，两道和ugly number相关，方法：记录要增长的index
一个是根据出现频率给字母排序，方法：bucket sort
Ugly Number               
Super Ugly Number
Sort Characters By Frequency

菜鸡七月第六天

学习了一下bit operation
1. hamming distance: hamming distance主要是看两个数XOR之后的1的数量，xor之后可以看最后一位是不是1然后把x^y right shift
    直到right shift到0
2. total hamming distance: 学习了一下新方法，先从loop每个digit，再loop array里面的每个number，通过(num >> i)&1来找1的count，
    在每个digit的时候有count个1，(n - count)个0，总的来讲会contribute count*(len - count) to the hamming distance
3. number of 1 bits: 和hamming distance差不多，每次可以用n&1, n = n>>> 1，或者用n&=(n-1)
4. bitwise ORs of subarrays: 这个用了hashset，每次在新的set加一个integer，再加上i|j for j in current set, 最后再把所有的加到result的set
    里面，最后return size
5. minimum window substring：这个用sliding window，先找到符合条件的window，再试图移left pointer直到不再含有substring，记下
    minimum length再继续找下一个

今天又是写啥啥不会的一天

今天刷的几题如下：