算法:回文数判断

题目描述

判断一个整数是否是回文数.回文数是指正序(从左到右)和倒序(从右到左)读都是一样的整数

说明:整数不包括010这样的

示例:

121  true
-121  false
10  false

翻转法

func isPalindrome(x: Int) -> Bool {
    var num: Int = x
    if num < 0 || (num%10 == 0 && num != 0 ) {
        return false
    }
    
    var revertedNum: Int = 0
    while num != 0 {
        revertedNum = revertedNum*10 + num%10
        num /= 10
    }
    // 核心 将得到的数值进行翻转 然后进行数值比较
    if revertedNum == x{
        return true
    }else{
        return false
    }
}

仔细观察规律

• 如果是偶数,比如1221,只需要比较前两位和后两位数字翻转后进行比较
• 如果是奇数,比如12321,只需要比较前两位和后两位数字翻转后进行比较,中间的数字不影响回文

稍作修改,变形后如下,这样计算速度就提升了一倍,时间复杂度相当于O(n/2)

func isPalindrome(x: Int) -> Bool {
    var num: Int = x
    if num < 0 || (num%10 == 0 && num != 0 ) {
        return false
    }
    // 用于记录翻转后的临时变量
    var revertedNum: Int = 0
    while num > revertedNum {
        revertedNum = revertedNum*10 + num%10
        num /= 10
    }
    return num == revertedNum || num == revertedNum/10
}

字符串是否为回文数

func isStrPalindrome(str: String) -> Bool {
    var temp = ""
    for c in str.enumerated().reversed() {
        print(c.1) // c是元祖类型
        temp.append(c.1)
    }
    if temp == str {
        return true
    }else{
        return false
    }
}

示例

let res = isStrPalindrome(str: "aba") // true
let res = isStrPalindrome(str: "121") // true

同理,不需要对所有字符进行遍历,只需要遍历一半,进行比较就可以

注意: 以下方法为自己逻辑书写,有可能有问题

func isStrPalindrome2(str: String) -> Bool {
    
    var temp = ""
    let count = str.count
    if count == 1{
        return true
    }
    var subStr = ""
    // 是否是偶数
    let isEven: Int = count%2 == 0 ? 0 : 1
    for c in str.enumerated().reversed() {
        if count/2 > c.0 {
            // 如果是奇数,就多截取一位数
            let startSlicingIndex = str.index(str.startIndex, offsetBy: c.0+isEven)
            subStr = String(str[...startSlicingIndex])
            break
        }else{
            temp.append(c.1)
        }
        print(c)
    }
    print(temp)
    print(subStr)
    if temp == subStr{
        return true
    }else{
        return false
    }
}

测试

let res = isStrPalindrome2(str: "12a21") // true
let res = isStrPalindrome2(str: "aba") // true