image frame

四月八日

53.最大子序和

算法 / 关联题目
LeetCode

暴力解法 窗口移动

  • 指定窗口大小，初始窗口大小为1。
  • 向右移动窗口并计算窗口内的元素和，直到窗口移动到数组尾部结束。
  • 在移动的过程中，比较窗口内的和是否比上一次大，如果比上一次大记录最大值。
  • 扩大窗口大小，并重复上面过程，直到窗口大小与数组大小相同，并返回最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var maxSubArray = function (nums) {
    var sum;
    for (var i = 0; i < nums.length; i++) {
        for (var j = 0; j + i < nums.length; j++) {
            var temp = 0;
            for (var k = 0; k < i + 1; k++) {
                temp += nums[j + k];
            }
            if (sum === undefined) sum = temp
            if (temp > sum) sum = temp;
        }
    }
    return sum;
};

复杂度分析

  • 时间复杂度：,时间复杂度较高，数据量大的时候可能通不过测试。

  • 空间复杂度：

暴力解法优化

  • 不需要确认窗口大小，只需要每次遍历到数组结尾即可
  • 也可以理解为线改变窗口大小遍历，下一次移动启示位置之后重新遍历窗口大小

1
2
3
4
5
6
7
8
9
10
11
12
var maxSubArray = function (nums) {
  var sum;
  for (var i = 0; i < nums.length; i++) {
      var temp = 0;
      for (var j = i; j < nums.length; j++) {
          temp += nums[j];
          if (temp > sum || sum === undefined) sum = temp;
      }
  }
  return sum;
};

复杂度分析

  • 时间复杂度：

  • 空间复杂度：

动态规划

我们用 代表 nums[i]，用 代表以第 个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：

因此我们只需要求出每个位置的 ，然后返回 数组中的最大值即可。那么我们如何求 呢？我们可以考虑 单独成为一段还是加入 对应的那一段，这取决于 和的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：

关键在于 子数组最大值的求法，为什么两两比较的最大值是最终最大字串的值？

  • 首先需要舍弃索引的概念，并不需要通过索引区间记录哪个区间字串的和最大
  • 每一次的结果是基于上一次的最大值比较的,从长度等于1开始，所以取和中最大的就是子数组中的最大的原因就在于此，因为上一次的结果就是最优解（最大值），所以本次只需要比较一次就可以了
  • 最后每次更新保存最终最大值的变量就可以了
