[leetcode/lintcode 题解] 阿里巴巴面试真题:数组评分

简介: [leetcode/lintcode 题解] 阿里巴巴面试真题:数组评分

描述
有一个数组nums,以及三个正整数k,u,l。 对于nums的所有长为k的子段,如果它的总和小于u,就得1分,如果它的总和大于l,就扣1分。 请求出最终能获得多少分?

nums的长度为n,1≤n≤105。 numsi为nums中的元素,0≤numsi≤105。 1≤k≤n。 1≤u≤l≤1010。 最后的得分可以是负数。 下列样例中,[0,1,2,3,4]所有的长为 2 的子段分别是[0,1],[1,2],[2,3],[3,4],它们的和分别为1,3,5,7。其中 1<2,加一分,7>5,扣一分。总计0分。

在线评测地址:领扣题库官网

样例1
样例输入:
nums = [0, 1, 2, 3, 4]
k = 2
u = 2
l = 5

样例输出:
0

解题思路
如果每次枚举起点,暴力计算求解前 kk 个数的和的话,时间复杂度会达到 O(N2)O(N2),会超时。所以暴力法不可行。
对于一个长为 kk 的子段,我们可以看作一个长度为 kk 的窗口。对于两个起点相邻的窗口,我们可以在 O(1)O(1) 时间内转移他们的和。如窗口 x,x+k−1 到 x+1,x+k,只需减去第 xx 个值,并加上第 x+kx+k 个值即可。

代码思路

  1. 计算前 kk 个数字的和,更新分数。
  2. 遍历后 n−kn−k 个数,当遍历到第 ii 个数时,减去第 i−ki−k 个数,更新答案。

复杂度分析
设数组的长度为 NN。
时间复杂度

  • 遍历一遍数组,复杂度为 O(N)O(N)。

空间复杂度

  • 只需额外 O(1)O(1) 的空间记录分数和子段和。

源代码

public class Solution {
    /**
     * @param nums: the array to be scored.
     * @param k: the requirement of subarray length.
     * @param u: if the sum is less than u, get 1 score.
     * @param l: if the sum is greater than l, lose 1 score.
     * @return: return the sum of scores for every subarray whose length is k.
     */
    public int arrayScore(List<Integer> nums, int k, long u, long l) {
        // 子段的和,这里用long是因为和最大为10^5 * 10^5,用int会溢出
        long sumOfSubarray = 0;
        int score = 0;
        int n = nums.size();
        
        // 先计算前k个的值
        for (int i = 0; i < k; i++) {
            sumOfSubarray += nums.get(i);
        }
        if (sumOfSubarray < u) {
            score++;
        }
        if (sumOfSubarray > l) {
            score--;
        }

        // 剩下的,窗口每次向右移动,加入第 i 个数,弹出第 i - k 个
        for (int i = k; i < n; i++) {
            sumOfSubarray += nums.get(i);
            sumOfSubarray -= nums.get(i - k);
            if (sumOfSubarray < u) {
                score++;
            }
            if (sumOfSubarray > l) {
                score--;
            }
        }
        
        return score;
    }
}

更多题解参考:九章官网solution

相关文章
|
7月前
|
C语言
【Amazon 面试题1】一个数组,里面得数出现的次数是偶数次,只有一个数出现的次数是奇数次,找出那个出现奇数次的数
本文介绍了解决Amazon面试题的一种方法,即在一个所有数字出现次数都是偶数,除了一个数字出现奇数次的数组中,利用异或运算的性质找出出现奇数次的数字,并提供了C语言实现的代码示例。
92 1
|
7月前
|
Java
Java 基础语法-面试题(54-63道)(数组+类+包)
Java 基础语法-面试题(54-63道)(数组+类+包)
58 16
|
7月前
|
开发者 索引 Python
这些年背过的面试题——LeetCode
本文是技术人面试系列LeetCode篇,一文带你详细了解,欢迎收藏!
|
8月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
9月前
|
开发框架 .NET
技术好文共享:面试题:找出数组中只出现一次的2个数(异或的巧妙应用)(出现3次)
技术好文共享:面试题:找出数组中只出现一次的2个数(异或的巧妙应用)(出现3次)
|
9月前
|
数据采集 算法 数据挖掘
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
|
6月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
7月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
82 6
|
7月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
165 2
|
4月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
115 1