细语呢喃

技术改变生活

0%

leetcode contest 1 solution

发表于 分类于 ， 阅读次数： 评论数：

The problems contains:

    1. Lexicographical Numbers
    1. First Unique Character in a String
    1. Longest Absolute File Path

386. Lexicographical Numbers

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.

题目地址：leetcode Lexicographical Numbers

题意：给定整数n，返回1~n的所有数字组成的集合，要求按照字典的顺序

思路：写一个生成器即可。比如1的我们就试试10 100这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def lexicalOrder(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        if n < 1: return []
        res = []
        for first in xrange(1, 10):
            if first > n: break
            res.append(first)
            self.get_all_number(first,n,res)
        return res

    def get_all_number(self, first, n, res):
        for i in xrange(10):
            t = first * 10 + i
            if t <= n:
                res.append(t)
                self.get_all_number(t, n, res)
            else:
                break

 

387. First Unique Character in a String

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

1
2
3
4
5
s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

题目地址：leetcode First Unique Character in a String

题意：给定一个仅由小写字母组成的字符串，寻找第一个只在字符串中出现的字母的下标

思路：水。 我懒得自己写26大小的数组来统计了。直接Counter类。 毕竟要看女排 →_→

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        x = collections.Counter(s)
        for i, c in enumerate(s):
            if x[c] == 1:
                return i
        return -1

 

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:

1
2
3
4
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:

1
2
3
4
5
6
7
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, return0.

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.

题目地址：leetcode Longest Absolute File Path

题意：给定一串路径，求最长的文件路径。

思路：

这题大概就是记录一下上一层目录在哪结尾的，换新的目录就替换一下。(t_cnt为)，当然这个过程也可以用栈来做。

注意，一定是要文件！目录不行！

下面是我当时为了看女排比赛写的代码，没有优化- -

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
class Solution(object):
    def lengthLongestPath(self, s):
        """
        :type s: str
        :rtype: int
        """
        t_cnt = collections.defaultdict(int)
        t_cnt[0] = ans = last_t_cnt = cur_t_cnt = 0
        cur_path = ''
        is_file = False
        while s:
            n = len(s)
            index = s.find('\n')
            if cur_t_cnt <= last_t_cnt:
                cur_path = cur_path[:t_cnt[cur_t_cnt]]

            t_cnt[cur_t_cnt] = len(cur_path)
            if cur_t_cnt != 0: cur_path += '/'
            if index != -1:
                next_t_cnt = 0
                for i in xrange(index + 1, n):
                    if s[i] == '\t':
                        next_t_cnt += 1
                    else:
                        break

                cur_s = s[:index]
                is_file = cur_s.find('.') != -1

                cur_path += s[:index]
                s = s[1 + next_t_cnt + index:]
                last_t_cnt, cur_t_cnt = cur_t_cnt, next_t_cnt

            else:
                cur_path += s
                is_file = s.find('.') != -1
                s = None
            if is_file:
                ans = max(ans, len(cur_path))

        return ans

上述的模拟过程可以用如下的代码替代(并且不用构造串，直接记录长度)，比我的简洁太多 Orz 一下 StefanPochmann

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def lengthLongestPath(self, input):
        maxlen = 0
        pathlen = {0: 0}
        for line in input.splitlines():
            name = line.lstrip('\t')
            depth = len(line) - len(name)
            if '.' in name:
                maxlen = max(maxlen, pathlen[depth] + len(name))
            else:
                pathlen[depth + 1] = pathlen[depth] + len(name) + 1
        return maxlen

 

本次是下面几道题的题解

  • leetcode 386. Lexicographical Numbers  
  • leetcode 387. First Unique Character in a String
  • leetcode 388. Longest Absolute File Path

更多题解可以查看：https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~