g**********y
发帖数: 14569 | 1 Rolling hash code ->
public class FirstPalindrome {
private final static int MOD = 1000000007;
public int first(int[] a) {
int pow3 = 1;
int hash = a[0];
int reverse = a[0];
for (int i=1; i
pow3 = (pow3 * 3) % MOD;
hash = (hash + a[i] * pow3) % MOD;
reverse = (3*reverse + a[i]) % MOD;
if (hash == reverse && test(a, i)) return i;
}
return -1;
... 阅读全帖 |
|
h*****7
发帖数: 60 | 2 沾人品 乱写一个3的幂睡觉。。
bool pow3(int a)
{
a = abs(a);
if (a==0) return false;
if (a==1) return true;
while (a == sqrt(a)*sqrt(a))
{
a = sqrt(a);
}
return (a%3 == 0) ? pow3(a/3) : false;
}
或者范围小就建表binary search |
|
s********k
发帖数: 6180 | 3 没有时间复杂度限制，很简单
bool pow3(int x){
while(x%3==0) x /=3;
return x==1;
} |
|
