LeetCode 2396 หมายเลขพาลินโดรมอย่างเคร่งครัด

หมายเหตุ LeetCode (43)

ปัญหา

วิธีที่ 1: แปลงเป็นฐาน b และเช็คเป็นพาลินโดรมิกหรือไม่

class Solution {
    fun isStrictlyPalindromic(n: Int): Boolean {
        for (i in 2..n - 2) {
            if (!isPalindromic(base(n, i))) return false
        }
        return true
    }

    private fun base(n: Int, base: Int): String {
        var result = ""
        var num = n
        while (num > 0) {
            result = "${num % base}$result"
            num /= base
        }
        return result
    }

    private fun isPalindromic(s: String): Boolean {
        val charArray = s.toCharArray()
        for (i in 0..charArray.size / 2 + 1) {
            if (charArray[i] != charArray[charArray.size - 1 - i])
                return false
        }
        return true
    }
}

การวิเคราะห์ความซับซ้อน

• ความซับซ้อนของเวลา: O(nlgn)
• ความซับซ้อนของอวกาศ: O(lgn)

แนวทางที่ 2: การสังเกต

สำหรับทุกฐาน n — 2

• n = 4 -› 100 (เท็จ)
• n > 4 -› 21 (เท็จ ตั้งแต่ n = (n-2) + 2)

เราไม่พบ n ที่ตรงตามข้อจำกัด ดังนั้นเราสามารถส่งคืน false ได้

class Solution {
    fun isStrictlyPalindromic(n: Int): Boolean {
        return false
    }
}

การวิเคราะห์ความซับซ้อน

• ความซับซ้อนของเวลา: O(1)
• ความซับซ้อนของอวกาศ: O(1)