豆包MarsCode AI 刷题 | 代码解读

1.英雄决斗次数2.子数组和最大

qq_30731313

738人浏览 · 2024-11-05 21:02:56

qq_30731313 · 2024-11-05 21:02:56 发布

个人学习笔记

转载：https://juejin.cn/post/7433440996271587379

英雄决斗的最大胜利次数

问题描述

小U和小F正在进行一场由 nn 轮组成的英雄决斗比赛。在每一轮中，小U和小F各自从他们的英雄队伍中选出一位英雄进行对决，英雄的能力值将决定比赛的胜负，能力值高者获胜。小U已经按照固定的能力顺序 1,2,3,…,n1,2,3,…,n 安排了他的英雄出场顺序。

小F希望通过调整他的英雄出场顺序，最大化他的获胜轮数。请帮助小 F 确定一个最佳的出场顺序，以获得最多的胜利。

输入说明

number: 一个整数，表示比赛的总轮数 nn。
heroes: 一个长度为 nn 的正整数数组，表示小 F 的每个英雄的能力值。

输出

返回一个整数，表示小 F 可以获得的最大胜利轮数。

def solution(number, heroes):
    # 小U的英雄能力值为1到n
    u_heroes = list(range(1, number + 1))
    
    # 排序小F的英雄能力值
    heroes.sort()

    # 初始化指针和胜利计数
    u_index = 0
    f_index = 0
    wins = 0
    
    while u_index < number and f_index < number:
        if heroes[f_index] > u_heroes[u_index]:
            # 小F可以赢得这一轮
            wins += 1
            u_index += 1  # 小U的指针向后移动
            f_index += 1  # 小F的指针向后移动
        else:
            # 小F无法赢得这一轮，尝试下一个英雄
            f_index += 1
    
    return wins

思路：

首先观察这道题，直观的思路就是小F的数字中大的要去打赢小U中大的，这样一个贪心的思路。这段代码的思路是通过比较两个玩家（小U和小F）拥有的英雄的能力值，来计算小F能够赢得多少轮比赛。

初始化英雄能力值：小U的英雄能力值是一个固定的范围，从1到number。而小F的英雄能力值是通过输入列表提供的。
排序小F的能力值：小F的英雄能力值被排序，以便后续的比较能够有效进行。
双指针策略：使用两个指针（u_index 和 f_index）分别指向小U和小F的英雄列表。指针的初始值为0，表示从各自的第一个英雄开始比较。
逐轮比较：在一个循环中，比较当前指向的两个英雄的能力值。如果小F的英雄能力值大于小U的英雄能力值，小F赢得这一轮，两个指针同时向后移动，表示这两个英雄都已被使用。如果小F的英雄能力值不够强，小F的指针仅向后移动，尝试下一个英雄，而小U的指针保持不变。
统计胜利轮次：通过维护一个胜利计数器，记录小F赢得的轮次。
结束条件：循环会在任一玩家的英雄用尽时结束，最后返回小F的胜利轮次。

总体逻辑：这个算法通过有效的排序和指针移动机制，实现了一个高效的比较过程，确保小F可以最大化其胜利的机会。通过对能力值的有序处理，避免了无谓的重复比较，提升了算法的效率。

子数组和的最大值问题

问题描述

小U手上有一个整数数组，他想知道如果从数组中删除任意一个元素后，能得到的长度为 k 的子数组和的最大值。你能帮小U计算出这个结果吗？
如果数组恰好为 k 个元素，那么不进行删除操作。

from collections import deque

def solution(n, k, nums):
    if k > n:
        return None  
    
    # 计算第一个窗口的和
    current_sum = sum(nums[:k])
    res = current_sum
    
    # 创建一个双端队列来维护当前窗口的最小值索引
    min_deque = deque()
    for i in range(k):
        while min_deque and nums[min_deque[-1]] >= nums[i]:
            min_deque.pop()
        min_deque.append(i)
    
    for i in range(k, n):
        # 更新结果
        res = max(res, current_sum + nums[i] - nums[min_deque[0]])
        
        # 移动窗口
        current_sum += nums[i] - nums[i - k]
        
        # 更新最小值
        while min_deque and min_deque[0] <= i - k:
            min_deque.popleft()
        
        while min_deque and nums[min_deque[-1]] >= nums[i]:
            min_deque.pop()
        min_deque.append(i)

    return res

思路：

输入参数：接收三个参数：n（数组长度），k（子数组长度），nums（整数数组）。
边界条件检查：如果 k 大于 n，返回 None，表示无法找到长度为 k 的子数组。
初始化：
- 计算第一个长度为 k 的子数组的和，存储在 current_sum 中，并初始化结果 res 为该和。
- 使用一个双端队列 min_deque 来维护当前窗口的最小值索引。
维护最小值：
- 在初始窗口中填充 min_deque，确保队列中的索引对应的值是单调递增的。
滑动窗口遍历：
- 从索引 k 开始，向右遍历数组。
- 在每一步中：
  - 更新结果 res 为当前窗口的和加上新的元素，减去当前窗口的最小值。
  - 移动窗口，更新 current_sum，通过添加新元素和去掉旧元素来调整和。
  - 更新 min_deque，确保它只包含当前窗口的有效索引，并且保持单调递增。
返回结果：最终返回 res，即所有可能的长度为 k 的子数组的最大和。