蜗居匹兹堡孤独刷题中

Wilson_2014 发表于 2019-2-9 07:57
多谢你的信息啊！
那天我进去了，排了半天微软，排到之后，他们告诉我我已经毕业了，不应该参加这个。还 ...

Soga，原来是这样，我之前也不知道毕业之后参加career fair限制那么大。不好意思呀！
不过没关系，加油刷题！！相信你总有一天可以杀进梦司的~~

Opus_A 发表于 2019-2-9 08:02
Soga，原来是这样，我之前也不知道毕业之后参加career fair限制那么大。不好意思呀！
不过没关系，加油 ...

还是非常感谢你的信息！你也加油！

Day 4 - 2019/02/08

834. Sum of Distances in Tree
又想了一遍，这道题实在是比较难。
首先要发现这样的规律：ans[x] - ans[y] = #(Y) - #(X)
在求解过程中使用两次DFS：
第一遍，count[node] += count[child] 和 stsum[node] += stsum[child] + count[child]
由此我们得到了第二遍DFS用到的公式中需要的初始值：ans[root] = stsum[root]
第二遍，计算ans[child] = ans[parent] - count[child] + (N - count[child])
注意：第一遍DFS是自底向上，第二遍DFS是自顶向下
注意：这里还用到了一个在Tree中不走回头路的技术，那就是只比较孙辈和爷辈是不是一样，因为Tree里面没有环，所以这样足以保证不走回头路。

655. Print Binary Tree
在DFS过程中，不仅要知道level还需要知道打印的位置，所以需要传入l和r。
先建一个String[][]把""都填入

652. Find Duplicate Subtrees
构建string来比较，注意null的处理。
注意对于结果的除重
这道题也要再练

156. Binary Tree Upside Down
背住答案吧

572. Subtree of Another Tree
这类题很多，就起个名字叫双层递归吧。

513. Find Bottom Left Tree Value
DFS或者BFS都行，把每行结果都记录下来是没必要的。

285. Inorder Successor in BST
递归的方法也应该掌握，注意判断的条件是： 如果小于等于，就往右边找。 别把等于忘记了。

872. Leaf-Similar Trees
我对leaf value sequence相等没理解对。
第一次用到list1.equals(list2)

894. All Possible Full Binary Trees
这道题和96，95有相似之处。由左右两子树的解构建新的解的时候，需要用nested loops，新解数量是两边解的cartesian product。

563. Binary Tree Tilt
这个题非常容易让人误解。但是解法是树类题中最常用的一种。关键是递归的定义。


129. Sum Root to Leaf Numbers
应该随时都练一练的经典题

450. Delete Node in a BST
改变树的结构的题都不容易。这道题要多练。

814. Binary Tree Pruning
随时练一练的经典题。关键是递归的定义。

889. Construct Binary Tree from Preorder and Postorder Traversal
和106，105一样的题，还是注意index别搞错

897. Increasing Order Search Tree
inorder非递归做了。test case有毛病，不管了。

426. Convert Binary Search Tree to Sorted Doubly Linked List
怎么感觉和897是一道题。用的inorder非递归

298. Binary Tree Longest Consecutive Sequence
经典解法的题，多种解法都要会。还有一点不让代码太丑的小技巧。

255. Verify Preorder Sequence in Binary Search Tree
这个题难啊。 为什么要在这个点上检查是否valid呢？理解了这个解法，但是这样的灵感是怎么来的？

Day 5 - 2019/02/09

今天看了Stefan Pochmann大神水下魔方表演，再在讨论区看他的代码的时候又多了几分膜拜。

510. Inorder Successor in BST II
BST题目的基本技术，找successor和predecessor

270. Closest Binary Search Tree Value
BST中大小比较的题目。

272. Closest Binary Search Tree Value II
感觉这也是一道好题。 正反两次inorder，把predecessors和successors分别存入两个stack。
注意double和int的比较：
int a = 2， double b = 2.0;
System.out.println(a == b); // true

515. Find Largest Value in Each Tree Row
比较基础的题。
这里有用ArrayList.add(int index, E elemen)和ArrayList.remove(int index)。也可以用ArrayList.set(int index, E elemen)

