Lamda expression

image-20230908102703169

image-20230908095717662

image-20230908103000971

image-20230908103033599

also in lambada.java

image-20230908103156544

image-20230908103219413

lambda:

image-20230908103649766

simplify:

image-20230908104049965

lambda make method into implementations into objects like any other than can be saved into variables and passed into methods as parameters.

Greedy Algorithm 🌼

455. Assign Cookies

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:

1
2
3
4
5
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.

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int j = 0;
        for(int i=0 ; i < s.length && j < g.length; i++){ // pay attention to i and j here
            if(g[j] <= s[i]){
                count ++;
                j++; //注意这是j++不是i++
            }     
        }
        return count;
    }
}

376. Wiggle Subsequence

A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences.

  • For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative.
  • In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.

A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

Given an integer array nums, return the length of the longest wiggle subsequence of nums.

Example 1:

1
2
3
Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

376.摆动序列

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
41
42
43
44
45
46
47
48
49
50
51
// my version: still has bugs:   28 / 31 testcases passed
这个方法平坡的时候会遇上问题
而且像这种每次循坏比较，比较了数组里面的三个元素，这样不方便情况分类
代码随想录中，每次只用i表示出来来个元素，这样的代码写出来更加清晰
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int count = 1;
        int start = 0;
        //找峰值
        for(int i = 1 ; i < nums.length - 1 ; i++){
            if(nums[ i - 1] <= nums[i] && nums[i+1] < nums[i]){
                count++;
            }
        }
        //找峰谷
        for(int i = 1 ; i < nums.length - 1 ; i++){
            if(nums[ i - 1] >= nums[i] && nums[i+1] > nums[i]){
                count++;
            }

        }
		//排查头和尾巴的情况
        if(nums.length > 1 && nums[nums.length-2]!= nums[nums.length-1] &&nums[0]!= nums[1]){
            count = count + 1;
        } 
        return count;
    }
    
}

// leetcodemaster:
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int count = 1; //默认最右边就是一个摆动
        int curDif = 0;
        int preDif = 0;
        
        for(int i = 1 ; i < nums.length ; i++){
            curDif = nums[i] - nums[i-1];
            //等于0的情况表示初始时的preDiff
            if((curDif >0 && preDif <=0) ||(curDif <0 && preDif >=0)){  
            //这里不是curDif >= 0 curDif <= 0 是为了考虑第一个元素
                count++;
                preDif = curDif; // preDif 不能和curDif一直实时变换  -> 1 2 2 2 3 
            }
            //preDif = curDif; cannot put it here 
        }
        return count;
    }
    
}

1005. Maximize Sum Of Array After K Negations

Given an integer array nums and an integer k, modify the array in the following way:

  • choose an index i and replace nums[i] with -nums[i].

You should apply this process exactly k times. You may choose the same index i multiple times.

Return the largest possible sum of the array after modifying it in this way.

Example 1:

1
2
3
Input: nums = [4,2,3], k = 1
Output: 5
Explanation: Choose index 1 and nums becomes [4,-2,3].

my:

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int  count = 0;
        int res = 0;
        int min = 100000;
        for(int i = 0 ; i < nums.length ; i++){
            if( nums[i] < 0){
                count++;
            }
            if(Math.abs(nums[i])< min ){
                min = Math.abs(nums[i]);
            }
        }
        if( k < count){
            for(int i = 0 ; i < nums.length ; i++){
                if(k > 0){
                    res -= nums[i];
                    k -- ;
                }else{
                    res += nums[i];
                }
            }
        }else{
             for(int i = 0 ; i < nums.length ; i++){
                res += Math.abs(nums[i]);
               
            }
             if( (k-count)%2 == 0){
                    return res;
                }else{
                    return res - 2*min;
                }
        }
        return res;
    }
}

///sencond try:

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int count= 0 ;
        for( int i =0 ; i < k && i < nums.length; i++){
            if(nums[i] < 0){
                nums[i] = -nums[i];
                count++;
            }else{      
                break;
            }
        }
        if((k - count)%2 != 0){
            // if( count+1 < nums.length && Math.abs(nums[count+1]) < Math.abs(nums[count])){
            //     nums[count+1] = - nums[count+1];
            // }else{
            //     nums[count] = - nums[count];
            // }
            Arrays.sort(nums);
            nums[0] = -nums[0]; !!!!!!!!!!!!!!!!!!!!!!
        }
        return  Arrays.stream(nums).sum();
    }
}

