分成子问题，局部最优——>整体最优 每一步都是尽可能满足
与动态规划区别：贪心不回退，动态规划可以回退综合找到最优
找零问题
https://juejin.im/post/5b0a8e0f51882538b2592963
给定4中面额 1分 2分 5分 6分 ，找零11分零钱。怎样做到硬币数量总数最少
if(i == 0){T[i][j] = j/coins[i]; //硬币找零一定要有个 最小面额1，否则会无解}else{if(j >= coins[i]){T[i][j] = min(T[i-1][j],1+T[i][j-coins[i]])}else{T[i][j] = T[i-1][j];}}
代码实现：
//动态规划 -- 硬币找零问题
function minCoins(coins,total,n){
var T = [];
for(let i = 0;i<n;i++){
T[i] = []
for (let j=0;j<= total;j++){
if(j == 0){
T[i][j] = 0;
continue;
}
if(i == 0){
T[i][j] = j/coins[i]; //硬币找零一定要有个 最小面额1，否则会无解
}else{
if(j >= coins[i]){
T[i][j] = Math.min(T[i-1][j],1+T[i][j-coins[i]])
}else{
T[i][j] = T[i-1][j];
}
}
}
}
findValue(coins,total,n,T);
return T;
}
function findValue(coins,total,n,T){
var i = n-1, j = total;
while(i>0 && j >0){
if(T[i][j]!=T[i-1][j]){
//锁定位置,确定i,j值，开始找构成结果的硬币组合。 其实根据这种计算方法，只需要考虑最右边那一列，从下往上推。
//console.log(T[i][j]);
break
}else{
i--;
}
}
var s = []; //存储组合结果
while(i >= 0 && j > 0 ){
s.push(coins[i]);
j=j-coins[i];
if(j <= 0){
break; //计算结束，退出循环
}
//如果 i == 0,那么就在第 0 行一直循环计算，直到 j=0即可
if(i>0){
//console.log(i);
while(T[i][j] == T[i-1][j]){
i--;
if(i== 0){
break;
}
}
}
}
console.log(s);
//可以把数组s return 回去
}
var coins = [1,2,5,6];
var total = 11
var n = coins.length
console.log(minCoins(coins,total,n));
455. 分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
注意：
你可以假设胃口值为正。
一个小朋友最多只能拥有一块饼干。
示例 1:
输入: [1,2,3], [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: [1,2], [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
/**
* @param {number[]} g
* @param {number[]} s
* @return {number}
*/
//排序，分别遍历需求数组g和饼干数组s
var findContentChildren = function(g, s) {
g.sort((a,b)=> a-b);
s.sort((a,b)=> a-b);
let child = 0;
let cookie =0;//记录饼干位置
while(child<g.length && cookie<s.length){
if(g[child] <= s[cookie]){ //可以满足当前孩子
child ++;
}
cookie ++;
}
return child;
};
376. 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例 1:
输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列。
示例 2:
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:
输入: [1,2,3,4,5,6,7,8,9]
输出: 2
/**
* @param {number[]} nums
* @return {number}
*/
//序列不一定要连续紧挨着的位置
var wiggleMaxLength = function(nums) {
if(nums.length<2){
return nums.length;
}
let BEGIN =0,UP=1,DOWN=2;
let state=BEGIN;
let maxLength=1;
//从第二个开始扫描
for(var i=1;i<nums.length;i++){
switch(state){
case BEGIN:
if(nums[i-1]<nums[i]){
state = UP;
maxLength ++;
} else if(nums[i-1]>nums[i]){
state=DOWN;
maxLength ++;
}
break;
case UP:
if(nums[i-1]>nums[i]){
state = DOWN;
maxLength ++;
}
break;
case DOWN:
if(nums[i-1]<nums[i]){
state = UP;
maxLength ++;
}
break;
}
}
return maxLength;
};
402. 移掉K位数字
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 示例 1 :
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :
输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :
输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。
/**
* @param {string} num
* @param {number} k
* @return {string}
*/
//使用栈来优化，存储结果，每次都选择最小的元素
// 1432219 . k=3
// i=0 1 2 3 4 5 6
// s=1 14 13 12 122 121 1219
// 栈顶4>3 3>2 栈顶遍历到栈顶
var removeKdigits = function(num, k) {
var s = [];
var res = '';
for(var i=0;i<num.length;i++){
var number=num[i]-0; //字符串转成数字
console.log('numner',number)
//栈为空或者不能再删除元素k=0或者当前元素小于当前元素
while(s[s.length-1] > number && k>0 && s.length != 0){
s.pop();//弹出栈顶元素；
k--;
}
//num = 100200, k = 1 时
if(number !=0 || s.length !=0){
s.push(number)
}
}
//如果栈不为空 且仍然可以删除数字 num=1234 k=3
while(s.length !=0 && k>0){
s.pop();
k--;
}
// s= [1,2,1,9]
for(var i=0;i<s.length;i++){
res=res+s[i];
}
if(res == ''){
return '0'
}
return res;
};
55. 跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
/**
* @param {number[]} nums
* @return {boolean}
*/
// 位置 i [0,1,2,3,4]
//最远跳越 nums [2,3,1,1,4]
//最远到达的位置index [2,4,3,4,8]
//从位置i跳到 i+1,i+2.......j-1,j中可以跳到最远的位置，即index[i],index[i+1]...中最大的那个
var canJump = function(nums) {
var index = [];//最远达到的位置
for(var i=0;i<nums.length;i++){
index.push(i+nums[i]);
}
var jump = 0;
var max_index = index[0];//代表从第0位置至第jump位置这个过程中，最远可到达的位置，初始化为index[0]。
//jump大于index长度 或者 jump超越了当前最远可以到达的位置,跳出
while(jump<index.length && jump<= max_index){
if(max_index<index[jump]){
max_index = index[jump];//如果可以跳的更远，更新max_index
}
jump ++;
}
//若等于index长度 返回true
if(jump == index.length){
return true
}
return false
};
452. 用最少数量的箭引爆气球
输入:
[[10,16], [2,8], [1,6], [7,12]]
输出:
2
解释:
对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。
/**
* @param {number[][]} points
* @return {number}
*/
var findMinArrowShots = function(points) {
if(points.length == 0){
return 0
}
points.sort((a,b)=> a[0]-b[0])
console.log(points)
var shoot_num = 1;
var shoot_begin = points[0][0];
var shoot_end = points[0][1];
for(var i=0;i<points.length;i++){
if(shoot_end >= points[i][0]){
shoot_begin = points[i][0];
if(shoot_end >points[i][1]){
shoot_end = points[i][1];
}
} else {
shoot_num ++;
shoot_begin = points[i][0];
shoot_end = points[i][1];
}
}
return shoot_num;
};
若有收获，就点个赞吧
0 人点赞
