# 目的

## 从 Amazon OA 高频题开始

### 146. LRU Cache

##### 解法一

``````protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}``````

``````class LRUCache {
private int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > capacity;
}
};
}

public int get(int key) {
if (cache.containsKey(key)) {
return cache.get(key);
}
else {
return -1;
}
}

public void put(int key, int value) {
cache.put(key, value);
}
}
/*
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/``````
##### 解法二

``````class LRUCache {
private class Node {
int key, value;
Node prev, next;
Node() {
this(0, 0);
}
Node(int k, int v) {
this.key = k;
this.value = v;
}
}

private int capacity, count;
private Map<Integer, Node> map;

public LRUCache(int capacity) {
this.capacity = capacity;
this.count = 0;
map = new HashMap<Integer, Node>();
// 定义头结点和尾节点
tail = new Node();
}

public int get(int key) {
Node n = map.get(key);
if (null == n) return -1;
update(n);
return n.value;
}

public void put(int key, int value) {
Node n = map.get(key);
if (null == n) {
n = new Node(key, value); // 没有这个值，直接新建就行
map.put(key, n );
++count;
}
else {
n.value = value; // 用新值替换
update(n);
}
if (count > capacity) {
Node toDel = tail.prev;
remove(toDel);
map.remove(toDel.key);
--count;
}
}

private void update(Node node) {
remove(node);
}

head.next = node; // 头结点后是 node
node.next = after; // node 后是 after;
after.prev = node; // after 前是 node;
}

// Double Linked List remove a node
private void remove(Node node) {
// Get the previous node and the after node.
Node before = node.prev, after = node.next;
// assign the next pointer of before node pointing to after; and the after node previous pointer points to before thus caneeling the connection of the node.
before.next = after;
after.prev = before;
}
}

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/``````
• Takeaway

### 42. Trapping Rain Water

##### 解法一: Brute Force

``````class Solution {
public int trap(int[] height) {
int sum = 0;
for (int  i = 1; i < height.length; i++) {
int maxLeft = 0;
for (int j = i -1; j >= 0; j--) {
if (height[j] > maxLeft) {
maxLeft = height[j];
}
}

int maxRight = 0;
for (int k = i + 1; k < height.length; k++) {
if (height[k] > maxRight) {
maxRight = height[k];
}
}

if (height[i] < Math.min(maxLeft, maxRight)) {
sum += Math.min(maxLeft, maxRight) - height[i];
}
}

return sum;
}
}``````

##### 解法二: 动态规划

``````class Solution {
public int trap(int[] height) {
int[] maxLeft = new int[height.length];
int[] maxRight = new int[height.length];

for (int i = 1; i < height.length; i++) {
// 这里的 trick 是求第 i 列的左边最大值时，只需将第 i-1 列的左边最大值和它的高进行比较即可。
maxLeft[i] = Math.max(maxLeft[i -1], height[i-1]);
}

for (int i = height.length -2; i >= 0; i--) {
maxRight[i] = Math.max(maxRight[i + 1], height[i+1]);
}

int sum = 0;
for (int i = 0; i < height.length; i++) {
if (height[i] < Math.min(maxLeft[i], maxRight[i])) {
sum += Math.min(maxLeft[i], maxRight[i]) - height[i];
}
}

return sum;
}
}``````

### 200. Number of Islands

##### 解法一: DFS

``````class Solution {
public int numIslands(char[][] grid) {
// 处理空数组，防止溢出
if (grid == null || grid.length == 0) {
return 0;
}

int row = grid.length;
int col = grid[0].length;
int numIsland = 0;
for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
if (grid[r][c] == '1') {
numIsland++; // 遇到 1 就进行一次 DFS, 那么必然有一个岛。
dfs(grid, r, c);
}
}
}
return numIsland;
}

private void dfs(char[][] grid, int r, int c) {
int row = grid.length;
int col = grid[0].length;
// 边界条件
if (r < 0 || c < 0 || r >= row || c >= col || grid[r][c] == '0') {
return;
}

grid[r][c] = '0'; // 标记查找过的点为 0
// 查找四个方向
dfs(grid, r + 1, c);
dfs(grid, r - 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
}``````
##### 解法二: BFS

• Takeaway
• 我们在本题中不需要用另外数组来记录 visited points，把访问过的点直接置零即可，因为 DFS 的退出条件之一就是访问到 '0' 这个点。
• 需要注意的是题中 grid 是 char 类型的二维数组，并非数字！如果给点赋值数字会造成 DFS 无法退出死循环。
##### 819. Most Common Words

``````class Solution {
public String mostCommonWord(String paragraph, String[] banned) {
/*
Create a HashMap to store every word.
*/
HashMap<String, Integer> map = new HashMap<>();
String str = paragraph + ".";
// 这里的 trick 是，对于 “a, c, b,b,b, e” 这样的 test case, 先替换逗号会造成三个 'b' 连在一起，所以先替换', ' (逗号及空格) 为 ',' 再替换 ',' 为空格。这样一来语句的格式就正确了。不过居然有人会想出这样的 test case 实在是太恶心了。。
String[] newStr = paragraph.replaceAll("\\, ",",").replaceAll("\\,"," ").replaceAll("\\.","").replaceAll("\\!","").replaceAll("\\?","").replaceAll("\\'","").replaceAll("\\;","").split(" ");
// 对字符串数组进行遍历，如果在 banned list 中就不加入 HashMap 里，不在的话就转换成小写后加入。
// 如果是第一次加入，就令 value 为 1；否则 value 加一。
for (String s : newStr) {
boolean containBanned = false;
for (String b : banned) {
if (s.toLowerCase().equals(b)) {
containBanned = true;
}
}
if (map.containsKey(s.toLowerCase()) && !containBanned) {
int value = map.get(s.toLowerCase());
map.put(s.toLowerCase(), value+1);
}
else if (!containBanned)
{
map.put(s.toLowerCase(), 1);
}
}
// Loop for the HashMap to find out the most frequent word (Not in the banned String lists).
Set<Map.Entry<String, Integer>> set = map.entrySet();
int max = 0;
String maxKey = "";
for (Map.Entry<String, Integer> s : set) {
if (s.getValue() >= max) {
max = s.getValue();
maxKey = s.getKey();
}
}
return maxKey;
}
}``````
• Takeaway
• 编程中出现了一些错误，比如忘记了所有的字符串比较存储都应该是在先转换成小写字符的前提下的。另外，Entry 是在 Map下的，所以得使用这种调用方式: Map.Entry。还有就是要时刻记住给变量赋值时两边类型应该一样！！

(=￣ω￣=)··· 暂无内容！

52

4

11

16