1
2
3
4
5
6
7
8
9
10
11
var maxSubArray = function (nums) {
    var sum_endof_here = nums[0];
    var sum_far_from = nums[0];
    for (var i = 1; i < nums.length; i++) {
        // 只有在当前值大于之前的和时，之前的值才会被丢弃，
        // 否则前面的值无论怎样波动增大或减小，但此时此刻加上当前值，就是当前子数组的最大值
        sum_endof_here = Math.max(nums[i], nums[i] + sum_endof_here);
        sum_far_from = Math.max(sum_far_from, sum_endof_here);
    }
    return sum_far_from;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var maxSubArray = function (nums) {
    var sum_endof_here = 0;
    var sum_far_from = nums[0];
    for (var i = 0; i < nums.length; i++) {
        // 等同于 if(sum_endof_here>0){}
       if(sum_endof_here+ nums[i]>nums[i]){
        sum_endof_here = sum_endof_here+ nums[i]
       }else{
        sum_endof_here = nums[i];
       }
       sum_far_from = Math.max(sum_far_from,sum_endof_here)
    }
    return sum_far_from;
};

  • 时间复杂度： 只需要遍历一次数组就可以得到结果。

  • 空间复杂度：

分治

38. 外观数列

算法 / 关联题目
LeetCode

注意

  • 处理边界情况，当n==1返回'1'

暴力解法 循环+使用栈结构

使用数组来处理统计字符个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var countAndSay = function (n) {
    if (n === 1) return '1';
    var res = '1',
        i = 1;
    for (; i < n; i++) {
        var str = '';
        var count = 0;
        var stack = [];
        for (var j = 0; j < res.length; j++) {
            if (stack[0] !== undefined && stack[0] !== res[j]) {
                str += stack.length + stack[0];
                stack = [];
            }
            stack.push(res[j])
        }
        if (stack.length) {
            str += stack.length + stack[0];
        }
        res = str;
    }
    return res;
};

优化 双指针

在处理字符个数时有个很通用且巧妙的解法，使用双指针来统计连续字符串出现的个数

计数二进制子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var countAndSay = function (n) {
    if (n === 1) return '1';
    var res = '1';
    for (var i = 1; i < n; i++) {
        var j = 0;
        var temp = '';
        for (var k = 0; k < res.length; k++) {
            if (res[j] !== res[k]) {
                temp += String(k - j) + res[j];
                j = k;
            }
        }
        temp += String(k - j) + res[j];
        res = temp;
    }
    return res;
};

递归

可以把循环n时改为递归的形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var countAndSay = function (n) {
    if (n === 1) return '1';
    var res = countAndSay(n - 1);
    var j = 0;
    var temp = '';
    for (var k = 0; k < res.length; k++) {
        if (res[j] !== res[k]) {
            temp += String(k - j) + res[j];
            j = k;
        }
    }
    temp += String(k - j) + res[j];
    return temp
};

35. 搜索插入位置

算法 / 关联题目

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

1
2
输入: [1,3,5,6], 2
输出: 1

注意

  • 如果数组中已经存在相同的数字，插入位置是当前数字的前一位
    1
    2
    输入: [1,3,5,6], 5
    输出: 2

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
var searchInsert = function (nums, target) {
    var i = 0,
        len = nums.length;
    // 处理边界
    if (nums[len - 1] < target) return len;
    if (nums[len - 1] === target) return len - 1;
    for (; i < len - 1; i++) {
        if (nums[i] === target) return i;
        if (nums[i] < target && nums[i + 1] > target) {
            return i + 1;
        }
    }
};

二分法

此题很容易想到用二分法解决，如果在一个给定范围的数组中查询某一项，大概率可以使用二分法。

思路

  • 定义左下标left,和右下标right
  • 计算mid=Math.floor(left+right),向下取整保证下表位整数
  • 根据nums[mid]值来判断，如果nums[mid]===target 返回mid，如果nums[mid]<target说明mid左侧值全都比mid小，下次比较时只需要关心mid右侧值，所以left变为mid的下一位，left=mid+1. 同理，nums[mid]>target 只需要关心mid左侧值，right=mid-1
  • 最后如果没有和mid相等的情况是返回left即位插入的位置.


为什么可以使用left作为返回结果？
因为向下取整所以在相邻位置时left===mid

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var searchInsert = function (nums, target) {
    var len = nums.length,
        left = 0,
        right = (0, len - 1);
    while (left <= right) {
        mid = Math.floor((right + left) / 2)
        if (nums[mid] === target) {
            return mid;
        }
        if (nums[mid] < target) {
            left = mid + 1;
        }
        if (nums[mid] > target) {
            right = mid - 1
        }
    }
    return left;
};

复杂度分析

  • 时间复杂度：

  • 空间复杂度：

2. 两数相加

算法 / 关联题目
LeetCode

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

1
2
3
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

分析

  • 观察题目可能会思考，如何实现进位，和从低位开始依次相加？
  • 进位可以通过一个变量来控制
  • 按位相加其实就是从链表的根节点依次相加，因为l1,l2两个链表表示的数字是从地位到高位。

基于以上分析何以做一个简单的实现

简单实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 var addTwoNumbers = function (l1, l2) {
    //新链表
    var head = {
        next: null
    }
    //头指针
    var cur = head;
    //当前为的和
    var sum = 0;
    //进位
    var curry = 0;
    while (l1 !== null || l2 !== null) {
        if (l1 && l2) {
            sum = (l1.sum + l2.sum + curry) % 10;
            curry = (l1.sum + l2.sum + curry) / 10 | 0;
            l1 = l1.next;
            l2 = l2.next;
        }
        if (l1 && !l2) {
            sum = l1.sum
            l1 = l1.next;
        }
        if (!l1 && l2) {
            sum = l2.sum
            l2 = l2.next;
        }
        cur.next = {
            sum: sum,
            next: null
        }
        cur = cur.next;
    }
    return head.next
};

处理边界

虽然上面的代码可以正确输出 7 -> 0 -> 8 的新链表，但是存在很多问题

  • 有一个链表为空时没有判断
    如果l1===null 应该直接返回 l2 无需关新 l2 是否为空

  • 边界判断
    如果是 [5],[5] 这样的两个链表求和时，没有在while中判断carry是否为有值，不应该直接跳出循环。

  • 边界判断
    如果是 [1],[999] 这样的两个链表求和时,即使[1].next===null, 也需要每次循环判断是否需要进位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

var addTwoNumbers = function (l1, l2) {
    // 判断边界条件
    if (l1 === null) return l2;
    if (l2 === null) return l1;
    var head = {
        next: null
    }
    var cur = head;
    var sum = 0;
    var carry = 0;
    //有进位是需要继续处理
    while (l1 !== null || l2 !== null || carry) {
        if (l1 && l2) {
            sum = (l1.sum + l2.sum + carry) % 10;
            carry = (l1.sum + l2.sum + carry) / 10 | 0;
            l1 = l1.next;
            l2 = l2.next;
        } else {
            if (!l1 && !l2) {
                sum = carry;
                carry = 0;
            }
            // 处理[999]+[1] 的情况，即使另一个链表为空，也需要注意是否回合当链表的值，产生进位的情况
            if (l1 && !l2) {
                sum = (l1.sum + carry) % 10;
                //位运算取强制转换位整数 等同于Math.floor()
                carry = (l1.sum + carry) / 10 | 0;
                l1 = l1.next;
            }
            if (!l1 && l2) {
                sum = (l2.sum + carry) % 10;
                carry = (l2.sum + carry) / 10 | 0;
                l2 = l2.next;
            }
        }
        cur.next = {
            sum: sum,
            next: null
        }
        cur = cur.next;
    }
    return head.next
};

优化算法

  • 清除重复计算,有大量重复的求和与求进位的运算

    1
    2
    sum = (l2.sum + carry) % 10;
    carry = (l2.sum + carry) / 10 | 0;

  • 相似的条件语句，我们分别判断 l1 && !l2 和 !l1 && l2 等情况，其实只需要关心，是否l1 !== null || l2 !== null, 如果其中一个链表先位null，它的值可以用0来代替，从而避免大量重复计算

  • 经过上面一条的优化，边界条件carry,只需要在循环结束时判断一次即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var addTwoNumbers = function (l1, l2) {
    var head = {
            next: null
        },
        cur = head,
        carry = 0;
    while (l1 !== null || l2 !== null) {
        var x = l1 !== null ? l1.val : 0,
            y = l2 !== null ? l2.val : 0,
            sum = x + y + carry;
        carry = sum / 10 | 0;
        cur.next = {
            val: sum % 10,
            next: null
        }
        cur = cur.next;
        l1 = l1 !== null ? l1.next : l1
        l2 = l2 !== null ? l2.next : l2
    }
    if (carry > 0) {
        cur.next = {
            val: carry,
            next: null
        }
    }
    return head.next
};

复杂度分析

  • 时间复杂度： ，假设 和 分别表示 和 的长度，上面的算法最多重复 次。

  • 空间复杂度：。使用的额外空间复杂度为常数。

28. 实现 strStr()

算法 / 关联题目
LeetCode

描述：

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

说明：

+

1
2
输入: haystack = "hello", needle = "ll"
输出: 2

+

1
2
输入: haystack = "aaaaa", needle = "bba"
输出: -1

  • 当 needle 是空字符串时我们应当返回 0，这与C语言的 strstr() 以及 Java，javascript的 indexOf() 定义相符。

1.双指针

  • 首先，只有子串的第一个字符跟 needle 字符串第一个字符相同的时候才需要比较。

  • 其次，可以一个字符一个字符比较，一旦不匹配了就立刻终止。

  • 注意在遇到不匹配位时，重置指针的位置

  • 返回字串的开始位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    var strStr = function (haystack, needle) {
    if (needle == '') return 0;
    var i = 0,
        j = 0,
        haystackLength = haystack.length,
        needleLength = needle.length;
    while (i !== haystack.length) {
        // 剩余长度不足字串长度跳出
        if (haystackLength - i < needleLength) return -1;
        while (haystack[j + i] === needle[j]) {
            j++
            if (j === needleLength) {
                return i;
            }
        }
        //不满足时重置索引
        j = 0;
        i++;
    }
    return -1
};

复杂度分析

  • 时间复杂度：最坏时间复杂度 ，最好

  • 空间复杂度：

27. 移除元素

算法 / 关联题目
LeetCode

描述：

  • 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
  • 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
  • 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

注意:

  • 在 原地 删除重复出现的元素，表示必须在原数组上操作

  • 方法返回的是一个长度，表示过滤后的个数，但并不代表是过滤后的数组长度。

    1
    2
    3
    4
    5
    6
    7
    8
    //给定 nums = [0,1,2,2,3,0,4,2], val = 2,

    //函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

    //注意这五个元素可为任意顺序。

    //你不需要考虑数组中超出新长度后面的元素。

  • 为什么返回数值是整数，但输出的答案是数组呢?
    输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

    1
    2
    3
    4
    5
    6
    7
    8
    // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
    int len = removeDuplicates(nums);

    // 在函数里修改输入数组对于调用者是可见的。
    // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
    for (int i = 0; i < len; i++) {
        print(nums[i]);
    }

1.暴力解法 逐个删除

1
2
3
4
5
6
7
8
9
10
11
12
var removeElement = function (nums, val) {
    var i = 0,
        len = nums.length;
    for (; i < len; i++) {
        if (nums[i] === val) {
            nums.splice(i, 1)
            len--;
            i--;
        }
    }
    return len;
};

2. 双指针

  • 当 nums[j]与给定的值相等时，递增 j以跳过该元素。只要 nums[j]!==val,就复制 nums[j]到 nums[i]并同时递增两个索引。重复这一过程，直到 j到达数组的末尾，该数组的新长度为 i。

  • 此解法和(26)删除排序数组中的重复项相似

1
2
3
4
5
6
7
8
9
10
11
12
var removeElement = function (nums, val) {
    var i = 0,
        j = 0,
        len = nums.length;
    for (; j < len; j++) {
        if (nums[j] !== val) {
            nums[i] = nums[j];
            i++
        }
    }
    return i;
};

复杂度分析

  • 时间复杂度：，假设数组总共有 个元素， 和 最多遍历 次。

  • 空间复杂度：

3. 双指针 交换位置

  • 考虑数组包含很少的要删除的元素的情况。例如，，，，，,。之前的算法会对前四个元素做不必要的复制操作。似乎没有必要将 ，，，这几个元素左移一步，因为问题描述中提到元素的顺序可以更改。
1
2
3
4
5
6
7
8
9
10
11
12
13
var removeElement = function (nums, val) {
    var i = 0,
        j = nums.length;
    while (i < j) {
        if (nums[i] === val) {
            nums[i] = nums[j - 1];
            j--;
        } else {
            i++
        }
    }
    return i;
};

复杂度分析

  • 时间复杂度：

  • 空间复杂度：

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

算法 / 关联题目
LeetCode

描述：

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

注意

  • 在 原地 删除重复出现的元素，表示必须在原数组上操作
  • 方法返回的是一个长度，表示过滤后的个数，但并不代表是过滤后的数组长度。
  • 1
    2
    3
    4
    5
    //给定 nums = [0,0,1,1,1,2,2,3,3,4],

    //函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

    //你不需要考虑数组中超出新长度后面的元素。
  • 为什么返回数值是整数，但输出的答案是数组呢?
    输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
    1
    2
    3
    4
    5
    6
    7
    8
    // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
    int len = removeDuplicates(nums);

    // 在函数里修改输入数组对于调用者是可见的。
    // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
    for (int i = 0; i < len; i++) {
        print(nums[i]);
    }
    所以，这就是为什么返回的是一个长度，判别结果是一个数组的原因。
    下面这中写法由于没有修改原数组所以错误：
    1
    2
    3
    var removeDuplicates = function (nums) {
        return nums.filter((num, index) => index === nums.indexOf(num)).length;
    };

1.暴力解法逐个删除

  • 正向逐位依次和下一位比较，如果相等把当前位删除，因为必须在原数组上操作，所以是使用splice方法。
  • 因为使用 splice 方法对元素组删除，所以正向比较时需要注意数组的长度，如果删除了数组项，数组长度需要减1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 var removeDuplicates = function (nums) {
    var len = nums.length-1,
    i=0;
    for (; i <len; i++) {
        if (nums[i] === nums[i + 1]) {
            nums.splice(i, 1);
            // 因为splice改变了数组的长度，所以数组长度需要减1
            len--;
            // 在删除了数组项之后，下次还需要在当前为比较
            i--
        }
    }
    return nums.length;
};
  • 根据上面注释可以换一种写法
1
2
3
4
5
6
7
8
9
10
11
12
13
var removeDuplicates = function (nums) {
    var len = nums.length-1,
    i=0;
    for (; i <len;) {
        if (nums[i] === nums[i + 1]) {
            nums.splice(i, 1);
            len--;
        }else{
            i++
        }
    }
    return nums.length;
};
  • 因为正向遍历需要考虑删除数组项对长度的影响，所以考虑反向遍历。
1
2
3
4
5
6
7
8
9
var removeDuplicates = function (nums) {
    var i = nums.length - 1;
    for (; i > 0; i--) {
        if (nums[i] === nums[i - 1]) {
            nums.splice(i, 1)
        }
    }
    return nums.length;
};

2.双指针

  • 注意到最终结果的生成方式，是用返回的数组长度（length）遍历原数组，所以原数组不需要完全是过滤后的结果，只需要前length项是过滤后的结果即可。
  • 使用 i , j 两个指针，i指针表示过滤后的数组索引，j表示遍历时的索引
  • 如果 nums[i]!==nums[j], j指针向后移动，继续遍历，如果nums[i]===nums[j], i之后向后移动，并且要把nums[j]赋值给nums[i+1];
1
2
3
4
5
6
7
8
9
10
11
12
13
var removeDuplicates = function (nums) {
    var i = 0,
        j = 1,
        len = nums.length;
    for (; j < len; j++) {
        if (nums[i] !== nums[j]) {
            i++;
            nums[i] = nums[j]
        }
    }
    // 因为i是索引，最后要返回长度所以+1
    return i + 1;
};

21.合并两个有序链表

算法 / 关联题目
LeetCode

1.暴力解题迭代

需要的数据结构

  • 返回结果为合并后的链表，所以需要一个链表保存合并后的结果，prehead={next:null}
  • 在链表合并的时候需要知道在什么位置插入节点，所以需要一个指针 prev={} 指向当前插入位置的节点
  • 最后需要l1,l2两个合并的链表

注意

  • 链表可能为空即: l1=null

思路

  • 需要一个占位节点，即：prehead={val:-1,next:null}, l1,l2,prev=prehead,都指向数据中的第一个节点

  • 比较l1,l2当前节点的值，把prehead.next指向值小的节点，同时把prehead = prehead.next,l2 = l2.next的指针移动到下一个节点，用于下一次比较

  • 依次比较直到链表l1.next===null, l2.next===null

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var mergeTwoLists = function (l1, l2) {
    var prehead = {
        next: null
    };
    var prev = prehead
    while (l1 || l2) {
        if (l1 && l2) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                prev = prev.next;
                l1 = l1.next;
            } else {
                prev.next = l2;
                prev = prev.next;
                l2 = l2.next;
            }
        }
        if (!l1 && l2) {
            prev.next = l2;
            prev = prev.next;
            l2 = l2.next;
        }
        if (!l2 && l1) {
            prev.next = l1;
            prev = prev.next;
            l1 = l1.next;
        }
    }
    return prehead.next;
};