optimize：

for(int i = 0 ; i < nums.length ; i++){

​ if( k > 0 && nums[i] < 0){

​ res += Math.abs(nums[i]);

​ k –;

​ }else{

​ res += nums[i];

​ }

​ }

​ if(k > 0){

​ if( k % 2 == 1)

​ res = res - 2 * min;

​ if( k % 2 == 0)

​ res= res;

​ }

leetcode-master:

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 largestSumAfterKNegations(int[] nums, int K) {
    	// 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
	nums = IntStream.of(nums)
		     .boxed()
		     .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
		     .mapToInt(Integer::intValue).toArray();
	int len = nums.length;	    
	for (int i = 0; i < len; i++) {
	    //从前向后遍历，遇到负数将其变为正数，同时K--
	    if (nums[i] < 0 && K > 0) {
	    	nums[i] = -nums[i];
	    	K--;
	    }
	}
	// 如果K还大于0，那么反复转变数值最小的元素，将K用完

	if (K % 2 == 1) nums[len - 1] = -nums[len - 1];
	return Arrays.stream(nums).sum();

    }
}

https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.md

860. Lemonade Change

Easy

At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5.

Note that you do not have any change in hand at first.

Given an integer array bills where bills[i] is the bill the ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.

Example 1:

1
2
3
4
5
6
7
Input: bills = [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output 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
28
29
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){
                ten++;
                five--;

            }else if(bills[i]==20 ){  // important
                if(ten > 0){
                    ten--;
                    five--;
                }else{
                    five -= 3;
                }

            }

            if(five < 0 || ten < 0){
                    return false;
                }
        }

        return true;
    }
}

122. Best Time to Buy and Sell Stock II

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:

1
2
3
4
5
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.
1
2
3
4
5
6
7
8
9
10
11
class Solution {
  public int maxProfit(int[] prices) {
    int prof = 0;
    for(int i = 0; i < prices.length - 1; i++){
      if(prices[i] < prices[i+1]){
        prof += prices[i+1] - prices[i];
      }
    }
    return prof;
  }
}

714. Best Time to Buy and Sell Stock with Transaction Fee

You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note:

  • You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
  • The transaction fee is only charged once for each stock purchase and sale.

Example 1:

1
2
3
4
5
6
7
8
Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

134. Gas Station

Medium

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
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
41
42
43
44
45
46
47
48
49
暴力解法：//not sure it's right and also exceeded tgt time limit
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int[] val = new int[gas.length];
        int sum = 0;
        for(int i = 0; i < gas.length; i++){
            val[i] = gas[i] - cost[i];
            sum += val[i];
        }
        if(sum < 0) return -1;
        for(int i = 0; i < val.length; i++){
            sum = 0;
            int time = val.length;
            int j = i;
            while(time > 0){
                if(j == val.length) j =0;
                sum += val[j];
                if(sum < 0) break;
                j++;
                time--;
            }
            if (time == 0) return i;
        }

        return -1;
    }
}

greedy algorithm:

	class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalsum = 0;
        int cursum = 0;
        int res = 0;
        for(int i = 0; i < gas.length; i++){
            totalsum += gas[i] - cost[i];
            cursum += gas[i] - cost[i];
            if(cursum < 0) {
                res = i + 1;
                if(res == gas.length) res = 0;
                cursum = 0;
            }
        }
        if(totalsum < 0) return -1;
        return res;
    }
}

那么局部最优：当前累加rest[i]的和curSum !!!一旦!!! 小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。

135. Candy

Hard

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:

1
2
3
Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
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 candy(int[] ratings) {
        int[] candy = new int[ratings.length];
        candy[0] = 1;
        for(int i = 1; i < ratings.length; i++){
            if(ratings[i] > ratings[i-1]) 
            {
                candy[i] = candy[i-1] + 1;
            }else{
                candy[i] = 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]);
        }
        int res = 0;
        for(int i = 0; i < ratings.length; i++){
            res += candy[i];
        }
        return res;
    }
}

从前向后遍历，再从后向前遍历，取最大值这样就两个方向都可以满足条件。

不要遍历一次同时比较左右两边，这样做会非常复杂。

img

所以确定左孩子大于右孩子的情况一定要从后向前遍历！

