首页目录 点击查看

第一题

• 难度：简单
• 题目： 7. 整数反转
  给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
  示例 1:

输入: 123
输出: 321

输入: -123
输出: -321

解题思路

• 翻转我想的比较快捷的方法就是用数组的reverse方法，所以需要把字符串先转为数组，反转后在join成字符串，但是也需要单独处理负数的情况。

我的答案

• 简单粗暴的字符串转换

       var reverse = function (x) {
           let num = parseInt((x + "").split('').reverse().join(''));
            if (num < -(2 ** 31) || num > 2 ** 31 - 1) {
                return 0;
            }
            return x < 0 ? -num : num
        };

• 时间复杂度：O(N)

• 空间复杂度： O(N)

  
  image.png

高分答案

取余法 321 = 123%10 12%10 1%10 ：这个方案我确实不知道，最后的结果也稍微略胜一筹，所以可以算比我优的解吧。

var reverse = function(x) {
    let ord = Math.abs(x);//去符号
    let now = 0;
    while(ord > 0){
        now = now * 10 + ord % 10;
        ord = Math.floor(ord / 10);
    }
    if(x < 0){
        return now <= Math.pow(2,31) ? -now : 0;
    }else{
        return now < Math.pow(2,31) ? now : 0;
    }
};

image.png

第二题

• 难度：中等
• 题目：8. 字符串转换整数 (atoi)
  请你来实现一个 atoi 函数，使其能将字符串转换成整数。
  首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
  如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
  假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
  该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
  注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
  在任何情况下，若函数不能进行有效的转换时，请返回 0 。
• 提示：
  本题中的空白字符只包括空格字符 ' ' 。
  假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

解题思路

• 第一种方法是拆开字符串处理：
  这道题需要符合条件的需要满足以下几个条件：

1. 字符的第一位正负号，且字符长度大于1，字符串第二位必须是数字
2. 字符串的第一位是数字
3. 字符串的转换的数字有大小范围限制

• 第二种是利用parseInt处理

我的答案

• 拆分字符串

          var myAtoi = function (str) {
            let newStr = str.trim(),  //先去掉前后空格
                firstStr = newStr[0],  //获取到第一个字符
                number = firstStr,      //最后待输出的number
              //如果首字符不是数字 或者首字符是- +符号，但是字符整体长度只有1个
           if (!isNaN(firstStr) || ((firstStr === '-' || firstStr === '+') && newStr.length > 1)) {
                for (let i = 1; i <= newStr.length - 1; i++) {
                    if (!isNaN(newStr[i]) && (newStr[i] !== ' ')) {
                        number += newStr[i]
                    } else {
                        break
                    }
                }
                if (number === "-" || number === "+") {  //如果最后只有+- 就返回0
                    return 0
                }
                number = Number(number)
                if (number < Math.pow(-2, 31) || number > Math.pow(2, 31) - 1) {  //判断范围
                    return number < Math.pow(-2, 31) ? Math.pow(-2, 31) : Math.pow(2, 31) - 1;
                }
                return number
            } else {
                return 0
            }
        };

结果

• parseInt

      let myAtoi = (str)=> {
            let number = parseInt(str)
            if (isNaN(number)) {
                return 0
            }
            if (number < Math.pow(-2, 31) || number > Math.pow(2, 31) - 1) {
                return number < Math.pow(-2, 31) ? Math.pow(-2, 31) : Math.pow(2, 31) - 1;
            }
            return number
      };

image.png

两者性能几乎差不多，但是第二种的代码量明显更少。

高分答案

我的代码量稍微偏大，在leetCode看到一个答案只有4行，用正则处理的，不怎么会正则，不过也算一个不错的解题方法。贴给大家看看,性能是我这个更好一些

let myAtoi = (str)=> {
    let res = str.trim().match(/^(\-|\+)?\d+/g)
    return res ? Math.max(Math.min(Number(res[0]),2**31-1),-(2**31)) : 0
};

image.png

第三题

• 难度：简单
• 题目：9. 回文数
  判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
  示例：

输入: 121
输出: true

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

解题思路

• 第一种方案是把字符拆成前后两部分，后面那部分转换成数组后倒序，然后和前面部分比较，如果相等则是回文
• 第二种方案是把数组分为前后两部分，角标i的数要等于数组长度-i，如果两者相等则为回文

我的答案

• 第一种：

        var isPalindrome = function (x) {
            x = x + ""
            if (x.length === 1) {
                return true
            }
            let isOdd = x.length % 2 === 0
            let halfLen = isOdd ? x.length / 2 : Math.floor(x.length / 2)
            if (x.slice(0, halfLen) === x.slice(isOdd ? halfLen : halfLen + 1).split("").reverse().join("")) {
                return true
            } else {
                return false
            }
        };
        console.log(isPalindrome("121"))

