星城哈哈

# 第4章 综合算法题

# 4-1 爬楼梯-读题

问题：

来源：LeetCode (opens new window)

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例：

示例 1：

输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶

  2. 2 阶

示例 2：

输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

示例 3：

输入： 10 输出： 89

示例 4：

输入： 11 输出：144

单元测试：

//climbingStarts.test.ts

// import climbingStars from "./climbingStarts";

// test("climbingStars", () => {
//   const func = climbingStars;
//   expect(func(1)).toBe(1);
//   expect(func(2)).toBe(2);
//   expect(func(3)).toBe(3);
//   expect(func(10)).toBe(89);
//   expect(func(11)).toBe(144);
// });
1
2
3
4
5
6
7
8
9
10
11
12

# 4-2 爬楼梯-枚举解

题目：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

分析：

  1. 复习数学知识

m 中选 n 组合计算方式 (opens new window)：

C(8,3)=8*7*6/(1*2*3) = 56=8!/(3!*5!)

img

  1. 推导

假设10阶楼梯的计算方法：

image-20191229173018282

如果走2阶的步数为x，则:

  1. x 取值范围 0到 Math.floor(n/2)
  2. 走1阶到步数为 n-2x
  3. 总步数为 n-x
  4. 最终走法为 C(n-x,x)=(n-x)!/(x!*(n-2x)!)

步骤：

  1. 准备
    1. 创建文件 climbingStarsExhaustivity.ts
    2. 完成函数基本结构并导出
    3. 添加测试
  2. 实现函数
    1. 实现阶乘计算公式 factorial
    2. 计算2步最多的次数 maxTwoStep
    3. 构建从 0 到 maxTwoStep 的数组
    4. 计算每一个的可能性（走法）
    5. 针对数组的值求和 sum
    6. 返回 sum

# 4-3 爬楼梯-递归解

题目：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

分析：

假设我们的在第 x 阶楼梯上，要么是从 x-1阶楼梯上来的，要么就是从 x-2 阶楼梯上来的。

爬到n阶楼梯的方法 = 爬到 n-1 阶楼梯的方法 + 爬到 n-2 阶楼梯的方法

递归的关键在与找到递归公式和递归的终止条件：

  • 递归公式 f(n)=f(n-1)+f(n-2)

  • 递归终止条件：f(1)=1;f(2)=2;

步骤：

  1. 准备
    1. 创建文件 climbingStarsRecursive.ts
    2. 完成函数基本结构并导出
    3. 添加测试
  2. 实现函数
    1. 实现递归边界条件
    2. 现递归公式

# 4-4 爬楼梯-递归解优化

题目：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

分析：

分析递归的执行过程：

image-20191230102701995

如何解决：

缓存f(n),从而避免重复计算

计算 f(n) 之前先检查缓存

  1. 命中缓存直接返回
  2. 未命中缓存，计算，将结果写入缓存，返回

步骤：

  1. 准备
    1. 创建文件 climbingStarsRecursiveCache.ts
    2. 粘贴 climbingStarsRecursive.ts 的代码并修改函数名称
    3. 添加测试
  2. 实现函数
    1. 添加缓存 const cache = {};
    2. 添加变量 let result = n;
    3. 根据缓存的命中情况 给 result 赋值
    4. 返回 result
  3. 对比
    1. 通过 console.log 查看函数调用的次数并对比

# 4-5 爬楼梯-动态规划解

题目：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

分析：

填表

image-20191231113229056

步骤：

  1. 准备
    1. 创建文件 climbingStarsDynamicProgramming.ts
    2. 添加函数框架并导出
    3. 添加测试
  2. 实现函数
    1. 解决 n<3 的情况
    2. 声明变量 index，lastLast，last，current
    3. 实现循环 index<n 时
      1. index++
      2. lastLast = last;
      3. last = current;
      4. ​ current = last + lastLast;
    4. 返回 current

# 4-6 最大子序列和-读题

题目：

来源：LeetCode (opens new window)

给定一个整数数组 ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6

输入:[8,-2,-4,-1,-8,3,8,8,3,4,2,-9,-1,-3,-6,8,-3,9] 输出: 28 解释: 连续子数组 [3,8,8,3,4,2] 的和最大，为 28

