返回信息流简单来说就是给一个字符串，比如"02002"，任取连续的子串，使其里面的chars可以在resort后成为回文(resort我们不用管)，然后给出可能的取法的个数。注: 其中单独的字符组成的子串，比如'0'在"02002"中可以算三次，所以最后"02002"有11种取法 ("0", "2", "0", "0", "2", "00", "020", "200", "002", "2002", "02002")。并且里面的char只有可能是'0'-'9'这10个字符。
我暴力解了 O(n^2), 不过题目里要求是O(n), 最后submit的结果是function correctly but with scalability problem. 所以应该是时间没达标。想请大神看看，对O(n)的解法有没有什么思路。
Winter is coming and Victor is going to buy some new lights. In the store, lights are available in 10 colors, numbered from 0 to 9. They are connected together in a huge chain. Victor can choose any single segment of the chain and buy it.
This task would be easy if it weren't for Victor's ambition. He wants to outdo his neighbors with some truly beautiful lights, so the chain has to look the same from both its left and right sides (so that both neighbors see the same effect).
Victor is a mechanic, so after buying a segment of the chain, he can rearrange its lights in any order he wants. However, now he has to buy a chain segment that will satisfy above condition when its lights are reordered. Can you compute how many possible segments he can choose from?
Write a function:
class Solution { public int solution(String S); }
that, given a description of the chain of lights, returns the number of segments that Victor can buy modulo 1,000,000,007. The chain is represented by a string of digits (characters from '0' to '9') of length N. The digits represent the colors of the lights. Victor can only buy a segment of the chain in which he can reorder the lights such that the chain will look identical from both the left and right sides (i.e. when reversed).
For example, given:
S = "02002"
the function should return 11. Victor can buy the following segments of the chain:
"0", "2", "0", "0", "2", "00", "020", "200", "002", "2002", "02002"
Note that a segment comprising a single "0" is counted three times: first it describes the subchain consisting of only the first light, then the subchain consisting of the third light and finally the subchain consisting of the fourth light. Also note that Victor can buy the whole chain ("02002"), as, after swapping the first two lights, it would become "20002", which is the same when seen from both from left and right.
Assume that:
string S consists only of digits (0-9);
the length of S is within the range [1..200,000].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1) (not counting the storage required for input arguments).
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #91895同步于 2016/12/30
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】winterlight - codility上的一道题
AlexO
2016/12/30镜像同步2 回复
订阅后，新回复会通过你的通知中心匿名送达。
2 条回复
想到一个方法不知能过不。前缀和的思路，s[i]代表从第一个字符到第i个字符为止，0~9这九个数字出现的奇偶状态，这样s[i]可以用一个二进制数来表示（范围0~1024）。其实就是要找s[i]和s[j]两两抑或结果是不是为0或者只差一个bit。然后做10轮抑或操作，每轮操作中，对所有的s[i]抑或某一个单个的比特位，意思是不考虑这个比特位的影响，看有多少对结果是相同的，所有结果相加得到ans。设这s[i] ^ 2个对中，没有经过任何抑或相同的对数有k个，因为这k对数字在10轮抑或中每轮都被计算，而只有一个位不同的数对只有在消除他们那个bit的轮中计算，最后的结果就是ans - 10 * k + k。相同数对的计算可以采用开一个1024的数组，然后得到一个值就放到一个格子里，那么得到的相同对数值就是每个格子里的数字取两个的组合数之和
同楼上前缀和的思路。“0~9这九个数字出现的奇偶状态，这样s[i]可以用一个二进制数来表示（范围0~1024）。其实就是要找s[i]和s[j]两两抑或结果是不是为0或者只差一个bit”。
到这里可以直接存储之前出现过的状态，然后对当前位置上的值，枚举0-9哪一位不去考虑，做个哈希，查询一下之前出现过的数量就行了。