CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

    • 前缀和问题

    • 差分

      • 1109 - 航班预订统计
        • 📃 题目描述
        • 🔔 解题思路
        • 💥 复杂度分析
    • 树状数组

    • 线段树

  • 排序

  • 回溯算法

  • 贪心算法

  • 动态规划

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 区间求和问题
  • 差分
小牛肉
2022-09-23
目录

1109 - 航班预订统计

# 📃 题目描述

题目链接:1109. 航班预订统计 (opens new window)

# 🔔 解题思路

换一种思路理解题意,将问题转换为:某公交车共有 n 站,第 i 条记录 bookings[i] = [i, j, k] 表示在 i 站上车 k 人,乘坐到 j 站,在 j+1 站下车,需要按照车站顺序返回每一站车上的人数

根据 1 的思路,定义 counter[] 数组记录每站的人数变化,counter[i] 表示第 i 站。遍历 bookings[]:bookings[i] = [i, j, k] 表示在 i 站增加 k 人即 counters[i] += k,在 j+1 站减少 k 人即 counters[j + 1] -= k

遍历(整理)counter[] 数组,得到每站总人数: 每站的人数为前一站人数加上当前人数变化 counters[i] += counters[i - 1]

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] gap = new int[n + 2];
        gap[0] = 0;

        for (int[] booking : bookings) {
            int from = booking[0];
            int end = booking[1];
            int count = booking[2];

            // 在 from 上车 count 人
            gap[from] += count;
            // 在 end + 1 下车 count 人
            gap[end + 1] -= count;
        }

        for (int i = 1; i <= n; i ++) {
            gap[i] += gap[i - 1];
        }

        return Arrays.copyOfRange(gap, 1, n + 1);

    }
}

# 💥 复杂度分析

  • 空间复杂度:
  • 时间复杂度:

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
除自身以外数组的乘积
排序理论基础

← 除自身以外数组的乘积 排序理论基础→

最近更新
01
02
线上环境 CPU 使用率飙升如何快速排查?
03-05
03
面试官再跟你说中国没有根服务器,雪人计划让他了解下
02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式