leetcode 09回文
11060 ワード
暴力解法(32 msまたは16 msを使用してはいけません)効率の下敷きになります.
leetcode 07の基礎の上で実現します.1.負の整数は必ず回文に属さないです.正の数は正数を反転させた後、元の数と比較してもいいです.等しいのは回文です.
数を剰余数として取る方式は、毎回得られる数を配列に保存し、再び配列の最初の両端を比較し、同じであれば条件に合致する.(実際に見ても時間の複雑さは上と同じO(N));
leetcode 07の基礎の上で実現します.1.負の整数は必ず回文に属さないです.正の数は正数を反転させた後、元の数と比較してもいいです.等しいのは回文です.
bool isPalindrome(int x){
long tmp = x;
if(tmp<0){
return false;
}
long res = 0;
while(tmp != 0){
res = res*10 + (tmp%10);
tmp = tmp/10;
}
printf("%d",res);
printf("tttt");
printf("%d",tmp);
if(res == x){
return true;
}
return false;
}
12 msの答えはlongとintの切り替えが少なくなりました.bool isPalindrome(int x){
int reverse=0;
int y=x;
if(x<0||x>2147447412)return false;
else {
while(x!=0){
reverse=reverse*10+x%10;
x/=10;
}
if(y==reverse)return true;
else return false;
}
}
3.以下は0 msの答えです.数を剰余数として取る方式は、毎回得られる数を配列に保存し、再び配列の最初の両端を比較し、同じであれば条件に合致する.(実際に見ても時間の複雑さは上と同じO(N));
int g_data[20] = {0};
bool cmpData(int cnt)
{
int i;
if(cnt == 1){
return true;
}
for(i = 0; i < (cnt/2); i++){
if(g_data[i] != g_data[cnt -1 -i]){
return false;
}
}
return true;
}
bool isPalindrome(int x){
int i;
int num = x;
int count = 0;
int num1 = 0;
if(x<0){
return false;
}else if(x==0){
return true;
}
for(i = 0; i < 20 ; i++){
g_data[i] = num % 10;
num = num / 10;
count++;
if(num == 0){
break;
}
}
return cmpData(count);
}