当前位置: 首页 > news >正文

2023-12-16:用go语言,给定整数数组arr,求删除任一元素后, 新数组中长度为k的子数组累加和的最大值。 来自字节。

2023-12-16:用go语言,给定整数数组arr,求删除任一元素后,

新数组中长度为k的子数组累加和的最大值。

来自字节。

答案2023-12-16:

来自左程云。

灵捷3.5

大体步骤如下:

算法 maxSum1 分析:

1.计算输入数组 arr 的长度 n。

2.如果 n <= k,则返回 0。

3.初始化 ans 为 int 类型的最小值(math.MinInt32)。

4.对于每个数组元素 arr[i],执行以下步骤:

4.a.删除第 i 个元素,得到新的数组 rest。

4.b.计算新数组 rest 的长度为 k 的子数组累加和的最大值,使用函数 lenKmaxSum(rest, k)。

4.c.将 ans 更新为 ans 和 lenKmaxSum(rest, k) 中的较大值。

5.返回 ans。

算法 delete 分析:

1.计算输入数组 arr 的长度 len0,即 len(arr) - 1。

2.创建一个长度为 len0 的新数组 ans。

3.初始化索引 i 为 0。

4.对于数组 arr 的每个元素 arr[j],执行以下步骤:

4.a.如果 j 不等于给定的索引 index,则将 arr[j] 赋值给 ans[i]。

4.b.将 i 递增 1。

5.返回新数组 ans。

算法 lenKmaxSum 分析:

1.计算输入数组 arr 的长度 n。
2.初始化 ans 为 int 类型的最小值(math.MinInt32)。
3.对于每个起始位置 i,从 i 到 i + (n - k) 执行以下步骤:
3.a.初始化 cur 为 0。
3.b.对于每个元素 arr[j],从 i 开始计数,执行以下步骤,直到计数 cnt 达到 k:
3.b. i.将 arr[j] 加到 cur 中。
3.b. ii.增加计数 cnt。
3.c.将 ans 更新为 ans 和 cur 中的较大值。
4.返回 ans。

算法 maxSum2 分析:

1.计算输入数组 arr 的长度 n。

2.如果 n <= k,则返回 0。

3.创建一个长度为 n 的窗口(window)数组。

4.初始化左指针 l 和右指针 r 为 0。

5.初始化变量 sum 为 0,并使用 int64 类型存储。

6.初始化 ans 为 int 类型的最小值(math.MinInt32)。

7.对于每个索引 i,从 0 到 n-1 执行以下步骤:

7.a.当窗口不为空且窗口中最后一个元素 arr[window[r-1]] 大于等于当前元素 arr[i] 时,移动右指针 r 减小窗口大小直至条件不满足。

7.b.将当前索引 i 添加到窗口中,即 window[r] = i,并递增右指针 r。

7.c.将当前元素 arr[i] 加到 sum 中。

7.d.如果 i >= k,说明窗口大小已达到 k,执行以下步骤:

7.d. i.将 ans 更新为 ans 和 sum 减去窗口左边界元素 arr[window[l]] 的较大值。

7.d. ii.如果窗口的左边界元素 arr[window[l]] 等于 i-k,说明该元素已经不在窗口内,移动左指针 l。

7.d. iii.从 sum 中减去窗口左边界元素 arr[i-k]。

8.返回 ans。

总的时间复杂度:

  • maxSum1 算法的时间复杂度为 O(n^2)。

  • delete 算法的时间复杂度为 O(n)。

  • lenKmaxSum 算法的时间复杂度为 O(n*k)。

  • maxSum2 算法的时间复杂度为 O(n)。

总的额外空间复杂度:

  • maxSum1 算法的额外空间复杂度为 O(n)。

  • delete 算法的额外空间复杂度为 O(n)。

  • lenKmaxSum 算法的额外空间复杂度为 O(1)。

  • maxSum2 算法的额外空间复杂度为 O(n)。

go完整代码如下:

