dfs 题目求思路

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



dfs tag.
但是我没有思路，我通过找下一个大数的方法暴力搜索，结果超时了。求大神提供思路。给大家加米哈。

找到解法了。

是这样吗？判断出target的字符串长，然后来构造target
1. 如果长度大于len(s), 果断选择最小的"333...555..."
2. 否则长度必然等于len(s)。因为位置越靠左对结果的影响越大，所以我们从左向右来构造target
2.1  对于5320...，我们得到53X... X对应的位是2。所以我们选择3, 如果还有剩余的。余下的选择最小的东东，即33..5...
2.2  对于5340...，我们得到53X... X对应的位是4。所以我们选择5, 如果还有剩余的。余下的选择最小的东东
2.3  对于5360...，我们得到53X... X对应的位是6。6>5，所以要向左去找第一个3并与第一个5对调。余下的选择最小的东东

dennyzhang007 发表于 2019-9-23 01:40
是这样吗？判断出target的字符串长，然后来构造target
1. 如果长度大于len(s), 果断选择最小的"333...555. ...

应该就是greedy，没毛病。你说的target这段应该是判断奇偶长度吧