豆包大模型 MarsCode AI 刷题专栏 001

001.找单独的数

难度：易

问题描述

在一个班级中，每位同学都拿到了一张卡片，上面有一个整数。有趣的是，除了一个数字之外，所有的数字都恰好出现了两次。现在需要你帮助班长小C快速找到那个拿了独特数字卡片的同学手上的数字是什么。

要求：

  1. 设计一个算法，使其时间复杂度为 O(n)，其中 n 是班级的人数。
  2. 尽量减少额外空间的使用，以体现你的算法优化能力。

测试样例

样例1：

输入：cards = [1, 1, 2, 2, 3, 3, 4, 5, 5]
输出：4
解释：拿到数字 4 的同学是唯一一个没有配对的。

样例2：

输入：cards = [0, 1, 0, 1, 2]
输出：2
解释：数字 2 只出现一次，是独特的卡片。

样例3：

输入：cards = [7, 3, 3, 7, 10]
输出：10
解释：10 是班级中唯一一个不重复的数字卡片。

约束条件

  • 1 ≤ cards.length ≤ 1001
  • 0 ≤ cards[i] ≤ 1000
  • 班级人数为奇数
  • 除了一个数字卡片只出现一次外，其余每个数字卡片都恰好出现两次

思路提示

要解决这个问题，我们可以利用异或（XOR）运算的特性。异或运算有以下几个关键性质：

  1. 相同数字异或结果为0：a ^ a = 0
  2. 任何数字与0异或结果为该数字本身：a ^ 0 = a
  3. 异或运算满足交换律和结合律：a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

基于这些性质，我们可以设计一个算法来找到那个唯一的独特数字：

解题思路

  1. 初始化一个变量 unique_number 为0。
  2. 遍历数组中的每一个数字，将 unique_number 与当前数字进行异或运算。
  3. 最终，unique_number 将只包含那个独特的数字，因为所有成对的数字都会通过异或运算相互抵消。

算法步骤

  1. 初始化 unique_number = 0。
  2. 遍历数组 cards 中的每一个数字 card：
    • 更新 unique_number 为 unique_number ^ card。
  3. 返回 unique_number。

时间复杂度

  • **O(n)**：我们只需要遍历数组一次。

空间复杂度

  • **O(1)**：我们只使用了常数级别的额外空间。

通过这种方式，我们可以在不使用额外空间的情况下，以线性时间复杂度找到那个独特的数字。

MarsCode AI答案

Python:

def solution(cards):
    # 初始化结果变量为0
    result = 0
    
    # 遍历数组中的每一个元素
    for card in cards:
        # 将结果与当前元素进行异或运算
        result ^= card
    
    # 返回最终结果
    return result

if __name__ == "__main__":
    # 添加你的测试用例
    print(solution([1, 1, 2, 2, 3, 3, 4, 5, 5]) == 4)
    print(solution([0, 1, 0, 1, 2]) == 2)

Go:

package main

import "fmt"

func solution(cards []int) int {
    result := 0
    for _, card := range cards {
        result ^= card
    }
    return result
}

func main() {
    fmt.Println(solution([]int{1, 1, 2, 2, 3, 3, 4, 5, 5}) == 4)
    fmt.Println(solution([]int{0, 1, 0, 1, 2}) == 2)
    fmt.Println(solution([]int{7, 3, 3, 7, 10}) == 10)
}

Rust:

fn solution(cards: Vec<i32>) -> i32 {
    // 使用异或运算来找到唯一的数字
    let mut unique_number = 0;
    for &card in &cards {
        unique_number ^= card;
    }
    unique_number
}

fn main() {
    // 添加你的测试用例
    println!("{}", solution(vec![1, 1, 2, 2, 3, 3, 4, 5, 5]) == 4);
    println!("{}", solution(vec![0, 1, 0, 1, 2]) == 2);
    println!("{}", solution(vec![7, 3, 3, 7, 10]) == 10);
}

 

002.徒步旅行中的补给问题

难度：中

问题描述

小R正在计划一次从地点A到地点B的徒步旅行，总路程需要 N 天。为了在旅途中保持充足的能量，小R每天必须消耗1份食物。幸运的是，小R在路途中每天都会经过一个补给站，可以先购买完食物后再消耗今天的1份食物。然而，每个补给站的食物每份的价格可能不同，并且小R在购买完食物后最多只能同时携带 K 份食物。

