Tag: Sort - Hexo

Posted 2022-09-11Updated 2022-09-11LeetCode / Hard / 复习2 minutes read (About 349 words)

Question

You are given two integers n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the ith engineer respectively.

Choose at most k different engineers out of the n engineers to form a team with the maximum performance.

The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers.

Return the maximum performance of this team. Since the answer can be a huge number, return it modulo 109 + 7.

Solution

排序，将所有工程师根据其效率降序排列。

此时遍历时后一个工程师的效率一定小于等于前一个工程师。

因此，此时遍历到每一个工程师，其前面所有的工程师的efficiency均大于等于其本身。
维护一个所有选取工程师的总速度ttSpd，每次计算并更新max的值。
用最小堆来维护选取的工程师速度，如果优先级队列的尺寸超过k-1，则poll掉队列内最低的速度。

Code

class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        final int mod = (int) Math.pow(10, 9) + 7;
        int[][] engineer = new int[n][2];
        
        for(int i = 0; i < n; i++){
            engineer[i][0] = speed[i];
            engineer[i][1] = efficiency[i];
        }
        
        Arrays.sort(engineer, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return b[1] - a[1];
            }
        });
        
        long max = 0, ttSpd = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 0; i < n; i++){
            int s = engineer[i][0], e = engineer[i][1];
            ttSpd += s;
            max = Math.max(max, ttSpd * e);
            pq.add(s);
            if(pq.size() == k) ttSpd -= pq.poll();
        }
        
        return (int) (max % mod);
    }
}

Posted 2022-09-11Updated 2022-09-11LeetCode / Medium / 复习2 minutes read (About 348 words)

1996. The Number of Weak Characters in the Game

Question

You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array properties where properties[i] = [attacki, defensei] represents the properties of the ith character in the game.

A character is said to be weak if any other character has both attack and defense levels strictly greater than this character’s attack and defense levels. More formally, a character i is said to be weak if there exists another character j where attackj > attacki and defensej > defensei.

Return the number of weak characters.

Solution

本题与354. Russian Doll Envelopes相近。

首先对数组进行排序，根据角色的attack数值降序排序，如果两者的attack数值相等，则根据两者的defence升序排序。

记录一个遍历过的最大defence数值maxDefence，遍历数组，如果当前maxDef大于角色的防御值，则此时当前遍历角色的attack与defence均严格小于上一个计算的角色，因此count加一。
否则更新maxDef。

*由于attack是降序的，因此可以确定遍历时下一组数组的attack一定更弱。（由于相同attack的角色是根据defence升序排列，因此记录maxDef时会逐个更新maxDef的值。）

Code

class Solution {
    public int numberOfWeakCharacters(int[][] properties) {
        int count = 0, maxDef = Integer.MIN_VALUE;
            
        Arrays.sort(properties, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                if(a[0] == b[0]) return a[1] - b[1];
                return b[0] - a[0];
            }
        });
        
        for(int[] character : properties){
            if(maxDef > character[1]) count++;
            else maxDef = character[1];
        }
        return count;
    }
}

Posted 2022-07-02Updated 2022-07-01LeetCode / Medium2 minutes read (About 264 words)

1465. Max Area After Horizontal and Vertical Cuts

Question

You are given a rectangular cake of size h x w and two arrays of integers horizontalCuts and verticalCuts where:

horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, and

verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut.

Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a large number, return this modulo 109 + 7.

Solution

先排序，记录两次切割之间的距离的最大值。
最后同样需要比较蛋糕的总尺寸和最后一次切割的距离。

返回宽度和长度的最大值的乘积即可。

注意：两个int整数相乘会溢出，max需要记录为long类型。

Code

class Solution {
    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        int MOD = (int) Math.pow(10,9)+7;
        Arrays.sort(horizontalCuts);
        Arrays.sort(verticalCuts);
        long maxH = 0, maxV = 0;
        int lastH = 0, lastV = 0;
        
