每日一题(day5)

简介: 每日一题(day5)

前言

💫你好,我是辰chen,一个正在考研途中的sophomore dog😖

💫目前每日一题主要来自于 leetcode,当然也可能来自洛谷或其他刷题平台,每日一题专栏地址:每日一题

💫欢迎大家的关注,我的博客主要关注于考研408以及AIoT的内容


🌟 每日一题我会给出两种代码,C 版以及 Python版,刷题的目的是为了考研的算法题以及机试(或手写代码)

🌟这也是为什么不用C++ 而用 C ,Python版代码是为了提高语言熟练度(以后开发大概率用的是 Python

🌟 坚持打卡!踏踏实实走好每一步


以下的几个专栏是本人比较满意的专栏(大部分专栏仍在持续更新),欢迎大家的关注:

💥ACM-ICPC算法汇总【基础篇】

💥ACM-ICPC算法汇总【提高篇】

💥AIoT(人工智能+物联网)

💥考研

💥CSP认证考试历年题解



👊每日一句:天行健,君子以自强不息。

大家做完可以在评论区打卡留言✒️,形成良好的学习氛围,一起进步!

LeetCode 53. 最大子数组和

题目描述:

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

示例 1:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

示例 2:

输入:nums = [1]
输出:1

示例 3:

输入:nums = [5,4,-1,7,8]
输出:23

image.png

C版AC代码:

int maxSubArray(int* nums, int numsSize){
    int b = nums[0], a = 0;
    int res = nums[0];
    for (int i = 1; i < numsSize; i ++ ){
        a = fmax(b + nums[i], nums[i]);
        res = fmax(res, a);
        b = a;
    }
    return res;
}

Python版AC代码:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        a, b, n, res = 0, nums[0], len(nums), nums[0]
        for i in range(1, n):
            a = max(b + nums[i], nums[i])
            res = max(res, a)
            b = a
        return res

LeetCode 918. 环形子数组的最大和

题目描述:

image.png

示例 1:

输入:nums = [1,-2,3,-2]
输出:3
解释:从子数组 [3] 得到最大和 3

示例 2:

输入:nums = [5,-3,5]
输出:10
解释:从子数组 [5,5] 得到最大和 5 + 5 = 10

示例 3:

输入:nums = [3,-2,2,-3]
输出:3
解释:从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3

image.png

思路: 有两种可能,第一种即为答案在数组中间,那么就转成了本博客的第一题;第二种即为答案在数组两边,那么我们就用数组的总和减最小子序和,其中会出现特殊情况即最小子序和 == 数组的和,这种情况下数组全为负数或全为0,那么此时我们输出数组中的最大值即可。

C版AC代码:

int maxSubarraySumCircular(int* nums, int numsSize){
    int pastf = nums[0], pastg = nums[0];
    int nowf = 0x3f3f3f3f, nowg = -0x3f3f3f3f;
    int res = nums[0], sum = nums[0], sumin = nums[0], sumax = nums[0];
    for (int i = 1; i < numsSize; i ++ ){
        sum += nums[i];
        nowf = fmax(pastf + nums[i], nums[i]);
        nowg = fmin(pastg + nums[i], nums[i]);
        res = fmax(res, nowf);
        sumin = fmin(sumin, nowg);   // 子数组的最小值
        sumax = fmax(sumax, nums[i]);   // 数组中的最大值
        pastf = nowf, pastg = nowg;
    }
    // 如果有 sum - sumin == 0, 证明数组全为负,那么就输出整个数组中的最大值
    res = fmax(res, sum - sumin == 0 ? sumax : sum - sumin);
    return res;
}

Python版AC代码:

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        nowf, pastf, nowg, pastg = -0x3f3f3f3f, nums[0], 0x3f3f3f3f, nums[0]
        n, res, numin, numax, suml = len(nums), nums[0], nums[0], nums[0], nums[0]
        for i in range(1, n):
            # 动态规划
            nowf = max(pastf + nums[i], nums[i])
            nowg = min(pastg + nums[i], nums[i])
            # 更新最大值,最小值,总和
            res = max(res, nowf)
            numax = max(numax, nums[i])
            numin = min(numin, nowg)
            suml += nums[i]
            pastf, pastg = nowf, nowg
        if suml - numin == 0:
            res = max(res, numax)
        else:
            res = max(res, suml - numin)
        return res


目录
相关文章
|
11月前
|
存储 前端开发 数据可视化
在实际项目中,如何选择使用 Flux 架构或传统的 MVC 架构
在实际项目中选择使用Flux架构或传统MVC架构时,需考虑项目复杂度、团队熟悉度和性能需求。Flux适合大型、高并发应用,MVC则适用于中小型、逻辑简单的项目。
|
11月前
|
存储 监控 测试技术
|
12月前
|
Rust 前端开发 iOS开发
打造《黑神话:悟空》壁纸软件:使用 Tauri 快速上手
本文首发于微信公众号“前端徐徐”。作者分享了如何仅用半天时间实现《黑神话:悟空》桌面壁纸软件的过程,并展示了实际效果。文中详细介绍了使用 Tauri 开发跨平台桌面应用的核心流程与关键技术,包括下载壁纸、更换壁纸以及前后端交互等细节。此外,还提供了源码和下载链接供读者体验。
171 0
打造《黑神话:悟空》壁纸软件:使用 Tauri 快速上手
|
数据可视化 数据挖掘 Go
GOplot|宝藏R包,拯救你的GO富集结果,杜绝平庸的条形图
`GOplot`是一款R包,专注于GO富集分析的可视化,提供多种图表类型如GOBar、GOBubble、GOCircle、GOChord和GOVenn等。这些函数允许用户轻松修改参数,定制颜色、大小和排序,实现数据的直观展示。示例代码展示了如何使用这些功能创建不同类型的图形,并提到了一个配套的shiny应用。`GOplot`简化了复杂的数据可视化过程,适合快速高效地展示差异分析结果。
573 0
ThinkPHP6模型中的获取器,修改器及搜索器的简单使用
本文介绍了ThinkPHP6模型中的获取器、修改器和搜索器的使用方法。获取器用于对模型数据进行自动处理,修改器用于处理模型设置的数据,搜索器用于封装字段的查询条件表达式。文章通过示例代码展示了如何在模型中定义和使用这些方法,以及如何通过控制器调用模型方法进行数据操作。
|
网络架构
如何在路由器上配置静态路由表?
【8月更文挑战第17天】如何在路由器上配置静态路由表?
1336 2
|
Java Spring
Spring属性注入的三种方式(超详细)
Spring属性注入的三种方式(超详细)
|
人工智能 算法
阿里云人工智能平台 PAI 扩散模型加速采样算法论文入选 CIKM 2023
近日CIKM 2023上,阿里云人工智能平台PAI和华东师范大学陈岑副教授团队主导的扩散模型加速采样算法论文《Optimal Linear Subspace Search: Learning to Construct Fast and High-Quality Schedulers for Diffusion Models》入选。此次入选意味着阿里云人工智能平台 PAI自研的扩散模型算法和框架达到了全球业界先进水平,获得了国际学者的认可,展现了中国人工智能技术创新在国际上的竞争力。
|
数据采集 机器学习/深度学习 存储
新闻报道的未来:自动化新闻生成与爬虫技术
自动化新闻生成是一种利用自然语言处理和机器学习技术,从结构化数据中提取信息并生成新闻文章的方法。它可以实现大规模、高效、多样的新闻内容生产。然而,要实现自动化新闻生成,首先需要获取可靠的数据源。这就需要使用爬虫技术,从互联网上抓取相关的新闻信息。本文将介绍如何使用Scrapy库,一个强大的Python爬虫框架,结合代理IP技术,从新浪新闻网站获取数据,并提供完整的代码示例和相关配置。
325 0
|
编解码 iOS开发 UED
IINA使用
IINA使用