面接問題アルゴリズム分析(2)

2318 ワード

1つの数字が文の数字の分析に戻るかどうかを判断します:テーマはすでに余分な空間を使うことができないことを要求するため、数字を文字列sに変換することができなくて、それからsに対して逆を取ってs'を得て、2つの文字列が等しいかどうかを判断します.解決策は、ループで直接数値を逆にし、最後に得られる新しい数値を元の数値と比較することです.
public class Solution {
    public boolean isPalindrome(int x) {
        int a = x, r = 0;

        if (x < 0) return false;

        while (a > 0) {
            r = r*10 + a%10;
            a = a / 10;
        }
        
        return r == x;
    }
}

提出しましたが、合格しました.しかし、いつも問題を感じているようですが、どんな問題ですか.上記のスキームでは、反転後のデジタルオーバーフローの問題は考慮されず、r*10が2^31−1より大きい場合、その高位を遮断すると元のxに近い値が得られる可能性が高く、a%10を加えると元のxにちょうど等しい.(もちろんこれはただの懸念で、暴捜しても条件に合った数字が見つかるとは限らないと推定されています).計算中にオーバーフローが許されないという制約が追加されたら?
任意のnビットの数字に対して、n=5、数字95349を例にとることを知っています.
95349 % 10 => 9
95349 / 10000 => 95349 / 10^4 => 9

モジュール10により最低位を取ることができ,10^(n−1)を除いて最高位を取ることができ,その最高位と最低位を比較すると,現在の返信要求に合致しているか否かが分かる.
最高位と最低位を比較した後、どうやってこの2人を除去しますか?これで、首を絞めて終わりました.
完全なコード:
95349 % 1000 => 95349 % 10^4 = 5349
95349 / 10 = 9534
public class Solution {
    public boolean isPalindrome(int x) {
        int a = x, h = 1;

        if (a < 0) return false;

        while (a / h >= 10) {
            h = h * 10;
        }

        while (a > 0) {
            if (a / h != a % 10) return false;
            a = a % h;
            a = a / 10;
            h = h / 100;
        }

        return true;
    }
}

より一般的には、文字列がエコー文字列の詳細コードであるかどうかを判断します.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void isPali_Number(char *head);

int main(int argc, char *argv[])
{
    char str[] = "abcddcba";
    isPali_Number(str);
    return 0;
}

void isPali_Number(char *head)
{
    char *tail;
    tail = head;
    while(*tail !=0)
    {
        tail++;   //                  
    }
    tail--;
    while(head <= tail)
    {
        if(*head == *tail)
        {//head ->     <-tail
            head++;
            tail--;
            if((head + 1 == tail) || (head == tail)) //        
            {
                printf("   
"); break; } }else if(*head != *tail) { printf("
"); break; } } }