DFS题目求思路

Job Hunting Interview
1

People usually think that a number that only contains 3 or 5 is a lucky number.

Now given an integer n, and you need to find the smallest lucky number that is not less than N and the number of occurrences of 3 in this lucky number is the same as the number of occurrences of 5.

Example

Example 1:

Input: n = “3500”

Output: “3535”

Explanation:

The smallest lucky number is 3533, but the number of occurrences of 3 is not equal to the number of occurrences of 5.

The second smallest lucky number is 3535, and the number of occurrences of 3 is equal to the number of occurrences of 5.

Example 2:

Input: n = “1”

Output: “35”

Notice

1 ≤ n ≤ 10^100000

我用从最小的组合33…555… 不停找下一个稍大一点的数的方式搜索，超时了。因为根据已有的digit找下一个更大的数需要进行部分的排序，导致比较慢。不知道DFS应该如何搜索啊？求思路。

2

什么公司的？

3

我改了类别，应该是刷题，非面经。

4

哪里来的题？

5

lintcode cat

6

为啥说是dfs？

7

可能也可以不是吧，不过题目的tag是dfs，而且这个题是一个系列里面的一道，其他题目我都是用dfs backtracking来做的，只是这个题我实在是没有思路。

8

本质就是从右往左决定每个digit是否要变成3或5吧

9

我的观察是如果n的长度是奇数，那么output比n多一位，并且全部的3排在5前面。如果n的长度是偶数，先比较5…53…3是不是比n大，如果不是，直接多加一个35，并且结果是3…35…5的形式。反之，结果肯定是在3…35…5 和 5…53…3 之间，并且需要从小到大搜索，才能早到最小的符合要求的数。不知道怎么用dfs在这个范围内搜索啊。

10

这题应该greedy做吧

11
  • 从第1位开始看：

    • (1) 如果该位大于5，那么同样长度为n又比这个数字大的已经没有了，
      所以直接return，然后返回n+2的最小的lucky number.

    • (2) 如果该位是4， 那么我们知道答案首位一定得是5，才使得答案大于当前数字，所以我们直接返回以5开头，长度为n的最小lucky num.

    • (3) 如果该位小于3，那么我们知道答案首位一定得是3，才使得答案大于当前数字且是最小的lucky num，所以我们直接返回以3开头，长度为n的最小lucky num.

    • 比较复杂的是该位是3或者是5的情况，也就是搜索 的部分：

    • (4) 若该位是3，我们需要搜索，attempt 3。即该位填3，看看是否有答案，若没有答案，再看该位填5的答案。

    • (5) 若该位是5，attempt 5。该位填5，搜索。

    • (6) 对于搜索终止条件, 比如(5)中若搜索没有答案，说明这个数字已经大于等于5开头n长度的lucky num了，返回到主程序，然后取3开头长度为n+2的最小lucky num即可。

    • (7) 每一次搜索之后都要判断：若没有找到答案，直接return ""不需要继续往下搜索了。若找到了答案，就整理一下stringBuilder然后返回答案。

12

这个题dfs搜索的时候要进行很多剪枝，个人觉得不太适合做面试题。

13

楼主干嘛刷不考的题？
都没公司考这个题。。。

14

说的对，我后来也不纠结了。