        for(int i = 0; i < horizontalCuts.length; i++){
            maxH = Math.max(maxH, horizontalCuts[i] - lastH);
            lastH = horizontalCuts[i];
        }
        
        maxH = Math.max(maxH, h - lastH);
        
        for(int i = 0; i < verticalCuts.length; i++){
            maxV = Math.max(maxV, verticalCuts[i] - lastV);
            lastV = verticalCuts[i];
        }
        
        maxV = Math.max(maxV, w - lastV);
        return (int) (maxV * maxH % MOD) ;
    }
}

Posted 2022-06-15Updated 2022-06-14LeetCode / Medium3 minutes read (About 477 words)

1048. Longest String Chain

Question

You are given an array of words where each word consists of lowercase English letters.

wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB.

For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".

A word chain* *is a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.

Return *the length of the longest possible word chain with words chosen from the given list of *words.

Solution

排序+动态规划。
采用一个一维动态规划数组记录到某个word的最大字符串链长度。

排序

每个predecessor必定比next少1，因此首先将数组根据word的长度排序。

动态规划

数组dp[i]记录到i位置时的最大长度。
双重遍历i和j，其中j>i。如果words[i-1]是words[j-1]的predecessor，则更新dp[j]为dp[j]与dp[i]+1的较大值。

辅助方法 isValid()

判断predecessor是否有效。
初始化一个flag为false记录不同字符是否已出现。
如果两者长度差不为1直接返回false。
双指针分别指向两个字符串，如果两个当前字符相等，则两个指针共同前进。
如果不相等且flag为true则i指针前进，并且将flag改为false。否则返回false。
如果循环结束返回true。

Code

class Solution {
    public int longestStrChain(String[] words) {
        int max = 0;
        Arrays.sort(words, (a,b) -> a.length() - b.length());
        int[] dp = new int[words.length+1];
        for(int i = 1; i <= words.length; i++){
            for(int j = i + 1; j <= words.length; j++){
                if(isValid(words[i-1], words[j-1])){
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                    max = Math.max(max, dp[j]);
                }
            }
        }
        return max + 1;
    }
    
    private boolean isValid(String predecessor, String next){
        if(predecessor.length() + 1 != next.length()) return false;
        boolean flag = true;
        int i = 0, j = 0;
        while(i < next.length() && j < predecessor.length()){
            if(next.charAt(i) == predecessor.charAt(j)){
                i++;
                j++;
            }
            else if(flag){
                i++;
                flag = false;
            }
            else{
                return false;
            }
        }
        return true;
    }
}

Posted 2022-06-12Updated 2022-06-11LeetCode / Medium / 复习4 minutes read (About 574 words)

2300. Successful Pairs of Spells and Potions

Question

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

Solution 1

排序+二分搜索。同时记录success与spells[i]的比值来减小计算量。

排序

首先对potions[]进行排序，这样可以使用二分搜索查找分界值。
数组scales[]记录success与spells[i]的比值，以此为界大于等于scales[i]的位置都可以计入ret[]数组。

二分搜索

这里有一些tricky。

由于Arrays.binarySearch()方法无法返回重复的数字，因此在搜索时我们将查找值scale减去一个小值，保证在搜索时一定返回负值。（查找值的插入位置的负数-1）
将ret[i]记录为potions[]的总数减去正确的插入位置即可。

Code

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int[] ret = new int[spells.length];
        
        Arrays.sort(potions);
        double[] scales = new double[potions.length];
        
        for(int i = 0; i < potions.length; i++){
            scales[i] = (double) potions[i];
        }
        
        for(int i = 0; i < spells.length; i++){
            double scale = (double) success / spells[i] - 0.000001;   //确保浮点数不在scale中出现，binarySearch方法返回的结果必定为上一个插入位置
            int index = Arrays.binarySearch(scales, scale);
            ret[i] = potions.length + (index + 1);
        }
        return ret;
    }
}

