Amazon OA 资料

作者 QIFAN 日期 2017-01-24
Amazon OA 资料

OA 1

前期准备主要看小土刀。Amazon OA

OA 2

地里找的九道题。

Number of valid parentheses
BST minimum sum path
Reverse Second Half of Linked List
Rotate Matrix
Longest Palindrome
Rectangle Overlap
DeepCopy ListNode
K Closest Points
Window Sum

1. Number of Valid Parentheses

给一个 String ,里面只包括 “[“ 与 “]” ,如果不是 valid ,返回 -1 ,否则返回 valid 的括号的个数。
使用 stack 做。要考虑的 corner case 如 “][[“ , “[[]” 。
代码:ValidParentheses.java

2. BST Minimum Sum Path

找到从 root 到 leaf 的最小路径和。
用递归做。
代码:BSTMinPathSum.java

3. Reverse Second Half of Linked List

将 LL 的后半部分翻转。
这是找中点和翻转 LL 的结合。用一快一慢两个指针先找到中点,再翻转。在 next 改变的时候注意先后顺序,不要陷入死循环。
代码:ReverseHalfLL.java

4. Rotate Matrix

把一个 m * n 的矩阵旋转 90 度。顺时针转和逆时针转都写一下。
最简单的思路是,先以对角线为轴翻转一下(顺时针的话翻左下->右上,逆时针翻左上->右下),然后上下翻转。
代码:RotateMatrix.java
只翻转一次的思路在这 48. Rotate Image

5. Longest Palindrome

给定一个字符串,返回最长的回文。
动态的移动回文的中心 $ 0 <= i <= n - 1$ ,如果可以扩展为一条回文,则与当前最大长度比较。注意展开回文可以是偶数,也可以是奇数。
代码: LongestPalindrome.java

6. Rectangle Overlap

给定两个矩形的左下与右上坐标,求重合面积。
和这道题一样的思路 223. Rectangle Area
代码: RectangleOverlap.java

7. DeepCopy ListNode

思路看这篇。LeetCode 138 - Copy List with Random Pointer

8. K Closest Points

Given a list of points and a central point, find the k nearest points from the central point.
k 临近想到 MaxHeap 和 MinHeap 。就是 PriorityQueue 。
代码: KNearest.java

9. Window Sum

There is a list and a window. The window says the number of elements to be added in the list, for example:
[4, 2, 73, 11, -5] and window size 2 should return [6, 75, 84, 6]
注意输入为空,或者 windows 长度小于 0 或比 list size 还大。
代码: WindowSum.java