打家劫舍、零钱兑换和跳跃游戏

打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

示例

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

方法一 用迭代的方式遍历计算

思路

由于不可以在相邻的房屋闯入,所以在当前位置 n 房屋可盗窃的最大值,要么就是 n-1 房屋可盗窃的最大值,要么就是 n-2 房屋可盗窃的最大值加上当前房屋的值,二者之间取最大值 动态规划方程:dp[n] = MAX( dp[n-1], dp[n-2] + num )

详解

  1. 获取房间的个数,如果为 0,就直接返回 0,

  2. 如果为 1,就直接返回数组第一个值,

  3. 设置三个变量 sumTemp 临时求和值,sumBefore n-2 总和,sumAfter n-1 总和

  4. 初始化 3 个变量的值,

  5. 循环 len-2 次求动态规划的值 nums[i] 为当前房间值

const rob = function (nums) {
const len = nums.length;
if (len === 0) return 0;
if (len === 1) {
return nums[0];
}
if (len === 2) {
return Math.max(nums[0], nums[1]);
}
let sumTemp = 0;
let sumBefore = nums[0];
let sumAfter = Math.max(nums[0], nums[1]);
let i = 2;
while (i < len) {
sumTemp = Math.max(sumAfter, sumBefore + nums[i]);
sumBefore = sumAfter;
sumAfter = sumTemp;
i++;
}
return sumAfter;
};

复杂度分析:

  • 时间复杂度:O(n)O(n)

    只需要单循环 nn 长度的数组 O(n2)O(n-2),故时间复杂度为 O(n)O(n)

  • 空间复杂度:O(1)O(1)

方法二

思路

由于不可以在相邻的房屋闯入,所以在当前位置 n 房屋可盗窃的最大值,要么就是 n-1 房屋可盗窃的最大值,要么就是 n-2 房屋可盗窃的最大值加上当前房屋的值,二者之间取最大值 动态规划方程:dp[n] = MAX( dp[n-1], dp[n-2] + num ) 总体的思路是一样的,方法一中,数组长度为 0,1,2 中单独处理,切换设计的求和变量过多,6 个可以利用数组变量优化。

详解

  1. 获取房间的个数,如果为 0,就直接返回

  2. 设置一个 len+1 的数组变量,初始化数组中的第一个和第二个对象,这边就可以不用单独处理数组长度为 1 和 2 的情况

  3. 每次的循环求和的结果都记录在对于长度的数组对象中,不必声明多个变量暂存。

  4. 然后利用动态规划公式查找 n 个最大的数组和的值

const rob = function (nums) {
const len = nums.length;
if (len === 0) return 0;
const dp = new Array(len + 1);
dp[0] = 0;
dp[1] = nums[0];
for (let i = 2; i <= len; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return dp[len];
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    只需要单循环 nn 长度的数组 O(n2)O(n-2),故时间复杂度为 O(n)O(n)

  • 空间复杂度:O(1)O(1)

零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

示例1

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

示例2

输入: coins = [2], amount = 3
输出: -1

解法一 动态规划法

思路

  1. 由于需要找到最少的硬币,所以需要列举出所有可能的结果(如题)

  2. 要凑够 amount 元硬币,可以从最 i -> amount 之前进行枚举 (counter) (下列出 最少次数)

    amount = 1; counter[1] = 1 coins[1] = 1

    amount = 2; counter[2] = 1 coins[2] = 2

    amount = 3; counter[3] = 2 coins[1] + coins[2]

    amount = 4; counter[4] = 2 coins[2] + coins[2]

    amount = 5; counter[5] = 3 coins[2] + coins[2] + coins[1]

    amount = 6; counter[6] = 3 coins[2] + coins[2] + coins[2]

    amount = 7; counter[7] = 2 coins[5] + coins[2]

    amount = 8; counter[8] = 3 coins[5] + coins[2] + coins[1]

    amount = 9; counter[9] = 3 coins[5] + coins[2] + coins[2]

    amount = 10; counter[10] = 2 coins[5] + coins[5]

    amount = 11; counter[11] = 1 coins[5] + coins[5] + coins[1]

  3. 递增 i 并且记录下 能组合成 i 的 硬币数量 counter[i]

  4. 遍历 coins 数组,从 counter 中找到对应剩余金额(i - coins[j])的最小次数 + 1

详解

  1. 需要计算出每一步的最佳次数,因此可以将每一步的次数保存在 counter 数组中

  2. counter中每一项的最大值应该是 amount / 1 次,此处默认填充 (amount / 1) + 1 次

  3. 遍历amoount 数组 依次递增,在 coins 数组中找到满足 i 的最少硬币数,保存在 counter 中

  4. 若 counter[i] 已经保存有最少的值,比较此次计算的最小次数,取两者较小

  5. 重复 3,4 步骤 直到 amount 遍历结束

const coinChange = (coins, amount) => {
const counter = Array(amount + 1);
counter.fill(amount + 1);
counter[0] = 0;
for (let i = 1; i <= amount; i ++) {
for (let j = 0; j < coins.length; j ++) {
if (i - coins[j] >= 0) {
// i - coins[j] 能凑成 i 的上一步的 最小硬币数量
counter[i] = Math.min(counter[i], counter[i - coins[j]] + 1);
}
}
}
// 最坏结果应该是 counter[amount] = amount
return counter[amount] > amount ? -1 : counter[amount];
}

复杂度分析

  • 时间复杂度:O(Sn)O(Sn)

    时间复杂度是 O(Sn)O(Sn),S是 amount大小,需要迭代 Sn

  • 空间复杂度:O(S)O(S)

    每次迭代时没有增加新的资源,O(1)O(1)

解法二 递归

思路

由于要获取最小奖金币次数,实质上就是能拿到的满足 amount 的面值尽可能大的银币的个数。例如:

coins = [11, 12, 5, 3] amount = 121;

则次数刚好是 121 / 11 = 11,其他的取法均大于 11 次。

若 amount = 124 则有次数 (121 / 11) + (3 / 3) = 12次

另外,在考虑最多次数时,应当满足有 amount / 1 = amount 次。

详解

  1. amount 是总金额,要用最少的硬币数,应当是从最大的硬币开始拿起

  2. 大的硬币可以多次拿取,就有 amount % coins[i] === 0 成立

  3. 可以保存一个最少硬币数 mincounter 的状态,按coins数组最大的开始,依次向最小的硬币循环

  4. 按照可以使用的最大硬币次数作为循环起始条件,依次减1直至为0,递归调用

  5. 当剩余 amount / coins[n] > 当前次数 + mincounter 则直接退出循环

  6. 当amount为0时,即可得到最优结果

const coinChange = (coins, amount) => {
// 假设 最少次数 最多不会超过 amount 次
let minCount = amount + 1;
let coinsTemp = coins.sort((a, b) => b - a);
// 防止有超过 amount 面值的硬币出现
const maxValueIndex = coinsTemp.findIndex(v => v <= amount);
// 已经计算的次数,剩余的金额,coins,当前硬币位置
const calculateCountes = (count, amount, coins, index) => {
if (amount === 0) {
if (count < minCount) {
// 每次递归的所有可能结果进行保存
minCount = count;
}
return;
}
let maxCountatIndex = parseInt((amount / coins[index]), 10);
// 执行到超出数组边界 或者 预计最小次数大于已有 minCount 时 直接退出递归
if((index === coins.length) || maxCountatIndex + count >= minCount) {
return;
}
// amount 最少是 amount / coins[index] 次 coins[index] 的 和
for (let j = maxCountatIndex; j >= 0 ; j --) {
// 累计次数,剩余amount,银币数组,到达的coins数组下标
calculateCountes(count + j, amount - (coins[index] * j), coins, index + 1 );
}
}
calculateCountes(0, amount, coinsTemp, maxValueIndex);
return minCount === amount + 1 ? -1 : minCount;
}

复杂度分析

  • 时间复杂度:O(Sn)O(Sn)

  • 空间复杂度:O(n)O(n)

    nn 为递归调用的最大深度,即需要 O(n)O(n) 空间的递归堆栈。

跳跃游戏

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例1:

输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例2:

输入: [3,2,1,0,4] 输出: false 解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。

方法一 贪心算法

思路

贪心算法的思路就是每到一个位置,都跳跃到当前位置可以跳跃的最大距离。当最后跳跃的最远距离等于或大于最后一个位置的时候,我们就认为可以到达最后一个位置,返回true

详解

  1. 首先我们初始化最远位置为0,然后遍历数组;

  2. 如果当前位置能到达,并且当前位置+跳数>最远位置,就更新最远位置;

  3. 每次都去比较当前最远位置和当前数组下标,如果最远距离小于等于当前下标就返回false。

const canJump = function (nums) {
let max = 0; // 跳到最远的距离
for (let i = 0; i < nums.length - 1; i += 1) {
// 找到能跳的最远的的距离
if (i + nums[i] > max) {
max = i + nums[i];
}
// 如果跳的最远的小于当前脚标,返回false
if (max <= i) {
return false;
}
}
return true;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    只需要访问 nums 数组一遍,共 nn 个位置,nnnumsnums 数组的长度。

  • 空间复杂度:O(1)O(1)

    在 max 变量分配内存情况下,内存不会随着遍历有增长趋势,不需要额外的空间开销。

方法二 动态规划

思路

我们遍历数组,每到一个点 i,我们就去判断是否可以到达当前点;如果可以,就记录 true,否则为false,最后判断 是否可以到达(nums.length - 1);

详解

  1. 遍历数组 nums,每到一个点 i,我们就判断时刻可以到达当前点;

  2. 如果 i 之前某点 j 本身是可以到达的,并且与当前点可达,表示点 i 是可达的;

  3. 我们遍完成后,直接判断(nums.length - 1)是否可以达到。

const canJump = function (nums) {
// 定义一个数组,用来记录nums的点是否是可以达到的
const list = [nums.length];
// 遍历nums
for (let i = 1; i < nums.length; i++) {
// 遍历list
for (let j = 0; j < i; j++) {
// 如果j点是可以到达的,并且j点是可以达到i点的
// 则表示i点也是可以达到的
if (list[j] && nums[j] + j >= i) {
list[i] = true;
// 如果i点可以达到,则跳出当前循环
break;
}
}
}
return list[nums.length - 1];
};

复杂度分析

  • 时间复杂度:O(n2)O(n^2) 对于每个元素,通过两次遍历数组的其余部分来寻找它所对应的目标元素,这将耗费 O(n2)O(n^2) 的时间

  • 空间复杂度:O(n)O(n) 对于每次循环都需要给 j 重新分配空间,所以空间复杂度 O(n)O(n)

方法三 回溯

思路

我们模拟从第一个位置跳到最后位置的所有方案。从第一个位置开始,模拟所有可以跳到的位置,然后判断当前点是否可以到达(nums.length - 1);当没有办法继续跳的时候,就回溯。

详解

  1. 我们每次传入一个下标 p,并且判断 p 是否可以达到最后的下标;

  2. 如果传入的 p 等于(nums.length - 1),则表示可以到达,如果不行,则继续循环判断;

  3. 如果存在 p 等于 (nums.length - 1),则返回 true,不存在则返回 false

const canJump = function (nums) {
return checkJumpPosition(0, nums); ;
};
function checkJumpPosition (p, nums = []) {
// 定义p点可以到达的最远距离
let jump = p + nums[p];
// 如果p点可以到达nums.length - 1,则返回true
if (p === nums.length - 1) {
return true;
}
// 如果最远距离大于(nums.length - 1),我们就将(nums.length - 1),设为最远距离
if (p + nums[p] > nums.length - 1) {
jump = nums.length - 1;
}
// 我们从p + 1开始到最远距离中间,找到(nums.length - 1)
// 如果可以,则返回true,找不到则返回false
for (let i = p + 1; i <= jump; i += 1) {
if (checkJumpPosition(i, nums)) {
return true;
}
}
return false;
}

复杂度分析

  • 时间复杂度:O(2n)O(2^n) 因为从第一个位置到最后一个位置的跳跃方式最多有 2^n 种,所以最多的耗时是 O(2n)O(2^n)

  • 空间复杂度:O(n)O(n) 对于每次循环都需要给 ii 重新分配空间,最大的长度是 nums.length,所以空间复杂度 O(n)O(n)