@cleardusk
2016-05-23T13:56:57.000000Z
字数 3210
阅读 1301
topcoder
做这个是为了熟悉 topcoder 的 SRM 规则以及练练手,目前貌似没有写程序的感觉了。
这道题很简单:
A positive integer is called a prime if it has exactly two distinct positive integer divisors: 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, ...
A positive integer is called a palindrome if its base-10 representation reads the same forwards and backwards. Some palindromes: 2, 77, 101, 33333, 12344321.
A positive integer is called a palindromic prime if it is both a palindrome and a prime.
You are given two ints: L and R. Compute and return the number of palindromic primes between L and R, inclusive.
就是判断 [L, R] 中有多少数,既是素数又是回文数。我的解法很传统,判断是否为回文数,我没有用字符串来判断,而是直接计算出反转的数值再判断是否相等。值得注意的细节是,第四行的代码是可以注释掉的,该函数依然能正确的判断 n 是否为素数。
class PalindromePrime {
public:
bool is_prime(int n){
//if(n == 2 || n == 3) return true;
for(int i = 2; i <= int(sqrt(n)); ++i)
if(n % i == 0)
return false;
return true;
}
bool is_palindromic(int n){
int on = n; // original n
int rn = 0;
while(n){
rn = 10*rn + n % 10;
n /= 10;
}
return rn == on;
}
int count(int L, int R) {
int res = 0;
for (int i = L; i <= R; ++i)
if(is_prime(i) && is_palindromic(i))
++res;
return res;
}
};
接下来,我用反转字符串的思路实现一下,用到 c++ 中的 std::reverse。受限,int -> string 用 std::to_string,这个能将 int, double 等类型转化为 string。OK,代码如下:
bool is_palindromic2(int n){
string s = to_string(n);
string sr = s;
reverse(sr.begin(), sr.end()); // reverse string
if (s.compare(sr) == 0)
return true;
return false;
}
reverse 只能 reverse 参数中的 string 对象。to_string 必须使用 -std=c++0x flag 编译,经测试,topcoder 默认开启了 c++0x。比较字符串我使用了 compare 函数,其实使用 == 运算符也行,不过 compare 支持可选参数多多了。
拓展一下,reverse 的可能实现如下,相当精炼。更多的参考 reverse_copy,并行版本的 reverse 等。
template<class BidirIt>
void reverse(BidirIt first, BidirIt last)
{
while ((first != last) && (first != --last)) {
std::iter_swap(first++, last);
}
}
他人的代码是只读不可复制的,quora 的一个讨论,这样能避免在 challenge 阶段暴力测试别人的 bug。
比赛排位第一的代码,一行搞定。注意生成式的结果是 bool 型的,注意一下 str(x) == str(x)[::-1] 这句代码。
class PalindromPrime():
def count(self, L, R):
return sum(str(x) == str(x)[::-1] and not any (x % i == 0 for i in range(2, x)) for x in range(L, R+1))
关于是否回文数,有人写的代码是 c 风格的,就是逐个字符的判断,str[i] == str[l-i] 类似这样的。
这道题花了我一晚上,还是在跑步的时候彻底想清楚的。
We have four strings: a, b, c, and d.
A superstring of our four strings is any string S such that each of the four strings occurs somewhere in S as a contiguous substring.
Note that some superstrings of our four strings always exist.
For example, the string S = a+b+c+d is obviously a superstring of a, b, c, and d.Find and return the length of the shortest superstring of a, b, c, and d.
暴力解法/朴素解法就是排列 (a, b, c, d),对每一个排列,进行字符串的融合,过程如下,其中 merge 是针对两个字符串,大致过程是对第一个字符串的尾部和第二个字符串的头部进行判断,若有重叠的就融合掉。
s <- a
s <- merge(s, b)
s <- merge(s, c)
s <- merge(s, d)
其实这道题目的难点是,如何证明该算法是正确的?我也大底是凭感觉的,排列出所有排列,然后对每一种排列融合,覆盖所有情况。这是一个好方法麽?
我的实现相当的搓,排列的生成简直。。
class FourStrings {
public:
string merge_two_str(string s1, string s2){
if(s1.find(s2) != -1)
return s1;
size_t l = min(s1.length(), s2.length());
for(size_t i = l; i > 0; --i){
string s1_tail = s1.substr(s1.length() - i);
string s2_head = s2.substr(0, i);
// cout << s1_tail << endl;
// cout << s2_head << endl;
if(s1_tail == s2_head)
return s1 + s2.substr(i);
}
return s1 + s2;
}
int shortestLength(string a, string b, string c, string d) {
int res = 0;
string s[4];
s[0] = a, s[1] = b, s[2] = c, s[3] = d;
for(int i = 0; i < 4; ++i)
res += int(s[i].length());
for(int i = 0; i < 4; ++i)
for(int j = 0; j < 4; ++j){
if (j == i) continue;
for(int k = 0; k < 4; ++k){
if (k == i || k == j) continue;
for(int l = 0; l < 4; ++l){
if(l == i || l == j || l == k) continue;
string ms = s[0];
for(int i = 1; i < 4; ++i)
ms = merge_two_str(ms, s[i]);
res = min(res, int(ms.length()));
}
}
}
return res;
}
};
需要学习的地方有排列的生成,看离散数学的书。
关于图的,赶紧去看离散数学补补相关知识。
参考:http://kmjp.hatenablog.jp/entry/2015/12/27/0930
review 了别人的代码,但是不懂。