贪心相关算法
给定一个数组arr，代表每个人的能力值。再给定一个非负数k，如果两个人能力差值正好为k，那么可以凑在一起比赛，一局比赛只有两个人，返回最多可以同时有多少场比赛
微信图片_20220427021521
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
| public int combinePair(int[] arr, int k) {
if (k < 0 || arr == null || arr.length < 2) {
return 0;
}
Arrays.sort(arr);
int pairNum = 0;
int L = 0;
int R = 0;
int N = arr.length;
Set<Integer> usedIndex = new HashSet<>();
while (L < N && R < N) {
if (usedIndex.contains(L)) {
L ++;
continue;
}
if (arr[R] - arr[L] > k) {
L ++;
} else if (arr[R] - arr[L] < k) {
R ++;
} else {
usedIndex.add(R);
pairNum ++;
L ++;
R ++;
}
}
return pairNum;
}
|
给定一个正数数组arr，代表若干人的体重，再给定一个正数limit，表示所有船共同拥有的载重量，每艘船最多坐两人，且不能超过载重。让所有的人同时过河，并且用最好的分配方法让船尽量少，返回最少的船
https://leetcode-cn.com/problems/boats-to-save-people/
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
34
35
36
37
38
39
40
| public int numRescueBoats(int[] people, int limit) {
if (people == null || people.length == 0) {
return 0;
}
Arrays.sort(people);
int halfLimit = limit >> 1;
int N = people.length;
int l = 0;
int r = 0;
int mid = 0;
for (int i = 0; i < N; i++) {
if (people[i] > halfLimit) {
l = i - 1;
r = i;
mid = i;
break;
}
}
if (l < 0) {
return N;
}
if (r == 0) {
return ((N + 1) >> 1);
}
int noUseNum = 0;
while (l >= 0 && r < N) {
if (people[l] + people[r] <= limit) {
l --;
r ++;
} else if (people[l] + people[r] > limit) {
l --;
noUseNum ++;
}
}
return ((l + 1 + noUseNum + 1) >> 1) + r - mid + N - r;
}
|
给定一个非负数组成的数组，长度一定大于1，想知道数组中哪两个数&的结果最大，返回这个最大结果。要求时间复杂度O(N)，额外空间复杂度O(1)
思路：贪心选择高位与运算结果为1的数字，如果正好有2个数字的高位为1，直接返回；如果小于2个，则该高位无法与出1，看下一位；如果大于2个，则看这些数的下一位哪些是1，直到第0位
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
| public int maxAndValue(int[] arr) {
int N = arr.length;
for (int i = 30; i >= 0 ; i--) {
int tmp = N;
for (int j = 0; j < N; ) {
if (((arr[j] >> i) & 1) == 0) {
swap(arr, j, --N);
} else {
j++;
}
}
if (N < 2) {
N = tmp;
}
if (N == 2) {
return arr[0] & arr[1];
}
}
return arr[0] & arr[1];
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
|
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为
摆动序列
。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列
1
2
3
4
| 输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length <= 1) {
return nums.length;
}
int curDiff = 0;
int preDiff = 0;
int count = 1;
for (int i = 1; i < nums.length; i++) {
curDiff = nums[i] - nums[i - 1];
if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
count++;
preDiff = curDiff;
}
}
return count;
}
}
|
给你一个整数数组 prices ，其中 prices[i]
表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候
最多 只能持有 一股
股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润
1
2
3
4
5
| 输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7
|
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
int diff = prices[i] - prices[i-1];
if (diff > 0) {
maxProfit += diff;
}
}
return maxProfit;
}
}
|
给定一个非负整数数组 nums ，你最初位于数组的
第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
1
2
3
| 输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标
|
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 right = 0;
for (int i = 0; i <= right; i++) {
if (nums[i] + i > right) {
right = nums[i] + i;
if (right >= nums.length - 1) {
return true;
}
}
}
return false;
}
}
|
给你一个非负整数数组 nums
，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置
1
2
3
4
| 输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int jump(int[] nums) {
int right = 0;
int step = 0;
int maxStep = Integer.MIN_VALUE;
for (int i = 0; i <= right; i++) {
if (right >= nums.length - 1) {
return step;
}
maxStep = Math.max(maxStep, nums[i] + i);
if (i == right) {
right = maxStep;
step ++;
}
}
return step;
}
}
|
在一条环路上有 n 个加油站，其中第 i
个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第
i+1 个加油站需要消耗汽油 cost[i]
升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost
，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回
-1 。如果存在解，则 保证 它是
唯一 的
1
2
| 输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
|
思路：
局部贪心：任意两个加油站能行驶一周，要求油总量减去总消耗大于等于0；每个加油站的剩余量rest[i]为gas[i]
- cost[i]。i 从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0,
i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。
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 canCompleteCircuit(int[] gas, int[] cost) {
int totalGas = 0;
int totalCost = 0;
int[] gasLeft = new int[gas.length];
for (int i = 0; i < gas.length; i++) {
totalGas += gas[i];
totalCost += cost[i];
gasLeft[i] = gas[i] - cost[i];
}
if (totalCost > totalGas) {
return -1;
}
int totalGasLeft = 0;
int start = 0;
for (int i = 0; i < gasLeft.length; i++) {
totalGasLeft += gasLeft[i];
if (totalGasLeft < 0) {
totalGasLeft = 0;
start = i + 1;
}
}
return start;
}
}
|
n 个孩子站成一排。给你一个整数数组 ratings
表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到
1 个糖果。
- 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的
最少糖果数目 。
1
2
3
| 输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
|
思路：先从左向右满足条件，再从右向左满足条件
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 candy(int[] ratings) {
int[] candyNum = new int[ratings.length];
Arrays.fill(candyNum, 1);
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i-1]) {
candyNum[i] = candyNum[i-1] + 1;
}
}
for (int i = ratings.length - 2; i >= 0 ; i--) {
if (ratings[i] > ratings[i+1] && candyNum[i] <= candyNum[i+1]) {
candyNum[i] = candyNum[i+1] + 1;
}
}
int totalCandyNum = 0;
for (int i = 0; i < candyNum.length; i++) {
totalCandyNum += candyNum[i];
}
return totalCandyNum;
}
}
|
在柠檬水摊上，每一杯柠檬水的售价为 5
美元。顾客排队购买你的产品，（按账单 bills
支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5
美元、10 美元或 20
美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付
5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第
i 位顾客付的账。如果你能给每位顾客正确找零，返回
true ，否则返回 false
1
2
| 输入：bills = [5,5,5,10,20]
输出：true
|
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
| class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0;
int ten = 0;
for (int i = 0; i < bills.length; i++) {
if (bills[i] == 5) {
five ++;
}
else if (bills[i] == 10) {
five--;
ten ++;
}
else if (bills[i] == 20) {
if (ten > 0) {
five--;
ten--;
} else {
five -= 3;
}
}
if (five < 0 || ten < 0) {
return false;
}
}
return true;
}
}
|
假设有打乱顺序的一群人站成一个队列，数组 people
表示队列中一些人的属性（不一定按顺序）。每个
people[i] = [hi, ki] 表示第 i 个人的身高为
hi ，前面 正好 有 ki
个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people
所表示的队列。返回的队列应该格式化为数组 queue ，其中
queue[j] = [hj, kj] 是队列中第 j
个人的属性（queue[0] 是排在队列前面的人）
1
2
| 输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int[][] reconstructQueue(int[][] people) {
// 先按照身高降序排序，如果身高相同，按照k升序排序
Arrays.sort(people, (o1, o2) -> {
if (o1[0] == o2[0]) {
return o1[1] - o2[1];
}
return o2[0] - o1[0];
});
// 身高从高到低，依次维护队列关系
LinkedList<int[]> que = new LinkedList<>();
for(int[] p : people) {
que.add(p[1], p);
}
return que.toArray(new int[people.length][]);
}
|
注：技巧性题目，考的可能性不大
有一些球形气球贴在一堵用 XY
平面表示的墙面上。墙面上的气球记录在整数数组 points
，其中points[i] = [xstart, xend] 表示水平直径在
xstart 和 xend之间的气球。你不知道气球的确切 y
坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直
地射出。在坐标 x
处射出一支箭，若有一个气球的直径的开始和结束坐标为
x``start，x``end， 且满足
xstart ≤ x ≤ x``end，则该气球会被 引爆
。可以射出的弓箭的数量 没有限制 。
弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的
最小 弓箭数
1
2
3
4
5
| 输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]
|
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 findMinArrowShots(int[][] points) {
Arrays.sort(points, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[1] == o2[1]) {
return 0;
}
return o1[1] > o2[1] ? 1 : -1;
}
});
int res = 1;
for (int i = 1; i < points.length; i++) {
if (points[i][0] > points[i-1][1]) {
res ++;
} else {
points[i][1] = points[i-1][1];
}
}
return res;
}
}
|
注：排序函数如下写法，会导致整型越界
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| @Test
public void integerTest() {
int[][] points = new int[][]{{1, 5}, {3, 2}, {4, Integer.MAX_VALUE}, {2, Integer.MIN_VALUE}};
Arrays.sort(points, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
System.out.println(Arrays.deepToString(points));
System.out.println(Integer.MAX_VALUE - Integer.MIN_VALUE);
}
|
给定一个区间的集合 intervals ，其中
intervals[i] = [starti, endi] 。返回
需要移除区间的最小数量，使剩余区间互不重叠
1
2
3
| 输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (o1, o2) -> {
if (o1[1] == o2[1]) {
return 0;
}
return o1[1] - o2[1] > 0 ? 1 : -1;
});
int noLapNum = 1;
int noLapIndex = 0;
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= intervals[noLapIndex][1]) {
noLapNum ++;
noLapIndex = i;
}
}
return intervals.length - noLapNum;
}
}
|
字符串 S
由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表
1
2
3
4
| 输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"
|
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
| class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> res = new ArrayList<>();
if (s == null || s.isEmpty()) {
return res;
}
char[] charArr = s.toCharArray();
int[][] charIndex = new int[26][2];
for (int i = 0; i < charArr.length; i++) {
if (charIndex[charArr[i] - 'a'][0] == 0) {
charIndex[charArr[i] - 'a'][0] = i;
}
charIndex[charArr[i] - 'a'][1] = i;
}
int start = 0;
int end = charIndex[charArr[0] - 'a'][1];
for (int i = 0; i < charArr.length; i++) {
int t = charIndex[charArr[i] - 'a'][1];
if (i == end) {
res.add(end - start + 1);
start = end + 1;
if (start < charArr.length) {
end = charIndex[charArr[start] - 'a'][1];
}
} else if (t > end) {
end = t;
}
}
return res;
}
}
|
以数组 intervals 表示若干个区间的集合，其中单个区间为
intervals[i] = [starti, endi]
。请你合并所有重叠的区间，并返回
一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间
1
2
3
| 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> res = new LinkedList<>();
Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
int start = intervals[0][0];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] > intervals[i-1][1]) {
res.add(new int[]{start, intervals[i-1][1]});
start = intervals[i][0];
} else {
intervals[i][1] = Math.max(intervals[i][1], intervals[i-1][1]);
}
}
res.add(new int[]{start, intervals[intervals.length - 1][1]});
return res.toArray(new int[res.size()][]);
}
}
|
注：先按左端点升序排序，再从左向右判断是否重合
当且仅当每个相邻位数上的数字 x 和 y 满足
x <= y
时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n
的最大数字，且数字呈 单调递增 。
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 monotoneIncreasingDigits(int n) {
String s = n + "";
int[] arr = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
arr[i] = s.charAt(i) - '0';
}
for (int i = arr.length - 1; i >= 1; i--) {
if (arr[i] >= arr[i-1]) {
continue;
}
arr[i] = 9;
arr[i-1] --;
}
int res = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[i-1]) {
arr[i] = 9;
}
res = res * 10 + arr[i];
}
return res;
}
}
|
对于
3332，先对最后两位判断是否单调递增，32改为29，整体变为3329，向左移，变为3299，继续左移，2999；对于100，先变为100，再变为090，最后将最后的0变为9