输入:[1] 输出: 1 解释: 连续子数组 [1] 的和最大，为 1

测试用例：

import maxSubArray from "./maxSubArray";

test("maxSubArray", () => {
  const func = maxSubArray;
  expect(func([-2, 1, -3, 4, -1, 2, 1, -5, 4])).toBe(6);
  expect(
    func([8, -2, -4, -1, -8, 3, 8, 8, 3, 4, 2, -9, -1, -3, -6, 8, -3, 9])
  ).toBe(28);
  expect(func([1])).toBe(1);
});
1
2
3
4
5
6
7
8
9
10

# 4-7 最大子序列和-枚举解

题目：

给定一个整数数组 ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

分析：

把所有的子序列都列举出来，然后计算他们都和，求得最大值。详细步骤如下：

假定给定的数组长度为n。

则子数组的长度可能为 1,2,3,…,n

  • 当子数组长度为1 ，有n个值，可以找到一个最大值

  • 当子数组长度为2 ，有n-2+1个值，可以找到一个最大值

  • 当子数组长度为3 ，有n-3+1个值，可以找到一个最大值

  • ...

  • 当子数组长度为x ，有n-x+1个值，可以找到一个最大值

  • ...

  • 当子数组长度为n ，可以找到一个最大值

假设子数组长度为3，则有n-3+1 个可能的和，找出其中最大值。

image-20191231162232571

步骤：

  1. 准备
    1. 创建文件 maxSubArrayExhaustivity.ts
    2. 添加函数框架并导出
    3. 添加测试
  2. 实现函数
    1. 声明变量 count=1，max=Number.MIN_SAFE_INTEGER,len=arr.length
    2. 实现循环 count<=len 时
      1. 定义子数组开始索引 start=0；
      2. 定义子数组结束索引 end = count - 1;
      3. 计算子数组和 sum
      4. 根据 sum 的大小更新 max
      5. 迭代后移子数组 直到 end=len-1
        1. start++
        2. end++
        3. 计算 sum
        4. 更新 max
      6. count++
    3. 返回 max

# 4-8 最大子序列和-动态规划解

题目：

给定一个整数数组 ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

分析：

  • 最大子数组的最后一个元素 x 肯定是数组中的某一个元素。

  • 当每一个元素为最大子数据的最后一个数的时候，计算出其对于的最大子序列和。

    • 当数组（arr）的第 1 个元素为最大子数组的最后一个元素时，最大子数组和 currentEndMax1 即为arr[0]
    • 当数组（arr）的第 2 个元素为最大子数组的最后一个元素时，最大子数组和 currentEndMax2 即为currentEndMax1>0? currentEndMax1+ arr[1]:arr[1]
    • 当数组（arr）的第 3 个元素为最大子数组的最后一个元素时，最大子数组和 currentEndMax3 即为currentEndMax2>0? currentEndMax2+ arr[2]:arr[2]
    • ...
    • 当数组（arr）的第 x 个元素为最大子数组的最后一个元素时，最大子数组和 currentEndMaxX即为currentEndMax(x-1)>0? currentEndMax(x-1)+ arr[x-1]:arr[x-1]
    • ...
    • 当数组（arr）的第 n 个元素为最大子数组的最后一个元素时，最大子数组和 currentEndMaxN 即为currentEndMax(n-1)>0? currentEndMax(n-1)+ arr[n-1]:arr[n-1]

  • 最后 所有 currentEndMax 中最大值即为 该数组的最大子序列和。

image-20191231182630988

步骤：

  1. 准备
    1. 创建文件 maxSubArrayDynamicProgramming.ts
    2. 添加函数框架并导出
    3. 添加测试
  2. 实现函数
    1. 声明变量 max=Number.MIN_SAFE_INTEGER，currentEndMax = arr[0]，index=1
    2. 根据 currentEndMax 的大小更新 max
    3. 实现循环 index < arr.length 时
      1. 计算出新的 currentEndMax
      2. 根据 currentEndMax 的大小更新 max
      3. index++;
    4. 返回 max
上次更新: 2021/2/24 上午10:55:31

← 第5章 总结 →