那么又要贪心了，局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。

局部最优可以推出全局最优。

所以就取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多，也比右边candyVec[i + 1]的糖果多。

如图：

135.分发糖果1

406. Queue Reconstruction by Height

Medium

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 exactly ki 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 array people. 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
2
3
4
5
6
7
8
9
10
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.
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
class Solution {
    LinkedList<int[]> que = new LinkedList<>();
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a,b) -> {
            if(a[0] == b[0]) return a[1] - b[1];
            // a - b 是升序排列，故在a[0] == b[0]的狀況下，會根據k值升序排列
            return b[0] - a[0];   //b - a 是降序排列，在a[0] != b[0]，的狀況會根據h值降序排列
        });

        for(int[] p : people){
            que.add(p[1], p);//Linkedlist.add(index, value)，會將value插入到指定index裡。
        }

        return que.toArray(new int[people.length][]);
    }
}




class Solution {
    LinkedList<int[]> que = new LinkedList<>();
    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]; 
        });
        for(int i = 0; i < people.length; i++){
            que.add(people[i][1], people[i]);
        }
        return (que.toArray(new int[people.length][people[0].length]));
    }
}
  1. (a, b) -> {...}: This is a lambda expression defining the custom comparator for sorting the people array.
  2. Inside the lambda expression:
    • if (a[0] == b[0]) return a[1] - b[1];: This condition checks if two people have the same height (a[0] == b[0]). If they have the same height, it compares their k values (a[1] and b[1]) in ascending order. This means that people with the same height will be sorted in ascending order of their k values.
    • return b[0] - a[0];: If two people have different heights (a[0] != b[0]), it compares their heights in descending order. This means that people with different heights will be sorted in descending order of their heights.

When you subtract b[1] from a[1], you are calculating the difference between the k values of two people, a and b. If the result is positive, it means that a[1] is greater than b[1], indicating that a should come after b in ascending order. Conversely, if the result is negative, it means that a[1] is less than b[1], indicating that a should come before b in ascending order.

So, return a[1] - b[1] sorts the array in ascending order of the k values. People with smaller k values (fewer people taller or as tall as them in front) will appear earlier in the sorted array, and people with larger k values (more people taller or as tall as them in front) will appear later in the sorted array. I apologize for any confusion in my previous responses, and thank you for pointing out the error.

  1. When you add elements with the same p[1] value to the LinkedList, the order in which they were added will be maintained. The first element with a particular p[1] value added to the queue will be positioned first among elements with the same p[1] value.
  2. Elements with different p[1] values (different values of k) will not be affected by this and will still be ordered based on the comparison logic provided in the Arrays.sort step.

So, if multiple people have the same number of people in front of them (p[1] values are the same), their relative order in the output will be determined by their original order in the input array, with the first one encountered being positioned first in the output.

Arrays.sort —-> comparator

https://www.geeksforgeeks.org/sort-an-array-in-java-using-comparator/

No, the second parameter in Arrays.sort should not be of type int. The second parameter in Arrays.sort is a Comparator object or a lambda expression that defines the custom sorting logic for the elements in the array. It does not have to be of type int, but rather, it should be a function that returns an int to indicate the ordering relationship between two elements.

The compare() method in the Comparator is responsible for comparing two elements and returning an integer value that indicates their relative order. It follows the following convention:

  • If compare(o1, o2) returns a negative value, o1 should come before o2 in the sorted order.

  • If compare(o1, o2) returns zero, o1 and o2 are considered equal in terms of sorting order.

  • If compare(o1, o2) returns a positive value, o1 should come after o2 in the sorted order.

  1. Sorting Examples:
    • You can use Comparator to sort arrays of custom objects based on specific attributes or fields within those objects.
    • You can also use it to perform case-insensitive or reverse sorting.

Here’s an example of using Arrays.sort() with a custom Comparator:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
javaCopy codeimport java.util.Arrays;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) {
        String[] fruits = {"apple", "Banana", "cherry", "date"};

        // Sorting the array using a custom Comparator for case-insensitive sorting
        Arrays.sort(fruits, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.compareToIgnoreCase(o2);
            }
        });

        // Printing the sorted array
        System.out.println(Arrays.toString(fruits));
    }
}

452. Minimum Number of Arrows to Burst Balloons