现在，小R希望在保证每天食物消耗的前提下，以最小的花费完成这次徒步旅行。你能帮助小R计算出最低的花费是多少吗？

**输入 **

  • n 总路程需要的天数
  • k 小R最多能同时携带食物的份数
  • data[i] 第i天补给站每份食物的价格

**输出 **

  • 返回完成这次徒步旅行的最小花费

**约束条件 **

  • 1 < n,k < 1000
  • 1 < data[i] < 10000

测试样例

样例1：

输入：n = 5 ,k = 2 ,data = [1, 2, 3, 3, 2]
输出：9

样例2：

输入：n = 6 ,k = 3 ,data = [4, 1, 5, 2, 1, 3]
输出：9

样例3：

输入：n = 4 ,k = 1 ,data = [3, 2, 4, 1]
输出：10

问题理解

小R每天需要消耗1份食物，并且每天经过一个补给站，可以购买食物。小R最多能携带 K 份食物。我们需要找到一种策略，使得小R在旅途中花费最少。

数据结构选择

我们可以使用一个数组来存储每天的食物价格，并且使用一个变量来记录当前携带的食物数量。

算法步骤

  1. 初始化：

    • 设置一个变量 current_food 表示当前携带的食物数量，初始为0。
    • 设置一个变量 total_cost 表示总花费，初始为0。

  2. 遍历每一天：

    • 如果当前携带的食物数量 current_food 大于0，则消耗1份食物。
    • 如果当前携带的食物数量 current_food 为0，则需要购买食物。
    • 在购买食物时，需要考虑当前补给站的价格和未来几天的价格，以决定购买多少份食物。

  3. 购买策略：

    • 在购买食物时，应该尽量购买未来几天价格较低的食物，以减少总花费。
    • 可以使用一个滑动窗口来找到未来几天内的最低价格，并决定购买的数量。

思路说明

题目要求在给定的天数 N 和最大携带食物量 K 的限制下，计算出完成徒步旅行所需的最小花费。每天经过的补给站食物价格不同，且每天必须消耗1份食物。我们可以通过维护一个单调递增的双端队列来记录当前窗口内的最小价格，从而在每次购买食物时选择最便宜的选项。通过滑动窗口的方式，逐步计算出每天的最小花费，最终得到总的最小花费。

解题过程

  1. 初始化：创建一个双端队列 mins 用于存储当前窗口内的最小价格及其对应的天数。初始化结果 result 为0。
  2. 遍历每一天：
    • 维护单调队列：在每次遍历中，首先检查队列 mins 的末尾元素，如果其价格大于当前天的价格，则将其弹出，直到队列为空或队列末尾元素的价格小于等于当前天的价格。然后将当前天的价格和天数加入队列。
    • 滑动窗口：检查队列 mins 的头部元素，如果其对应的天数已经不在当前窗口内（即 mins[0][0] <= j - k），则将其弹出。
    • 计算花费：将当前窗口内的最小价格（即队列头部元素的价格）累加到 result 中。
  3. 返回结果：遍历结束后，result 即为完成徒步旅行的最小花费。

复杂度分析

  • 时间复杂度：O(N)，其中 N 是天数。我们只需要遍历每一天，并且在每次遍历中，队列的插入和删除操作都是 O(1) 的时间复杂度。
  • 空间复杂度：O(K)，其中 K 是最大携带食物量。我们使用了一个双端队列来存储当前窗口内的最小价格，其最大长度为 K。

知识点扩展

  • 双端队列（deque）：双端队列是一种允许在两端进行插入和删除操作的队列。在本题中，我们使用双端队列来维护当前窗口内的最小价格，通过在队列两端进行操作，可以高效地维护单调性。
  • 单调队列：单调队列是一种特殊的队列，其内部元素保持单调递增或单调递减的顺序。在本题中，我们使用单调递增队列来记录当前窗口内的最小价格，从而在每次购买食物时选择最便宜的选项。
  • 滑动窗口：滑动窗口是一种常见的算法技巧，用于在数组或列表中维护一个固定大小的窗口，并对其进行操作。在本题中，我们通过滑动窗口的方式，逐步计算出每天的最小花费。