508. Most Frequent Subtree Sum
题目简单写起来烦。用DFS得到所有sum及其对应的频次。

559. Maximum Depth of N-ary Tree
分治法

700. Search in a Binary Search Tree
最简单的BST寻值题，递归和迭代都要会

701. Insert into a Binary Search Tree
简单的BST题目

671. Second Minimum Node In a Binary Tree
这个树有很大的特殊性。老实用暴力法，或者背住优化解法。

学而不思则罔，这6天做了76道Tree有关的题，现在总结一下，以便以后再做。也学王国维或者某章来个三重境界娱乐一下自己：

第一重境界：
inorder/preorder/postorder/levelorder是解决树类题目的基本功（ 94，144，145）
递归和迭代，正着来反着来，都要会，随时背一遍。
用Queue的levelorder练习题：101, 102，637

第二重境界：
递归作为解决树类题目的基本手段，细分了一下：
1 答案即是递归的定义： 104, 226, 617, 100, 235, 669，112，404 ）
2 需要定义新的递归，递归的定义是关键： 124，543，437，250， 687，563 ， 814，129
3 和数组有关的递归需要传入坐标 (108, 654， 105，655 )
4 需要定义RstType的递归 (110)
5 双层递归 （222，572）
6 DFS求所有方案：107， 103， 653， 113， 652，508
7 DFS求极值：111，230，513，501，298，515，671
8 需要考虑爷孙三辈： 337

分治法也是解决树类题目的常用方法： 236，114， 257，559
某种顺序遍历（递归或者迭代）： 199， 606，872， 897， 426，

BST类题目的常见技术：
Inorder traversal： 99，538
successor：285
successor/predecessor的综合运用：272
iterator实现：173
BST中增删查改：270，700，701， 450

第三重境界：
类型题：各类方法的综合应用，各种解法都要握
1 非常重要的Serialization and Deserialization: 297， 449， 98
2 用某两种遍历顺序的数组构建树：105，106，889
3 Next Right Pointers类题目：116， 117

最后，走火入魔之奇技淫巧系列：
绝对不像是自己想出来的：255
与树有关的数学题：96， 95， 894
Tree和Graph结合的题目：834
改变树的结构：156

楼主有没有想过挂靠呀？有没有什么别的渠道呀？学校教授要怎么找挂靠呢？

打卡打卡 不努力就去死 努力一定会成功

Day 6 - 2019/02/10

今天开始做Graph的题，原计划是做10道，投十个公司，可是没有完成，在269上面浪费了太多时间了。明天加油吧。

133. Clone Graph
基础高频题

269. Alien Dictionary
第一眼感觉很难啊，再一看就是拓扑排序嘛。这个题描述很有歧义，研究了几个case才确定自己的理解是对的，然后搞了两个多小时，到处缝缝补补处理各种情况，5次wrong才过了。

这道题的关键在于判断什么时候是edge。 什么时候出现了环。一开始我的方法是每一轮遍历所有word在同一个index上的字符。
看了讨论区之后，发现自己的思路不太好，我应该遍历这个Words数组，两两比较才对，这样会简单一些，因为我要找的edge（char -> char)只出现在相邻的两个word之间，这两个word的顺序只由这一条edge决定。这样可以少处理一些情况。

吃完午饭又用讨论区的方法做了一遍，这道题真是需要非常细心。
这时候判断有环的方法不同了，有环的一点，无法达到入度为零，所以我们可以在最后一步进行判断。
还有就是重复的edge的处理，要避免重复增加入度。

发现讨论区还有一个更优一点的解法，留到下次练吧。

令狐大神告诉我们：每一个公司都有一道拓扑排序题。是时候再练几道了！

207. Course Schedule
如果先做这道题，对于成环这件事就会理解更深一些
这类题要掌握优化空间复杂度的方法（adjacency list)，要会把大函数分成小函数(initialization)。

210. Course Schedule II
DFS和BFS都要会，我现在还不会DFS。
这道题的答案似乎写得很好啊。等总结图类题目的时候一定看一下。

444. Sequence Reconstruction
queue里保持一个元素，这样序列就唯一了。

