回文对 Palindrome Pairs
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
倒水 Pour Water
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+
+++++++
+++++++
文件系统 File System
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() {
System.out.println(alert);
}
};
callbackMap.put(path, runnable);
}
}
}
二维迭代器 Flatten 2D Vector
LC251 —- M3
外星字典 Alien Dictionary
LC269
便宜航班 Cheapest Flights Within K Stops
LC787 —- M25
print 飞行路径
菜单 Menu Order
M22
output: name, not price; item can be reused; DFS
坑：double的精度
优化：memorization (key shouldn’t be double, use integer)
找中位数 Find Median in Large File of Integers
M9
Data is read-only. So use lower/upper bound, watch for duplicate cases.
滑雪题 (to be continued)
设计队列 Implement Queue with fixed-size array
M2
push/poll/pop
BOGGLE游戏 —- Boggle Game / Word Search II
LC212 —- M24
滑动九宫格 —- Sliding Puzzle (8 puzzle)
LC773 —- M19
Implement 2 functions: canSolve() and getPath()
十巫师 10 Wizards
Dijkstra —- M30
旅行伙伴 Find Buddy
M6
11-28
猜词 Guess the word
LC843
猜数字 Guess Number
M33
11-28
有向图遍历 Minimum Vertices to traverse Directed Graph
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
转载请注明：XAMPP中文组官网 » A/B Summary