Solution 2

由于Arrays.binarySearch()无法正确的搜索有重复元素的数组，因此采用辅助方法binarySearch()来搜索最左侧的下标。

直接在binarySearch()方法中查找target，比较的对象为spell和potions[i]的乘积。

为了搜寻重复的第一个元素，当遇到target时不直接返回，而是继续修改right的位置，直到left等于right。

如果未搜索到，则返回数组的总长度。

Code

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int[] ret = new int[spells.length];
        Arrays.sort(potions);
        for(int i = 0; i < spells.length; i++){
            int index = binarySearch(potions, spells[i], success);
            ret[i] = potions.length - index;
        }
        return ret;
    }
    
    private int binarySearch(int[] potions, long spell, long target){
        int left = 0, right = potions.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(potions[mid] * spell < target) left = mid + 1;
            else right = mid;
        }
        return potions[left] * spell < target ? potions.length : left;
    }
}

Posted 2022-05-25Updated 2022-09-11LeetCode / Hard / 复习7 minutes read (About 979 words)

354. Russian Doll Envelopes

Question

You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Solution 1

最长递增子数列

这道题是LIS问题（Longest Increasing Subsequence）的升级版。
后一个数组中的两个元素应该同时严格大于前一个数组中的两个元素。
因此我们需要维护一个宽度和高度同时严格单调递增的数列。

排序

我们可以对数组以宽度进行比较排序。当二者的宽度相等时，以高度的倒序排序。
（采用倒序排序是为了下面处理时排除不严格大于上一个数组的情况。）

递增数列

我们可以维护一个递增动态数组arr，记录高度组成的单调递增数列。（LIS）
首先将数组中的第一个元素的高度加入动态数组。
然后遍历数组envelopes[]：

如果当前数组的高度height大于单调递增数列的最大值：
- 则当前的数组的宽度和高度均严格大于数组中最后一个高度对应的数组。
- 数组是优先以宽度的顺序排列，相等时以高度的倒序排列。由于相同宽度时高度大的在前，因此当当前高度大于之前的最大高度，则宽度也一定大于之前的最大宽度。
如果小于或者等于单调递增数列的最大值：
- 单调数列中高度的增长越平缓，我们在后面找到更多严格大于height的可能性就越大，因此可以用贪心思想，更新单调数列中的第一个大于当前高度的值。
- 由于单调递增数列是有序的，因此可以采用二分搜索来寻找第一个大于当前高度的值的下标，并将其更新为当前的height。

排序的时间复杂度为O(nlogn)，遍历数组的时间复杂度为O(n)，二分搜索的时间复杂度为O(logn)。
总的时间复杂度为O(nlogn)。

Code

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a,b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        
        List<Integer> arr = new ArrayList<>();
        arr.add(envelopes[0][1]);
        for(int i = 1; i < envelopes.length; i++){
            int height = envelopes[i][1];
            if(height > arr.get(arr.size()-1)){
                arr.add(height);
            }
            else{
                int index = Collections.binarySearch(arr, height);
                if(index < 0) index = -index-1;
                arr.set(index, height);
            }
        }
        return arr.size();
    }
}

Solution 2

注意这个方法在LeetCode中会超时，仅仅是记录一下思路，也可以采用动态规划的方法。
记忆化搜索剪枝。
记忆化搜索每个envelope。

memorazation()方法，返回当前的envelope中可以包含的最大数量。
当数组memo[i]不等于0时，返回memo[i]。
否则初始化最大值max为1。
遍历数组中的所有元素，如果宽度于长度都大于envelopes[i]，则向下递归搜索该元素。
比较并更新max和递归结果的返回值+1。
最后将当前位置memo[i]设置为包含的最大数量max。

遍历所有元素时间复杂度O(n)。
记忆化搜索元素的子项时间复杂度O(n)。
时间复杂度为O(n2)。

