贪心算法
分发饼干
思考
- 先用大饼干满足胃口大的小孩
方法一
function findContentChildren(g: number[], s: number[]): number {
g = g.sort((a, b) => a - b);
s = s.sort((a, b) => a - b);
let result = 0;
let index = s.length - 1;
for (let i = g.length - 1; i >= 0; i--) {
if (index >= 0 && s[index] >= g[i]) {
result++;
index--;
}
}
return result;
};
摆动序列
思考
方法一
function wiggleMaxLength(nums: number[]): number {
let length: number = nums.length;
if (length <= 1) return length;
let preDiff: number = 0;
let curDiff: number = 0;
let count: number = 1;
for (let i = 1; i < length; i++) {
curDiff = nums[i] - nums[i - 1];
if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {
preDiff = curDiff;
count++;
}
}
return count;
}
最大子数组和
思考
- 如果是负数就会带来负担，重启就可以了
- 记录最大值
方法一
function maxSubArray(nums: number[]): number {
let curSum: number = 0;
let resMax: number = -Infinity;
for (let i = 0; i < nums.length; i++) {
curSum += nums[i];
resMax = Math.max(curSum, resMax);
if (curSum < 0) curSum = 0;
}
return resMax;
}
买卖股票的最佳时机 II
思考
- 算出每天的利率，只挑选获利的就简化为上一题了
方法一
function maxProfit(prices: number[]): number {
let result = 0
for(let i=1;i<prices.length;i++){
result += Math.max(prices[i]-prices[i-1],0)
}
return result
};
跳跃游戏
题号55. 跳跃游戏
思考
- 每次都去最大的覆盖范围
方法一
function canJump(nums: number[]): boolean {
if (nums.length === 1) return true
let cover = 0
for (let i = 0; i <= cover; i++) {
cover = Math.max(cover, i + nums[i])
if (cover >= nums.length - 1) {
return true
}
}
return false
};
跳跃游戏 II
思考
- 要考虑下一步
方法一
function jump(nums: number[]): number {
const length: number = nums.length;
let curFarthestIndex: number = 0,
nextFarthestIndex: number = 0;
let curIndex: number = 0;
let stepNum: number = 0;
while (curIndex < length - 1) {
nextFarthestIndex = Math.max(nextFarthestIndex, curIndex + nums[curIndex]);
if (curIndex === curFarthestIndex) {
curFarthestIndex = nextFarthestIndex;
stepNum++;
}
curIndex++;
}
return stepNum;
}
K 次取反后最大化的数组和
思考
- 按绝对值排序
- 如果还有k，先把负数变为正的
- 如果有多余的k，就反复翻转绝对值最小的元素
方法一
function largestSumAfterKNegations(nums: number[], k: number): number {
nums.sort((a,b) => Math.abs(b) - Math.abs(a))
for(let i = 0 ;i < nums.length; i++){
if(nums[i] < 0 && k > 0){
nums[i] = - nums[i];
k--;
}
}
// 若k还大于0,则寻找最小的数进行不断取反
while( k > 0 ){
nums[nums.length-1] = - nums[nums.length-1]
k--;
}
// 使用箭头函数的隐式返回值时，需使用简写省略花括号，否则要在 a + b 前加上 return
return nums.reduce((a, b) => a + b)
};
加油站
题号134. 加油站
思考
- 使用暴力法，遍历存在的所有可能
- 贪心算法
方法一 暴力法
// 暴力法
function canCompleteCircuit(gas: number[], cost: number[]): number {
for(let i=0;i<cost.length;i++){
let rest = gas[i]-cost[i] //记录剩余油量
// 以i为起点行驶一圈，index为下一个目的地
let index = (i+1)%cost.length
while(rest>0&& index!==i){
rest+=gas[index] - cost[index]
index = (index+1)%cost.length
}
if(rest>=0&&index===i)return i
}
return -1
};
方法二 贪心算法
function canCompleteCircuit(gas: number[], cost: number[]): number {
let total: number = 0; // 记录总的剩余油量
let curGas: number = 0; // 记录当前剩余油量
let tempDiff: number = 0; // 记录当前加油站的油量和花费之差
let resIndex: number = 0; // 记录起始加油站的索引
for (let i = 0, length = gas.length; i < length; i++) {
tempDiff = gas[i] - cost[i];
total += tempDiff; // 累计总的剩余油量
curGas += tempDiff; // 更新当前剩余油量
if (curGas < 0) {
resIndex = i + 1; // 如果当前剩余油量为负数，将下一个加油站作为新的起始站
curGas = 0; // 重置当前剩余油量
}
}
if (total < 0) return -1; // 如果总的剩余油量小于0，无法环绕一圈，返回-1
return resIndex; // 返回起始加油站的索引
};
分发糖果
思考
两次贪心来做
先保证右边高分孩子一定比左边低分孩子发更多的糖果
再保证左边高分孩子一定比右边低分孩子发更多的糖果
方法一 贪心算法
function candy(ratings: number[]): number {
const candies: number[] = [];
candies[0] = 1;
// 保证右边高分孩子一定比左边低分孩子发更多的糖果
for (let i = 1, length = ratings.length; i < length; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
} else {
candies[i] = 1;
}
}
// 保证左边高分孩子一定比右边低分孩子发更多的糖果
for (let i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
return candies.reduce((pre, cur) => pre + cur);
};
柠檬水找零
思考
- 情况一：账单是5，直接收下。
- 情况二：账单是10，消耗一个5，增加一个10
- 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5
方法一
function lemonadeChange(bills: number[]): boolean {
let fiveCount = 0,
tenCount = 0
for (let i = 0; i < bills.length; i++) {
let bill = bills[i]
if (bill === 5) {
fiveCount++
} else if (bill === 10) {
if (fiveCount > 0) {
fiveCount--
tenCount++
} else {
return false
}
}else {
if(tenCount>0&&fiveCount>0){
tenCount--
fiveCount--
}else if(fiveCount>=3){
fiveCount-=3
}else{
return false
}
}
}
return true
};
根据身高重建队列
思考
- 先根据身高插入
- 再按照前面比该元素高的排序
方法一
function reconstructQueue(people: number[][]): number[][] {
let queue = []
people.sort((a, b) => {
if (b[0] !== a[0]) {
return b[0] - a[0] // 如果不相等按h从高到低排
} else {
return a[1] - b[1]
}
})
for (let i = 0; i < people.length; i++) {
queue.splice(people[i][1], 0, people[i])
}
return queue
};
用最少的箭引爆气球
思考
- 先按照左边界排序
- 如果左边界大于上一个元素的右边界result++
- 如果不大于就融合两个元素的右边界
方法一
function findMinArrowShots(points: number[][]): number {
points.sort((a, b) => {
return a[0] - b[0] // 按照左边界进行排序
})
let result = 1
for (let i = 1; i < points.length; i++) {
if (points[i][0] > points[i - 1][1]) {
result++
} else {
points[i][1] = Math.min(points[i - 1][1], points[i][1])
}
}
return result
};
无重叠区间
思考
- 和上题射箭有点像，count其实就是重叠区间
方法一
function eraseOverlapIntervals(intervals: number[][]): number {
// 按照左边界升序排列
if(intervals.length)
intervals.sort((a, b) => a[0] - b[0])
let count = 0
for(let i = 1; i < intervals.length; i++ ){
if(intervals[i][0] < intervals[i-1][1]) {
count++
intervals[i][1] = Math.min(intervals[i-1][1],intervals[i][1])
}
}
return count
};
划分字母区间
思考
- 统计每一个字符最后出现的位置
- 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
方法一
function partitionLabels(s: string): number[] {
let hash = {}
for(let i = 0; i < s.length; i++) {
hash[s[i]] = i
} //记录字符最远
let result = []
let left = 0
let right = 0
for(let i = 0; i < s.length; i++) {
right = Math.max(right, hash[s[i]]) // 更新字符的最远出现下标
if(right === i) {
result.push(right - left + 1) //如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
left = i + 1
}
}
return result
};
合并区间
题号56. 合并区间
思考
- 还是判断重复区间的那个概念
方法一
function merge(intervals: number[][]): number[][] {
let result = []
if(intervals.length===0)return result // 区间为空直接返回
intervals.sort((a,b)=>a[0]-b[0]) // 按左区间排序
result.push(intervals[0]) // 放入第一个元素
for(let i=1;i<intervals.length;i++){
if(result[result.length-1][1]>=intervals[i][0]){ //如果上一个元素的右区间大于当前元素的左区间
// 合并区间
result[result.length-1][1] = Math.max(result[result.length-1][1],intervals[i][1])
}else{
result.push(intervals[i])
}
}
return result
};
单调递增的数字
题号
思考
- 从后往前遍历，如果当前的数字比后面的数字要大就减一
- 记录位置，之后让这个位置后面的数都为9
方法一
function monotoneIncreasingDigits(n: number): number {
let strArr = String(n).split('').map(i=>parseInt(i)) //字符串转数组
const length = strArr.length
let flag = length
for(let i=length-2;i>=0;i--){ //从后往前遍历
if(strArr[i]>strArr[i+1]){
strArr[i] -=1
flag=i+1 //flag标签就是判断之后哪里要变为9的
}
}
for(let i=flag;i<length;i++){
strArr[i]=9
}
return parseInt(strArr.join(''));
};
监控二叉树
思考
- 首先要了解再叶节点的父节点装是最省的
- 然后就是有三种情况，状态转移
方法一
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function minCameraCover(root: TreeNode | null): number {
/** 0-无覆盖， 1-有摄像头， 2-有覆盖 */
type statusCode = 0 | 1 | 2;
let resCount: number = 0;
if (recur(root) === 0) resCount++;
return resCount;
function recur(node: TreeNode | null): statusCode {
if (node === null) return 2; // 空节点返回有覆盖
const left: statusCode = recur(node.left),
right: statusCode = recur(node.right);
let resStatus: statusCode = 0;
if (left === 0 || right === 0) { //如果左右节点都是无覆盖装一个摄像头
resStatus = 1;
resCount++;
} else if (left === 1 || right === 1) { // 都是有摄像头该节点是有覆盖的
resStatus = 2;
} else { // 其他都是无覆盖
resStatus = 0;
}
return resStatus;
}
};