image.png

• 第二种

          var isPalindrome = function (x) {
            x = x + ""
            if (x.length === 1) {
                return true
            }
            let flag = true
            for (let i = 0; i < Math.floor(x.length / 2); i++) {
                if ((i < x.length - 1 - i) && x[i] !== x[x.length - 1 - i]) {
                    flag = false
                }
            }
            return flag
        };
        console.log(isPalindrome("1221"))

image.png

高分答案

• 看了题解还有一种方案非常的好，不需要把数字转为字符，用取余的方式。如果是负数直接返回false,如果最后一位是0，也直接返回false。
  对于数字 1221，如果执行 1221 % 10，我们将得到最后一位数字 1，要得到倒数第二位数字，我们可以先通过除以 10 把最后一位数字从 1221 中移除，1221 / 10 = 122，再求出上一步结果除以 10 的余数，122 % 10 = 2，就可以得到倒数第二位数字。如果我们把最后一位数字乘以 10，再加上倒数第二位数字，1 * 10 + 2 = 12，就得到了我们想要的反转后的数字。如果继续这个过程，我们将得到更多位数的反转数字。
  现在的问题是，我们如何知道反转数字的位数已经达到原始数字位数的一半？
  由于整个过程我们不断将原始数字除以 10，然后给反转后的数字乘上 10，所以，当原始数字小于或等于反转后的数字时，就意味着我们已经处理了一半位数的数字了。

  
  image.png

        var isPalindrome = function (x) {
            if (x < 0 || (x % 10 === 0 && x !== 0)) {
                return false
            }
            let newNum = 0;
            while (x > newNum) {
                newNum = newNum * 10 + x % 10
                x = Math.floor(x / 10)
            }
            return x === newNum || x === Math.floor(newNum / 10)
        };
        console.log(isPalindrome(123212))

这性能非常好啊，几乎双百了

image.png

第四题

• 难度：中等
• 题目：43. 字符串相乘
  给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
  示例：

输入: num1 = "2", num2 = "3"
输出: "6"

输入: num1 = "123", num2 = "456"
输出: "56088"

说明:

num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

解题思路

• 这道题不能直接用数字相乘得最后的结论，因为大数会直接超出，题目也不允许，所以，这里只能用读书学乘除法得方法依次做乘法，然后错位相加。

我的答案

        var multiply = function (num1, num2) {
            if (num1 === "0" || num2 === "0") return "0"
            let len1 = num1.length,
                len2 = num2.length,
                array = new Array(len1 + len2).fill(0)
            for (let i = len1 - 1; i >= 0; i--) {
                for (let j = len2 - 1; j >= 0; j--) {
                    const product = num1[i] * num2[j];
                    const sum = array[i + j + 1] + product;
                    array[i + j + 1] = sum % 10;
                    array[i + j] += sum / 10 | 0;
                }
            }
            if (array[0] == 0) {
                array.shift();
            }
            return array.join("")
        };
        console.log(multiply("999", '999'))

• 时间复杂度：O(N2)

• 空间复杂度： O(N)

  
  image.png

第五题

• 难度：简单
• 题目：172. 阶乘后的零
  给定一个整数 n，返回 n! 结果尾数中零的数量。
  示例：

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.

说明: 你算法的时间复杂度应为 O(log n) 。

解题思路

• 这道题，本来打算用递归解决的，可是发现递归其实没必要，也不是真正的需要求得最后的数值，看了大神的思路，其实只要找出有多少个5就可以，一个5就有一个0

我的答案

var trailingZeroes = function (n) {
    let num = 0;
    while (n >= 5) {
        n = parseInt(n / 5)
        num += n
    }
    return num
};

第六题

• 难度：简单
• 题目：258. 各位相加
  给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
  示例：

输入: 38
输出: 2 
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。

你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？

解题思路

• 这道题实际上很简单，但是主要是O(1)的时间复杂度，也就是说不能用循环，直接处理输出结果，就需要找规律，比如'1111 = 1 * 1000 + 1 * 100 + 1 * 10 + 1'，现在换成'4= 1 + 1 + 1 + 1' 两者之间差了'999 + 99 + 9',所以直接把这个数取9的余数，如果小于9直接输出num,如果取余===0，则直接输出9，其他情况，输出余数

我的答案

var addDigits = function (num) {
    if (num < 9) {
        return num
    } else {
        if (num % 9 === 0) {
            return 9
        }
        return num % 9
    }
};

• 时间复杂度：O(1) image.png