算法贪心算法
hiriki分发饼干
leetcode题目链接
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int count = 0;
for(int i = 0,j = 0;i < s.length && j < g.length;i++){
if(s[i]>=g[j]){
count++;
j++;
}
}
return count;
}
}
|
摆动序列
leetcode题目链接
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int wiggleMaxLength(int[] nums) {
if(nums.length<=1){
return nums.length;
}
int prediff = 0;
int curdiff = 0;
int result = 1;
for(int i = 0;i<nums.length-1;i++){
curdiff = nums[i+1]-nums[i];
if(prediff>=0&&curdiff<0||prediff<=0&&curdiff>0){
result++;
prediff = curdiff;
}
}
return result;
}
}
|
最大子数组和
leetcode题目链接
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int maxSubArray(int[] nums) {
if(nums.length==1){
return nums[0];
}
int count = 0;
int result = Integer.MIN_VALUE;
for(int i = 0;i<nums.length;i++){
count += nums[i];
result = Math.max(count,result);
if(count<=0){
count=0;
}
}
return result;
}
}
|
买卖股票的最佳时机II
leetcode题目链接
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
思路草稿
题解
1
2
3
4
5
6
7
8
9
| class Solution {
public int maxProfit(int[] prices) {
int result = 0;
for(int i = 1;i<prices.length;i++){
result += Math.max(prices[i]-prices[i-1],0);
}
return result;
}
}
|
跳跃游戏
leetcode题目链接
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public boolean canJump(int[] nums) {
if(nums.length==1){
return true;
}
int size = 0;
for(int i = 0;i<=size;i++){
size = Math.max(i+nums[i],size);
if(size >= nums.length-1){
return true;
}
}
return false;
}
}
|
跳跃游戏II
leetcode题目链接
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public int jump(int[] nums) {
if(nums.length==1){
return 0;
}
int cur = 0;
int next = 0;
int step = 0;
for(int i = 0;i<nums.length;i++){
next = Math.max(i+nums[i],next);
if(next>=nums.length-1){
step++;
break;
}
if(cur==i){
step++;
cur = next;
}
}
return step;
}
}
|
K 次取反后最大化的数组和
leetcode题目链接
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
Arrays.sort(nums);
int sum = 0;
for(int i = 0;i<nums.length;i++){
if(nums[i]<0&&k>0){
nums[i]=-nums[i];
k--;
}
sum+=nums[i];
}
Arrays.sort(nums);
return sum - (k%2==0 ? 0 : 2*nums[0]);
}
}
|
加油站
leetcode题目链接
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int curSum = 0;
int totalSum = 0;
int start = 0;
for(int i = 0;i<gas.length;i++){
curSum += gas[i]-cost[i];
totalSum += gas[i]-cost[i];
if(curSum<0){
start=i+1;
curSum=0;
}
}
if(totalSum<0){
return -1;
}
return start;
}
}
|
分发糖果
leetcode题目链接
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int candy(int[] ratings) {
int[] candy = new int[ratings.length];
int result = 0;
Arrays.fill(candy,1);
for(int i = 1;i<ratings.length;i++){
if(ratings[i]>ratings[i-1]){
candy[i]=candy[i-1]+1;
}
}
for(int i = ratings.length-2;i>=0;i--){
if(ratings[i]>ratings[i+1]){
candy[i] = Math.max(candy[i+1]+1,candy[i]);
}
}
for(int i = 0;i<candy.length;i++){
result += candy[i];
}
return result;
}
}
|
柠檬水找零
leetcode题目链接
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0,ten = 0,twenty = 0;
for(int bill:bills){
if(bill==5){
five++;
}
if(bill==10){
if(five>0){
five--;
ten++;
} else {
return false;
}
}
if(bill==20){
if(ten>0&&five>0){
ten--;
five--;
twenty++;
} else if(five>=3){
five-=3;
twenty++;
} else {
return false;
}
}
}
return true;
}
}
|
根据身高重建队列
leetcode题目链接
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people,(a,b)->{
if(a[0]==b[0]){
return a[1]-b[1];
}
return b[0]-a[0];
});
List<int[]> list = new ArrayList<>();
for(int[] p : people){
list.add(p[1],p);
}
return list.toArray(new int[people.length][]);
}
}
|
用最少数量的箭引爆气球
leetcode题目链接
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int findMinArrowShots(int[][] points) {
if(points.length==0){
return 0;
}
int result = 1;
Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));
for(int i = 1;i<points.length;i++){
if(points[i][0]>points[i-1][1]){
result++;
} else {
points[i][1]=Math.min(points[i][1],points[i-1][1]);
}
}
return result;
}
}
|
