LeetCodeブラシ記録(5,6,7)-Java言語

5.最長回文子列
文字列sを指定すると、sの中で最も長い回文サブ列が見つかります.sの最大長さは1000と仮定できます.
例1:
入力:“babad”出力:“bab”注意:“aba”も有効な答えです.例2:
入力:「cbbd」出力:「bb」
構想
この問題の最も直接的な解法は中心拡散法であり,各文字あるいは各2文字の間から左右の両側が等しいか否かを判断するが,時間的複雑度が高すぎて,最も適しているのはManacherアルゴリズムであり,このアルゴリズムは中心拡散アルゴリズムに基づいて,繰り返し判断操作を簡略化することによって時間的複雑度をO(N)とする.具体的な方法は,以前に判断した文脈の対称性を利用して不要な判断を省略することである.
コード#コード#

class Solution {
    public String longestPalindrome(String s) {
        StringBuilder str = new StringBuilder("!#");
        for(int i=0;i"#");
        }
        str.append("@");
        String t = str.toString();
        int p[] = new int[t.length()];
        int right=0,center=0,resCenter=0,resLength=0;
        for(int i=1;i1;i++){
            p[i] = right>i?Math.min(p[2*center-i],right-i):1;
            while(t.charAt(i+p[i])==t.charAt(i-p[i]))++p[i];
            if(right < i+p[i]){
                right = i+p[i];
                center = i;
            }
            if(resLength
int start = (resCenter-resLength)/2;
        return s.substring(start,start+resLength-1);
    }
}

6.ジグザグ変換
文字列「PAYPALISHIRING」を所定の行数にZ字で並べます.
P A H N A P L S I I I G Y I R以降左から右へ、行ごとに文字を読み取る:“PAHNAPLSIIGYIR”
文字列を指定した行数変換する関数を実装します.
string convert(string s, int numRows); 例1:
入力:s="PAYPALISHIRING",numRows=3出力:「PAHNAPLSIIGYIR」例2:
入力:s=“PAYPALISHIRING”,numRows=4出力:“PINALSIGYAHRPI”解釈:
P I N A L S I G Y A H R P I
構想
まず文字列は横になっているZ字形が並んでいますが、実はN字形と言ったほうが明らかで、例を多く見ると特徴がわかります.N字形は循環配列であり、1サイクル数は2*numRows-2である.では、1サイクルの特徴をつかむだけで問題を解決することができます.最初の行と最後の行の数について言えば、最初の数から直接1サイクルを加えることで、対応する次の数を得ることができます.一方、中間の数行は1行につき2つの数に対応し、上から下への2つの数の下付き文字は2*numRows-2*(行番号+1)の差しかありません.ここで行番号は0からnumRows-1までです.この周期の特徴を利用して各行の文字の抽出を完了し、上から下へすべての行を抽出すると、結果が得られます
コード#コード#
numは1サイクルに含まれる文字数であり、tempは現在のサイクル内の行を取得するために次の文字(最初の行と最後の行の中間の行だけが次の文字)に対応しています.最初のレイヤループは行番号ループであり、2番目のレイヤループは階層ループで各行のすべての文字を取得します.

class Solution {
    public String convert(String s, int numRows) {
        if(numRows<=1)
            return s;
        int num = 2*numRows-2;
        StringBuilder str = new StringBuilder();
        for(int i=0;ifor(int j=i;jstr.append(s.charAt(j));
                int temp = j+num-2*i;
                if(i!=0&&i!=numRows-1&&tempstr.append(s.charAt(temp)); 
            }
        return str.toString();
    }
}

7.整数の反転
32ビットの符号付き整数を指定し、整数の数値を反転します.
例1:
入力:123出力:321例2:
入力:-123出力:-321例3:
入力:120出力:21注意:
我々の環境では32ビットの符号付き整数しか記憶できないと仮定し,その数値範囲は[−231,231−1]である.この仮定によれば,反転後の整数がオーバーフローすると0を返す.
構想
この考え方は,入力値をビット毎に分割して再編成することで反転効果を達成することが簡単である.ただし、注意すべき点は反転オーバーフローであり、例えばintの最大値は2147483647であり、反転後は7463847412であり、明らかにint値の取値範囲を超えているので、0を返す必要がある.ここではlongタイプを直接使用して記憶し、反転後にオーバーフローの有無を判断し、オーバーフローしたら0を返し、逆に反転後の数字を返す.

class Solution {
    public int reverse(int x) {
        long num = Math.abs(x);
        boolean flag = x<0;
        long res=0;
        while(num>0){
            res = res*10+num%10;
            num/=10;
        }
        if(!flag&&res>Integer.MAX_VALUE
           ||flag&&res*-1return 0;
        }
        return flag?(int)(-1*res):(int)res;
    }
}