Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.
Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
Example 1:
Input: g = [1,2,3], s = [1,1] Output: 1 Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content. You need to output 1.
Example 2:
Input: g = [1,2], s = [1,2,3] Output: 2 Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. You have 3 cookies and their sizes are big enough to gratify all of the children, You need to output 2.
classSolution { publicintfindContentChildren(int[] g, int[] s) { if(s.length==0){ return0; } Arrays.sort(g); Arrays.sort(s); int len1=g.length; int len2=s.length; int j=0; int ans=0; for(int i=0;i<len1;i++){ if(j==len2){ return ans; } while(j<len2){ if(g[i]<=s[j]++){ ans++; break; } } } return ans; } }
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.
Example 1:
Input: ratings = [1,0,2] Output: 5 Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:
Input: ratings = [1,2,2] Output: 4 Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively. The third child gets 1 candy because it satisfies the above two conditions.
Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.
Example 1:
Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.
Example 2:
Input: intervals = [[1,2],[1,2],[1,2]] Output: 2 Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.
Example 3:
Input: intervals = [[1,2],[2,3]] Output: 0 Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.
Given an integer array flowerbed containing 0‘s and 1‘s, where 0 means empty and 1 means not empty, and an integer n, return trueifnnew flowers can be planted in theflowerbedwithout violating the no-adjacent-flowers rule andfalseotherwise.
Example 1:
Input: flowerbed = [1,0,0,0,1], n = 1 Output: true
Example 2:
Input: flowerbed = [1,0,0,0,1], n = 2 Output: false
first idea
Firstly, if we want to be Greedy, it is great way that planting the
flower when left and right is zero.
Off course, we can find a problem when we coding it, we must notice the start and end of array.
Clearly, we can use a way named Defensive Programming
we can expand original array two capacity to get a new array
## [452. Minimum Number of Arrows to Burst Balloons](https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/)
There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array `points` where `points[i] = [xstart, xend]` denotes a balloon whose **horizontal diameter** stretches between `xstart` and `xend`. You do not know the exact y-coordinates of the balloons.
Arrows can be shot up **directly vertically** (in the positive y-direction) from different points along the x-axis. A balloon with `xstart` and `xend` is **burst** by an arrow shot at `x` if `xstart <= x <= xend`. There is **no limit** to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.
Given the array `points`, return *the **minimum** number of arrows that must be shot to burst all balloons*.
**Example 1:**
Input: points = [[10,16],[2,8],[1,6],[7,12]] Output: 2 Explanation: The balloons can be burst by 2 arrows:
Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].
**Example 2:**
Input: points = [[1,2],[3,4],[5,6],[7,8]] Output: 4 Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.
**Example 3:**
Input: points = [[1,2],[2,3],[3,4],[4,5]] Output: 2 Explanation: The balloons can be burst by 2 arrows:
Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].
### WTF
```Java class Solution { public int findMinArrowShots(int[][] points) { int length = points.length; if(length==0||length==1){ return 1; } int ans = 1; Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0])); int end = points[0][1]; for (int i = 1; i < points.length; i++) { if(points[i][0]>end){ ans ++; end = points[i][1]; }else if(points[i][0]<end){ end = Math.min(end,points[i][1]); } } return ans; } }
You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.
Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.
Return a list of integers representing the size of these parts.
Example 1:
Input: s = "ababcbacadefegdehijhklij" Output: [9,7,8] Explanation: The partition is "ababcbaca", "defegde", "hijhklij". This is a partition so that each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.
Example 2:
Input: s = "eccbbbbdec" Output: [10]
classSolution { public List<Integer> partitionLabels(String s) { intlength= s.length(); int []arrays = newint[26]; List<Integer> result = newArrayList<>(); for (inti=0; i < length; i++) { charc= s.charAt(i); arrays[c-'a'] = i; } intstart=0; intend=0; for (inti=0; i < length; i++) { // 一直走，谁最后落点最大就走到哪 end = Math.max(end,arrays[s.charAt(i)-'a']); if(end==i){ result.add(end-start+1); start = end+1; } } return result; } }
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Example 1:
Input: prices = [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit is 4 + 3 = 7.
Example 2:
Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Total profit is 4.
Example 3:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
classSolution { publicintmaxProfit(int[] prices) { intmax=0 ; for (inti=0; i < prices.length-1; i++) { if(prices[i+1]>prices[i]){ max += prices[i+1]-prices[i]; } } return max; } }
You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactlyki other people in front who have a height greater than or equal to hi.
Reconstruct and return the queue that is represented by the input arraypeople. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).
Example 1:
Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] Explanation: Person 0 has height 5 with no other people taller or the same height in front. Person 1 has height 7 with no other people taller or the same height in front. Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1. Person 3 has height 6 with one person taller or the same height in front, which is person 1. Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3. Person 5 has height 7 with one person taller or the same height in front, which is person 1. Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.
Example 2:
Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
