阿俊带你用Kotlin刷算法（三）

2021-06-27 本文已影响0人谭嘉俊

本系列通过Java和Kotlin这两种语言来解决力扣上面的算法题，由于本人算法菜鸟一枚，可能部分题目并不是最优题解，希望能和各位大神共同讨论~

阿俊带你用Kotlin刷算法（一）

阿俊带你用Kotlin刷算法（二）

阿俊带你用Kotlin刷算法（三）

项目的GitHub：Algorithm

整数反转（Reverse Integer）

难度：简单

链接：Reverse Integer

代码

Java

/**
 * Created by TanJiaJun on 2021/6/15.
 * 7. 整数反转（Reverse Integer）
 * 难度：简单
 *
 * @see <a href="https://leetcode-cn.com/problems/reverse-integer/">Reverse Integer</a>
 */
class ReverseInteger {

    public static void main(String[] args) {
        // 示例一
        System.out.print("示例一：");

        int firstNumber = 123;
        System.out.println(reverse(firstNumber));

        System.out.print("\n");

        // 示例二
        System.out.print("示例二：");

        int secondNumber = -123;
        System.out.println(reverse(secondNumber));

        System.out.print("\n");

        // 示例三
        System.out.print("示例三：");

        int thirdNumber = 120;
        System.out.println(reverse(thirdNumber));

        System.out.print("\n");

        // 示例四
        System.out.print("示例四：");

        int fourthNumber = 0;
        System.out.println(reverse(fourthNumber));

        System.out.print("\n");
    }

    /**
     * 时间复杂度：O(log|n|)，其中n是整型x的位数
     * 空间复杂度：O(1)
     *
     * @param x 整型x
     * @return 结果
     */
    private static int reverse(int x) {
        int result = 0;
        while (x != 0) {
            // 得到最后一位，例如：123的3
            int digit = x % 10;
            if (result < -214748364 || (result == -214748364 && digit < -8)) {
                // 判断结果是否小于Integer.MIN_VALUE，也就是是否小于-2147483648
                return 0;
            }
            if (result > 214748364 || (result == 214748364 && digit > 7)) {
                // 判断结果是否大于Integer.MAX_VALUE，也就是是否大于2147483647
                return 0;
            }
            // 得到除了最后一位的前几位，例如：123的12
            x /= 10;
            result = result * 10 + digit;
        }
        return result;
    }

}

Kotlin

/**
 * Created by TanJiaJun on 2021/6/26.
 * 7. 整数反转（Reverse Integer）
 * 难度：简单
 *
 * @see <a href="https://leetcode-cn.com/problems/reverse-integer/">Reverse Integer</a>
 */
object ReverseIntegerKotlin {

    @JvmStatic
    fun main(args: Array<String>) {
        // 示例一
        print("示例一：")

        val firstNumber = 123
        println(reverse(firstNumber))

        print("\n")

        // 示例二
        print("示例二：")

        val secondNumber = -123
        println(reverse(secondNumber))

        print("\n")

        // 示例三
        print("示例三：")

        val thirdNumber = 120
        println(reverse(thirdNumber))

        print("\n")

        // 示例四
        print("示例四：")

        val fourthNumber = 0
        println(reverse(fourthNumber))

        print("\n")
    }

    /**
     * 时间复杂度：O(log|n|)，其中n是整型x的位数
     * 空间复杂度：O(1)
     *
     * @param x 整型x
     * @return 结果
     */
    private fun reverse(x: Int): Int {
        var result = 0
        var number = x
        while (number != 0) {
            // 得到最后一位，例如：123的3
            val digit = number % 10
            if (result < -214748364 || (result == -214748364 && digit < -8)) {
                // 判断结果是否小于Integer.MIN_VALUE，也就是是否小于-2147483648
                return 0
            }
            if (result > 214748364 || (result == 214748364 && digit > 7)) {
                // 判断结果是否大于Integer.MAX_VALUE，也就是是否大于2147483647
                return 0
            }
            // 得到除了最后一位的前几位，例如：123的12
            number /= 10
            result = result * 10 + digit
        }
        return result
    }

}

时间复杂度：O(log|n|)，其中n是整型x的位数。

空间复杂度：O(1)。

题解

大部分逻辑可以用数学表达式完成，举个例子：假设x是123，袋盖步骤如下所示：

123 % 10 = 3，3就是最后一位，然后123 / 10得到12，结果就是3。
12 % 10 = 2，2就是最后一位，然后12 / 10得到1，结果就是32。
1 % 10 = 1，1就是最后一位，然后1 / 10得到0，结果就是321，跳出循环。

要注意的是，根据题义可知，如果反转后整数超过32位的有符号整数的范围[ $2^31$ , $2^31 - 1$ ]，就返回0，并且环境不允许存储64位整数（有符号或者没有符号），也就是说我们不能使用long类型存储结果，所以我们需要对其进行判断，让结果在[ $2^31$ , $2^31 - 1$ ]范围中，也就是[-2147483648, 2147483647]范围中，也就是如果result的值小于214748364或者大于214748364都不符合，如果result的值刚好是214748364呢？那就判断下digit的值，也就是最后一位是否小于8或者大于7。

