黄威龙的笔记

coding 笔记

0%

LeetCode 笔记

发表于 更新于 分类于 阅读次数： Valine：

7. 整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321

这里想到3种方法:

  1. 将数字丢进数组里,用数组自带的reverse方法再依次乘以对应10的i次方
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number} x
 * @return {number}
 */
const reverse = function(x) {
    const arr = []
    const xAbs = Math.abs(x)
    for (let number of xAbs.toString()) {
        arr.push(number)
    }
    arr.reverse()
    let result = 0
    for (i = arr.length, j = 0; i > 0; i--, j++) {
        result += arr[j] * Math.pow(10, i - 1)
    }
    if (result >= Math.pow(2, 31)) {
        return 0
    }
    return x < 0 ? 0 - result : result
};

整个过程做了2次循环,还做了很多次的指数运算,虽然还是O(lg(n)),但效率相对较低

  1. 使用取模的办法来获取每一位数,这样就减少了10的指数运算,并且只做了一次循环
1
2
3
4
5
6
7
8
9
10
11
12
13
const reverse2 = function(x) {
    let result = 0
    let xAbs = x < 0 ? x * -1 : x
    while (xAbs !== 0) {
        let pop = xAbs % 10;
        xAbs = Math.floor(xAbs / 10);
        result = result * 10 + pop
    }
    if (result >= 2**31 - 1) {
        return 0
    }
    return x < 0 ? 0 - result : result
}

但这种方法依然是做了算计计算,取模,乘除

  1. 用字符串拼接的方法
1
2
3
4
5
6
7
8
9
10
const xAbs = Math.abs(x).toString()
    let result = ''
    for (let i = 0; i < xAbs.length; i++) {
        result += xAbs[xAbs.length - i - 1]
    }
    result = parseInt(result)
    if (result > 2**31 - 1) {
        return 0
    }
    return x < 0 ? 0 - result :

26.删除排序数组中的重复项

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

例如: nums = [1,1,2] -> [1,2]
return 2

题目要求在原地删除重复出现的元素,不能使用额外的数组空间,所以就不能new Set()来处理,也不能用新数组来存储没有重复的数字.
也就是说

1
2
// 不能使用set
return [...new Set(nums)]
1
2
3
4
5
6
7
8
// 也不能使用
const arr = [nums[0]]
for (let i = 1; i < nums.length; i++) {
    if (!arr.includes(nums[i])) {
        arr.push(nums[i])
    }
}
return arr
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 使用双指针
// 前提是输入的数组是已经排序好的
if (nums.length < 2) {
    return nums
}
let i = 0,j = 1;
while (j < nums.length) {
    if (nums[i] !== nums[j]) {
        nums[i + 1] = nums[j]
        i++;
    }
    j++
}
return nums.slice(0, i + 1)
// 可以画图理解一下指针的移动过程

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

如果使用遍历叠加的方式,但是又不确定到底是连续几项相加最大,所以暴力法不可取,否则时间复杂度也会非常高.经过分析,如果要连续子数组和最大(子数组元素大于1的情况),那第一项必定是正数,如果元素全为负数,子数组和最大就是最大的子元素.所以找到一个正数就往后叠加,并且把叠加和赋值给当前的位置,再和当前计算出的和最大值比较,取大的数

1
2
3
4
5
6
7
8
let maxCount = nums[0];
for (let i = 1; i < nums.length; i++) {
    if (nums[i - 1] > 0) {
        nums[i] += nums[i - 1]; // 改变原数组,如果这个值是负数,就另找正数开始
    }
    maxCount = Math.max(maxCount, nums[i]);
}
return maxCount;