在职招新工作刷题贴

430. Flatten a Multilevel Doubly Linked List - Stack
114. Flatten Binary Tree to Linked List - DFS + Stack
116. Populating Next Right Pointers in Each Node - DFS 以后重新看下
357. Count Numbers with Unique Digits - Recursion backtracking
77. Combinations - Backtracking 用current list和candidates组建新的list，长度一样加入return，同类型很多，以后复习
526. Beautiful Arrangement - 和77差不多
667. Beautiful Arrangement II - Backingtracking TLE了，要直接construct string 有recursion的问题的time complexity不够熟练。。
1215. Stepping Numbers - 主要还是找到规律 heap用来保证大小
1079. Letter Tile Possibilities - 77差不多

529. Minesweeper - 用bfs做 helper function return 点击周围的mine的数量 题目表述不是很清楚
819. Most Common Word - 难点在于python怎么去掉符号
167. Two Sum II - Input array is sorted - two pointer 用sorted这个特点做
205. Isomorphic Strings- 没啥好说的
557. Reverse Words in a String III
286. Walls and Gates - BFS
1101. The Earliest Moment When Everyone Become Friends - Union find,到现在都没有特别熟悉 要多做
1135. Connecting Cities With Minimum Cost - union find 同1101，要多做

264. Ugly Number II - python要先用heap把所有ugly number算出来然后solution创造一个ugly instance然后回最后一个
252. Meeting Rooms
253. Meeting Rooms II - heap push结束的时间然后新的meeting开始的时间和最早结束的meeting比较 用heap保持最早结束的房间
1046. Last Stone Weight - 用heap保持最重的石头 python没有max heap就所有数字乘-1 记得改回来就行
973. K Closest Points to Origin - sort distance array然后回倒数第k个
378. Kth Smallest Element in a Sorted Matrix - 这道题有点复杂 heappush 一个list ( 当前row的开头用来排序 index 整个row ) 然后把每个row push进heap list的当前数字保证了heap头上的是最小的 然后依次pop下去就行
451. Sort Characters By Frequency - sort hashmap然后组成新的string
1217. Play with Chips - 把所有的都移到一边 再odd位上可以不花钱移到1，even - 0， 看even odd哪个多就行
692. Top K Frequent Words - heap
23. Merge k Sorted Lists - 和378 差不多 要复习

还有好多题没加 下班来加

684. Redundant Connection - dfs找到有见到过的node就说明有circle 有circle就说明这个是多余的边 好多题都是以这个想法为基础做的 circle detection
207. Course Schedule - 如果course schedule有circle就说明课不能全上 所以用684的做法
743. Network Delay Time - heap 和dfs的结合 以后要复习
734. Sentence Similarity - easy 略
737. Sentence Similarity II - 用dfs做 stack而不是recursion
547. Friend Circles - 简单的dfs 遍历所有1的位置加1
323. Number of Connected Components in an Undirected Graph - 同547
841. Keys and Rooms - 拿到key后dfs遍历下去就行 难得在于怎么记录progress 用array of booleans代表是否能进每一个房间
205. Isomorphic Strings - 复习下
531. Lonely Pixel I - 遍历全图 m*n的2d array记录出现次数
533. Lonely Pixel II - 和531差不多 但是用hashmap记录
851. Loud and Rich - 用dfs找到每一个比person有钱的人 一开始tle了 加了一个map记录了一下每个人所对应的答案就快了很多 取出来很多重复操作
108. Convert Sorted Array to Binary Search Tree - 简单的recursion
394. Decode String - 用stack做 好多edge case
979. Distribute Coins in Binary Tree - 死活想不出怎么做 其实题目只想找root和leaf的coin数量差距 每个node需要多少个coin
105. Construct Binary Tree from Preorder and Inorder Traversal
106. Construct Binary Tree from Inorder and Postorder Traversal - 这两题都是主要用postorder 和 preorder的特点 即root在第一个和最后一个来确定当前的root 然后在inorder里面找到左边和右边leaf的inorder顺序 往下recursion
198. House Robber - 根据公式推导怎么通过n来返回答案 iterative从下往上做 不然tle
213. House Robber II - 比较1-[n-1] 和2-n哪个大

10/22/2019
146 LRU Cache: 用多余的data structure来提升time complexity 但是还是没有O(1), 以后来复习
721 Account Merges: union find会了一点 - find找到root， union把两个node的root连在一起 初始化的时候每个node的root都是自己 然后根据题目input union每个node 最后把root拿出来 连在一起的都是一个区域的

10/26/2019
最近做的几道题
957. Prison Cells After N Days 直接做TLE 用hashmap来检测是不是cycle才不会TLE
767. Reorganize String 用heap存储(count, char),每次取两个最大的char然后append 'xy'*count_y, 再把x加回heap 直到heap空了为止
109. Convert Sorted List to Binary Search Tree 用fast slow prev三个node取中间的node 然后recursion就完事了
219. Contains Duplicate II  因为是<=k 所以只要存储最近的一次occurrence就行
708. Insert into a Cyclic Sorted List 两个condition 普通的数(比最大小比最小大),直接insert就行 或者最大最小 找打尾部就行
147. Insertion Sort List 复习insertion sort 之后复习一下bucket sort
148. Sort List 复习merge sort
280. Wiggle Sort 数学题。。

hr说没有headcount所以没做题 重新开始刷题
713. Subarray Product Less Than K 从左开始找到最大的然后除法找到距离 two pointer 中间所以的subarray都加到答案 每次位置变化都会多 right - left + 1
75. Sort Colors 只有三个数字所以小于1的放到左边的pointer然后+1大于一放到右边-1
18. 4Sum 排序 然后每个数字做3sum n^3
844. Backspace String Compare 我是从尾巴开始one pass的 写的很复杂 stringbuilder可能会精简很多
76. Minimum Window Substring 用sliding window和dictionary做 *** 以后重新做
142. Linked List Cycle II 龟兔赛跑  先确认有cycle 然后从cycle那个点和head继续赛跑 最后碰到的地方就是开头 原理是数学证明
57. Insert Interval 每个interval看过来 然后update new interval

12.22.2019
Grokking the coding interview
Merge Interval
Cyclic Sort - 把数字放到对应的index上
Reverse Linked List - prev, cur, next
Breadth First Search - queue

12/23/2019
Grokking the coding interview
Chapter BFS, DFS
Two heaps 做了一半 sliding window有点难 用heapq.index做 对于leetcode 480

Grokking:
Two heap: 用来找中位数等等
Subset: 像bts一样一步一步往下找答案 主要有 上一个iteration的答案
Binary Search: 主要记住 mid=left+(right-left)//2