回文数算法

解释

正读和倒读都一样

例

汉字: “我为人人, 人人为我”
英文: “eye”
普通自然数: 232
平方回数: 121(11^2)
回文算式: 3 x 51 = 153(去掉x号和=号)

回文数算法

随意找一个十进制的数，把它倒过来成另一个数，再把这两个数相加，得一个和数，这是第一步;然后把这个和数倒过来，与原来的和数相加，又得到一个新的和数，这是第二步。照此方法，一步步接续往下算，直到出现一个“回文数”为n。例如:28+82=110,110+011=121，两步就得出了一个“回文数”。如果接着算下去，还会得到更多的“回文数”。这个过程称为“196算法”。

利克瑞尔数, 猜测第一个利克瑞尔数是196, 但是尚未被证实
领军人W.V.Landingham到2006年2月已经计算到了699万步，得到了一个2.89亿位以上的和数，之间的结果仍未出现“回文数”

算法一

解释: 逆序后进行恒等于比较

public boolean isPalindrome(String s) {
    return this.reverse(s).equals(s);
}

public String reverse(String s) {
    StringBuilder ans = new StringBuilder();
    for (char i : s.toCharArray()) {
        ans.insert(0, i);
    }
    return ans.toString();
}

public boolean isPalindrome(String s) {
    return StringUtils.reverse(s).equals(s);
}

// StringUtils.reverse(s)的底层为
public static String reverse(String str) {
    return str == null ? null : (new StringBuilder(str)).reverse().toString();
}

算法二

图解

解释

第一位为Left, 最后一位为Right
Left == Right, Left + 1 == Right - 1, …

public boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;
    char[] chars = s.toCharArray();
    while (left < right) {
        if (chars[left] != chars[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

算法三

public boolean isPalindrome(String s) {
    int length = s.length();
    char[] chars = s.toCharArray();
    for (int i = 0; i < length / 2; i++) {
        if (chars[i] != chars[length - 1 - i]) {
            return false;
        }
    }
    return true;
}

算法四

public boolean isPalindrome(String s) {
    char[] chars = s.toCharArray();
    Stack<String> stack = new Stack<>();
    for (char c : chars) {
        stack.push(String.valueOf(c));
    }
    for (char c : chars) {
        String x = stack.pop();
        if(!StringUtils.equals(x, String.valueOf(c))) {
            return false;
        }
    }
    return true;
}