MarsCode AI答案

Python:

from collections import deque

def solution(n: int, k: int, data: list) -> int:
    assert n == len(data)
    assert k < n

    mins = deque()
    result = 0

    for j in range(n):
        while len(mins) > 0 and mins[-1][1] > data[j]:
            mins.pop()
        mins.append([j, data[j]])
        while mins[0][0] <= j - k:
            mins.popleft()
        result += mins[0][1]

    return result


if __name__ == '__main__':
    print(solution(n = 5 ,k = 2 ,data = [1, 2, 3, 3, 2]) == 9)
    print(solution(n = 6 ,k = 3 ,data = [4, 1, 5, 2, 1, 3]) == 9)
    print(solution(n = 4 ,k = 1 ,data = [3, 2, 4, 1]) == 10)

Go:

package main

import (
    "fmt"
    "math"
)

func solution(n int, k int, data []int) int {
    // 初始化dp数组，dp[i]表示在第i天结束时的最小花费
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = math.MaxInt32 // 初始化为一个很大的值
    }
    dp[0] = 0 // 第0天不需要花费

    // 填充dp数组
    for i := 1; i <= n; i++ {
        for j := i - 1; j >= max(0, i-k); j-- {
            // 计算在第j天购买食物，然后走到第i天的总花费
            cost := dp[j] + data[i-1] * (i - j)
            if cost < dp[i] {
                dp[i] = cost
            }
        }
    }

    return dp[n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    fmt.Println(solution(5, 2, []int{1, 2, 3, 3, 2}) == 9)
    fmt.Println(solution(6, 3, []int{4, 1, 5, 2, 1, 3}) == 9)
    fmt.Println(solution(4, 1, []int{3, 2, 4, 1}) == 10)
}

Rust:

use std::collections::VecDeque;

fn solution(n: usize, k: usize, data: Vec<usize>) -> usize {
    assert_eq!(n, data.len());
    assert!(k < n);

    let mut mins: VecDeque<(usize, usize)> = VecDeque::new();
    let mut result = 0;

    for j in 0..n {
        while let Some(&(_, price)) = mins.back() {
            if price > data[j] {
                mins.pop_back();
            } else {
                break;
            }
        }
        mins.push_back((j, data[j]));

        while let Some(&(index, _)) = mins.front() {
            if index <= j.saturating_sub(k) {
                mins.pop_front();
            } else {
                break;
            }
        }

        result += mins.front().unwrap().1;
    }

    result
}

fn main() {
    println!("{}", solution(5, 2, vec![1, 2, 3, 3, 2]) == 9);
    println!("{}", solution(6, 3, vec![4, 1, 5, 2, 1, 3]) == 9);
    println!("{}", solution(4, 1, vec![3, 2, 4, 1]) == 10);
}

代码解释

  1. VecDeque: Rust中的VecDeque类似于Python中的deque，支持高效的头部和尾部操作。
  2. assert_eq! 和 assert!: Rust中的断言函数，用于确保输入的合法性。
  3. while let: Rust中的模式匹配语法，用于简化循环条件。
  4. saturating_sub: Rust中的饱和减法，防止下溢。

来源：https://www.marscode.cn/practice

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/982421.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

迭代器模式：遍历集合的艺术

迭代器模式：遍历集合的艺术

文章目录 什么是迭代器模式&#xff1f;现实中的例子迭代器模式的结构代码示例1. 定义Iterator接口2. 实现ConcreteIterator3. 定义Aggregate接口4. 实现ConcreteAggregate5. 客户端代码输出结果 迭代器模式的优缺点优点缺点 总结 在软件开发中&#xff0c;我们经常需要遍历集合…
阅读更多...
通用文件模型

通用文件模型

一、通用文件模型 通常一个完整的Linux系统有数千到数百万个文件组成&#xff0c;文件中存储了程序、数据和各种信息。层次化的目录结构用于对文件进行编排和分组。 1.ReiserFS(新型的文件系统) -->Reiser4 它通过一种与众不同的方式----完全平衡树来容纳数据&#xff0c;包…
阅读更多...
DeepSeek + 飞书多维表格搭建你的高效工作流

