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

菜鸡七月第二十九天

1. task scheduler: july challenge里的，又抄了一遍之前的，先找最多的task，然后再算中间的空余的位置，看剩下的task够不够填进去，
    如果有没填上的位置就加到整个task length里面
2. merge k sorted lists: 学习了用一个priority queue，可以用lists.length, (a, b)->a.val - b.val来specify，然后从pq里面poll同时加到list里
3. partition equal subset sum: 先算整个sum，然后如果sum是奇数就没法split，是偶数的话就除以二然后用dp，dp array装可不可以实现
    当前num，同时用dp[i] = dp[i] || dp[i-num]
4. transpose matrix: 偷懒挑了一道easy，很简单把新的matrix[r][c]设成之前的matrix[c][r]
5. contains duplicate II: 可以用一个set来存k个value，每次i超过k的时候就去掉第i-k-1，如果set已经有当前element了就return true，
    不然的话到最后就return false

来来来，都来刷题

每天一练，充实自己

29. Divide Two Integers 这道题很奇怪，实际上是用bit shift来实现除法，可以用is来实现XOR的功能判断正负，然后两层循环可以计算出商。
19. Remove Nth Node From End of List 这是一道中等题，关键是想明白如何一遍就能找到倒数第n的，其实设置两个指针就行，linkedlist都是这么玩的，一个快一个慢，然后当快的到底的时候，慢的正好在n-1的位置上。
22. Generate Parentheses 一开始想到写一个函数用栈来判别括号是否有效，然后遍历全部的。后来发现只要记录左括号和右括号的数目就能判别是否有效，如果没有中括号和大括号的话。然后就写了递归来实现，实现后发现自己写的还是过于复杂，递归传参的时候只要传string就可以了。

Day 12
Reorder Data in Log Files: edge case: when two logs are same, it should be ordered based on identifier, could put the identifier in the end
Binary Tree Postorder Traversal:练习了iterative的方法，if use cur_node = stack.pop() in the end, 需要注意处理stack 空的情况
K Closest Points to Origin: use heap to save the top k points
Convert Binary Search Tree to Sorted Doubly Linked List: inorder traverse binary search tree and update left and right pointer
Burst Balloons        : dp 问题, 一个array的问题可以拆成左边最优解+右边最优解+当前值*最前面的值（左侧的其他值已经被pop完了）*最后面的值（右侧的其他值已经被pop完了），遍历所有可能求最优解

gyzdmgqy 发表于 2020-7-29 12:10
29. Divide Two Integers 这道题很奇怪，实际上是用bit shift来实现除法，可以用is来 ...

好巧😄

好帖求米求监督哈哈哈！

睡前两题睡得香。。

7.28 day22 July LeetCoding Challenge
昨天没做

Day 18

621. Task Scheduler, heap + deque 或者用数学实现
498. Diagonal Traverse, loop中多一个direction flag 或者利用diagonal上元素的column index 和 row index的和相同
1296. Divide Array in Sets of K Consecutive Numbers, freq count + sort/heap

7/28 打卡第28天， 刷了3道题

146. LRU Cache
使用双向的linked list, 可以方便删除和前插，用hashtable存node

240. Search a 2D Matrix II
从左下角或右上角开始收索

387. First Unique Character in a String
Hash table