zyb的面试 - HDU - 6468

发表于 | 更新于 | 分类于

今天zyb参加一场面试,面试官听说zyb是ACMer之后立马抛出了一道算法题给zyb:
有一个序列,是1到n的一种排列,排列的顺序是字典序小的在前,那么第k个数字是什么?
例如n=15,k=7, 排列顺序为1, 10, 11, 12, 13, 14, 15, 2, 3, 4, 5, 6, 7, 8, 9;那么第7个数字就是15.
那么,如果你处在zyb的场景下,你能解决这个问题吗?

Input

T组样例(T<=100)
两个整数n和k(1<=n<=1e6,1<=k<=n),n和k代表的含义如上文

Output

输出1-n之中字典序第k小的数字

Sample Input

1
15 7

Sample Output

15

解题思想

对于这题来说，是一个数位问题，第一想法是数位dp或者全转字符串再按字典序排序(~然而都想复杂了~)
注意到一个树下面最多会产生10个子树，又是字典序搜，联想到dfs，如果是bfs那就是正常的数字序.
子树实现

  • 利用for循环10种情况
  • 定义一个新的变量, 不会影响来扩展的10种情况的原情况

细节处理
如果找到答案,标记flag = 1, 在每次dfs开头判断,如果找到,后面的操作不必要进行,
相当于结束递归剩下的函数全部出栈

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
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int n, k, ans, flag, step;
void dfs(int x)
{	
	if(flag)	return ;		//找到答案, 剩余函数全出栈
	if(step == k)		//步数,相等,找到答案
	{
		flag = 1;
		ans = x;
		return ;
	}	
	step ++;		
	for(int i = 0; i <= 9; i ++ )	//10个分支情况子树, 利用for循环实现
	{
		int u = x * 10 + i;				//注意利用u来实现不影响10种情况的来源
		if(u > n)	return ;		//即时判断
		dfs(u);				//搜子情况
	}
}
int main()
{
	int t;
	cin >> t;
	while(t -- )
	{
		flag = 0, step = 1;
		cin >> n >> k; 
		for(int i = 1; i <= 9; i ++ )		//从1 ~ 9开始搜, 区别于上面的 * 10 + i, 但也满足找到答案直接出栈.
			dfs(i);
		cout << ans << endl;
	}
	return 0;	
}

0%