1

これが私のisPalindromeメソッドです

public static boolean isPalindrome(String s){
    for(int i = 0; i < s.length()/2; i++){
        int j = s.length() - 1 - i;
        if(s.charAt(i) != s.charAt(j))
            return false;
    }
    return true;
}

先生は複雑さを減らすことができると言っていますが、その方法がわかりません。私はすでに文字列の半分しか通過していません。このソリューションの複雑さを軽減する方法はありますか？

4

5 に答える 5

3

あなたはこのようなことを試すことができます：

public static boolean isPalindrome (String str) {
    int left = 0;
    int right = str.length() - 1;

    while (left < right) {
        if (str.charAt(left) != str.charAt(right))
            return false;
        left++;
        right--;
    }
    return true;
}

これには、ループを通過するたびに右側のインデックスを計算しないという利点があります。特に、毎回文字列の長さにアクセスする必要があるためです（これは一定です）。

余談ですが、私は、よりも意味のある変数名を好む傾向がありますs。i私jの基本的なルールは、カウンターに頼る必要がある場合はj、カウンターにもっと表現力のある名前を付ける方がよいということです（iこれが唯一のカウンターであれば問題ありません）。 ）。

于 2013-01-29T00:26:50.270 に答える
1

私が考えることができる唯一のことは、次の長さを格納することですs：

final int n = s.length();
for(int i=0; i<n/2; i++) {
    int j = n-1-i;
    if(s.charAt(i) != s.charAt(j))
        return false;
}
return true;

それを除けば、どうすればもっと簡単に、もっと効率的にできるのかわかりません。

于 2013-01-29T00:25:05.210 に答える
1

彼があなたのコードが美的にどのように見えるかの複雑さを意味するなら、ここに再帰的な解決策があります：

public static boolean isPalindrome(String s) {
    if (s.charAt(0) != s.charAt(s.length() - 1)
       return false;
    return isPalindrome(s.substring(1, s.length() - 1);
}

彼がアルゴリズムの複雑さを意味するのなら、あなたがそれをもっと速くできるかどうかはわかりません。おそらく、サブストリングを（スレッドを使用して）異なるコアに移動し、結果を組み合わせることができます。

編集：paxdiabloはより良いコードを提案し、私はそれをで再保留*しました。

于 2013-01-29T00:28:13.593 に答える
0

文字列を逆にしても、それがそれ自体と等しい場合、それは回文であることを意味します。これが私がそれを実装する方法です：

package com.sandbox;

import org.apache.commons.lang.StringUtils;
import org.junit.Test;

import static junit.framework.Assert.assertFalse;
import static junit.framework.Assert.assertTrue;

public class PalindromeTest {

    @Test
    public void testTheseArePalindromes() {
        assertTrue(isPalindrome("abccba"));
        assertTrue(isPalindrome("121"));
        assertTrue(isPalindrome("Malayalam"));
        assertTrue(isPalindrome("peeweep"));
        assertTrue(isPalindrome("123 321"));
    }

    @Test
    public void testTheseAreNOTPalindromes() {
        assertFalse(isPalindrome("abc"));
        assertFalse(isPalindrome("123"));
        assertFalse(isPalindrome("123 123"));
    }

    private boolean isPalindrome(String input) {
        String lowerIn = input.toLowerCase();
        String reversed = StringUtils.reverse(lowerIn);
        return lowerIn.equals(reversed);
    }

}

このページのフレーズも回文です。それらに取り組む必要がありますか？もしそうなら、それは非常に単純な変更です：

package com.sandbox;

import org.apache.commons.lang.StringUtils;
import org.junit.Test;

import static junit.framework.Assert.assertFalse;
import static junit.framework.Assert.assertTrue;

public class PalindromeTest {

    @Test
    public void testTheseArePalindromes() {
        assertTrue(isPalindrome("abccba"));
        assertTrue(isPalindrome("121"));
        assertTrue(isPalindrome("Malayalam"));
        assertTrue(isPalindrome("peeweep"));
        assertTrue(isPalindrome("123 321"));
        assertTrue(isPalindrome("A dog, a plan, a canal: pagoda."));
        assertTrue(isPalindrome("A man, a plan, a canal: Panama."));
        assertTrue(isPalindrome("A tin mug for a jar of gum, Nita."));
    }

    @Test
    public void testTheseAreNOTPalindromes() {
        assertFalse(isPalindrome("abc"));
        assertFalse(isPalindrome("123"));
        assertFalse(isPalindrome("123 123"));
    }

    private boolean isPalindrome(String input) {
        String removedPunctuation = input.toLowerCase().replaceAll("[.,;: \t]", "");
        String reversed = StringUtils.reverse(removedPunctuation);
        return removedPunctuation.equals(reversed);
    }

}
于 2013-01-29T00:57:54.067 に答える
0

これがC＃の私の解決策です、私はそれをスピードテストしていません。

using System;

public class Palindrome
{
    public static bool IsPalindrome(string word)
    {
        var arr = word.ToCharArray();
        Array.Reverse(arr);
        return word.ToLower() == new string(arr).ToLower() ? true : false;
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(Palindrome.IsPalindrome("Deleveled"));
    }
}
于 2019-04-21T12:54:31.853 に答える