局部最优:当气球重叠时,一起射,所用弓箭最少。
对数组排序,如果气球重叠了,重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。
var findMinArrowShots = function(points) {
points.sort((a, b) => a[0] - b[0]);
let ans = 1;
for(let i = 1; i < points.length; i++) {
if(points[i][0] > points[i - 1][1]) {
ans++;
}else{
points[i][1] = Math.min(points[i][1], points[i - 1][1]);
}
}
return ans;
};
总结:感觉这道题,虽然有了点思路,但不知道从何下手。发现代码其实很简洁,当points[i]
与points[i - 1]
无交集时,弓箭数直接加一,否则更新points[i]右端点的值。
思路:知道这道题要排序,但不清楚具体应该怎么排序,排完序之后进行什么操作?
以下解法采用,按照右边界排序,从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
局部最优:按右边界排序后,优先选右边界小的区间,所以从左向右遍历,留给下一个区间的空间大一些,从而尽量避免交叉。全局最优:选取最多的非交叉区间。
重点:直接求重叠区间,是很复杂的。把问题转换成求最大非重复区间个数,求个数时,用分割点做标记。
按右边界排序
var eraseOverlapIntervals = function(intervals) {
// 按右边界排序
intervals.sort((a, b) => a[1] - b[1]);
let ans = 1;
let end = intervals[0][1];
for(let i = 1; i < intervals.length; i++) {
if(intervals[i][0] >= end) {
end = intervals[i][1];
ans += 1;
}
}
return intervals.length - ans;
};
按左边界排序
var eraseOverlapIntervals = function(intervals) {
// 按照左边界升序排列
intervals.sort((a, b) => a[0] - b[0])
let count = 1
let end = intervals[intervals.length - 1][0]
// 倒序遍历,对单个区间来说,左边界越大越好,因为给前面区间的空间越大
for(let i = intervals.length - 2; i >= 0; i--) {
if(intervals[i][1] <= end) {
count++
end = intervals[i][0]
}
}
// count 记录的是最大非重复区间的个数
return intervals.length - count
}
思路:
var partitionLabels = function(s) {
let hash = {};
// 统计每个字符出现的最远位置
for(let i = 0; i < s.length; i++) {
hash[s[i]] = i;
}
let ans = [];
let l = 0, r = 0;
for(let i = 0; i < s.length; i++) {
r = Math.max(r, hash[s[i]]);
if(r === i) {
ans.push(r - l + 1);
l = i + 1;
}
}
return ans;
};
重点:新建一个数组,然后不断更新这个数组中区间段的右端点。
var merge = function(intervals) {
// 按区间的左端点排序
intervals.sort((a,b)=>a[0]-b[0]);
const ans=[];
for(let i=0;i<intervals.length;i++){
let l=intervals[i][0],r=intervals[i][1];
// 区间段中的区间左端点大于ans中右端点
if(ans.length==0||l>ans[ans.length-1][1]){
ans.push([l,r]);
}else{
// 更新ans中右端点的值
ans[ans.length-1][1]=Math.max(ans[ans.length-1][1],r);
}
}
return ans;
};
思路:遇到strNum[i - 1]
> strNum[i]
时,让strNum[i - 1]--
,strNum[i]
为9。
重点:要从后向前遍历,因为如果从前向后遍历,strNum[i - 1]--
后可能会小于strNum[i - 2]
。此外,还需要一个flag
标记从哪里开始赋值为9的,然后需要把flag
之后位的都赋值为9。
var monotoneIncreasingDigits = function(n) {
n = n.toString();
// 转成数组
n = n.split('').map(item => {
return +item;
})
let flag = Infinity;
for(let i = n.length - 1; i > 0; i--) {
if(n[i - 1] > n[i]) {
flag = i;
n[i - 1]--;
}
}
for(let i = flag; i < n.length; i++) {
n[i] = 9;
}
return n.join('');
};
var maxProfit = function(prices, fee) {
let ans = 0;
let minPrice = prices[0];
for(let i = 0; i < prices.length; i++) {
if(prices[i] < minPrice) {
minPrice = prices[i];
}
if(prices[i] >= minPrice && prices[i] <= minPrice + fee) continue;
if(prices[i] > minPrice + fee) {
ans += prices[i] - minPrice -fee;
minPrice = prices[i] - fee; // 买入和卖出只需要支付一次手续费
}
}
return ans;
};
动态规划
重点:从下往上看,局部最优:让叶子节点的父节点安摄像头,所用摄像头最少,整体最优:全部摄像头数量所用最少!
0:该节点无覆盖
1:本节点有摄像头
2:本节点有覆盖
var minCameraCover = function(root) {
let ans = 0;
function traversal(cur) {
if(cur === null) return 2;
let l = traversal(cur.left);
let r = traversal(cur.right);
if(l === 2 && r === 2) return 0;
if(l === 0 || r === 0) {
ans++;
return 1;
}
if(l === 1 || r === 1) return 2;
return -1;
}
if(traversal(root) === 0) ans++;
return ans;
};