package mainimport ("fmt""math""math/rand""time"
)func maxSum1(arr []int, k int) int {n := len(arr)if n <= k {return 0}ans := math.MinInt32for i := 0; i < n; i++ {rest := delete(arr, i)ans = int(math.Max(float64(ans), float64(lenKmaxSum(rest, k))))}return ans
}func delete(arr []int, index int) []int {len0 := len(arr) - 1ans := make([]int, len0)i := 0for j := 0; j < len(arr); j++ {if j != index {ans[i] = arr[j]i++}}return ans
}func lenKmaxSum(arr []int, k int) int {n := len(arr)ans := math.MinInt32for i := 0; i <= n-k; i++ {cur := 0for j, cnt := i, 0; cnt < k; j, cnt = j+1, cnt+1 {cur += arr[j]}ans = int(math.Max(float64(ans), float64(cur)))}return ans
}func maxSum2(arr []int, k int) int {n := len(arr)if n <= k {return 0}window := make([]int, n)l, r := 0, 0var sum int64 = 0ans := math.MinInt32for i := 0; i < n; i++ {for l < r && arr[window[r-1]] >= arr[i] {r--}window[r] = ir++sum += int64(arr[i])if i >= k {ans = int(math.Max(float64(ans), float64(sum-int64(arr[window[l]]))))if window[l] == i-k {l++}sum -= int64(arr[i-k])}}return ans
}func randomArray(n, v int) []int {arr := make([]int, n)for i := 0; i < n; i++ {arr[i] = rand.Intn(2*v+1) - v}return arr
}func main() {N := 100V := 1000testTimes := 10000fmt.Println("测试开始")rand.Seed(time.Now().Unix())for i := 0; i < testTimes; i++ {rand.Intn(N)n := rand.Intn(N) + 1arr := randomArray(n, V)k := rand.Intn(N) + 1ans1 := maxSum1(arr, k)ans2 := maxSum2(arr, k)if ans1 != ans2 {fmt.Println("出错了!")}}fmt.Println("测试结束")
}

在这里插入图片描述

c++完整代码如下:

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <ctime>using namespace std;int lenKmaxSum(const vector<int>& arr, int k);int maxSum1(vector<int>& arr, int k) {int n = arr.size();if (n <= k) {return 0;}int ans = INT_MIN;for (int i = 0; i < n; i++) {vector<int> rest(arr.begin(), arr.end());rest.erase(rest.begin() + i);ans = max(ans, lenKmaxSum(rest, k));}return ans;
}int lenKmaxSum(const vector<int>& arr, int k) {int n = arr.size();int ans = INT_MIN;for (int i = 0; i <= n - k; i++) {int cur = 0;for (int j = i, cnt = 0; cnt < k; j++, cnt++) {cur += arr[j];}ans = max(ans, cur);}return ans;
}int maxSum2(const vector<int>& arr, int k) {int n = arr.size();if (n <= k) {return 0;}vector<int> window(n);int l = 0, r = 0;long long sum = 0;int ans = INT_MIN;for (int i = 0; i < n; i++) {while (l < r && arr[window[r - 1]] >= arr[i]) {r--;}window[r] = i;r++;sum += arr[i];if (i >= k) {ans = max(ans, static_cast<int>(sum - arr[window[l]]));if (window[l] == i - k) {l++;}sum -= arr[i - k];}}return ans;
}void randomArray(vector<int>& arr, int n, int v) {arr.resize(n);for (int i = 0; i < n; i++) {arr[i] = rand() % (2 * v + 1) - v;}
}int main() {const int N = 100;const int V = 1000;const int TEST_TIMES = 10000;cout << "测试开始" << endl;srand(time(NULL));for (int i = 0; i < TEST_TIMES; i++) {int n = rand() % N + 1;vector<int> arr;randomArray(arr, n, V);int k = rand() % N + 1;int ans1 = maxSum1(arr, k);int ans2 = maxSum2(arr, k);if (ans1 != ans2) {cout << "出错了!" << endl;}}cout << "测试结束" << endl;return 0;
}

在这里插入图片描述

c完整代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>#define int64_t long longint64_t max0(int64_t a, int64_t b) {return (a > b) ? a : b;
}int64_t lenKmaxSum(int64_t* arr, int64_t size, int64_t k);int64_t maxSum1(int64_t* arr, int64_t size, int64_t k) {if (size <= k) {return 0;}int64_t ans = LLONG_MIN;for (int64_t i = 0; i < size; i++) {int64_t* rest = malloc((size - 1) * sizeof(int64_t));int64_t restIndex = 0;for (int64_t j = 0; j < size; j++) {if (j != i) {rest[restIndex] = arr[j];restIndex++;}}ans = max0(ans, lenKmaxSum(rest, size - 1, k));free(rest);}return ans;
}int64_t lenKmaxSum(int64_t* arr, int64_t size, int64_t k) {int64_t ans = LLONG_MIN;for (int64_t i = 0; i <= size - k; i++) {int64_t cur = 0;for (int64_t j = i, cnt = 0; cnt < k; j++, cnt++) {cur += arr[j];}ans = max(ans, cur);}return ans;
}int64_t maxSum2(int64_t* arr, int64_t size, int64_t k) {if (size <= k) {return 0;}int64_t* window = malloc(size * sizeof(int64_t));int64_t l = 0, r = 0;int64_t sum = 0;int64_t ans = LLONG_MIN;for (int64_t i = 0; i < size; i++) {while (l < r && arr[window[r - 1]] >= arr[i]) {r--;}window[r] = i;r++;sum += arr[i];if (i >= k) {ans = max0(ans, sum - arr[window[l]]);if (window[l] == i - k) {l++;}sum -= arr[i - k];}}free(window);return ans;
}void randomArray(int64_t* arr, int64_t size, int64_t v) {for (int64_t i = 0; i < size; i++) {arr[i] = rand() % (2 * v + 1) - v;}
}int main() {const int64_t N = 100;const int64_t V = 1000;const int64_t TEST_TIMES = 10000;printf("测试开始\n");srand(time(NULL));for (int64_t i = 0; i < TEST_TIMES; i++) {int64_t n = rand() % N + 1;int64_t* arr = malloc(n * sizeof(int64_t));randomArray(arr, n, V);int64_t k = rand() % N + 1;int64_t ans1 = maxSum1(arr, n, k);int64_t ans2 = maxSum2(arr, n, k);if (ans1 != ans2) {printf("出错了!\n");}free(arr);}printf("测试结束\n");return 0;
}

