# A/B Summary

XAMPP案例 1092浏览

LC336 —- M8
https://leetcode.com/problems…
Step 1: store all strings as <string, index> in a map;
Step 2: if there’s an empty string “”, find all strings which are palindrome, pair them –> save both (i, j) and (j, i);
Step 3: reverse each word, check if its reversed already in the map, pair and save them;
Step 4: for each word, break it into two parts, if part[0] is palindrome, check if there’s reversed part[1] in the map; and vice versa;
Note: use Arrays.asList(i, index) for simplicity

LC755 —- M14
https://leetcode.com/problems…
class Solution {
public int[] pourWater(int[] heights, int drops, int pos) {
if (heights == null || heights.length == 0 || drops == 0) return heights;
int index;
while (drops > 0) {
index = pos;
//找到pos左边最低点
for (int i = pos-1; i >= 0; i–) {
if (heights[i] > heights[index]) break;
if (heights[i] < heights[index]) index = i;
}
//若确实存在最低点，放入水滴，升高height，继续下一次循环
if (index != pos) {
heights[index]++;
drops–;
continue;
} else {
//否则，说明左边没有找到，index还在pos点，去找右边的最低点
for (int i = pos+1; i < heights.length; i++) {
if (heights[i] > heights[index]) break;
if (heights[i] < heights[index]) index = i;
}
//因为左边全是高点了，不可能放水滴，所有无所谓index是否变化，直接放水滴
heights[index]++;
drops–;
}
}
return heights;
}
}

class Solution {
public int[] pourWater(int[] heights, int drops, int pos) {
if (heights == null || heights.length == 0 || drops == 0) return heights;
int maxHeight = 0;
int totalHeights = 0;
for (int height: heights) {
maxHeight = Math.max(maxHeight, height);
totalHeights += height;
}
int total = maxHeight*heights.length;
int totalWaters = total-totalHeights;
if (drops > totalWaters) System.out.println(“Water will overflow.”);
int[] waters = new int[heights.length];
int index;
while (drops > 0) {
index = pos;
//找到K左边最低点
for (int i = pos-1; i >= 0; i–) {
if (heights[i]+waters[i] > heights[index]+waters[index]) break;
if (heights[i]+waters[i] < heights[index]+waters[index]) index = i;
}
//若确实存在最低点，放入水滴，升高height，继续下一次循环
if (index != pos) {
//*增加难度：放之前可以检查index两边是否有墙
waters[index]++;
drops–;
continue;
} else {
//否则，说明左边没有找到，index还在K点，去找右边的最低点
for (int i = pos+1; i < heights.length; i++) {
if (heights[i]+waters[i] > heights[index]+waters[index]) break;
if (heights[i]+waters[i] < heights[index]+waters[index]) index = i;
}
//因为左边全是高点了，不可能放水滴，所有无所谓index是否变化，直接放水滴
//*增加难度：放之前可以检查index两边是否有墙
waters[index]++;
drops–;
}
}
print(heights, waters);
int[] combined = new int[heights.length];
for (int i = 0; i < heights.length; i++) {
combined[i] = heights[i]+waters[i];
}
return combined;
}
private void print(int[] heights, int[] waters) {
int maxHeight = 0;
for (int i = 0; i < heights.length; i++) {
maxHeight = Math.max(maxHeight, heights[i]);
}
for (int height = maxHeight; height >= 0; height–) {
for (int i = 0; i < heights.length; i++) {
if (height <= heights[i]) {
System.out.print(“+”);
} else if (height > heights[i] && height <= heights[i]+waters[i]) {
System.out.print(“W”);
}
}
System.out.println();
}
}
}

Water will overflow.
+WWWWW+
+WWWWW+
++W++W+
+++++++
+++++++

M7
create, set, get
follow-up: watch(path, callBackFunc())
detail: if path invalid, throw exception
https://rextester.com/PCH74934
class Rextester {
public static void main(String args[]) {
FileSystem fs = new FileSystem();
fs.create(“/a”, 1);
System.out.println(“get(\”/a\”) => ” + fs.get(“/a”));
System.out.println();
fs.create(“/a/b”, 2);
System.out.println(“get(\”/a/b\”) => ” + fs.get(“/a/b”));
System.out.println();
fs.create(“/c/d”, 3);
System.out.println(“get(\”/c\”) => ” + fs.get(“/c”));
System.out.println();
fs.set(“/a/b”, 4);
System.out.println(“get(\”/a/b\”) => ” + fs.get(“/a/b”));
System.out.println();
fs.watch(“/a”, “/a call back triggerred”);
fs.watch(“/a/b”, “/a/b call back triggerred”);
fs.create(“/a/b/c”, 10);
System.out.println();
fs.set(“/a/b/c”, 11);
System.out.println();
fs.set(“/a/b/c”, 23);
}
static class FileSystem {
Map<String, Integer> map;
Map<String, Runnable> callbackMap;
public FileSystem() {
this.map = new HashMap<>();
map.put(“”, 0);
this.callbackMap = new HashMap<>();
}
public boolean create(String key, int value) {
if (map.containsKey(key)) {
return false;
}
String prefix = key.substring(0, key.lastIndexOf(“/”));
if (!map.containsKey(prefix)) {
System.out.println(“Error creating file: File path does not exist.”);
return false;
}
map.put(key, value);
System.out.println(“Successfully created.”);
return true;
}
public boolean set(String key, int value) {
if (!map.containsKey(key)) {
System.out.println(“Error setting file: File path does not exist.”);
return false;
}
map.put(key, value);
String curt = key;
while (curt.length() > 0) {
if (callbackMap.containsKey(curt)) {
callbackMap.get(curt).run();
}
curt = curt.substring(0, curt.lastIndexOf(“/”));
}
System.out.println(“Successfully set.”);
return true;
}
public int get(String key) {
if (!map.containsKey(key)) {
return -1;
}
return map.get(key);
}
public void watch(String path, String alert) {
Runnable runnable = new Runnable() {
public void run() {
}
};
callbackMap.put(path, runnable);
}
}
}

LC251 —- M3

LC269

LC787 —- M25
print 飞行路径

M22
output: name, not price; item can be reused; DFS

M9
Data is read-only. So use lower/upper bound, watch for duplicate cases.

M2
push/poll/pop
BOGGLE游戏 —- Boggle Game / Word Search II
LC212 —- M24

LC773 —- M19
Implement 2 functions: canSolve() and getPath()

Dijkstra —- M30

M6
11-28

LC843

M33
11-28

Collatz Conjecture
2018-10
IP to CIDR
LC751 – M10
Combination Sum
Round Price
Wiggle Sort
Bank System
CSV Parser
Display Page / Pagination
Board Score
Text Justification
Regular Expression
Pyramid Transition Matrix
House Robber
Employer Free Time
Number of Night can accommodate
Preference List
Hilbert Curve
Finding Ocean
K Edit Distance
Find Case Combinations of a String