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:用go语言,给定整数数组arr,求删除任一元素后, 新数组中长度为k的子数组累加和的最大值。 来自字节。 答案2023-12-16: 来自左程云。 灵捷3.5 大体步骤如下: 算法 maxSum1 分析࿱…...

libxls - 编译
文章目录 libxls - 编译概述笔记静态库工程测试控制台exe工程测试备注备注END libxls - 编译 概述 想处理.xls格式的excel文件. 查了一下libxls库可以干这个事. 库地址 https://github.com/libxls/libxls.git 但是这个库的makefile写的有问题, 在mingw和WSL下都编译不了. 好在…...
自建私有git进行项目发布
自建私有git进行博客项目发布 之前尝试过通过建立私有git仓库,来发布自己的hexo静态博客,但是失败了,今天尝试了一下午,算是有了结果。下面记录我的过程。 我的需求: 我有一个服务器,希望在服务器端建一…...
华为HCIP认证H12-821题库上
1、2.OSPF核心知识 (单选题)下面关于0SPF的特殊区域,描述错误的是: A、Totally Stub Area允许ABR发布缺省的三类LSA,不接受五类LSA和细化三类LSA B、NSSA Area和Stub区域的不同在于该区域允许自治系统外部路由的引入,由ABR发布…...

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

C++入门【9-C++循环】
C 循环 有的时候,可能需要多次执行同一块代码。一般情况下,语句是顺序执行的:函数中的第一个语句先执行,接着是第二个语句,依此类推。 编程语言提供了允许更为复杂的执行路径的多种控制结构。 循环语句允许我们多次…...
Python3 数字(Number) ----20231215
Python3 数字(Number) # Python3 数字(Number)# Python 数字数据类型用于存储数值。 # 数据类型是不允许改变的,这就意味着如果改变数字数据类型的值,将重新分配内存空间。# 以下实例在变量赋值时 Number 对象将被创建: var1 = 1 var2 = 10# 您也可以使用del语句删除一些数…...

PyQt6 QToolBar工具栏控件
锋哥原创的PyQt6视频教程: 2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~共计44条视频,包括:2024版 PyQt6 Python桌面开发 视频教程(无废话版…...

nodejs+vue+微信小程序+python+PHP基于大数据的银行信用卡用户的数仓系统的设计与实现-计算机毕业设计推荐
银行信用卡用户的数仓系统综合网络空间开发设计要求。目的是将银行信用卡用户的数仓系统从传统管理方式转换为在网上管理,完成银行信用卡用户的数仓管理的方便快捷、安全性高、交易规范做了保障,目标明确。银行信用卡用户的数仓系统可以将功能划分为管理…...

EMC RI/CI测试方案助您对抗电磁设备干扰!
方案背景 电磁或射频干扰的敏感性,会给工程师带来重大的风险和安全隐患。尤其是在工业、船用和医疗设备环境。这些环境系统中的控制、导航、监控、通信和警报等关键零部件必须具备电磁抗扰水平,以确保系统始终正常运行。 抗扰系统测试方案一般分为传导…...
【机器学习】数据降维
非负矩阵分解(NMF) sklearn.decomposition.NMF找出两个非负矩阵,即包含所有非负元素(W,H)的矩阵,其乘积近似于非负矩阵x。这种因式分解可用于例如降维、源分离或主题提取。 主成分分析(PCA) sklearn.decomposition.PCA使用数据的奇异值分解…...
vue3路由跳转及传参
1.创建项目及路由 1.1 创建文件时记得勾选上vue-router,没有勾选也没有关系 // vue3安装命令 npm create vuelatest // 以下选项可根据自己所需,进行选择,不懂就翻译 ✔ Project name: … <your-project-name> ✔ Add TypeScript? …...

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

引用阿里图标库,不知道对应的图标是什么,可在本地显示图标ui,再也不要担心刚来不知道公司图标对应的是什么了
项目中使用了阿里的图标库,但是无法看到对应显示什么,每次都要去阿里图标库里面找 在下载下来的文件中会发现有两个文件一个是iconfont.css和iconfont.json, 这两个文件的数据可以拿到然后显示在页面上 有两个问题: 1:…...
HandlerMethodArgumentResolver用于统一获取当前登录用户
这里记录回顾一些知识,不然就快忘记啦。 环境:SpringBoot 2.0.4.RELEASE需求:很多Controller方法,刚进来要先获取当前登录用户的信息,以便做后续的用户相关操作。准备工作:前端每次请求都传token࿰…...

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

anolisos8.8安装显卡+CUDA工具+容器运行时支持(containerd/docker)+k8s部署GPU插件
anolisos8.8安装显卡及cuda工具 一、目录 1、测试环境 2、安装显卡驱动 3、安装cuda工具 4、配置容器运行时 5、K8S集群安装nvidia插件 二、测试环境 操作系统:Anolis OS 8.8 内核版本:5.10.134-13.an8.x86_64 显卡安装版本:525.147.05 c…...
Golang 链表的创建和读取 小记
文章目录 链表的相关知识链表的创建:模拟方式建立链表的**递归创建** 链表的读取遍历读取递归读取 完整代码 链表的相关知识 链表有时会具有头节点,头节点的指针指向第一个节点的地址,其本身的数据域可以根据自己的选择进行赋值 接下来我将以将int转…...

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

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

网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...

循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...