在这里插入图片描述

相关文章:

2023-12-16:用go语言,给定整数数组arr,求删除任一元素后, 新数组中长度为k的子数组累加和的最大值。 来自字节。

2023-12-16&#xff1a;用go语言&#xff0c;给定整数数组arr&#xff0c;求删除任一元素后&#xff0c; 新数组中长度为k的子数组累加和的最大值。 来自字节。 答案2023-12-16&#xff1a; 来自左程云。 灵捷3.5 大体步骤如下&#xff1a; 算法 maxSum1 分析&#xff1…...

libxls - 编译

文章目录 libxls - 编译概述笔记静态库工程测试控制台exe工程测试备注备注END libxls - 编译 概述 想处理.xls格式的excel文件. 查了一下libxls库可以干这个事. 库地址 https://github.com/libxls/libxls.git 但是这个库的makefile写的有问题, 在mingw和WSL下都编译不了. 好在…...

自建私有git进行项目发布

自建私有git进行博客项目发布 之前尝试过通过建立私有git仓库&#xff0c;来发布自己的hexo静态博客&#xff0c;但是失败了&#xff0c;今天尝试了一下午&#xff0c;算是有了结果。下面记录我的过程。 我的需求&#xff1a; 我有一个服务器&#xff0c;希望在服务器端建一…...

华为HCIP认证H12-821题库上

1、2.OSPF核心知识 &#xff08;单选题&#xff09;下面关于0SPF的特殊区域&#xff0c;描述错误的是: A、Totally Stub Area允许ABR发布缺省的三类LSA,不接受五类LSA和细化三类LSA B、NSSA Area和Stub区域的不同在于该区域允许自治系统外部路由的引入&#xff0c;由ABR发布…...

Web安全漏洞分析—文件包含

在当今数字化时代&#xff0c;随着Web应用程序的广泛应用&#xff0c;网络安全问题愈加凸显。其中&#xff0c;文件包含漏洞作为一种常见但危险的安全隐患&#xff0c;为恶意攻击者提供了可乘之机。在这篇博客中&#xff0c;我们将深入探讨文件包含漏洞的本质、攻击手法以及应对…...

C++入门【9-C++循环】

C 循环 有的时候&#xff0c;可能需要多次执行同一块代码。一般情况下&#xff0c;语句是顺序执行的&#xff1a;函数中的第一个语句先执行&#xff0c;接着是第二个语句&#xff0c;依此类推。 编程语言提供了允许更为复杂的执行路径的多种控制结构。 循环语句允许我们多次…...

Python3 数字(Number) ----20231215

Python3 数字(Number) # Python3 数字(Number)# Python 数字数据类型用于存储数值。 # 数据类型是不允许改变的,这就意味着如果改变数字数据类型的值,将重新分配内存空间。# 以下实例在变量赋值时 Number 对象将被创建: var1 = 1 var2 = 10# 您也可以使用del语句删除一些数…...

PyQt6 QToolBar工具栏控件

锋哥原创的PyQt6视频教程&#xff1a; 2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~共计44条视频&#xff0c;包括&#xff1a;2024版 PyQt6 Python桌面开发 视频教程(无废话版…...

nodejs+vue+微信小程序+python+PHP基于大数据的银行信用卡用户的数仓系统的设计与实现-计算机毕业设计推荐

银行信用卡用户的数仓系统综合网络空间开发设计要求。目的是将银行信用卡用户的数仓系统从传统管理方式转换为在网上管理&#xff0c;完成银行信用卡用户的数仓管理的方便快捷、安全性高、交易规范做了保障&#xff0c;目标明确。银行信用卡用户的数仓系统可以将功能划分为管理…...

EMC RI/CI测试方案助您对抗电磁设备干扰!