字符串转整数（atoi）（String to Integer(atoi)）

难度：简单

链接：https://leetcode-cn.com/problems/string-to-integer-atoi/

代码

Java

import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * Created by TanJiaJun on 2021/6/18.
 * 8. 字符串转整数（atoi）（String to Integer(atoi)）
 * 难度：简单
 *
 * @see <a href="https://leetcode-cn.com/problems/string-to-integer-atoi/">String to Integer(atoi)</a>
 */
class StringToInteger {

    public static void main(String[] args) {
        // 示例一
        System.out.print("示例一：");

        String firstStr = "42";
        System.out.println(myAtoi(firstStr));

        System.out.print("\n");

        // 示例二
        System.out.print("示例二：");

        String secondStr = "-42";
        System.out.println(myAtoi(secondStr));

        System.out.print("\n");

        // 示例三
        System.out.print("示例三：");

        String thirdStr = "4193 with words";
        System.out.println(myAtoi(thirdStr));

        System.out.print("\n");

        // 示例四
        System.out.print("示例四：");

        String fourthStr = "words and 987";
        System.out.println(myAtoi(fourthStr));

        System.out.print("\n");

        // 示例五
        System.out.print("示例五：");

        String fifthStr = "-91283472332";
        System.out.println(myAtoi(fifthStr));
    }

    /**
     * 时间复杂度：O(N)，其中N是字符串的长度
     * 空间复杂度：O(1)
     *
     * @param s 字符串
     * @return 结果
     */
    private static int myAtoi(String s) {
        // 去掉字符串前面和后面的空格
        s = s.trim();
        // ^[\+\-]?的意思是判断字符是否匹配+或者-，匹配零次或者一次
        // \d+的意思是判断字符是否匹配[0-9]，匹配一次或者多次
        Pattern pattern = Pattern.compile("^[\\+\\-]?\\d+");
        Matcher matcher = pattern.matcher(s);
        boolean isInteger = matcher.find();
        int result = 0;
        if (isInteger) {
            try {
                result = Integer.parseInt(s.substring(matcher.start(), matcher.end()));
            } catch (NumberFormatException exception) {
                // 如果抛出NumberFormatException异常，证明小于整型的最小值，大于整型的最大值
                result = s.charAt(0) == '-' ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
        }
        return result;
    }

}

Kotlin

import java.util.regex.Pattern

/**
 * Created by TanJiaJun on 2021/6/26.
 * 8. 字符串转整数（atoi）（String to Integer(atoi)）
 * 难度：简单
 *
 * @see <a href="https://leetcode-cn.com/problems/string-to-integer-atoi/">String to Integer(atoi)</a>
 */
object StringToIntegerKotlin {

    @JvmStatic
    fun main(args: Array<String>) {
        // 示例一
        print("示例一：")

        val firstStr = "42"
        println(myAtoi(firstStr))

        print("\n")

        // 示例二
        print("示例二：")

        val secondStr = "-42"
        println(myAtoi(secondStr))

        print("\n")

        // 示例三
        print("示例三：")

        val thirdStr = "4193 with words"
        println(myAtoi(thirdStr))

        print("\n")

        // 示例四
        print("示例四：")

        val fourthStr = "words and 987"
        println(myAtoi(fourthStr))

        print("\n")

        // 示例五
        print("示例五：")

        val fifthStr = "-91283472332"
        println(myAtoi(fifthStr))
    }

    /**
     * 时间复杂度：O(N)，其中N是字符串的长度
     * 空间复杂度：O(1)
     *
     * @param s 字符串
     * @return 结果
     */
    private fun myAtoi(s: String): Int {
        // 去掉字符串前面和后面的空格
        val str = s.trim()
        // ^[\+\-]?的意思是判断字符是否匹配+或者-，匹配零次或者一次
        // \d+的意思是判断字符是否匹配[0-9]，匹配一次或者多次
        val pattern = Pattern.compile("^[\\+\\-]?\\d+")
        val matcher = pattern.matcher(str)
        val isInteger = matcher.find()
        var result = 0
        if (isInteger) {
            result = try {
                str.substring(startIndex = matcher.start(), endIndex = matcher.end()).toInt()
            } catch (exception: NumberFormatException) {
                // 如果抛出NumberFormatException异常，证明小于整型的最小值，大于整型的最大值
                if (str[0] == '-') Int.MIN_VALUE else Int.MAX_VALUE
            }
        }
        return result
    }
}

时间复杂度：O(N)，其中N是字符串的长度。

空间复杂度：O(1)。

题解

这道题我使用了正则表达式来解决，这里我解释下^[\+\-]?\d+这段正则表达式的含义：

^[\\+\\-]?的意思是判断字符是否匹配+或者-，匹配零次或者一次。
\\d+的意思是判断字符是否匹配[0-9]，匹配一次或者多次。

要注意的是，根据题义可知，结果要在[ $2^31$ , $2^31 - 1$ ]范围内，所以如果抛出NumberFormatException异常的时候，需要将值设置为整型的最小值Int.MIN_VALUE（ $2^31$ ，2147483648）或者最大值Int.MAX_VALUE（ $2^31-1$ ，2147483647）。

回文数（Palindrome Number）

难度：简单

链接：https://leetcode-cn.com/problems/palindrome-number/

代码

Java

/**
 * Created by TanJiaJun on 2021/6/19.
 * 9. 回文数（Palindrome Number）
 * 难度：简单
 *
 * @see <a href="https://leetcode-cn.com/problems/palindrome-number/">Palindrome Number</a>
 */
class PalindromeNumber {

