388. Longest Absolute File Path
Suppose we abstract our file system by a string in the following manner:
The string
"dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:
dir
subdir1
subdir2
file.ext
The directory
dir contains an empty sub-directory
subdir1 and a sub-directory
subdir2 containing a file
file.ext.
The string
"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" represents:
dir
subdir1
file1.ext
subsubdir1
subdir2
subsubdir2
file2.ext
The directory
dir contains two sub-directories
subdir1 and
subdir2.
subdir1 contains a file
file1.ext and an empty second-level sub-directory
subsubdir1.
subdir2 contains a second-level sub-directory
subsubdir2 containing a file
file2.ext.
We are interested in finding the longest (number of characters)
absolute path to a file within our file system. For example, in the
second example above, the longest absolute path is
"dir/subdir2/subsubdir2/file2.ext", and its length is
32 (not including the double quotes).
Given a string representing the file system in the above format,
return the length of the longest absolute path to file in the abstracted
file system. If there is no file in the system, return
0.
Note:
- The name of a file contains at least a
. and an extension.
- The name of a directory or sub-directory will not contain a
..
Time complexity required:
O(n) where
n is the size of the input string.
Notice that
a/aa/aaa/file1.txt is not the longest file path, if there is another path
aaaaaaaaaaaaaaaaaaaaa/sth.png.
----------------------------------
1. Get the current level
2. Keep the length-so-far of previous levels in stack or array.
Solution #1, with Stack
class Solution {
public int lengthLongestPath(String input) {
Stack<Integer> s = new Stack<>();
int currentLevel = 1;
int index = 0;
String str = "";
int maxLength = 0;
while (index <= input.length()) {
if (index == input.length() || input.charAt(index) == '\n') {
while (currentLevel - s.size() <= 0 && !s.isEmpty()) {
s.pop();
}
int currentLength = 0;
if (!s.isEmpty()) {
currentLength = s.peek() + 1;
}
currentLength += str.length();
s.push(currentLength);
if (isFile(str)) {
maxLength = Math.max(maxLength, currentLength);
}
currentLevel = 1;
str = "";
} else if (input.charAt(index) == '\t') {
currentLevel++;
} else {
str += input.charAt(index);
}
index++;
}
return maxLength;
}
private static boolean isFile(String str) {
return str.indexOf(".") > -1;
}
}
Solution #2, with array
class Solution {
public int lengthLongestPath(String input) {
List<Integer> levels = new ArrayList<>();
int index = 0;
int currentLevel = 0;
StringBuilder stb = new StringBuilder();
int maxLength = 0;
while (index <= input.length()) {
if (index == input.length() || input.charAt(index) == '\n') {
int preLevelSum = getPreLevel(currentLevel - 1, levels);
int currentLength = preLevelSum + stb.length();
levels.add(currentLevel, currentLength);
if (isFile(stb.toString())) {
maxLength = Math.max(maxLength, currentLength);
}
stb = new StringBuilder();
currentLevel = 0;
} else if (input.charAt(index) == '\t') {
currentLevel++;
} else {
stb.append(input.charAt(index));
}
index++;
}
return maxLength;
}
private int getPreLevel(int level, List<Integer> levels) {
if (level < 0) {
return 0;
}
return levels.get(level) + 1;
}
private static boolean isFile(String str) {
return str.indexOf(".") > -1;
}
}
Shorter version, from online
class Solution {
public int lengthLongestPath(String input) {
String[] paths = input.split("\n");
int[] stack = new int[paths.length+1];
int maxLen = 0;
for(String s : paths){
int level = s.lastIndexOf("\t") + 1;
int currentLength = stack[level] + s.length() - level + 1;
stack[level + 1] = currentLength;
if(s.contains(".")) {
maxLen = Math.max(maxLen, currentLength - 1);
}
}
return maxLen;
}
}
683. K Empty Slots
There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.
Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.
For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.
Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.
If there isn't such day, output -1.
Example 1:
Input:
flowers: [1,3,2]
k: 1
Output: 2
Explanation: In the second day, the first and the third flower have become blooming.
Example 2:
Input:
flowers: [1,2,3]
k: 1
Output: -1
Note:
- The given array will be in the range [1, 20000].
------------------------------
Solution #1
1. 建立flower -> day的对应days[]
2. 对于i和 i+k+1 位置的花，如果中间所有的位置开花时间比两者都大，则可以确认i和i+k+1为可能的答案
class Solution {
public int kEmptySlots(int[] flowers, int k) {
int len = flowers.length + 1;
int[] days = reverseFlowers(flowers);
int prePos = 1;
int futurePos = prePos + k + 1;
int index = prePos + 1;
int shortest = Integer.MAX_VALUE;
while (index < len && futurePos < len) {
if (index == futurePos) {
shortest = Math.min(shortest, Math.max(days[futurePos], days[prePos]));
prePos = index;
futurePos = prePos + k + 1;
} else if (days[index] < days[futurePos] || days[index] < days[prePos]) {
prePos = index;
futurePos = prePos + k + 1;
}
index++;
}
return shortest == Integer.MAX_VALUE ? -1 : shortest;
}
private int[] reverseFlowers(int[] flowers) {
int len = flowers.length + 1;
int days[] = new int[len];
for (int i = 1; i < len; i++) {
days[flowers[i - 1]] = i;
}
return days;
}
}
这题有点范围搜索的意思
Solution #2
每开完一朵花，分别检查它左右范围(k+1)的花是否开放，且两者之间的花都未开放
参考：http://zxi.mytechroad.com/blog/simulation/leetcode-683-k-empty-slots/
class Solution {
public int kEmptySlots(int[] flowers, int k) {
int len = flowers.length;
boolean[] bloomed = new boolean[len];
int minDay = Integer.MAX_VALUE;
for (int i = 0; i < len; i++) {
int pos = flowers[i] - 1;
if (isValidDay(pos, bloomed, k)) {
return i + 1;
}
}
return -1;
}
public boolean isValidDay(int pos, boolean[] bloomed, int k) {
int len = bloomed.length;
bloomed[pos] = true;
if (pos + k + 1 < len && bloomed[pos + k + 1]) {
boolean valid = true;
for (int i = pos + 1; i < pos + k + 1; i++) {
if (bloomed[i]) {
valid = false;
break;
}
}
if (valid) return true;
}
if (pos - k - 1 >= 0 && bloomed[pos - k - 1]) {
boolean valid = true;
for (int i = pos - k; i < pos; i++) {
if (bloomed[i]) {
return false;
}
}
return true;
}
return false;
}
}
Solution #3, 用BinarySearchTree来存开过花的位置
class Solution {
public int kEmptySlots(int[] flowers, int k) {
TreeSet<Integer> bst = new TreeSet<>();
for (int i = 0; i < flowers.length; i++) {
int pos = flowers[i];
bst.add(pos);
Integer lower = bst.lower(pos);
Integer higher = bst.higher(pos);
if (bst.lower(pos) != null) {
if (pos - lower == k + 1) {
return i + 1;
}
}
if (bst.higher(pos) != null) {
if (pos + k + 1 == higher) {
return i + 1;
}
}
}
return -1;
}
}
Solution #4, 类似bucket sort，每个bucket的大小为 k + 1
class Solution {
public int kEmptySlots(int[] flowers, int k) {
int len = flowers.length;
int bucketSize = (len + k) / (k + 1);
List<Integer> lower = getBucket(Integer.MAX_VALUE, bucketSize);
List<Integer> higher = getBucket(Integer.MIN_VALUE, bucketSize);
for (int i = 0; i < len; i ++) {
int slot = flowers[i];
int curBucket = (slot - 1) / (k + 1);
if (slot < lower.get(curBucket)) {
lower.set(curBucket, slot);
if (curBucket > 0 && slot - k - 1 == higher.get(curBucket - 1)) {
return i + 1;
}
}
if (slot > higher.get(curBucket)) {
higher.set(curBucket, slot);
if (curBucket < bucketSize - 1 && slot + k + 1== lower.get(curBucket + 1)) {
return i + 1;
}
}
}
return -1;
}
public List<Integer> getBucket(int fill, int size) {
List<Integer> rt = new ArrayList<>();
for (int i = 0; i < size; i ++) {
rt.add(fill);
}
return rt;
}
}
