💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

1️⃣ 第一题计数相关，比较简单

2️⃣ 第二题看着很复杂，但是注意到数据范围，可以直接猜结论

3️⃣ 第三题是一个大整数的模拟，可以预处理前后缀来解决

🍑 01.K小姐的快乐时光

问题描述

K小姐是一位热爱生活的年轻女性。她每天都会记录自己的心情指数，用正数表示心情愉悦，0或负数表示心情不佳。现在，K小姐想知道在她的心情记录中，有多少个连续的时间段里她的心情一直保持愉悦。

输入格式

第一行包含一个整数 ，表示K小姐记录心情的天数。

第二行包含 个整数，用空格分隔，表示K小姐每天的心情指数。

输出格式

输出一个整数，表示K小姐心情愉悦的连续时间段的数量。

样例输入

4
1 2 0 3

样例输出

4

数据范围

• 
• 每个整数的绝对值不超过

题解

这道题目的核心是计算连续正数序列可以形成的区间数量。我们可以遍历整个数组，当遇到正数时，继续向后遍历；当遇到非正数时，计算之前连续正数序列可以形成的区间数量。

对于一个长度为 的连续正数序列，它可以形成的区间数量为 。这是因为我们可以选择序列的起始位置（ 种选择）和结束位置（从起始位置到序列末尾的任意位置），总共有 种可能。

算法步骤如下：

1. 初始化计数器 和起始位置 。
2. 遍历数组，对于每个元素：
   • 如果元素小于等于0，计算之前连续正数序列的区间数，更新 ，并将 设置为下一个位置。
   • 如果遍历到数组末尾，计算最后一个连续正数序列的区间数，更新 。
3. 返回 。

时间复杂度：，其中 是数组的长度。 空间复杂度：，只使用了常数额外空间。

参考代码

• Python

def count_happy_periods(n, moods):
    """
    计算K小姐心情愉悦的连续时间段数量
    
    Args:
    n (int): 记录天数
    moods (List[int]): K小姐每天的心情指数列表
    
    Returns:
    int: 心情愉悦的连续时间段数量
    """
    count = 0
    start = 0
    
    for i in range(n):
        if moods[i] <= 0:
            # 计算之前连续正数序列的区间数
            length = i - start
            count += (length * (length + 1)) // 2
            start = i + 1
    
    # 处理最后一个连续正数序列
    length = n - start
    count += (length * (length + 1)) // 2
    
    return count

# 读取输入
n = int(input())
moods = list(map(int, input().split()))

# 计算结果
result = count_happy_periods(n, moods)

# 输出结果
print(result)

• Java

import java.util.Scanner;

public class Main {
    /**
     * 计算K小姐心情愉悦的连续时间段数量
     * 
     * @param n 记录天数
     * @param moods K小姐每天的心情指数数组
     * @return 心情愉悦的连续时间段数量
     */
    public static int countHappyPeriods(int n, int[] moods) {
        int count = 0;
        int start = 0;
        
        for (int i = 0; i < n; i++) {
            if (moods[i] <= 0) {
                // 计算之前连续正数序列的区间数
                int length = i - start;
                count += (length * (length + 1)) / 2;
                start = i + 1;
            }
        }
        
        // 处理最后一个连续正数序列
        int length = n - start;
        count += (length * (length + 1)) / 2;
        
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] moods = new int[n];
        
        for (int i = 0; i < n; i++) {
            moods[i] = scanner.nextInt();
        }
        
        int result = countHappyPeriods(n, moods);
        System.out.println(result);
        
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <vector>

using namespace std;

/**
 * 计算K小姐心情愉悦的连续时间段数量
 * 
 * @param n 记录天数
 * @param moods K小姐每天的心情指数向量
 * @return 心情愉悦的连续时间段数量
 */
int countHappyPeriods(int n, const vector<int>& moods) {
    int count = 0;
    int start = 0;
    
    for (int i = 0; i < n; i++) {
        if (moods[i] <= 0) {
            // 计算之前连续正数序列的区间数
            int length = i - start;
            count += (length * (length + 1)) / 2;
            start = i + 1;
        }
    }
    
    // 处理最后一个连续正