C#版 - ZJNUoj1259 - 幸运数字——中高级 - 题解
C#版 - ZJNUoj1259 - 幸运数字——中高级 - 题解
C#版 - ZJNUoj1259 - 幸运数字——中高级 - 题解
ZJNUoj1259 - Lucky numbers
Time Limit: 1000 ms Memory Limit: 65536 KB Total Submissions: 116 Accepted: 76
在线提交: http://acm.zjnu.edu.cn/CLanguage/submitpage?problem_id=1259
Problem Description
数字4和7是幸运数字，而其他的都不是幸运数字。一个整数是幸运数字，当且仅当它的十进制表示只包含幸运数字。 现在让你给出第 K 个幸运数字(幸运数序列默认是从小到大排的)。
Input
第一行一个整数K (1 ≤K≤109≤K≤109\leq K \leq 10^9).
Output
打印出第 K 个幸运数字。
Sample Input
1 5 100 10000000
Sample Output
4 74 744747 44774447447477474444447
思路: 一开始用暴力法试了一下，代码如下： https://github.com/yanglr/AlgoSolutions/blob/master/tempSolutions/ZJNUoj1259_LuckyNum-brute-sol.cs 速度感受一下，40s，远超过1000ms，直接TLE。而且此时用的for循环的上界是100000000，题中要求的上界是100000000 0，更不满足要求了~
4
47
RunTime: 00:00:40.03好吧，此路不通，那只能用别的思路~
找规律: f(1) = “4” f(2) = “7” f(3) = “44” = f(1)+”4” = f((3-1)/2) + “4” f(4) = “47” = f(1)+”7” = f((4-1)/2) + “7” f(5) = “74” = f(2)+”4” = f((5-1)/2) + “4” f(6) = “77” = f(2)+”7” = f((6-1)/2) + “7” ⋮⋮\vdots
递推关系如下：
f(n)={f(n奇−12)+‘‘4"f(n偶2)+‘‘7"(n=2⋅k−1,n∈Z)(n=2⋅k,n∈Z)f(n)={f(n奇−12)+‘‘4"(n=2⋅k−1,n∈Z)f(n偶2)+‘‘7"(n=2⋅k,n∈Z)f(n)=\left\{ \begin{array}{rcl} f(\frac{n_奇 -1}{2}) + ``4" & (n = 2 \cdot k -1, n \in Z) \\ f(\frac{n_偶}{2}) + ``7" & (n = 2 \cdot k, n \in Z) \end{array} \right.
其中+表示字符串的连接，k=⌊n2⌋k=⌊n2⌋ k = \lfloor \frac{n}{2} \rfloor，不论n是奇是偶，对其折半后下取整即可得到 k. C#实现的代码:
using System;
namespace ZJNUoj1259_LuckyNum
{
class Program
{
public class Solution
{
public string GetKthLuckyNum(int n)
{
int k = (n - 1) / 2;
if (n <= 0)
return String.Empty;
if (n == 1)
return "4";
if (n == 2)
return "7";
return GetKthLuckyNum(k) + (n % 2 == 0 ? "7" : "4"); // 如果使用迭代或动态规划，变量名可选用 pre, res/current, next.
}
}
static void Main(string[] args)
{
string str;
while ((str = Console.ReadLine()) != null)
{
int k = int.Parse(str);
var sol = new Solution();
Console.WriteLine(sol.GetKthLuckyNum(k));
}
}
}
}提交到OJ的已AC代码(C++):
#include <iostream>
#include<string>
using namespace std;
string GetKthLuckyNum(int n)
{
int k = (n - 1) / 2;
if (n <= 0)
return "";
if (n == 1)
return "4";
if (n == 2)
return "7";
return GetKthLuckyNum(k) + (n % 2 == 0 ? "7" : "4");
}
int main() {
int n;
while (cin >> n)
{
cout << GetKthLuckyNum(n) << endl;
}
return 0;
}Rank:
Result | Score | Time | Memory |
|---|---|---|---|
Accepted | 100 | 15MS | 0K |
其他方法： 1.完全二叉树 2.将4、7分别替换为0，1，然后在新数首位插入1，处理完成后换回4、7
ps: 京东2016、2017的校招中均考到了这题，有公司的面试中也考到此题~