LeetCode Day 3

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

/**

 * @param {string} s

 * @return {number}

 */

var lengthOfLongestSubstring = function (s) {

    let maxLength = 0;

    let tmp = [];

    let count = 0;

    for (let index = 0, lens = s.length; index < lens; index++) {

        let dup = tmp.indexOf(s[index]);

        if (dup > -1) {

            if (count > maxLength) {

                maxLength = count;

            }

            tmp.splice(0, dup + 1);

            tmp.push(s[index]);

            count = tmp.length;

        }

        else {

            tmp.push(s[index]);

            count++;

        }

    }

    tmp = null;

    return Math.max(maxLength, count);

};

LeetCode0009

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。(进阶：不将整数转为字符串来解决这个问题。)
输入: 121
输出: true

思路一

/**

 * @param {number} x

 * @return {boolean}

 */

var isPalindrome = function(x) {

    //最简单的就将x.toString().reverse() === x.toString()即可

    //let str = x.toString();

    //return str.split('').reverse().join('') === str;

    //不用考虑溢出问题，因为如果是回文数肯定最后不会溢出，溢出就返回false即可

    if (x < 0) return false;

    if (x === 0) return true;

    let y = x, remainder = 0, result = 0;

    while (y > 0) {

        remainder = y % 10;

        result = result * 10 + remainder;

        y = Math.floor(y / 10);

    }

    return result === x;

};

思路二（官方题解：只反转一半数字）

上面我们考虑到了反转全部数字，对于int要求严格的语言来说，很容易在计算上超过int.Max，那么你还要去处理溢出问题。
那么能不能只反转一半数字呢？
例如，输入1221，我们可以将数字 “1221” 的后半部分从 “21” 反转为 “12”，并将其与前半部分 “12” 进行比较，因为二者相同，我们得知数字 1221 是回文。
对于数字 1221，如果执行 1221 % 10，我们将得到最后一位数字 1，要得到倒数第二位数字，我们可以先通过除以 10 把最后一位数字从 1221 中移除，1221 / 10 = 122，再求出上一步结果除以 10 的余数，122 % 10 = 2，就可以得到倒数第二位数字。如果我们把最后一位数字乘以 10，再加上倒数第二位数字，1 * 10 + 2 = 12，就得到了我们想要的反转后的数字。如果继续这个过程，我们将得到更多位数的反转数字。
现在的问题是，我们如何知道反转数字的位数已经达到原始数字位数的一半？

/**

 * @param {number} x

 * @return {boolean}

 */

var isPalindrome = function (x) {

    if (x < 0) return false;

    if (x === 0) return true;

    if (x % 10 === 0) return false;

    let result = 0;

    //注意这个判断条件，我们上面判断的是大于0，也就是完全反转

    //为什么这里x只要大于result就可以停下来了呢

    //以x = 1221为例，第一步执行，result=1， x = 122

    //第二步，result = 12， x=12

    //可以看到这个时候result就已经等于x了，后面再执行也就是把x=0，result=1221而已

    //考虑到上面是偶数的情况，我们以x=12321为例，第一步执行，result=1， x = 1232

    //第二步，result = 12， x=123

    //第三步，result = 123, x=12,此时跳出循环

    //只要result/10 = 12等于x即可，中间的奇数位不需要跟其他数字做任何比较

    while (x > result) {

        result = result * 10 + x % 10;;

        x = Math.floor(x / 10);

    }

    return result === x || Number.parseInt(result / 10) === x;

};

巴特西

LeetCode Day 3

思路一

思路二（官方题解：只反转一半数字）

最新文章

热门文章