【算法】5.判断回文数

目录

一、方法一（双指针）

1.解法思路

2.代码

二、方法二（栈存在bug）

1.解法思路

2.特别注意

3.代码

一、方法一（双指针）

1.解法思路

        1.在头部设置一个头指针i=0 

        2.尾部设置一个尾指针j=text.length()-1

        3.while循环中，当两个指针对应的字符相等则i++,j--。不相等则返回 false

        4.当尾指针<=头指针时则对称遍历完了，则返回true

2.代码

private static boolean fangfa01() {
        String s="上海自来水来自海上";
        int i=0;
        int j=s.length()-1;
        while (true){
            if(s.charAt(i)==s.charAt(j)){
                i++;
                j--;
            }else{
                return false;
            }
            if (j<=i){
                return true;
            }
        }
    }

二、方法二（栈存在bug） 1.解法思路

        1. 对字符串进行遍历从0开始，与栈顶元素进行比较

        2.如果栈顶为空或栈顶元素与当前遍历到的字符不相等则将该字符进栈，接着遍历下一位字符

        3.如果遍历到的字符与栈顶元素相等则将栈顶元素弹栈，接着遍历下一位字符

        4.当遍历到的字符下标等于s.length/2且s.length()%2==1则这次遍历终止,接着遍历下一个字符

                这一步是为了排除当字符长度为奇数个时最中间的那个不用与栈顶元素比较

        5.最后判断栈是否为空，为空则是回文，否则相反

2.特别注意

        这个实现方法不好，因为当字符串为112233这个类型的最后也是true,则仅供参考即可！！！

3.代码

private static void solution01() {
        String text = "上海自来水来自海上";  //112233
        ArrayStack stack = new ArrayStack<>();
        for (int i = 0; i < text.length(); i++) {
            if (text.length() % 2 == 1 && i == text.length() / 2) {
                continue;
            }
            char c = text.charAt(i);
            if (stack.isEmpty()) {
               stack.push(c);
            } else {
                if (c != stack.peek()) {
                    stack.push(c);
                } else {
                    stack.pop();
                }
            }
        }
        System.out.println(stack.isEmpty());
    }