眯眯眼猫头鹰的小树杈

Owned By Deer&Owl

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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.

要求从String字符串中找到最长的文件路径。这里要注意，要求的是文件路径，文件夹路径不予考虑。文件和文件夹的区别在于文件中一定包含.。

这里\n代表根目录平级，每多一个\t就多一层路径，这一层路径都是相对于当前的上层路径的。
以dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext为例
dir为第0层目录
\n\tsubdir1代表subdir1是第一层目录，且其是当前父目录dir的子目录
\n\t\n\tsubdir2代表subdir2为第一层目录，且其是当前父目录dir的子目录，此时的一级父目录从subdir1更新为subdir2
\n\t\tfile.ext代表tfile.ext为二级目录，位于当前一级目录subdir2之下

思路和代码

综上分析，我们可以记录一个信息，即当前每一级的目录究竟是谁，每次只需要保留当前一级目录已有的路径长度即可。还是拿上面的例子dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext：

1
2
3
4
5
6
遍历完dir: 0级目录长度为3
遍历完\n\tsubdir: 0级目录长度为3, 1级目录长度为11（dir/subdir1）
遍历完\n\tsubdir2: 0级目录长度为3, 1级目录长度为11（dir/subdir2）
遍历完\n\t\tfile.ext: 0级目录长度为3, 1级目录长度为11（dir/subdir2）, 2级目录长度为20

综上，最长的文件路径长为20

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public int lengthLongestPath(String input) {
     if(input==null || input.isEmpty()) return 0;
     //记录当前每一级路径对应的路径长度
     List<Integer> stack = new ArrayList<Integer>();
     int left = 0, right = 0;
     int max = 0;
     int curDepth = 0;
     //当前遍历的是文件还是文件夹
     boolean isFile = false;
     while(right < input.length()) {
         char c = input.charAt(right);
         if(c == '\n' || c == '\t') {
             //如果是文件分割符的起点，则处理前面的字符串
             if(right-1>=0 && input.charAt(right-1)!='\n' && input.charAt(right-1)!='\t') {
                 int length = right - left;
                 if(stack.isEmpty()) {
                     stack.add(length+1);
                 }else if(curDepth == 0){
                     stack.set(0, length+1);
                 }else{
                     int prev = stack.get(curDepth-1);
                     int now = prev + length + 1;
                     if(stack.size() <= curDepth) {
                         stack.add(now);
                     }else{
                         stack.set(curDepth, now);
                     }
                 }
                 if(isFile) {
                     max = Math.max(max, stack.get(curDepth)-1);
                 }
                 left = right;
                 isFile = false;
             }
             
             //如果是文件分隔符的末尾，则处理文件分隔符，判断是几级路径
             if(right+1<input.length() && input.charAt(right+1)!='\n' && input.charAt(right+1) !='\t'){
                 curDepth = right - left;
                 left = right+1;
             }
         }else if(c == '.') {
             isFile = true;
         }
         right++;
     }
     //处理最后的字符串
     if(left != right && isFile) {
         if(curDepth == 0) {
             max = Math.max(max, right - left);
         }else {
             max = Math.max(max, stack.get(curDepth-1) + right - left);
         }
     }
     return max;
 }

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

找出字符串中的最长子字符串，满足该子字符串中任何字符出现的次数都大于k。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

For 1-byte character, the first bit is a 0, followed by its unicode code.
For n-bytes character, the first n-bits are all one's, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.
This is how the UTF-8 encoding would work:

   Char. number range  |        UTF-8 octet sequence
      (hexadecimal)    |              (binary)
   --------------------+---------------------------------------------
   0000 0000-0000 007F | 0xxxxxxx
   0000 0080-0000 07FF | 110xxxxx 10xxxxxx
   0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
   0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
Given an array of integers representing the data, return whether it is a valid utf-8 encoding.

Note:
The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.

Example 1:

data = [197, 130, 1], which represents the octet sequence: 11000101 10000010 00000001.

Return true.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.
Example 2:

data = [235, 140, 4], which represented the octet sequence: 11101011 10001100 00000100.

Return false.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.

检验整数数组能否构成合法的UTF8编码的序列。UTF8的字节编码规则如下：

  1. 每个UTF8字符包含1~4个字节
  2. 如果只包含1个字节，则该字节以0作为开头，剩下的位随意
  3. 如果包含两个或两个以上字节，则起始字节以n个1和1个0开头，例如，如果该UTF8字符包含两个字节，则第一个字节以110开头，同理，三个字符的第一个字节以1110开头。剩余的字节必须以10开头。
阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

设计一个数据结构，使得从该数据结构中查询一个数字时，能够以等概率返回该数字所在的任何下标。额外的要求是只要占用O(1)的额外的空间复杂度。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

设计一个数据结构，使得能够在O(1)的时间复杂度中插入数字，删除数字，以及随机获取一个数字。要求所有的数字都能够被等概率的随机出来。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.
insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.
Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

设计一个数据结构，支持能够在O(1)的时间内完成对数字的插入，删除和获取随机数的操作，允许插入重复的数字，同时要求每个数字被随机获取的概率和该数字当前在数据结构中的个数成正比。

强烈建议先看一下这个问题的基础版本，传送门在这里。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.
Note: 
You may assume k is always valid, 1 ≤ k ≤ n2.

在一个从左到右，从上到下均有序的二维数组中，找到从小到第k个数字，这里需要注意，不要求一定要是唯一的值，即假设存在这样一个序列1,2,2,3，则第三个数字是2而不是3。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

一个猜数字游戏，数字区间为1~n，每猜一次，会有人告诉你猜中了或者当前的数字是大于结果值还是小于结果值。猜对则本次猜测免费，猜错则本次猜测需要花费和数字等额的金钱。
问如果要确保能够猜中数字，最少要花费多少钱。

其实这题的英文表述有些问题，确切来说，在所有能够确保找到目标值的方法中，找到花费金钱最少的哪种。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
Given an integer n, return 1 - n in lexicographical order.

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

将1n这n个数字按照字母序排序，并返回排序后的结果。
即如果n=13，则113的字母序为1,10,11,12,13,2,3,4,5,6,7,8,9

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
Given an encoded string, return it's decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

将一个字符串解码，要求按照次数展开原字符串中的中括号。如3[a]2[bc]对应的字符串就是aaabcbc，即a展开3次，bc展开2次。注意，源字符串中的括号是允许嵌套的，且展开的字符中不会包含任何数字。

阅读全文 »
0%