判断是否是回文结构_回文结构怎么判断

作者：Monodyee | 2024-05-04 02:32:43

踩

回文结构怎么判断

判断是否是回文结构

题目如下
在这里插入图片描述

我的思路是分三种情况

先判断最左与最右是否相等，如果相等则继续判断剩下的元素，不相等直接输出answer=false
剩下两种，是把这个链表里的数组进行差分。差分情况分奇、偶数。但检测的思路都是一样的，就是把前半部分的元素放到一个栈stack1里面，再把后半部分的元素放到stack2里面，stack2的元素再弹出放到stack3里，这样它元素的先后顺序就能和stack1一样。然后依次判断stack1和stack3弹出的元素是否相等。如果出现不相等的情况就可以退出判断，如果一直相等，那它就是回文结构

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        int b=0;
        int c=0;
        int d=0;
        Stack<Integer> stack1=new Stack<Integer>();
         Stack<Integer> stack2=new Stack<Integer>();
          Stack<Integer> stack3=new Stack<Integer>();
        ListNode a=head;
        ListNode h=head;
        boolean answer=true;
        while(h!=null)
        {
            b=h.val;
            h=h.next;
            c=c+1;
        }
        if(b!=head.val)
        {
            answer=false;
        }
        else if(c%2==0)
        {
            c=c/2;
            for(int i=0;i<c;i++)
            {   
                stack1.push(a.val);
                a=a.next;
            }
             for(int i=0;i<c;i++)
            {   
                stack2.push(a.val);
                a=a.next;
            }
              for(int i=0;i<c;i++)
            {   
               stack3.push(stack2.pop());
            }
            
            for(int i=0;i<c;i++)
            {
                if(stack1.pop()!=stack3.pop())
                {
                    answer=false;
                    break;
                }
                 answer=true;
            }
          
        }
        else if(c%2!=0)
        {
            c=c/2;
            for(int i=0;i<c;i++)
            {   
                stack1.push(a.val);
                a=a.next;
            }
            a=a.next;
             for(int i=0;i<c;i++)
            {   
                stack2.push(a.val);
                a=a.next;
            }
             for(int i=0;i<c;i++)
            {   
               stack3.push(stack2.pop());
            }
            
            for(int i=0;i<c;i++)
            {
                if(stack1.pop()!=stack3.pop())
                {
                    answer=false;
                    break;
                }
                 answer=true;
            }
           
        }
        return answer;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

然后得到的结果是还有两组数据输出的答案是错误的
在这里插入图片描述

应该是判断false里面出了问题，判断的pop对应不上出错了

然后我在pop之前加了一个判断，该栈是否为空，依旧是有错

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        int b=0;
        int c=0;
        int d=0;
        Stack<Integer> stack1=new Stack<Integer>();
         Stack<Integer> stack2=new Stack<Integer>();
          Stack<Integer> stack3=new Stack<Integer>();
        ListNode a=head;
        ListNode h=head;
        boolean answer=true;
        while(h!=null)
        {
            b=h.val;
            h=h.next;
            c=c+1;
        }
        if(b!=head.val)
        {
            answer=false;
        }
        else if(c%2==0)
        {
            c=c/2;
            for(int i=0;i<c;i++)
            {   
                stack1.push(a.val);
                a=a.next;    
            }
             for(int i=0;i<c;i++)
            {   
                stack2.push(a.val);
                a=a.next;
            }
              for(int i=0;i<c;i++)
            {   
               stack3.push(stack2.pop());
            }
            
            for(int i=0;i<c;i++)
            {
                if(stack1.peek()!=null&&stack3.peek()!=null){
                    if(stack1.pop()!=stack3.pop())
                {
                    answer=false;
                    break;
                }
                }
                
//                  answer=true;
            }
          
        }
        else if(c%2!=0)
        {
            c=c/2;
            for(int i=0;i<c;i++)
            {   
                stack1.push(a.val);
                a=a.next;
            }
            a=a.next;
             for(int i=0;i<c;i++)
            {   
                stack2.push(a.val);
                a=a.next;
            }
             for(int i=0;i<c;i++)
            {   
               stack3.push(stack2.pop());
            }
            
            for(int i=0;i<c;i++)
            {
                if(stack1.peek()!=null&&stack3.peek()!=null){
                    if(stack1.pop()!=stack3.pop())
                {
                    answer=false;
                    break;
                }
                }
//                  answer=true;
            }
           
        }
        return answer;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

然后看了很久我又改了一个地方，我发现那个变量c

c=c/2;
1

这里第一个else if会改变c的值，然后导致它有可能执行完第一个else if继续执行第二个else if 语句。

但改完以后还是有问题！

最后我不断地查看，我发现这句话特别奇怪

stack1.pop()!=stack3.pop()
1

然后把它改了，先进行pop的赋值再进行比较

 q=stack1.pop();
                w=stack3.pop();
                    if(q!=w)
                {
                    answer=false;
                    break;
                }
1
2
3
4
5
6
7

具体为什么不能直接比较pop的数值还要查一下

最后终于可以得到结果是（虽然运行效率几乎垫底，但也算是通过了），日后再看看有什么办法简化程序

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        int b=0;
        int c=0;
        int d=0;
        int q=0;
        int w=0;
        Stack<Integer> stack1=new Stack<Integer>();
         Stack<Integer> stack2=new Stack<Integer>();
          Stack<Integer> stack3=new Stack<Integer>();
        ListNode a=head;
        ListNode h=head;
        boolean answer=true;
        while(h!=null)
        {
            b=h.val;
            h=h.next;
            c=c+1;
        }
        if(b!=head.val)
        {
            answer=false;
        }
        else if(c%2==0)
        {
            //这里面c的值改变了，就会执行下一个函数c的值
            d=c/2;
            for(int i=0;i<d;i++)
            {   
                stack1.push(a.val);
                a=a.next;    
            }
             for(int i=0;i<d;i++)
            {   
                stack2.push(a.val);
                a=a.next;
            }
              for(int i=0;i<d;i++)
            {   
               stack3.push(stack2.pop());
            }
            
            for(int i=0;i<d;i++)
            {
//                 if(stack1.peek()!=null&&stack3.peek()!=null){
                q=stack1.pop();
                w=stack3.pop();
                    if(q!=w)
                {
                    answer=false;
                    break;
                }
//                 }
                
//                  answer=true;
            }
          
        }
        else if(c%2!=0)
        {
            c=c/2;
            for(int i=0;i<c;i++)
            {   
                stack1.push(a.val);
                a=a.next;
            }
            a=a.next;
             for(int i=0;i<c;i++)
            {   
                stack2.push(a.val);
                a=a.next;
            }
             for(int i=0;i<c;i++)
            {   
               stack3.push(stack2.pop());
            }
            
            for(int i=0;i<c;i++)
            {
//                 if(stack1.peek()!=null&&stack3.peek()!=null){
                q=stack1.pop();
                    w=stack3.pop();
                    if(q!=w)
                {
                    answer=false;
                    break;
                }
//                 }
//                  answer=true;
            }
           
        }
        return answer;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/532635