代码随想录 Day36 - 贪心算法(五)

简介: 代码随想录 Day36 - 贪心算法(五)

435. 无重叠区间

本题的关键在于判断重复的区间的起止,需要通过不断比较当前区间和下一个区间的起止值。若当前区间的起始大于上一个区间的结束值,则统计的无重叠区间+1.

package jjn.carl.greedy;
import java.util.Arrays;
import java.util.Scanner;
/**
 * @author Jjn
 * @since 2023/8/2 09:43
 */
public class LeetCode435 {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (i1, i2) -> {
            if (i1[0] == i2[0]) {
                return Integer.compare(i1[1], i2[1]);
            }
            return Integer.compare(i1[0], i2[0]);
        });
        int count = 0;
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= end) {
                end = intervals[i][1];
                continue;
            }
            end = Math.min(end, intervals[i][1]);
            count++;
        }
        return count;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int total = scanner.nextInt();
        int[][] intervals = new int[total][2];
        for (int i = 0; i < total; i++) {
            for (int j = 0; j < 2; j++) {
                intervals[i][j] = scanner.nextInt();
            }
        }
        int count = new LeetCode435().eraseOverlapIntervals(intervals);
        System.out.println(count);
    }
}


763. 划分字母区间

遍历一遍,更新字母和其出现的最大的下标 index,构建为一个 Map。随后遍历字符串,若字符串是区间的最大下标,则将结果加到 result 数组里,否则继续往后遍历。

package jjn.carl.greedy;
import java.util.*;
/**
 * @author Jjn
 * @since 2023/8/2 12:33
 */
public class LeetCode763 {
    public List<Integer> partitionLabels(String s) {
        List<Integer> parts = new ArrayList<>();
        int[] dict = new int[26];
        for (int i = 0; i < s.length(); i++) {
            dict[s.charAt(i) - 'a'] = i;
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, dict[s.charAt(i) - 'a']);
            if (i == end) {
                parts.add(end - start + 1);
                start = end + 1;
            }
        }
        return parts;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String s = scanner.nextLine();
            List<Integer> list = new LeetCode763().partitionLabels(s);
            System.out.println(list.toString());
        }
    }
}


56. 合并区间

排序后,不断更新其区间内的右端点。

package jjn.carl.greedy;
import java.util.*;
/**
 * @author Jjn
 * @since 2023/8/2 14:40
 */
public class LeetCode56 {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(i -> i[0]));
        Deque<int[]> result = new LinkedList<>();
        for (int i = 0; i < intervals.length; i++) {
            int left = intervals[i][0], right = intervals[i][1];
            if (result.isEmpty() || result.peekLast()[1] < left) {
                result.offer(new int[]{left, right});
                continue;
            }
            result.peekLast()[1] = Math.max(result.peekLast()[1], right);
        }
        return result.toArray(new int[result.size()][]);
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int total = scanner.nextInt();
            int[][] intervals = new int[total][2];
            for (int i = 0; i < total; i++) {
                for (int j = 0; j < 2; j++) {
                    intervals[i][j] = scanner.nextInt();
                }
            }
            int[][] merge = new LeetCode56().merge(intervals);
            StringBuilder stringBuilder = new StringBuilder();
            stringBuilder.append("[");
            for (int[] ints : merge) {
                stringBuilder.append(Arrays.toString(ints));
                stringBuilder.append(",");
            }
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            stringBuilder.append("]");
            System.out.println(stringBuilder);
        }
    }
}

目录
相关文章
|
12天前
|
存储 算法 程序员
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
|
13天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
37 1
|
21天前
|
存储 缓存 算法
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
|
28天前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
1月前
|
算法 测试技术 开发者
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗;代码审查通过检查源代码发现潜在问题,提高代码质量和团队协作效率。本文介绍了一些实用的技巧和工具,帮助开发者提升开发效率。
41 3
|
1月前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
2月前
|
存储 缓存 算法
如何通过优化算法和代码结构来提升易语言程序的执行效率?
如何通过优化算法和代码结构来提升易语言程序的执行效率?
|
2月前
|
搜索推荐
插入排序算法的讲解和代码
【10月更文挑战第12天】插入排序是一种基础的排序算法,理解和掌握它对于学习其他排序算法以及数据结构都具有重要意义。你可以通过实际操作和分析,进一步深入了解插入排序的特点和应用场景,以便在实际编程中更好地运用它。
|
4月前
|
机器学习/深度学习 人工智能 自然语言处理
【自然语言处理】TF-IDF算法在人工智能方面的应用,附带代码
TF-IDF算法在人工智能领域,特别是自然语言处理(NLP)和信息检索中,被广泛用于特征提取和文本表示。以下是一个使用Python的scikit-learn库实现TF-IDF算法的简单示例,并展示如何将其应用于文本数据。
277 65
|
2月前
|
缓存 分布式计算 监控
优化算法和代码需要注意什么
【10月更文挑战第20天】优化算法和代码需要注意什么
22 0