    public static void main(String[] args) {
        // 示例一
        System.out.print("示例一：");

        int firstNumber = 121;
        System.out.println(isPalindrome(firstNumber));

        System.out.print("\n");

        // 示例二
        System.out.print("示例二：");

        int secondNumber = -121;
        System.out.println(isPalindrome(secondNumber));

        System.out.print("\n");

        // 示例三
        System.out.print("示例三：");

        int thirdNumber = 10;
        System.out.println(isPalindrome(thirdNumber));

        System.out.print("\n");

        // 示例四
        System.out.print("示例四：");

        int fourthNumber = -101;
        System.out.println(isPalindrome(fourthNumber));
    }

    /**
     * 时间复杂度：O(N)，其中N是整型x的位数
     * 空间复杂度：O(N)，其中N是整型x的位数，因为要创建长度为位数的字符串
     *
     * @param x 整型x
     * @return 结果
     */
    private static boolean isPalindrome(int x) {
        // 将整型x转为字符串
        String str = String.valueOf(x);
        int length = str.length();
        // 只需要遍历该字符串长度一半就可以了
        for (int i = 0; i < length / 2; i++) {
            // 因为回文串的特性，我们可以用该字符和索引为length-i-1的字符比较是否相同就可以判断了
            if (str.charAt(i) != str.charAt(length - i - 1)) {
                // 只要有一个不相同，证明不是回文串
                return false;
            }
        }
        // 如果都相同，证明是回文串
        return true;
    }

}

Kotlin

/**
 * Created by TanJiaJun on 2021/6/26.
 * 9. 回文数（Palindrome Number）
 * 难度：简单
 *
 * @see <a href="https://leetcode-cn.com/problems/palindrome-number/">Palindrome Number</a>
 */
object PalindromeNumberKotlin {

    @JvmStatic
    fun main(args: Array<String>) {
        // 示例一
        print("示例一：")

        val firstNumber = 121
        println(isPalindrome(firstNumber))

        print("\n")

        // 示例二
        print("示例二：")

        val secondNumber = -121
        println(isPalindrome(secondNumber))

        print("\n")

        // 示例三
        print("示例三：")

        val thirdNumber = 10
        println(isPalindrome(thirdNumber))

        print("\n")

        // 示例四
        print("示例四：")

        val fourthNumber = -101
        println(isPalindrome(fourthNumber))
    }

    /**
     * 时间复杂度：O(N)，其中N是整型x的位数
     * 空间复杂度：O(N)，其中N是整型x的位数，因为要创建长度为位数的字符串
     *
     * @param x 整型x
     * @return 结果
     */
    private fun isPalindrome(x: Int): Boolean {
        // 将整型x转为字符串
        val str = x.toString()
        val length = str.length
        // 只需要遍历该字符串长度一半就可以了
        for (i in 0 until length / 2) {
            // 因为回文串的特性，我们可以用该字符和索引为length-i-1的字符比较是否相同就可以判断了
            if (str[i] != str[length - i - 1]) {
                // 只要有一个不相同，证明不是回文串
                return false
            }
        }
        // 如果都相同，证明是回文串
        return true
    }

}

时间复杂度：O(N)，其中N是整型x的位数。

空间复杂度：O(N)，其中N是整型x的位数，因为要创建长度为位数的字符串。

题解

由于回文串的特征是正读和反读都一样，例如：abba就是回文串，abda就不是回文串了，所以我们只要找到某个字符，并且找到该字符索引length-i-1的字符，只需要遍历该字符串长度一半就可以判断该字符串是否为回文串，要注意的是，我这里先将整型x转为字符串，然后再执行相应的逻辑即可。

我的GitHub：TanJiaJunBeyond

Android通用框架：Android通用框架

我的掘金：谭嘉俊

我的简书：谭嘉俊

我的CSDN：谭嘉俊

阿俊带你用Kotlin刷算法（三）

整数反转（Reverse Integer）

代码

Java

Kotlin

题解

字符串转整数（atoi）（String to Integer(atoi)）

代码

Java

Kotlin

题解

回文数（Palindrome Number）

代码

Java

Kotlin

题解

猜你喜欢

热点阅读