leetcode contest 5 solution

本次题解包括:

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

leetcode 400. Nth Digit

Find the nth 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:

Example 2:

传送门:leetcode Nth Digit

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

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

 

 

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:

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。感觉可以位运算,过阵子再看看。

 

 

 

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:

Example 2:

Example 3:

传送门:leetcode Remove K Digits

题意:给定一个num(字符串)和k,让你从num中删除k个字符使得整个字符串值最大。

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

 

 

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:

Example 2:

传送门: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

另一种写法

设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的可达列表中),如此循环。

 

 

本次是 leetcode 如下的题解

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

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

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode contest 5 solution
本文地址:https://www.hrwhisper.me/leetcode-contest-5-solution/

打赏一杯咖啡钱呗

Leetcode , , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *