1.困于环中的机器人
题目：
在无限的平面上，机器人最初位于 (0, 0) 处，面朝北方。机器人可以接受下列三条指令之一：
"G"：直走 1 个单位"L"：左转 90 度"R"：右转 90 度
机器人按顺序执行指令 instructions，并一直重复它们。
只有在平面中存在环使得机器人永远无法离开时，返回 true。否则，返回 false。
思路：明确一点：如果执行完一轮指令之后，方向不是朝北，或者回到原点，那么都会成环。
回到原点不多说。方向不是朝北呢？其实就是，如果方向不是朝北，那么后续的路径是绕着原点中心对称的。所以肯定成环
所以执行完一轮命令之后判断方向和位置即可
时间复杂度O(n)，空间复杂度O(1)
/**
* @param {string} instructions
* @return {boolean}
*/
var isRobotBounded = function(instructions) {
let dir = 0;
const position = [0, 0];
const vmap = {
0: 1,
1: 1,
2: -1,
3: -1,
};
const dmap = {
0: 1,
1: 0,
2: 1,
3: 0,
};
for (const s of instructions) {
if (s === "G") {
position[dmap[dir]] += vmap[dir];
} else if (s === "L") {
dir = (dir - 1 + 4) % 4;
} else {
dir = (dir + 1) % 4;
}
}
if (position[0] === 0 && position[1] === 0) return true;
if (dir === 0) return false;
return true;
};2.分隔数组以得到最大和
题目：
给你一个整数数组 arr，请你将该数组分隔为长度最多为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。
返回将数组分隔变换后能够得到的元素最大和。
注意，原数组和分隔后的数组对应顺序应当一致，也就是说，你只能选择分隔数组的位置而不能调整数组中的顺序。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-array-for-maximum-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：动态规划。假设dp[i]表示前i个数字对应的最大和。
那么，将该组数字分成两部分：1-k的右半部分和左半部分，假设右半部分长度为j，那么有：
dp[i] = max (dp[i], dp[i - j] + max(arr[i]-arr[i-j]) * j)
即，枚举右半部分的所有可能(1-k)的长度枚举一遍，就能计算出dp[i]的最大值
时间复杂度O(nk)，空间复杂度O9n0
/**
* @param {number[]} arr
* @param {number} k
* @return {number}
*/
var maxSumAfterPartitioning = function(arr, k) {
const l = arr.length;
const dp = new Array(l + 1).fill(0);
for (let i = 1; i <= l; i++) {
let max = 0;
for (let j = i - 1; i - j <= k && j >= 0; j--) {
max = Math.max(max, arr[j]);
dp[i] = Math.max(dp[i], dp[j] + (i - j) * max);
}
}
return dp[l];
};3.最长字符串链
题目：
给出一个单词列表，其中每个单词都由小写英文字母组成。
如果我们可以在 word1 的任何地方添加一个字母使其变成 word2，那么我们认为 word1 是 word2 的前身。例如，"abc" 是 "abac" 的前身。
词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word_1 是 word_2 的前身，word_2 是 word_3 的前身，依此类推。
从给定单词列表 words 中选择单词组成词链，返回词链的最长可能长度。
思路：这个类似最长上升子序列，不过有一点区别。
因为某个字符串是另一个字符串的前身的话，那么长度肯定比它小1.
所以先字符串按照长度进行分组，然后从长度为1开始的字符串，依次记录每个字符串对应的下一个字符串(存在一对多，所以用数组记录)。
那么从前往后开始，用一个数组记录每个字符串的最大深度，也就是词链的最大长度。
时间复杂度O(n),空间复杂度O(n)
/**
* @param {string[]} words
* @return {number}
*/
const isS = (s1, s2) => {
const l = s2.length;
for (let i = 0; i < l; i++) {
if (s2.slice(0, i) + s2.slice(i + 1) === s1) return true;
}
return false;
};
var longestStrChain = function (words) {
const l = words.length;
const deep = words.slice().fill(1);
const nextS = words.slice();
const dp = new Array(17).fill("").map(() => []);
for (let i = 0; i < l; i++) {
dp[words[i].length].push(i);
}
for (let i = 1; i < 16; i++) {
const next = dp[i + 1];
const current = dp[i];
for (const cur of current) {
const nextIndex = next.filter((item) => isS(words[cur], words[item]));
nextS[cur] = nextIndex;
}
}
for (let i = 1; i < 16; i++) {
dp[i].forEach((item) => {
const next = nextS[item];
next.forEach((n) => {
deep[n] = Math.max(deep[n], deep[item] + 1);
});
});
}
return Math.max(...deep);
};4.最后一块石头的重量
题目：
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎； - 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
思路：这题可以转换为背包问题。一万年两块石头粉碎后，剩余质量是它们的差。所以其实就是对石头分组，并尽可能平均分配。所以是在重量限制为最大重量的一半时，最大重量是多少，
时间复杂度O(mn)，空间复杂度O(n)，m是石头的总重量
/**
* @param {number[]} stones
* @return {number}
*/
var lastStoneWeightII = function(stones) {
const l = stones.length;
const sum = stones.reduce((a, b) => a + b, 0);
const max = ~~(sum / 2);
const dp = new Array(max + 1).fill(0);
for (let i = 1; i <= l; i++) {
for (let j = max; j >= 0; j--) {
if (stones[i - 1] > j) {
continue;
} else {
dp[j] = Math.max(dp[j], stones[i - 1] + dp[j - stones[i - 1]]);
}
}
}
return sum - 2 * dp[max];
};5.爱生气的书店老板
题目：
今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。
请你返回这一天营业下来，最多有多少客户能够感到满意的数量。
思路：滑动窗口。在长度为k的范围内，将老板生气时的客户数量记录下来，并计算最大值，就是最多能挽回的客户数量
时间复杂度O(n)，空间复杂度O(1)
/**
* @param {number[]} customers
* @param {number[]} grumpy
* @param {number} X
* @return {number}
*/
var maxSatisfied = function(customers, grumpy, X) {
let c = 0;
let l = customers.length;
for (let i = 0; i < l; i++) {
if (!grumpy[i]) {
c += customers[i];
}
}
let cur = 0;
for (let i = 0; i < X; i++) {
if (grumpy[i]) {
cur += customers[i];
}
}
let max = cur;
for (let i = X; i < l; i++) {
if (grumpy[i - X]) {
cur -= customers[i - X];
}
if (grumpy[i]) {
cur += customers[i];
}
max = Math.max(max, cur);
}
return c + max;
};