Code

class Solution {
    int[][] dolls;
    int[] memo;
    
    public int maxEnvelopes(int[][] envelopes) {
        dolls = envelopes;
        memo = new int[dolls.length];
        int res = 0;
        for(int i = 0; i < dolls.length; i++){
            if(memo[i] != 0) continue;
            memorazation(i);
            res = Math.max(res, memo[i]);
        }
        return res;
    }
    
    private int memorazation(int i){
        if(memo[i] != 0){
            return memo[i];
        }
        int max = 1;
        for(int k = 0; k < dolls.length; k++){
            if(dolls[k][0] < dolls[i][0] && dolls[k][1] < dolls[i][1]){
                max = Math.max(max, memorazation(k) + 1);
            }
        }
        return memo[i] = max;
    }
}

Posted 2022-05-22Updated 2022-05-21LeetCode / Medium2 minutes read (About 271 words)

2280. Minimum Lines to Represent a Line Chart

Question

You are given a 2D integer array stockPrices where stockPrices[i] = [dayi, pricei] indicates the price of the stock on day dayi is pricei. A line chart is created from the array by plotting the points on an XY plane with the X-axis representing the day and the Y-axis representing the price and connecting adjacent points. One such example is shown below:

Solution

如果只有一个点，无法组成线段则返回0。否则至少可以组成1条线段。

首先将所有点根据x的位置排序，然后一次比较连续的各个向量的方向。
为了防止除法精度问题，计算两个向量（三个点组成两个向量）的叉乘，如果叉乘为0，则说明两个向量是平行的，此时不需要增加计数。
如果叉乘结果不等于0，则将计数+1。

最后返回计数的结果。

Code

class Solution {
    public int minimumLines(int[][] stockPrices) {
        if(stockPrices.length == 1) return 0;
        
        Arrays.sort(stockPrices, (a,b) -> a[0] - b[0]);
        int count = 1, lastX = 0, lastY = 0;
        
        for(int i = 1; i < stockPrices.length; i++){
            int x = stockPrices[i][0] - stockPrices[i-1][0];
            int y = stockPrices[i][1] - stockPrices[i-1][1];
            
            int k = lastX * y - lastY * x;
            if(k != 0) count++;
            lastX = x;
            lastY = y;
        }
        return count;
    }
}

Posted 2022-05-22Updated 2022-05-21LeetCode / Medium2 minutes read (About 226 words)

2279. Maximum Bags With Full Capacity of Rocks

Question

You have n bags numbered from 0 to n - 1. You are given two 0-indexed integer arrays capacity and rocks. The ith bag can hold a maximum of capacity[i] rocks and currently contains rocks[i] rocks. You are also given an integer additionalRocks, the number of additional rocks you can place in any of the bags.

Return* the maximum number of bags that could have full capacity after placing the additional rocks in some bags.*

Solution

计算每个背包的剩余空间，然后进行排序。
按从小到大的顺序依次减少石头的总数。
设置i作为选取石头的计数。每次循环将i增加，直到剩余的石头数量小于0。
如果最后剩下的石头仍然大于等于0，则返回计数。
否则返回计数-1。

Code

class Solution {
    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        int[] diff = new int[capacity.length];
        for(int i = 0 ; i < capacity.length; i++){
            diff[i] = capacity[i] - rocks[i];
        }
        
        Arrays.sort(diff);
        int i = 0;
        while(additionalRocks > 0 && i < diff.length){
            additionalRocks -= diff[i];
            i++;
        }
        return additionalRocks >= 0 ? i : i - 1;
    }
}

Posted 2022-05-05Updated 2022-05-05LeetCode / Medium / 复习2 minutes read (About 260 words)

973. K Closest Points to Origin

Question

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Solution

此题可以采用快速排序的思想。可以在O(n)时间复杂度里完成排序。

Solution 2

优先级队列，根据每个点距离的平方排序。时间复杂度O(nlogk)。

