细语呢喃

技术改变生活

0%

leetcode contest 5 solution

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

本次题解包括：

  • 400 Nth Digit
  • 401 Binary Watch
  • 402 Remove K Digits
  • 403 Frog Jump

leetcode 400. Nth Digit

Find the _n_th digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...

Note: n is positive and will fit within the range of a 32-bit signed integer (n < 231).

Example 1:

1
2
3
4
5
Input:
3

Output:
3

Example 2:

1
2
3
4
5
6
7
8
Input:
11

Output:
0

Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

传送门：leetcode Nth Digit

题意：给定一个数字n，求从1开始的整数中，第n个字母

思路：主要是求出该数字需要的位数，因为一位数有9*1，两位数有90*2​，三位数有900*3以此类推。剩下的直接看看是否整除啥的即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def findNthDigit(self, n):
        """
        :type n: int
        :rtype: int
        """
        num = 9
        cnt = 1
        while n > num * cnt:
            n -= (num * cnt)
            num *= 10
            cnt += 1
        t = n // cnt
        base = 10 ** (cnt - 1) + t
        if t * cnt == n: return (base - 1) % 10
        n -= t * cnt
        return int(str(base)[::-1][-n])

 

leetcode 401. Binary Watch

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads "3:25".

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

1
2
Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

  • The order of output does not matter.
  • The hour must not contain a leading zero, for example "01:00" is not valid, it should be "1:00".
  • The minute must be consist of two digits and may contain a leading zero, for example "10:2" is not valid, it should be "10:02".

传送门：leetcode Binary Watch

题意：给定一个二进制的表，让你求时间。其中，用1，2，4，8 表示小时，1，2，4，8，16，32表示分钟。给定n，让你求在n盏灯亮的情况下，可以表示的所有时间。

思路：可以直接DFS，注意小时<12,分钟<60。感觉可以位运算，过阵子再看看。

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
class Solution(object):
    def readBinaryWatch(self, num):
        """
        :type num: int
        :rtype: List[str]
        """
        hour = [1, 2, 4, 8]
        minute = [1, 2, 4, 8, 16, 32]
        _time = hour + minute
        res = []
        self.dfs(0, 0, [0, 0], _time, len(hour), num, res)
        ans = []
        for h, m in res:
            ans.append(str(h) + ":" + str(m).zfill(2))
        return ans

    def dfs(self, j, cnt, cur, _time, time_len, k, ans):
        if cnt == k:
            ans.append(cur[:])
            return
        for i in range(j, len(_time)):
            if i < time_len:
                cur[0] += _time[i]
                if cur[0] < 12:
                    self.dfs(i + 1, cnt + 1, cur, _time, time_len, k, ans)
                cur[0] -= _time[i]
            else:
                cur[1] += _time[i]
                if cur[1] < 60:
                    self.dfs(i + 1, cnt + 1, cur, _time, time_len, k, ans)
                cur[1] -= _time[i]

 

leetcode 402. Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

  • The length of num is less than 10002 and will be ≥ k.
  • The given num does not contain any leading zero.

Example 1:

1
2
3
4
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

1
2
3
4
Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

1
2
3
Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

传送门：leetcode Remove K Digits

题意：给定一个num（字符串）和k，让你从num中删除k个字符使得整个字符串值最大。

思路：用栈。保证栈里的元素比较小即可。类似于leetcode Remove Duplicate Letters 以及 leetcode Create Maximum Number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        n = len(num)
        remain = n - k
        if remain <= 0: return '0'
        s = []
        for i in range(n):
            while s and s[-1] > num[i] and len(s) + n - i > remain:
                s.pop()
            s.append(num[i])
        if len(s) > n - k: s = s[:-k]
        return ''.join(s).lstrip('0') or '0'

 

leetcode 403. Frog Jump

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

Note:

  • The number of stones is ≥ 2 and is < 1,100.
  • Each stone's position will be a non-negative integer < 231.
  • The first stone's position is always 0.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
[0,1,3,5,6,8,12,17]

There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.

Return true. The frog can jump to the last stone by jumping 
1 unit to the 2nd stone, then 2 units to the 3rd stone, then 
2 units to the 4th stone, then 3 units to the 6th stone, 
4 units to the 7th stone, and 5 units to the 8th stone.

Example 2:

1
2
3
4
[0,1,2,3,4,8,9,11]

Return false. There is no way to jump to the last stone as 
the gap between the 5th and 6th stone is too large.

传送门：leetcode Frog Jump

题意：给定一个数组，要你从第一个位置到最后一个位置。（第一个位置总是0，第一步为1），当前跳了k步，那么下一次只能k+1,k,或者k-1步，问是否能从第一个位置到最后一个位置。

思路：

青蛙过河，上一次跳k长度，下一次只能跳k-1,k或者k+1。

因此对于到达了某一个点，我们可以查看其上一次是从哪个点跳过来的。

设dp[ j ][ i ] 为从i到达j 的步数，初始时把所有的石头存放进hash表。然后设置dp[0][0] = 0. 接着对于每个石头，从可以到达该石头的所有石头中取出步数k（k > 0），然后当前的stone + k看其是否是合法的石头，是的话就有d[stone + k ][stone] = k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def canCross(self, stones):
        """
        :type stones: List[int]
        :rtype: bool
        """
        dp = {stone: {} for stone in stones}
        dp[0][0] = 0
        for stone in stones:
            for step in dp[stone].values():
                for k in [step + 1, step, step - 1]:
                    if k > 0 and stone + k in dp:
                        dp[stone + k][stone] = k
        return len(dp[stones[-1]].keys()) > 0

另一种写法

设dp[j][i] 从i可以到达j，因此，对于点 j，我们只需要查看可以从哪个地方跳转过来（这里假设为i），然后查看其跳跃的距离\(step = stones[j] - stones[i]\) , 则下一次的跳的距离为\(step + 1, step, step - 1\) ，然后查看下一个点_id存不存在（用Hash），存在将dp[_id][j] 设置为可达 ,若\(id==n-1\)，说明到达了对岸。这样复杂度为O(n^2)

直接DP，对于i，把i能到达的放进对应的列表中(如i到达j就把i放入j的可达列表中)，如此循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def canCross(self, stones):
        """
        :type stones: List[int]
        :rtype: bool
        """
        if len(stones) == 2:  return stones[1] == 1
        n = len(stones)
        val2id = {stone: i for i, stone in enumerate(stones)}
        dp = collections.defaultdict(set)
        dp[1].add(0)
        for j in range(1, n):
            for i in dp[j]:
                step = stones[j] - stones[i]
                for k in [step + 1, step, step - 1]:
                    _next = stones[j] + k
                    _next = val2id.get(_next, j)
                    if _next != j:
                        if _next == n - 1:
                            return True
                        dp[_next].add(j)

        return False

 

本次是 leetcode 如下的题解

  • 400 Nth Digit
  • 401 Binary Watch
  • 402 Remove K Digits
  • 403 Frog Jump

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

请我喝杯咖啡吧~