[编程题] 回文数问题

回文数问题

题目描述

输入输出例如：

样例

方法1：对子串的首位比较，向中间进行

思想

我们每次拿出一个子串，然后一个头指针和一个尾指针分别指向前后，然后依次比较最后和第一个值是否是相等的，如果是相等，再比较第2个数和倒数第2个数是否相等，相等就依次向前推进，直到head>tail的时候停止。如果在这个子串的比较期间，一直进行到了结尾，即head>tail退出，那么本次子串是回文数。如果中途有不等，直接返回这个子串不是回文。

Java代码

import java.util.*;
public class Main{
   public static void main(String[] args){

        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        int count = huiwen(str);
        System.out.println(count);
    }

    public static int huiwen(String str) {
        if (str == null) {
            return 0;
        }
        if (str.length() == 1) {
            return 1;
        }

        //记录结果
        int count = 0;
        //把字符串变为字符数组
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            //这里这样写是因为subString函数在subxxx(0,0)是取不到子串的
            for (int j = i + 1; j <= chars.length; j++) {
                String curStr = str.substring(i, j);
                boolean judge = judge(curStr);
                if (judge){
                    count++;
                }
            }

        }
        return count;
    }

    //判断
    public static boolean judge(String curStr){
        int head=0;
        int tail=curStr.length()-1;
        boolean flag = true;
        while (head<tail){
            if (curStr.charAt(head)==curStr.charAt(tail)){
                head++;
                tail--;
            }else {
                return  false;
            }
        }
        return true;
    }
}

测试输出：

方法2：对子串的首位比较借用栈

思路：

对子串入栈，出栈使用stringBuilder拼接成子串，直接比较出栈后的字符串和入栈前的字符串是否相等，如果等这个子串是回文，不等就不是回文。

牛客-Java代码

package newcode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * @author jiyongjia
 * @create 2020/6/27 - 15:22
 * @descp: 回文数问题
 * https://www.nowcoder.com/questionTerminal/9475dc0eca9248e78d3385e9986621e0?answerType=1&f=discussion
 *
 * 存在问题：不满足时间复杂度
 */
public class P2_huiwenNum{
    public static void main(String[] args){
        long start = System.currentTimeMillis();

        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        int count = huiwen(str);
        System.out.println(count);
        long end = System.currentTimeMillis();
        System.out.println((end-start)/1000);
    }

    public static int huiwen(String str){
        if(str==null) {return 0;}
        if(str.length()==1){ return 1;}
        //借助栈
        Deque<Character> statck = new LinkedList<>();
        //记录结果
        int count=0;
        //把字符串变为字符数组
        char[] chars = str.toCharArray();
        for(int i=0;i<chars.length;i++){
            for(int j=i+1;j<=chars.length;j++){
                String curStr = str.substring(i,j);
                char[] cur = curStr.toCharArray();

                for(char s:cur){
                    statck.push(s);
                }

                StringBuilder builder = new StringBuilder();
                while(!statck.isEmpty()){
                    builder.append(statck.pop());
                }

                String reverseStr = builder.toString();
                if(reverseStr.equals(curStr)){
                    count++;
                }
            }
        }
        return count;
    }
}

测试：

缺点：

时间复杂度高