Tip: After the article is written, the table of contents can be automatically generated. For how to generate it, please refer to the help document on the right.
Article directory
-
- 445
- 376
- 53
- 122. The best time to buy and sell stocks
- 45.
-
- Problems encountered: The termination condition should be placed first, otherwise you will encounter problems at the nums.length-1 step which happens to be currDistance.
- 1005. Flip k times and find the maximum sum of the sequence
- 134. Gas station
-
- Problems encountered:
- 135. Hand out candy
- 860. Lemonade change
- 406.Reconstruct queue based on height
- interval problem
-
- 452. Detonate a balloon with the minimum number of arrows
- 435. No overlapping intervals
- 763. Divide letter intervals
- 56. Merge intervals
445
376
53
122. The best time to buy and sell stocks
It is very similar to the swing sequence. Just add peaks and troughs and pay attention to specific conditions. Forgot to add length<2 in the first pass
class Solution {<!-- -->
public int maxProfit(int[] prices) {<!-- -->
int count =0;
if(prices.length<2){<!-- -->
return count;
}
List<Integer> nums = new ArrayList<>();
if(prices[1]-prices[0]>=0){<!-- -->
nums.add(prices[0]);
}
for(int i=2; i<prices.length;i + + ){<!-- -->
if(nums.size()%2==1){<!-- -->
if(prices[i]-prices[i-1]<0){<!-- -->
nums.add(prices[i-1]);
}
}
if(nums.size()%2==0){<!-- -->
if(prices[i]-prices[i-1]>0){<!-- -->
nums.add(prices[i-1]);
}
}
}
if(nums.size()%2==1){<!-- -->
nums.add(prices[prices.length-1]);
}
for(int j=1; j<nums.size();j=j + 2){<!-- -->
count + =nums.get(j)-nums.get(j-1);
}
return count;
}
}
But actually the answer is simpler, just add up all the positive profits.
// Greedy idea
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;
}
}
45.
When taking a step, calculate the farthest point you can go next. For this question, you only need to consider the range.
Problems encountered: The termination condition should be placed first, otherwise you will encounter problems at the nums.length-1 step of currDistance
class Solution {<!-- -->
public int jump(int[] nums) {<!-- -->
int currDistance=0;
int count =0;
int maxDistance=0;
if(nums.length==1 || nums.length==0){<!-- -->
return 0;
}
for(int i=0;i<nums.length;i + + ){<!-- -->
maxDistance=Math.max(maxDistance,i + nums[i]);
if(maxDistance>=nums.length-1){<!-- -->
count + + ;
break;
}
if(i==currDistance){<!-- -->
count + + ;
currDistance=maxDistance;
}
}
return count;
}
}
1005. Flip k times and find the maximum sum of the sequence
Sort first and turn the negative number with the largest absolute value into an integer. If k is not enough (the negative number is not completely flipped), sum is returned directly. If k is enough, we will discuss whether there are odd or even numbers left in k. If it is an even number, it has no effect; if it is an odd number, it is reordered and the minimum value becomes a negative number for summation:
class Solution {<!-- -->
public int largestSumAfterKNegations(int[] nums, int k) {<!-- -->
Arrays.sort(nums);
int sum=0;
for(int i=0; i<nums.length;i + + ){<!-- -->
if(k>0 & amp; & amp; nums[i]<0){<!-- -->
nums[i]=-nums[i];
k--;
}
sum + =nums[i];
}
Arrays.sort(nums);
return sum-(k%2==0? 0:2*nums[0]);
}
}
134. Gas station
Note that if there is a path (starting from x, going to y, but cannot reach the next stop of y through y), then starting from any station on this path cannot reach the next stop of y. Therefore, we perform branch reduction operation, i=i + count + 1, where count is the number of stations that can be reached by this station. Through this operation, we directly reset the starting point to the unreachable station.
class Solution {<!-- -->
public int canCompleteCircuit(int[] gas, int[] cost) {<!-- -->
int n = gas.length;
int i = 0;
while (i < n) {<!-- -->
int sumOfGas = 0, sumOfCost = 0;
int cnt = 0;
while (cnt < n) {<!-- -->
int j = (i + cnt) % n;
sumOfGas + = gas[j];
sumOfCost + = cost[j];
if (sumOfCost > sumOfGas) {<!-- -->
break;
}
cnt + + ;
}
if (cnt == n) {<!-- -->
return i;
} else {<!-- -->
i =i + cnt + 1;
}
}
return -1;
}
}
Problems encountered:
Pay attention to the increment of the current site j, which is completed by taking the remainder of the sum of i and the arriving site, where count is incremented (count + +)
135. Distribute candy
Don’t consider both sides at the same time; In the first pass of preorder traversal, consider whether the ratings on the right side are higher than those on the left side. If it is higher, add the number of candies in front + 1. If it is not higher, just give 1; In the second post-order traversal, consider whether the ratings on the left side are higher than those on the right side. If so, compare the existing candies on the left and the existing number of candies on the right + 1, which one is greater, and take the larger value;
class Solution {<!-- -->
public int candy(int[] ratings) {<!-- -->
int length = ratings.length;
int[] candyVec = new int[length];
candyVec[0]=1;
int sum=0;
for(int i =0; i<length-1;i + + ){<!-- -->
candyVec[i + 1]=(ratings[i + 1]>ratings[i])? candyVec[i] + 1:1;
}
for(int i=length-2;i>=0;i--){<!-- -->
if(ratings[i]>ratings[i + 1]){<!-- -->
candyVec[i]=Math.max(candyVec[i],candyVec[i + 1] + 1);
}
}
for(int num:candyVec){<!-- -->
sum + =num;
}
return sum;
}
}
860. Lemonade change
Pay attention to adding judgment logic. When there is more than 5 yuan, first use 5 yuan to find change of 20.
class Solution {<!-- -->
public boolean lemonadeChange(int[] bills) {<!-- -->
int[] res = new int[3];
for(int num:bills){<!-- -->
if(num==5){<!-- -->
res[0] + + ;
}else if(num==10){<!-- -->
res[0]--;
res[1] + + ;
if(res[0]<0){<!-- -->
return false;
}
}else{<!-- -->
if(res[0]>res[1] & amp; & amp; res[0]>=3){<!-- -->
res[0]=res[0]-3;
}else{<!-- -->
res[0]--;
res[1]--;
res[2] + + ;
}
if(res[0]<0||res[1]<0){<!-- -->
return false;
}
}
}
return true;
}
}
406. Reconstruct the queue based on height
Pay attention to the implementation method of Arrays.sort(); Sorting first with more vacancies (person[1]) will have no effect on sorting those with fewer vacancies.
class Solution {<!-- -->
public int[][] reconstructQueue(int[][] people) {<!-- -->
Arrays.sort(people, new Comparator<int[]>(){<!-- -->
public int compare(int []person1, int[] person2){<!-- -->
if(person1[0]!=person2[0]){<!-- -->
return person1[0]-person2[0];
}else{<!-- -->
return person2[1]-person1[1];
}
}
});
int n=people.length;
int[][] ans= new int[n][];
for(int[] person: people){<!-- -->
int space = person[1];
for(int i=0; i<n;i + + ){<!-- -->
if(ans[i]==null){<!-- -->
if(space==0){<!-- -->
ans[i]=person;
break;
}
space--;
}
}
}
return ans;
}
}
Interval problem
452. Detonate the balloon with the minimum number of arrows
Pay attention to updating the right border
class Solution {<!-- -->
public int findMinArrowShots(int[][] points) {<!-- -->
// Sort according to the starting coordinates of the balloon diameter from small to large
// Use Integer built-in comparison method without overflow
Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
int count = 1; // if points are not empty, at least one arrow is required
for (int i = 1; i < points.length; i + + ) {<!-- -->
if (points[i][0] > points[i - 1][1]) {<!-- --> // Balloon i and balloon i-1 are not next to each other. Note that this is not >=
count + + ; // need an arrow
} else {<!-- --> // Balloon i and balloon i-1 are next to each other
points[i][1] = Math.min(points[i][1], points[i - 1][1]); // Update the minimum right boundary of the overlapping balloon
}
}
return count;
}
}
435. No overlapping intervals
Similar to archery Note that you need to use Math.min to obtain the smallest bounded
class Solution {<!-- -->
public int eraseOverlapIntervals(int[][] intervals) {<!-- -->
Arrays.sort(intervals,(a,b)->{<!-- -->
return Integer.compare(a[0],b[0]);
});
int count=1;
for(int i=1;i<intervals.length;i + + ){<!-- -->
if(intervals[i][0]<intervals[i-1][1]){<!-- -->
intervals[i][1]=Math.min(intervals[i][1], intervals[i-1][1]);
}else{<!-- -->
count + + ;
}
}
return intervals.length-count;
}
}
763. Divide letter intervals
Introduce idx as the farthest position of the current letter, starting from the next position and ending at the farthest position of this letter; If the new farthest position exceeds the current farthest position, the farthest position is updated.
class Solution {<!-- -->
public List<Integer> partitionLabels(String S) {<!-- -->
List<Integer> list = new LinkedList<>();
int[] edge = new int[26];
char[] chars = S.toCharArray();
for (int i = 0; i < chars.length; i + + ) {<!-- -->
edge[chars[i] - 'a'] = i;
}
int idx = 0;
int last = -1;
for (int i = 0; i < chars.length; i + + ) {<!-- -->
idx = Math.max(idx,edge[chars[i] - 'a']);
if (i == idx) {<!-- -->
list.add(i - last);
last = i;
}
}
return list;
}
}
56. Merge interval
class Solution {<!-- -->
public int[][] merge(int[][] intervals) {<!-- -->
if(intervals.length==0){<!-- -->
return new int[1][2];//[0][2] or [1][2]
}
Arrays.sort(intervals,new Comparator<int[]>(){<!-- -->
public int compare(int[] interval1, int[] interval2){<!-- -->
return interval1[0]-interval2[0];
}
});
List<int[]> merged = new ArrayList<int[]>();
for(int i=0;i<intervals.length;i + + ){<!-- -->
int L=intervals[i][0];
int R=intervals[i][1];
if(merged.size()==0 || L>merged.get(merged.size()-1)[1]){<!-- -->
merged.add(new int[]{<!-- -->L,R});
}else{<!-- -->
merged.get(merged.size()-1)[1]=Math.max(merged.get(merged.size()-1)[1],R);
}
}
return merged.toArray(new int[merged.size()][]);//Two-dimensional arrays can also be converted using toArray
}
}