Code

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int[][] ret = new int[k][2];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> squaredDistance(a) - squaredDistance(b));
        for(int[] point : points){
            pq.add(point);
        }
        for(int i = 0; i < k; i++){
            ret[i] = pq.poll();
        }
        return ret;
    }
    
    private int squaredDistance(int[] point){
        int x = point[0], y = point[1];
        return x * x + y * y;
    }
}

Solution 3

直接排序。时间复杂度为O(nlogn)。

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int[][] ret = new int[k][2];
        Arrays.sort(points, (a, b) -> squaredDistance(a) - squaredDistance(b));
        for(int i = 0; i < k; i++){
            ret[i] = points[i];
        }
        return ret;
    }
    
    private int squaredDistance(int[] point){
        int x = point[0], y = point[1];
        return x * x + y * y;
    }
}

Posted 2022-05-05Updated 2022-06-21LeetCode / Mediuma minute read (About 149 words)

215. Kth Largest Element in an Array

Problem

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Solution

直接排序数组，返回倒数第k个值。

Code

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

Solution 2

采用优先级队列，将所有元素加入队列，采用倒序比较器。
挤出前k-1个值，然后返回第k个值。

Code

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int num : nums){
            pq.add(num);
        }
        for(int i = 0; i < k-1; i++){
            pq.poll();
        }
        return pq.peek();
    }
}

Posted 2022-05-04Updated 2022-05-04LeetCode / Medium2 minutes read (About 358 words)

1679. Max Number of K-Sum Pairs

Question

You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

Solution

两种思路，第一种，哈希表统计总数，然后逐个排除。
每次从数组中取一个数，先查询寻找的target是否在哈希表内。
如果表内存在target，则将target的计数减一，对数加一。

如果target不在表内，则将当前的数字加入表内。
最后返回结果。时间复杂度为O(n)。

Code

class Solution {
    public int maxOperations(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 0;
        for(int num : nums){
            int target = k - num;
            if(map.containsKey(target) && map.get(target) > 0){
                map.put(target, map.get(target)-1);
                count++;
            }
            else{
                map.put(num, map.getOrDefault(num, 0)+1);
            }
        }
        return count;
    }
}

Solution 2

第二种思路，先排序。
然后双指针放在首尾。
当两者的和等于目标值时增加计数器，并移动两个指针。
当两者的和大于目标值时，右侧指针左移。
当两者的和小于目标值时，左侧指针右移。
最后返回结果。由于有排序存在，因此时间复杂度为O(nlogn) + O(n)。

Code

class Solution {
    public int maxOperations(int[] nums, int k) {
        Arrays.sort(nums);
        int left = 0, right = nums.length-1, count = 0;

        while(left < right){
            if(nums[left] + nums[right] == k){
                count++;
                left++;
                right--;
            }
            else if(nums[left] + nums[right] > k){
                right--;
            }
            else{
                left++;
            }
        }
        return count;
    }
}

Posted 2022-04-25Updated 2022-04-24LeetCode / Medium2 minutes read (About 229 words)

40. Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

由于有重复性元素，因此先将数组排序。
储存一个数组，记录元素是否被选择。
回溯，遍历选择元素，并计算加和，并记录选择的元素。当选择的元素与上一个元素重复时，则跳过。

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(candidates);
        backtracking(candidates, ret, new ArrayList<>(), new int[candidates.length], target, 0, 0);
        return ret;
    }
    
    private void backtracking(int[] candidates, List<List<Integer>> ret, List<Integer> arr, int[] visited, int target, int sum, int level){
        if(sum > target ){
            return;
        }
        else if (sum == target){
            ret.add(new ArrayList<>(arr));
            return;
        }

        for(int i = level; i < candidates.length; i++){
            if(i > 0 && candidates[i] == candidates[i-1] && visited[i-1] == 0) continue;
            visited[i] = 1;
            arr.add(candidates[i]);
            sum+= candidates[i];
            backtracking(candidates, ret, arr, visited, target, sum, i+1);
            visited[i] = 0;
            sum-= candidates[i];
            arr.remove(arr.size()-1);
        }
    }
}

