经典优秀题目
Posted by Mars . Modified at
经典的题目。
记录一些解决思路比较巧妙，具有参考价值的题目。
逃离黑洞
题目
【 逃离黑洞 】
你驾驶一艘飞船正在宇宙中遨游，宇宙可简化为一个二维平面，你所在的位置坐标是[0,0]，你想要到达的目标坐标是[a,b]。
宇宙中有若干个黑洞，它们的坐标在holes数组中给出，每一个坐标为一对正整数值，代表黑洞中心的横、纵坐标位置[x,y]，给出的黑洞中心点都位于平面内（含边界）。
假设每个黑洞的半径r都是相同的，当你的位置与黑洞中心距离l <= r时，你会被立即吸入黑洞。
求你有机会到达目标坐标的条件下，最大的黑洞半径r。
你可以在宇宙中沿着任意连续路线行驶，且位置不必在整数坐标点上。
思路
- 黑洞半径越小，通过越容易，半径越大，通过越困难。则问题的答案
r具有单调性，可以考虑使用二分查找。假设我们判断黑洞半径r是否可以通过的函数为can(r)，下面思考如何实现； - 黑洞的最小半径为
r = 0，最大半径为r = Math.min(a,b)。此外，当某一个黑洞覆盖了目标位置[a,b]时，目标位置也不再可到达，因此最大半径还需要考虑距离目标位置最近的黑洞中心点，到目标位置的距离l。r需要取a,b,l中的最小值，此时我们可以知道目标点一定不会被黑洞覆盖； - 当半径变大时，某些黑洞会相交，它们中间没有间隙，因此可以被看做是一个黑洞。这与集合的合并有关，考虑使用并查集维护；
- 因为当前位置为
[0,0]。当目标位置不可到达时，目标位置要么被黑洞与上、下边界形成的隔离带隔开，要么被黑洞与左、下边界形成的隔离带隔开； - 对于每一个黑洞半径
r，我们用并查集维护连在一起的黑洞集合，并且记录集合中黑洞的最上、下、左位置的坐标，用来判断是否与上述边界形成隔离带； - 如果连在一起的黑洞集合与左、下边界或上、下边界形成了隔离带，我们就无法通过，此时
r过大，can(r)应该返回false； - 否则，有缝隙，
can(r)应该返回true。
代码
function blackHole(a, b, holes = []) {
let l = 0,
r = Infinity;
for (let [x,y] of holes) {
r = Math.min(r, Math.floor(Math.sqrt((x-a)**2 + (y-b)**2)));
}
r = Math.min(r, a, b);
function touched(c1, c2, r) {
// 检查是否触碰
let cur = Math.sqrt((c1[0] - c2[0]) ** 2 + (c1[1] - c2[1]) ** 2);
return cur <= 2 * r;
}
function can(r) {
// judge if radius = r can pass.
let set = new UnionFind(holes);
for (let i = 0; i < holes.length - 1; i++) {
for (let j = i + 1; j < holes.length; j++) {
if (touched(holes[i], holes[j], r)) set.merge(i, j);
}
}
for (let i of set.set) {
let {
top,
left,
down
} = set.getValue(i);
if (down - r <= 0) {
if (top + r >= b || left - r <= 0) return false;
}
}
return true;
}
while (l < r) {
// 二分查找
let m = Math.ceil((l + r) / 2);
if (can(m)) l = m;
else r = m - 1;
}
return r;
}
class UnionFind {
// 并查集
constructor(holes = []) {
this.holes = holes;
let map = new Map();
let set = new Set();
for (let i = 0; i < holes.length; i++) {
map.set(i, {
parent: i,
rank: 1,
top: holes[i][1],
down: holes[i][1],
left: holes[i][0],
});
set.add(i);
}
this.map = map;
this.set = set;
}
isSame(e1, e2) {
return this.getParent(e1) === this.getParent(e2);
}
getParent(e) {
if (this.map.get(e).parent === e) return e;
let res = this.getParent(this.map.get(e).parent);
this.map.get(e).parent = res;
return res;
}
getSize() {
return this.set.size;
}
add(e) {
if (this.map.has(e)) return;
this.map.set(e, {
parent: e,
rank: 1,
});
this.set.add(e);
}
refreshValue(p, c) {
this.map.get(p).top = Math.max(this.map.get(p).top, this.holes[c][1]);
this.map.get(p).left = Math.min(this.map.get(p).left, this.holes[c][0]);
this.map.get(p).down = Math.min(this.map.get(p).down, this.holes[c][1]);
}
getValue(e) {
return this.map.get(e);
}
merge(e1, e2) {
let p1 = this.getParent(e1),
p2 = this.getParent(e2);
if (p1 === p2) return;
let r1 = this.map.get(p1).rank,
r2 = this.map.get(p2).rank;
let np = r1 >= r2 ? p1 : p2;
let nc = r1 >= r2 ? p2 : p1;
this.map.get(nc).parent = np;
// refresh the top, left, down value of new parent.
this.refreshValue(np, nc);
if (r1 === r2) this.map.get(np).rank += 1;
this.set.delete(nc);
}
}
// test
let holes = [
[5, 5],
[10, 10],
[15, 3],
];
console.log(blackHole(20, 10, holes)); // 4
所有子数组的最小值之和
题目
给定一个整数数组arr，找到min(b)的总和，其中b的范围为arr的每个子数组（连续）。
由于答案可能很大，因此 返回答案模10^9 + 7。
输入：arr = [3,1,2,4]
输出：17
解释：子数组为: [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
数据量大，需要
O(n)解法。
思路
- 暴力枚举不可行，因为复杂度为
O(n2)； - 每个子数组，都一定含有一个最小值。那么反过来思考，对于每个元素
arr[i]，都对应着若干以它作为最小值的子数组； - 可以枚举每个元素
arr[i]，找到以它作为最小值的子数组数目n，那么这个元素对于结果（最小值和）的贡献为n * arr[i]； - 问题转化为：如何确定以
arr[i]为最小值的子数组数目？如果一个子数组以arr[i]为最小值，那么在arr[i]两侧，一定有若干值>= arr[i]的元素； - 假设
arr[i]左侧有m个大于等于其值的元素，右侧有n个，那么加上arr[i]自身，它们一共形成了m * n + m + n + 1个子数组，这些子数组都是以arr[i]为最小值的； - 我们找到
arr[i]左侧第一个小于它的元素位置l，和右侧第一个小于它的元素位置r，那么用上面的计算方法就可以计算出最终结果； - 找到第一个小于自身的元素位置，标准方法是单调栈。此时还有一个很重要的注意点：如果存在相同的值的元素怎么办？
[2,2,2,2]这样的数组，岂不是中间会重复计算很多次？； - 让左、右区间一开一闭就可以了！比如在左侧寻找
<= arr[i]的第一个元素位置，而在右侧寻找< arr[i]的第一个元素位置。
代码
var sumSubarrayMins = function(arr) {
let mod = 1e9 + 7;
let res = 0;
let stk = [];
let after = arr.slice().fill(0);
let before = arr.slice().fill(0);
arr.forEach((i,idx) => {
while (stk.length && arr[stk[stk.length-1]] > i) after[stk.pop()] = idx;
stk.push(idx);
});
while (stk.length) after[stk.pop()] = arr.length;
for (let i=arr.length-1; i>=0; i--) {
while (stk.length && arr[stk[stk.length-1]] >= arr[i]) before[stk.pop()] = i;
stk.push(i);
}
while (stk.length) before[stk.pop()] = -1;
for (let i=0; i<arr.length; i++) {
let left = i - before[i] - 1;
let right = after[i] - i - 1;
res = res % mod + (arr[i] % mod) * ((1 + left + right + left * right) % mod) % mod;
}
return res;
};
最大宽度坡
题目
给定一个整数数组A，坡是元组 (i, j)，其中 i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。
找出 A 中的坡的最大宽度，如果不存在，返回 0 。
思路
- 暴力方法时间复杂度是
O(n^2)； - 观察发现：如果找到了这样一对元素
i < j满足要求，我们希望j和i相距尽可能远，也就是说对于每个j，我们希望用尽可能小的i和它匹配，这样宽度更大； - 考察
i位置元素A[i]和i之后区间的元素A[t]，如果A[t] >= A[i]，那么能与A[t]形成有效数对的元素A[j]，都能与A[i]形成有效数对，且区间[i,j]更宽。因此无需对位于i之后，且值更大的元素进行考虑； - 我们分别对
i位置的元素、j位置的元素性质进行考察：假设一对元素i < j满足要求，对于[i+1, j-1]之间的元素t，如果也满足A[t] >= A[i]，那么：- 考察元素对
(i,t)：因为t-i < j-i，宽度更小，因此对结果没有影响； - 如果
A[t] <= A[j]，考察元素对(t,j)：因为j-t < j-i，宽度更小，因此对结果没有影响； - 综上，如果存在元素
i < j满足要求，我们只需要考虑[i,j]之外的元素匹配情况，无需对[i,j]区间再作考虑。
- 考察元素对
- 基于以上结论，使用单调栈实现高效算法：
- 从前向后遍历，维护一个单调递减的单调栈，栈底元素为
A[0]； - 从后向前遍历，假设当前遍历的元素为
A[j]，栈顶元素在A中的索引为top:- 如果
A[j] >= A[top]: 则记录区间宽度j - top到结果（取最大值），并在栈中弹出top； - 如果
A[j] < A[top]，继续向前移动j，不做任何操作。
- 如果
- 从前向后遍历，维护一个单调递减的单调栈，栈底元素为
代码
var maxWidthRamp = function(nums) {
let stk = []; // 单调栈
let res = 0;
for (let i=0; i<nums.length; i++) {
if (stk.length === 0 || nums[i] < nums[stk[stk.length-1]]) stk.push(i);
}
for (let i=nums.length-1; i>=0; i--) { // 从后向前遍历，找最大宽度
while (stk.length && nums[i] >= nums[stk[stk.length-1]]) res = Math.max(res, i - stk.pop());
}
return res;
};
在二叉树中分配硬币
题目
思路
- 叶子节点如果有多余的硬币，只能向父节点转移。同理，如果叶子节点缺硬币，只能由父节点转移给它；
- 那么考察两个叶子节点的父节点，它的硬币转移情况可能有：
- 左边硬币多、右边硬币少（或者相反），那么需求可以内部消化（左手倒右手）；
- 左右硬币都多，那么左右子节点都需要向父节点转移硬币；
- 左右硬币都少，那么父节点需要向左右子节点输送硬币；
- 我们将子节点向父节点输出
n个硬币记为+n，将从父节点索取n个硬币记为-n，那么：- 左子节点向父节点输送
L(索取则L为负值)个硬币； - 右子节点向父节点输送
R(索取则R为负值)个硬币； - 父节点此时的硬币总数为
node.val + L + R； - 父节点只需要保留一个给自己，其余要向上输出（或者索取），数目为
node.val + L + R - 1。
- 左子节点向父节点输送
- 对于父节点，我们可以按子节点同样的方式递归处理，将它的硬币需求向上传递，直到根节点；
- 对于每个节点，它与左子节点交换的硬币数为
abs(L)，它与右子节点交换的硬币数为abs(R)，我们需要对每个节点将它们加和起来作为结果；
即使是左右倒右手（L和R一正一负），也是需要计入结果的。
代码
var distributeCoins = function(root) {
let res = 0;
function dfs(node = root) {
if (node === null) return 0;
let left = dfs(node.left);
let right = dfs(node.right);
res += Math.abs(left) + Math.abs(right);
return node.val - 1 + left + right;
}
dfs();
return res;
};