Medium

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
2
3
4
5
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].
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
wrong version:

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a,b) -> {
            return a[0] - b[0]; // here will be some overflow!
        });
        int time = 1;
        for(int i = 1; i < points.length; i++){
            if(points[i - 1][1] < points[i][0]){
                time++;
            }else{
                points[i][1] = Math.min(points[i][1], points[i-1][1]);
            }
        }

        return time;

    }
}



here's right version:
		// 使用Integer内置比较方法，不会溢出
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
        
you can also write like this:

Arrays.sort(points, (a,b) ->{
           return Integer.compare(a[0], b[0]);
        });

The Integer.compare method returns a negative value if a[0] is less than b[0], zero if they are equal, and a positive value if a[0] is greater than b[0]

435. Non-overlapping Intervals

Medium

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.

Example 1:

1
2
3
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int count = 0;
        Arrays.sort(intervals, (a,b) -> {
            if(a[0] == b[0]){
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });
        for(int i = 1; i < intervals.length; i++ ){
           if (intervals[i][0] < intervals[i-1][1]){
               count++;
               intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);  //!!!!!!!!!
           }
        }
        return count;

    }
}

763. Partition Labels

Medium

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:

1
2
3
4
5
6
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> res = new LinkedList<>();
        char[] chars = s.toCharArray();
        int[] edge = new int[26];
        for(int i = 0; i < chars.length; i++){
            edge[chars[i] - 'a'] = i;
        }
        int count = 0;
        int temp = -1; //mark the edge
        for(int i = 0; i < chars.length; i++){
            temp = Math.max(temp, edge[chars[i] - 'a']);
            count++;
            if(i == temp){
                res.add(count);
                count = 0;
            }
        }
        return res;
    }
}
  • 统计每一个字符最后出现的位置
  • 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

如图：

763.划分字母区间

56. Merge Intervals

Medium

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

1
2
3
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
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[][] merge(int[][] intervals) {
        LinkedList<int[]> res = new LinkedList<>();
        Arrays.sort(intervals, (a,b)->{
            if(a[0] == b[0]) return a[1] - b[1];
            return a[0] - b[0];
        });
        int left = intervals[0][0];
        int right = intervals[0][1];
        for(int i = 1; i < intervals.length; i++){
            if(right < intervals[i][0]){
                //right = intervals[i-1][1]; !!! dont need it here
                res.add(new int[]{left,right});
                left = intervals[i][0];
                right = intervals[i][1];
            }else{
                right = Math.max(right,intervals[i][1]);
                //!!!
                // wrong: right = Math.max(intervals[i][1],intervals[i-1][1]);
            }
        }
        res.add(new int[]{left, right}); //!!!important, dont forget to add the last round
        return res.toArray(new int[res.size()][2]); //!!! syntax
    }
}

53. Maximum Subarray

Medium

Example 1:

1
2
3
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

1
2
3
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 1){
            return nums[0];
        }
        int add = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0 ; i < nums.length; i++){
            add += nums[i];
            max = Math.max(add, max); // NEED TO PUT THIS BEFORE IF STATEMENT!!!!!!
            if(add <= 0) add = 0;
            
        }
        return max;
    }
}

55. Jump Game

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

1
2
3
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean canJump(int[] nums) {

       if(nums.length == 1) return true;
       int range = nums[0] ;
       for(int i = 0 ; i <= range; i++){
           range = Math.max(i + nums[i], range);
           if(range >= nums.length - 1) return true;
       }
       return false;
    }
}

45. Jump Game II

Medium

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

  • 0 <= j <= nums[i] and
  • i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

1
2
3
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
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
//////////////55 jump game///////////////
class Solution {
    public boolean canJump(int[] nums) {

       if(nums.length == 1) return true;
       int range = nums[0] ;
       for(int i = 0 ; i <= range; i++){
           range = Math.max(i + nums[i], range);
           if(range >= nums.length - 1) return true;
       }
       return false;
    }
}

////////////////////////////////////////
class Solution {
    public int jump(int[] nums) {
        if(nums.length == 1) return 0;
        int cur = 0 ; 
        int next = 0;
        int res = 0;
        for(int i = 0 ; i < nums.length; i++){
            next = Math.max(nums[i] + i, next);
            if(cur == i){ 
                cur = next;
                res ++;
                if(next >=  nums.length - 1) break;
            }

        } 
        return res;
    }
}

[toc]