Java 문자열 회문 구현의 코드 예

이 기사는 Java 문자열 회문 구현에 대한 코드 예제를 제공합니다. 이는 특정 참조 값을 가지고 있습니다. 도움이 필요한 친구가 도움이 되기를 바랍니다.

문자열 회문

문자열이 회문 문자열인지 확인하는 방법 오늘 우리의 주제는 이
문제의 수정된 버전을 기반으로 한 것입니다. 문자열이 단일 연결 목록을 통해 저장된 경우 회문 문자열인지 확인하는 방법은 무엇입니까? 좋은 해결책이 있나요? 해당 시간 및 공간 복잡도는 얼마입니까?

아이디어:

1. 중간 노드를 찾기 위해 빠른 포인터와 느린 포인터를 사용합니다.
2. 중간 노드를 찾는 동안 이전의 역순 연결 리스트를 처음부터 중간 노드까지 복사합니다.
3. 느린 연결 목록을 사용하여 동일한지 확인하세요.

코드:

package me.study.algorithm;

/**
 * public class LinkNode {
 *
 *     char val;
 *
 *     LinkNode next;
 *
 *     public LinkNode() {
 *     }
 *
 *     public LinkNode(char val) {
 *         this.val = val;
 *     }
 * }
 */
public class StringBack {


    public boolean clac(LinkNode head) {

        if (head.next == null && head.next == null){
            return true;
        }

            LinkNode prev = null;
            LinkNode slow = head;
            LinkNode fast = head;

            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                LinkNode next = slow.next;
                slow.next = prev;
                prev = slow;
                slow = next;
            }


            if (fast != null) {
                slow = slow.next;
            }

            while (slow != null) {
                if (slow.val != prev.val) {
                    return false;
                }
                slow = slow.next;
                prev = prev.next;
            }

            return true;


    }
}

최고의 시간 복잡도:

가장 좋은 경우는 단일 문자이거나 빈 문자열이며, 시간 복잡도는 O(1)

최악의 시간 복잡도:

중간 노드를 찾는 시간 복잡도는 n/2
크기 비교의 시간 복잡도는 같은지 끝까지 비교하지 않으므로 n/2
모두 더하면 최종 시간 복잡도는 O(n)

이 글은 여기까지이고, 다른 흥미로운 내용도 더 있습니다. PHP 중국어 홈페이지의

Java Video Tutorial 칼럼을 주목해주세요!

위 내용은 Java 문자열 회문 구현의 코드 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!