2.优化迭代

  • 在比较的过程中，l1,l2中最多有一个会先为空。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var mergeTwoLists = function (l1, l2) {
    var prehead = {
        next: null
    };
    var prev = prehead
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            prev.next = l1;
            l1 = l1.next;
        } else {
            prev.next = l2;
            l2 = l2.next;
        }
        prev = prev.next;

    }
    prev = prev.next;

    prev.next = l1 ? l1 : l2;
    return prehead.next;
};

复杂度分析

  • 时间复杂度：, 和 分别为两个链表的长度。因为每次循环迭代中， 和 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 。

空间复杂度： 。我们只需要常数的空间存放若干变量。

3.算法思维 递归解法

识别结构，为什么可以使用递归？

因为题目是求的合并，假如的第一个节点小于的第一个节点，问题可以转化为,即list1.next 和 list2 的合并，其结果为list[0].next

  • 如果 L1 或者 L2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。
  • 判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。
  • 如果两个链表有一个为空，递归结束。
1
2
3
4
5
6
7
8
9
10
11
var mergeTwoLists = function (l1, l2) {
    if (l1 === null) return l2;
    if (l2 === null) return l1;
    if (l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

复杂度分析

  • 时间复杂度：O(n + m)，其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 O(n+m)。

  • 空间复杂度：O(n + m)，其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次，因此空间复杂度为 O(n+m)。

20. 有效的括号

算法 / 关联题目
LeetCode

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 注意空字符串可被认为是有效字符串。
1
2
输入: "()"
输出: true
1
2
输入: "(]"
输出: false

1.使用栈

判断括号的有效性可以使用「栈」这一数据结构来解决。

我们对给定的字符串 s 进行遍历，当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此我们可以将这个左括号放入栈顶。

当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串 s 无效，返回 False。为了快速判断括号的类型，我们可以使用哈希映射（HashMap）存储每一种括号。哈希映射的键为右括号，值为相同类型的左括号。

在遍历结束后，如果栈中没有左括号，说明我们将字符串 s 中的所有左括号闭合，返回 True，否则返回 False。

注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 False，省去后续的遍历判断过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    var map = {
    "(": ")",
    "[": "]",
    "{": "}",
}
var isValid = function (s) {
    var stack = [],
        i = 0,
        length = s.length;
    if (length % 2 === 1) return false;
    for (; i < length; i++) {
        if (map[stack[0]] !== s[i]) {
            stack.unshift(s[i])
        } else {
            stack.shift();
        }
    }
    console.log(stack)
    return !stack.length
};

复杂度分析

  • 时间复杂度：，其中 是字符串 的长度。

  • 空间复杂度：，其中 表示字符集，本题中字符串只包含 6 种括号，。栈中的字符数量为 ，而哈希映射使用的空间为 ，相加即可得到总空间复杂度。

14.最长公共前缀

算法 / 关联题目
LeetCode

需要注意的坑

  • 公共的意思是数组中所有项公共的部分，["aa",'aabb','aabbcc'],最长公共前缀是aa,而不是aabb,因为并不是每一项都包含aabb

  • 最长公共前缀而不是最长公共子串，["xbbcc","xaabbcc","xbbccdd"],最长公共前缀是x,最长公共子串 bbcc

  • 在输入的数组长度为0时返回空字符串

1.纵向扫描

纵向扫描是最容易想到的方法步骤为：

  • 依次遍历每一个数组，检查同一列上的字符是否相同
  • 如果相同记录并累加字符串结果，遍历下一列
  • 如果不同跳出循环，返回结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var longestCommonPrefix = function (strs) {
    if (!strs.length) return '';
    var result = '', //记录公共前缀结果
        i = 0, //表示字符串索引，从第一位开始检查
        j = 1, // 输入数组的索引
        str = strs[0]; //输入数组中的第一个
    for (i = 0; i < str.length; i++) {
        for (j = 1; j < strs.length; j++) {
            if (strs[j][i] !== str[i]) return result;
        }
        result += str[i]
    }
    return result;
}

复杂度分析

  • 时间复杂度：，其中 是字符串数组中的字符串的平均长度， 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。

  • 空间复杂度：。使用的额外空间复杂度为常数。

2.横向扫描

  • 依次遍历字符串数组中的每个字符串，把前两个公共前缀的结果和输入数组中的下一个进行比较，数组遍历完成后即得到结果
  • 如果在尚未遍历完所有的字符串时，最长公共前缀已经是空串，则最长公共前缀一定是空串，因此不需要继续遍历剩下的字符串，直接返回空串即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var longestCommonPrefix = function (strs) {
    if (!strs.length) return '';
    var i = 0,
        len = strs.length - 1,
        result = strs[0];
    for (; i < len; i++) {
        var temp = prefixCompare(result, strs[i + 1]);
        if(!temp) return temp;
        result = temp;
    }
    return result;
}
// 找出两个字符串的最大公共前缀
function prefixCompare(first, second) {
    var i = 0, //索引
        len = first.length;
    for (; i < len; i++) {
        if (first[i] !== second[i]) return first.substring(0, i);
    }
    return first;
}

复杂度分析

  • 时间复杂度：O(mn)，其中 mm 是字符串数组中的字符串的平均长度，nn 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。

  • 空间复杂度：O(1)。使用的额外空间复杂度为常数。

3.分治

注意到 的计算满足结合律，有以下结论：

其中是字符串的最长公共前缀，

基于上述结论，可以使用分治法得到字符串数组中的最长公共前缀。对于问题 可以分解成两个子问题,与,其中。对两个子问题分别求解，然后对两个子问题的解计算最长公共前缀，即为原问题的解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var longestCommonPrefix = function (strs) {
    if (!strs.length) return '';
    if (strs.length < 2) return strs[0];
    var mid = Math.floor(strs.length / 2),
        left = strs.slice(0, mid),
        right = strs.slice(mid);
    return prefixCompare(longestCommonPrefix(left), longestCommonPrefix(right))
}

// 找出两个字符串的最大公共前缀
function prefixCompare(first, second) {
    var i = 0, //索引
        len = first.length;
    for (; i < len; i++) {
        if (first[i] !== second[i]) return first.substring(0, i);
    }
    return first;
}

复杂度分析

  • 时间复杂度：O(mn)，其中 mm 是字符串数组中的字符串的平均长度，nn 是字符串的数量。

  • 空间复杂度：，其中 mm 是字符串数组中的字符串的平均长度，nn 是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为 ，每层需要 m 的空间存储返回结果。

4.二分法

显然，最长公共前缀的长度不会超过字符串数组中的最短字符串的长度。用 minLength 表示字符串数组中的最短字符串的长度，则可以在 [0,minLength] 的范围内通过二分查找得到最长公共前缀的长度。每次取查找范围的中间值 mid，判断每个字符串的长度为 mid 的前缀是否相同，如果相同则最长公共前缀的长度一定大于或等于 mid，如果不相同则最长公共前缀的长度一定小于 mid，通过上述方式将查找范围缩小一半，直到得到最长公共前缀的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var longestCommonPrefix = function (strs) {
    if (!strs.length) return '';
    var minlength = Math.min.apply(null, strs.map(item => item.length)),
        low = 0,
        high = minlength;
    while (low < high) {
        var mid = ~~((high - low + 1) / 2 + low);
        if (prefixCompare(strs, mid)) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    return strs[0].substring(0, low);
}

function prefixCompare(strs, mid) {
    var str0 = strs[0].substring(0, mid);
    var count = strs.length;
    for (var i = 1; i < count; i++) {
        var str = strs[i];
        for (var j = 0; j < mid; j++) {
            if (str0[j] != str[j]) {
                return false;
            }
        }
    }
    return true;
}

复杂度分析

  • 时间复杂度：，其中 mm 是字符串数组中的字符串的最小长度，nn 是字符串的数量。二分查找的迭代执行次数是 ，每次迭代最多需要比较 个字符，因此总时间复杂度是 .

  • 空间复杂度：。使用的额外空间复杂度为常数。

  • Copyrights © 2015-2025 SunZhiqi

此时无声胜有声！

支付宝
微信