返回信息流1.大意是一个字符串s，长度为n，循环左移动0～n-1位，得到的字符串中，有多少个和原字符串相等的。例如abcabcabc 答案为3。朴素算法只能过百分之四十，我的做法是找到第一次左移x位字符串相等的，然后用总长度除以x…其实最坏的复杂度还是没变…只多对了一个点。我认为关键在于怎么确定字符串的这个循环节？
2.第二题求1到n字典序的第m个，我没有字符串排序，一个个去生成的…结果和用排序得到得分一样多…尴尬。对了n最大为10^18，想到了大概用二分？但不知道怎么求数x是字典序的第几个…
发自「贵邮」
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #91293同步于 2016/9/28
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
今日头条算法题求解…
ak47b51c4
2016/9/28镜像同步45 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
…真假的啊 为什么我不行…具体咋朴素的 难不成大牛们的朴素对我等来说就是最高难的解法@_@
【 在 chenxiansf 的大作中提到: 】
: 第一题朴素算法一遍过了
:
发自「贵邮」
就是遍历找最小循环节啊
【 在 ak47b51c4 (Hi_fish) 的大作中提到: 】
: …真假的啊 为什么我不行…具体咋朴素的 难不成大牛们的朴素对我等来说就是最高难的解法@_@
第二题
不知道题目，感觉像是leetcode400 难度：easy
public int findNthDigit(int n) {
int l = 1;
long span = 9;
int start = 1;
// find out how many digits does the target number has.
while(n > l * span) {
n -= l * span;
span *= 10;
l++;
start *= 10;
}
// the target number is the ith number from 10 or 100 or 1000 or 10000...
int ithNum = (n - 1) / l + 1;
// the digit is the the kth digit in that target number
int kthDigit = (n - 1) % l;
int theNum = start + ithNum - 1;
String s = Integer.toString(theNum);
return Character.getNumericValue(s.charAt(kthDigit));
}
第一题感觉是用kmp算法。当时试了下50%。改了个版本最后没提交上去也不知道对不对。第二道不是leedcode说那道题。直接构造序列在30%的时候超时了。感觉要不就是直接构造出那个数字，要不就是在构造序列的时候跳过不必要的构造。不过当时是没想出来。