网站开发制作价格,广州最新防疫动态,wordpress主题栏,wordpress 还是写代码文章目录1.分发饼干1.1 题目描述1.2 解题思路1.3 C实现2.摆动序列2.1 题目描述2.2 解题思路2.3 C实现3.移掉K位数字3.1 题目描述3.2 解题思路3.3 C实现4.跳跃游戏4.1 题目描述4.2 解题思路4.3 C实现5.跳跃游戏 II5.1 题目描述5.2 解题思路5.3 C实现6.用最少数量的箭引爆气球6.1…
文章目录1.分发饼干1.1 题目描述1.2 解题思路1.3 C实现2.摆动序列2.1 题目描述2.2 解题思路2.3 C实现3.移掉K位数字3.1 题目描述3.2 解题思路3.3 C实现4.跳跃游戏4.1 题目描述4.2 解题思路4.3 C实现5.跳跃游戏 II5.1 题目描述5.2 解题思路5.3 C实现6.用最少数量的箭引爆气球6.1 题目描述6.2 解题思路6.3 C实现7.最优加油方法7.1 题目描述7.2 解题思路7.3 C实现1.分发饼干
1.1 题目描述 假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。 对每个孩子 i都有一个胃口值 g[i]这是能让孩子们满足胃口的饼干的最小尺寸并且每块饼干 j都有一个尺寸 s[j] 。如果 s[j] g[i]我们可以将这个饼干 j 分配给孩子 i 这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子并输出这个最大数值。 题目来源于力扣455
1.2 解题思路 1.3 C实现
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int child0;int cookie0;while((childg.size())(cookies.size())){if(g[child]s[cookie]){child;}cookie;}return child;}
};2.摆动序列
2.1 题目描述 如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为摆动序列。第一个差如果存在的话可能是正数或负数。少于两个元素的序列也是摆动序列。 例如 [1,7,4,9,2,5] 是一个摆动序列因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列第一个序列是因为它的前两个差值都是正数第二个序列是因为它的最后一个差值为零。 给定一个整数序列返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些也可以不删除元素来获得子序列剩下的元素保持其原始顺序。 2.2 解题思路 2.3 C实现
class Solution {
public:int wiggleMaxLength(vectorint nums) {if(nums.size()2){return nums.size();}static const int BEGIN0;static const int UP1;static const int DOWN2;int STATEBEGIN;int max_length1;for(int i1;inums.size();i){switch(STATE){case BEGIN:if(nums[i]nums[i-1]){STATEUP;max_length;}else if(nums[i]nums[i-1]){STATEDOWN;max_length;}break;case UP:if(nums[i]nums[i-1]){STATEDOWN;max_length;}break;case DOWN:if(nums[i]nums[i-1]){STATEUP;max_length;}break;} }return max_length;}
};3.移掉K位数字
3.1 题目描述 给定一个以字符串表示的非负整数 num移除这个数中的 k 位数字使得剩下的数字最小。 num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 3.2 解题思路 3.3 C实现
class Solution {
public:string removeKdigits(string num, int k) {vectorint S;string result;for(int i0;inum.length();i){int numbernum[i]-0;while(S.size()!0S[S.size()-1]numberk0){S.pop_back();k--;}if(S.size()!0||number!0){S.push_back(number);}}while(S.size()!0k0){S.pop_back();k--;}for(int i0;iS.size();i){result.append(1,0S[i]);}if(result){return 0;}return result;}
};4.跳跃游戏
4.1 题目描述 给定一个非负整数数组 nums 你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 4.2 解题思路 4.3 C实现
class Solution {
public:bool canJump(vectorint nums) {vectorint index;for(int i0;inums.size();i){index.push_back(inums[i]);}int max_indexindex[0];int jump0;while(jumpindex.size()jumpmax_index){if(max_indexindex[jump]){max_indexindex[jump];}jump;}if(jumpnums.size()){return true;}return false;}
};5.跳跃游戏 II
5.1 题目描述 给定一个非负整数数组你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 5.2 解题思路 5.3 C实现
class Solution {
public:int jump(vectorint nums) {if(nums.size()2){return 0;}int current_max_indexnums[0];int pre_max_max_indexnums[0];int jump1;for(int i0;inums.size();i){if(icurrent_max_index){jump;current_max_indexpre_max_max_index;}if(pre_max_max_indexnums[i]i){pre_max_max_indexnums[i]i;}}return jump;}
};6.用最少数量的箭引爆气球
6.1 题目描述 在二维空间中有许多球形的气球。对于每个气球提供的输入是水平方向上气球直径的开始和结束坐标。由于它是水平的所以纵坐标并不重要因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。 一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭若有一个气球的直径的开始和结束坐标为 xstartxend 且满足 xstart ≤ x ≤ xend则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后可以无限地前进。我们想找到使得所有气球全部被引爆所需的弓箭的最小数量。 给你一个数组 points 其中 points [i] [xstart,xend] 返回引爆所有气球所必须射出的最小弓箭数。 6.2 解题思路 6.3 C实现
class Solution {
public:int findMinArrowShots(vectorvectorint points) {if(points.size()0){return 0;}sort(points.begin(),points.end());int shoot_num1;int shoot_beginpoints[0][0];int shoot_endpoints[0][1];for(int i1;ipoints.size();i){if(shoot_endpoints[i][0]){shoot_beginpoints[i][0];if(shoot_endpoints[i][1]){shoot_endpoints[i][1];}}else{shoot_num;shoot_beginpoints[i][0];shoot_endpoints[i][1];}}return shoot_num;}
};7.最优加油方法
7.1 题目描述 7.2 解题思路 7.3 C实现
#include iostream
#includevector
#includequeue
#includealgorithm
using namespace std;bool cmp(pairint, int a, pairint, int b) {return a.first b.first;
}int get_min_stop(int L, int P, vector pairint, int stop)
{priority_queueint Q;int result 0;stop.push_back(make_pair(0, 0));sort(stop.begin(), stop.end(), cmp);for (int i 0; i stop.size(); i) {int dis L - stop[i].first;while (dis P !Q.empty()) {P P Q.top();Q.pop();result;}if (Q.empty() dis P) {return -1;}P P - dis;L stop[i].first;Q.push(stop[i].second);}return result;
}
int main()
{vectorpairint,int stop;int L, P;L 25;P 10;stop.push_back(make_pair(4, 4));stop.push_back(make_pair(5, 2));stop.push_back(make_pair(11, 5));stop.push_back(make_pair(15, 10));cout 加油次数 get_min_stop(L, P, stop) endl;return 0;
}