Posted 2022-04-25Updated 2022-04-24LeetCode / Medium / 复习2 minutes read (About 255 words)

47. Permutations II

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

首先排序，对于有重复数据的数组，排序可以方便剪枝。
回溯，每次遍历数组内的元素。
创建一个数组记录元素是否已被遍历。
遍历时如果数组已经被记录，或者当前元素与数组中的上一个元素相等，且上一个数组未被选择，则跳过。
（如果上一个同样的数字没被选择，则放弃这个排列。即在元素相同时，优先选择前面的元素进行排列）

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int[] visited = new int[nums.length];
        backtracking(ret, new ArrayList<>(), visited , nums);
 
        return ret;
    }

    private void backtracking(List<List<Integer>> ret, List<Integer> arr, int[] visited, int[] nums){
        if(arr.size() == nums.length){
            ret.add(new LinkedList<>(arr));
            return;
        }
        
        for(int i = 0; i < nums.length; i++){
            if(visited[i] == 1) continue;
            if(i > 0 && nums[i] == nums[i-1] && visited[i-1] == 0) continue;
            arr.add(nums[i]);
            visited[i] = 1;
            backtracking(ret, arr, visited, nums);
            visited[i] = 0;
            arr.remove(arr.size()-1);
        }
    }
}

Posted 2022-04-21Updated 2022-04-21LeetCode / Mediuma minute read (About 219 words)

763. Partition Labels

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.

将英文字母出现的首尾作为intervals看待。
根据字符创建数组并填入左右的index。
根据左侧index排序数组。

从左至右，如果intervals有交集，则合并。
否则在答案中添加当前interval的长度。

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[][] alphabet = new int[26][2];
        int head = s.charAt(0) - 'a';
        for(int i = 0; i < s.length(); i++){
            int index = s.charAt(i) - 'a';
            if(head != index && alphabet[index][0] == 0) alphabet[index][0] = i;
            alphabet[index][1] = i;
        }
        
        Arrays.sort(alphabet, (a,b) -> a[0] - b[0]);
        
        List<Integer> ans = new ArrayList();
        int[] hold = alphabet[0];
        for(int i = 1; i < alphabet.length; i++){
            if(alphabet[i][0] <= hold[1]){
                hold[1] = Math.max(hold[1], alphabet[i][1]);
            }
            else{
                ans.add(hold[1]-hold[0]+1);
                hold = alphabet[i];
            }
        }
        ans.add(hold[1]-hold[0]+1);
        return ans;
        
    }
}

Posted 2022-04-19Updated 2022-04-19LeetCode / Mediuma minute read (About 183 words)

435. Non-overlapping Intervals

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.

首先对intervals按照后一项的大小进行排序。（直接将两数字相减作为比较值比Integer.compare方法更快。）
贪心算法，将已取得的最大值max设置为最小整数值。
遍历intervals，如果当前interval的左侧小于max，则不能选择该interval，计数加一。
反之则可以选择interval，更新max的值为interval的最大值。
返回总数。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a,b) -> a[1] - b[1]);
        int max = Integer.MIN_VALUE;
        int count = 0;
        for(int[] interval : intervals){
            if(interval[0] < max){
                count++;
            }
            else{
                max = interval[1];
            }
        }
        return count;
    }
}

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

排序

动态规划

辅助方法 isValid()

Code

Question

Solution 1

排序

二分搜索

Code

Solution 2

Code

Question

Solution 1

最长递增子数列

排序

递增数列

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Solution 2

Code

Solution 3

Problem

Solution

Code

Solution 2

Code

Question

Solution

Code

Solution 2

Code

Recents

Archives

Links