399. Evaluate Division
首先，这道题要能够想到是一道graph的题。然后要想清楚在DFS过程中需要哪些值，用什么数据结构保存这些值，回溯过程中应该注意什么，如何不走回头路，如何传递计算结果。 这是一道比较综合的题，应该多练。

要注意用Double.compare(double a, double b)
这个题还有UninFind的解法，下次再练。

lz加油 我就跟着你刷了

Day 7 - 2019/02/11

743. Network Delay Time
这个题用到的算法感觉非常陌生，图论全忘了
至今还是想不通DFS的时间复杂度为什么是N的N次方。没走到一个点，面临N - 1个选择，一共要走N个点，于是就是N个N相乘，似乎是这样。

DFS算法：
使用int[]记录下一个点及其花费的时间。
构建Graph之后，把List of next node info 排个序，这样利于DFS中的剪枝。
使用一个Map，记录到达一个点需要的最短时间，这是这个题的关键。
在DFS过程中，如果到达此点的时间，比Map记录的最短时间长，那么就不需要走下去了。
如何判断是否到达所有点？将这个记录最短达到时间的Map用Integer.MAX_VALUE初始化,如果DFS完成的时候还是这个值,那就是没有走到过.

Dijkstra's single source shortest path Algorithm(权重图最短路径算法)
这个算法应用的场景:1)权重图;2)给定出发点;2)最短路径

这个算法的关键在于如何确定下一步要走的点: （贪心法，局部最优就是全局最优）
对List of next node这些点，使用edge的赋值将next点到原点的距离update一下（操作一），然后走向距离原点最近的那个点（操作二）
操作一：Decrease-Key
操作二：Extract-Min

本题的做法是:
用Map记录所有点目前的最短距离, 这同时也记录了目前走过的点，可以用来不走回头路.
用minHeap保存下一点的距离.这里的距离是指距离出发点的总距离,不要和edge的权重搞混了.

时间复杂度:
1. 不用minHeap是V平方
         1) extract-min操作要遍历所有点，所以是O(V)时间。总时间是O(V^2)
         2）

2. 如果这个graph是sparse的(E = o(V ^ 2 / logV)), 那么可以用binary minHeap或者Fibonacci Heap优化时间复杂度。

优化后是O((V + E)lgV):
         1) 建堆是O(logV)时间 * V = O(VlogV)
         2) 堆的poll操作花费logV时间,有多少条边就有多少poll操作,所以是ElogV时间.
         一共就是O((V + E)logV)   可以看出来只有E = o(V^2/logV)，这个才是优化的，不然还是V方。

不用minHeap的算法有一个while（true）循环，不知道怎么才能不用。

332. Reconstruct Itinerary
首先，这个题意保证了这是一个Eulerian circuit or Eulerian cycle（an Eulerian trail which starts and ends on the same vertex）
StefanPochmann用了Greedy DFS, building the route backwards when retreating。非常简洁明了
可是，面试的时候如何证明这个算法的正确性？如何把这个算法解释清楚？这个算法到底是Hierholzer算法吗？

维基百科上描述的Hierholzer算法：
By using a data structure such as a doubly linked list to maintain the set of unused edges incident to each vertex, to maintain the list of vertices on the current tour that have unused edges, and to maintain the tour itself, the individual operations of the algorithm (finding unused edges exiting each vertex, finding a new starting vertex for a tour, and connecting two tours that share a vertex) may be performed in constant time each, so the overall algorithm takes linear time, O(|E|)
并没有搞清楚上面的算法和这个Greedy DFS, building the route backwards when retreating是不是一回事。

硬着头皮写了一个DFS回溯的算法但是发现的testcase里还有这样的重复edge，这算欧拉回路吗？
[["EZE","AXA"],["TIA","ANU"],["ANU","JFK"],["JFK","ANU"],["ANU","EZE"],["TIA","ANU"],["AXA","TIA"],["TIA","JFK"],["ANU","TIA"],["JFK","TIA"]]
只好又改成用Map存所有的ticket，操作起来繁琐极了。最后也没有通过，是TLE。 最终还是完全copy了答案里的那个backtracking。