134. 加油站
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int len = gas.length;
// for(int i = 0; i < len; i++){
// gas[i] -= cost[i];
// }
int sum = 0;
int res = -1;
for(int i = 0; i < len;){
int curr = 0;
res = i;
while(i < len && curr >= 0){
curr += gas[i];
curr -= cost[i];
i++;
}
sum += curr;
}
return sum >= 0 ? res : -1;
}
}
1005. K 次取反后最大化的数组和
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
int[] arr = new int[201];
int sum = 0;
for(int n : nums){
arr[n+100]++;
sum += n;
}
for(int i = 0; i < 100 && k > 0; i++){
if(arr[i] != 0){
int min = Math.min(arr[i],k);
k -= min;
// i - 100 100 - i
arr[200-i] += min;
sum += (200-2*i)*min;
}
}
if(k % 2 != 0){
for(int i = 100; i <= 200; i++){
if(arr[i] != 0){
sum -= (i-100)*2;
return sum;
}
}
}
return sum;
}
}
406. 根据身高重建队列
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, new Comparator
@Override
public int compare(int[] o1, int[] o2) {
if(o1[0] == o2[0]){
return o1[1] - o2[1];
}
return o2[0] - o1[0];
}
});
List
for (int[] person : people) {
list.add(person[1],person);
}
return list.toArray(new int[list.size()][]);
}
}
452. 用最少数量的箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, new Comparator
public int compare(int[] point1, int[] point2) {
if (point1[1] > point2[1]) {
return 1;
} else if (point1[1] < point2[1]) {
return -1;
} else {
return 0;
}
}
});
int len = points.length;
boolean[] pass = new boolean[len];
int i = 0;
int res = 0;
while(i < len){
int left = points[i][0],right = points[i][1];
pass[i] = true;
int j = i+1;
while(j < len && left <= right && points[j][0] <= right){
if(pass[j]){
j++;
continue;
}
left = Math.max(left,points[j][0]);
right = Math.min(right,points[j][1]);
pass[j] = true;
j++;
}
while(i < len && pass[i]){
i++;
}
res++;
}
return res;
}
}
860. 柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
class Solution {
public boolean lemonadeChange(int[] bills) {
int ten = 0, five = 0;
for(int b : bills){
if(b == 5){
five++;
}else if(b == 10){
ten++;
five--;
}else{
if(ten > 0){
ten--;
}else{
five -= 2;
}
five--;
}
if(ten < 0 || five < 0) return false;
}
return true;
}
}
56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
class Solution {
public int[][] merge(int[][] intervals) {
int len = intervals.length;
if (len == 1) return intervals;
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int[] h = new int[len];
int[] t = new int[len];
int[][] temp = new int[len][];
int index = 0;
for (int i = 0; i < len; i++) {
h[i] = intervals[i][0];
t[i] = intervals[i][1];
}
for (int i = 0; i < len; i++) {
int head = h[i];
int tail = t[i];
while (i < len-1 && h[i + 1] <= tail) {
tail = Math.max(tail, t[i + 1]);
i++;
}
temp[index++] = new int[]{head, tail};
}
int[][] res = new int[index][];
System.arraycopy(temp, 0, res, 0, index);
return res;
}
}
435. 无重叠区间
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals,(o1,o2) -> (o1[1]-o2[1]));
int sum = 1;
int end = intervals[0][1];
for(int i = 1; i < intervals.length; i++){
if(end <= intervals[i][0]){
end = intervals[i][1];
sum++;
}
}
return intervals.length - sum;
}
}
763. 划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
class Solution {
public List
char[] chs = s.toCharArray();
int[] first = new int[26];
LinkedList
list.add(0);
for(int i = 0; i < chs.length; i++){
int curr = chs[i]-'a';
if(first[curr] == 0){
first[curr] = i+1;
list.offerLast(i+1);
}else{
while(list.peekLast() >= first[curr]){
list.pollLast();
}
list.offerLast(i+1);
}
}
List
// for(int i = 0; i < list.size(); i++){
// System.out.print(list.get(i) + " ");
// }
while(list.size() > 1){
res.add(-list.pollFirst() + list.peekFirst());
}
return res;
}
}
好文推荐
发表评论