方案背景 电磁或射频干扰的敏感性&#xff0c;会给工程师带来重大的风险和安全隐患。尤其是在工业、船用和医疗设备环境。这些环境系统中的控制、导航、监控、通信和警报等关键零部件必须具备电磁抗扰水平&#xff0c;以确保系统始终正常运行。 抗扰系统测试方案一般分为传导…...

【机器学习】数据降维

非负矩阵分解(NMF) sklearn.decomposition.NMF找出两个非负矩阵&#xff0c;即包含所有非负元素(W&#xff0c;H)的矩阵&#xff0c;其乘积近似于非负矩阵x。这种因式分解可用于例如降维、源分离或主题提取。 主成分分析(PCA) sklearn.decomposition.PCA使用数据的奇异值分解…...

vue3路由跳转及传参

1.创建项目及路由 1.1 创建文件时记得勾选上vue-router&#xff0c;没有勾选也没有关系 // vue3安装命令 npm create vuelatest // 以下选项可根据自己所需&#xff0c;进行选择&#xff0c;不懂就翻译 ✔ Project name: … <your-project-name> ✔ Add TypeScript? …...

cesium 自定义贴图,shadertoy移植教程。

1.前言 cesium中提供了一些高级的api&#xff0c;可以自己写一些shader来制作炫酷的效果。 ShaderToy 是一个可以在线编写、测试和分享图形渲染着色器的网站。它提供了一个图形化的编辑器&#xff0c;可以让用户编写基于 WebGL 的 GLSL 着色器代码&#xff0c;并实时预览渲染结…...

引用阿里图标库,不知道对应的图标是什么,可在本地显示图标ui,再也不要担心刚来不知道公司图标对应的是什么了

项目中使用了阿里的图标库&#xff0c;但是无法看到对应显示什么&#xff0c;每次都要去阿里图标库里面找 在下载下来的文件中会发现有两个文件一个是iconfont.css和iconfont.json&#xff0c; 这两个文件的数据可以拿到然后显示在页面上 有两个问题&#xff1a; 1&#xff1a…...

HandlerMethodArgumentResolver用于统一获取当前登录用户

这里记录回顾一些知识&#xff0c;不然就快忘记啦。 环境&#xff1a;SpringBoot 2.0.4.RELEASE需求&#xff1a;很多Controller方法&#xff0c;刚进来要先获取当前登录用户的信息&#xff0c;以便做后续的用户相关操作。准备工作&#xff1a;前端每次请求都传token&#xff0…...

记录 | mac打开终端时报错:login: /opt/homebrew/bin/zsh: No such file or directory [进程已完成]

mac打开终端时报错&#xff1a;login: /opt/homebrew/bin/zsh: No such file or directory [进程已完成]&#xff0c;导致终端没有办法使用的情况 说明 zsh 没有安装或者是安装路径不对 可以看看 /bin 下有没有 zsh&#xff0c;若没有&#xff0c;肯定是有 bash 那就把终端默…...

anolisos8.8安装显卡+CUDA工具+容器运行时支持(containerd/docker)+k8s部署GPU插件

anolisos8.8安装显卡及cuda工具 一、目录 1、测试环境 2、安装显卡驱动 3、安装cuda工具 4、配置容器运行时 5、K8S集群安装nvidia插件 二、测试环境 操作系统&#xff1a;Anolis OS 8.8 内核版本&#xff1a;5.10.134-13.an8.x86_64 显卡安装版本&#xff1a;525.147.05 c…...

Golang 链表的创建和读取 小记

文章目录 链表的相关知识链表的创建:模拟方式建立链表的**递归创建** 链表的读取遍历读取递归读取 完整代码 链表的相关知识 链表有时会具有头节点&#xff0c;头节点的指针指向第一个节点的地址&#xff0c;其本身的数据域可以根据自己的选择进行赋值   接下来我将以将int转…...

实验记录:深度学习模型收敛速度慢有哪些原因

深度学习模型收敛速度慢有哪些原因&#xff1f; 学习率设置不当&#xff1a; 学习率是算法中一个重要的超参数&#xff0c;它控制模型参数在每次迭代中的更新幅度。如果学习率过大&#xff0c;可能会导致模型在训练过程中的振荡&#xff0c;进而影响到收敛速度&#xff1b;如果…...

Arris VAP2500 list_mac_address未授权RCE漏洞复现

0x01 产品简介 Arris VAP2500是美国Arris集团公司的一款无线接入器产品。 0x02 漏洞概述 Arris VAP2500 list_mac_address接口处命令执行漏洞,未授权的攻击者可通过该漏洞在服务器端任意执行代码,写入后门,获取服务器权限,进而控制整个web服务器。 0x03 复现环境 FOFA…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...