DeepSeek + 飞书多维表格搭建你的高效工作流

众所周知&#xff0c;大模型DeepSeek擅长于处理大规模语言模型推理任务&#xff0c;特别是在成本降低和思维链推理方面表现出色‌&#xff0c;我们一般把大模型必做我们的大脑&#xff0c;但是一个人不能只有大脑&#xff0c;还需要其他输入输出以及操作支配的眼耳鼻嘴手足等。…
阅读更多...
微服务架构下的 Node.js

微服务架构下的 Node.js

Node.js 在微服务架构中的特点 轻量级和高效性 Node.js 以其轻量级和高效的特点&#xff0c;非常适合构建微服务架构。它具有事件驱动和非阻塞 I/O 模型&#xff0c;能够在处理高并发请求时表现出色。这意味着 Node.js 可以同时处理大量的并发连接&#xff0c;而不会因为阻塞…
阅读更多...
用DeepSeek-R1-Distill-data-110k蒸馏中文数据集 微调Qwen2.5-7B-Instruct！

用DeepSeek-R1-Distill-data-110k蒸馏中文数据集 微调Qwen2.5-7B-Instruct！

下载模型与数据 模型下载&#xff1a; huggingface&#xff1a; Qwen/Qwen2.5-7B-Instruct HF MirrorWe’re on a journey to advance and democratize artificial intelligence through open source and open science.https://hf-mirror.com/Qwen/Qwen2.5-7B-Instruct 魔搭&a…
阅读更多...
flask-定时任务

flask-定时任务

文章目录 前言一、APScheduler是什么二、APScheduler 主要功能&#xff1a;三、主要组成部分&#xff1a;四、典型使用场景&#xff1a;五、具体使用1.安装 APScheduler2.假设我们有一个需要五分钟请求一次http接口的任务1.定义一个scheduler.py去专门处理定时2.启动文件处理3.…
阅读更多...
Python的Pandas和matplotlib库：让数据可视化贼简单

Python的Pandas和matplotlib库：让数据可视化贼简单

在数据爆炸的时代&#xff0c;数据可视化已成为数据分析的关键环节。Python 作为强大的编程语言&#xff0c;拥有众多用于数据可视化的库&#xff0c;而 pandas 库在其中扮演着重要角色。它不仅能高效处理和分析数据&#xff0c;还具备强大的数据可视化功能&#xff0c;让我们轻…
阅读更多...
rabbitmq版本升级并部署高可用

rabbitmq版本升级并部署高可用

RabbitMQ版本升级 先检查是否已经安装rabbitmq rpm -qa|grep rabbitmq|wc -l //如果结果是0&#xff0c;表示没有安装 rpm -e --nodeps $(rpm -qa|grep rabbitmq) //如安装了&#xff0c;则进行卸载 先检查是否已经安装erlang rpm -qa|grep erlang|wc -l //如果结果…
阅读更多...
Electron-Forge + Vue3 项目初始化

Electron-Forge + Vue3 项目初始化

本人对Electron的浅薄理解如下图所示 由上图可以&#xff0c;如果你需要开发一个electron应用&#xff0c;你得具备基本的前端开发经验。对于electron相关的知识&#xff0c;建议先了解下基本的窗口操作&#xff0c;比如新建窗口、关闭窗口等简单的操作&#xff0c;这些内容在…
阅读更多...
pinginfoview网络诊断工具中文版

pinginfoview网络诊断工具中文版

介绍 pinginfoview中文版本是一款实用的网络诊断工具&#xff0c;它专为中文用户设计&#xff0c;提供了方便易用的界面&#xff0c;使得在Windows环境下进行ping测试变得更加简单。该工具是由NirSoft开发的一款免费的桌面应用程序&#xff0c;尽管官方可能并未正式发布中文版…
阅读更多...
DeepSeek R1 + 飞书机器人实现AI智能助手

DeepSeek R1 + 飞书机器人实现AI智能助手

效果 TFChat项目地址 https://github.com/fish2018/TFChat 腾讯大模型知识引擎用的是DeepSeek R1&#xff0c;项目为sanic和redis实现&#xff0c;利用httpx异步处理流式响应&#xff0c;同时使用buffer来避免频繁调用飞书接口更新卡片的网络耗时。为了进一步减少网络IO消耗&…
阅读更多...
Go学习笔记：基础语法3

Go学习笔记：基础语法3

1. 常量 Go语言中的常量使用关键字const定义&#xff0c;用于存储不会改变的数据&#xff0c;常量是在编译时被创建的&#xff0c;即使定义在函数内部也是如此&#xff0c;并且只能是布尔型、数字型&#xff08;整数型、浮点型和复数&#xff09;和字符串型。 由于编译时的限…
阅读更多...
010---基于Verilog HDL的分频器设计

010---基于Verilog HDL的分频器设计

文章目录 摘要一、时序图二、程序设计2.1 rtl2.2 tb 三、仿真分析四、实用性 摘要 文章为学习记录。绘制时序图&#xff0c;编码。通过修改分频值参数&#xff0c;实现一定范围分频值内的任意分频器设计。 一、时序图 二、程序设计 2.1 rtl module divider #(parameter D…
阅读更多...
EX_25/3/6

EX_25/3/6

1&#xff1a;是进度条通过线程自己动起来 myThread.h #ifndef MYTHREAD_H #define MYTHREAD_H#include <QThread>class myThread : public QThread {Q_OBJECT public:myThread(QObject* partennullptr);signals:void sig(int value);protected:void run();private:int…
阅读更多...
客户端及时通讯系统（1）

客户端及时通讯系统（1）

编写核心数据结构 一、核心数据结构介绍二、将本地新项目推送到gitee已有仓库上三、代码实现3.1 核心数据结构成员变量设计和工具类设计 一、核心数据结构介绍 1&#xff09;用户信息&#xff08;UserTnfo&#xff09; 用户的属性 2&#xff09;会话信息&#xff08;ChatSess…
阅读更多...
针对半导体行业招聘系统有哪些？

针对半导体行业招聘系统有哪些？

近年来&#xff0c;全球半导体产业迎来爆发式增长&#xff0c;芯片设计、制造、封装等环节对高技能人才的需求急剧攀升。然而&#xff0c;行业面临多重挑战&#xff1a;技术迭代快导致岗位要求动态变化、优质人才争夺激烈、传统招聘模式效率低下。以某头部半导体企业为例&#…
阅读更多...
汽车智能钥匙中PKE低频天线的作用

汽车智能钥匙中PKE低频天线的作用

PKE&#xff08;Passive Keyless Entry&#xff09;即被动式无钥匙进入系统&#xff0c;汽车智能钥匙中PKE低频天线在现代汽车的智能功能和安全保障方面发挥着关键作用&#xff0c;以下是其具体作用&#xff1a; 信号交互与身份认证 低频信号接收&#xff1a;当车主靠近车辆时…
阅读更多...
清华大学DeepSeek赋能家庭教育【附下载链接】

清华大学DeepSeek赋能家庭教育【附下载链接】

核心要点&#xff1a; DeepSeek通过基础模型&#xff08;V3&#xff09;、深度思考模型&#xff08;R1&#xff09;及联网模型&#xff0c;为家庭教育提供分层支持&#xff1a;V3用于作业辅导&#xff0c;R1培养批判性思维&#xff0c;联网模型助力探究性学习。家长需遵循目标导…
阅读更多...
是德科技十周年：以创新丈量未来，用科技赋能世界

是德科技十周年：以创新丈量未来，用科技赋能世界

是德科技成立十周年&#xff0c;以全球测试测量领域领军者的姿态&#xff0c;书写了一部突破与创新的发展史诗。作为从惠普、安捷伦深厚技术积淀中孕育而生的行业标杆&#xff0c;十年来是德科技始终站在科技浪潮之巅&#xff0c;构建起覆盖5G通信、人工智能、汽车电子、量子计…
阅读更多...
Springboot 梳理

Springboot 梳理

一、Springboot 特性 方便创建可独立运行的spring应用程序直接内嵌Tomcat等服务简化了项目的构建配置为spring及第三方库提供自动配置提供生产级特性无需生成代码或者进行xml配置 二、四大核心 自动配置起步依赖命令行界面Actuator - 生成级的特性 三、自动配置的实现原理 …
阅读更多...
最新文章

Copyright @ 2022~2023