首页 > 其他分享 >数据结构实验第一周

数据结构实验第一周

时间:2024-09-14 19:01:52浏览次数:9  
标签:排序 第一周 int 最大值 实验 ans 做法 数据结构 dp

6-1 差距几何

排序的话复杂度要O(n),可以选择桶排序或者计数排序,我选择的是计数排序
比如是 3 2 1 4 4 7 8 6
我开一个数组a [9] (因为最大为8),然后分别对出现的数计数有
a:1 1 1 2 0 1 1 1 0
然后按顺序放回 就是1 2 3 4 4 6 7 8

int fun(int D[],int N)
{
    if(N<2) return 0;
    int mx=0;//用来看最多要开多大的数组
    for(int i=0;i<N;i++)
        if(mx<D[i]) mx=D[i];
    
    int len=mx+1;
    int tp[len];
    for(int i=0;i<len;i++) tp[i]=0;//先对计数数组初始化
    for(int i=0;i<N;i++) tp[D[i]]++;//计数

    //放回的过程
    for(int i=0,j=0;i<len;i++)
    {
        while(tp[i]!=0)
        {
            D[j]=i;
            j++;
            tp[i]--;
        }
    }
    int ans=-1;
    for(int i=1;i<N;i++)
    if(D[i]-D[i-1]>ans) ans=D[i]-D[i-1];//找相邻最大值
    return ans;
}

6-2 最大子段和* - 《C++编程基础及应用》- 习题7-4


这道题可以选择两层循环的暴力做法,或者使用dp的做法,建议学习一下dp的做法
dp的做法跟第三题是一样的
这里写的暴力做法,dp看最后一题

int mis(int a[],const int n)
{
    //两层循环可以遍历到所有的连续线段
    //找到最大值即可
        int ans=0;
      for(int i=0;i<n;i++)
      {
          int tmp=0;
          for(int j=i;j<n;j++)
          {
              tmp+=a[j];
              if(tmp>ans) ans=tmp;
          }
      }
    return ans;
}

7-1 最大子列和问题


dp的状态转移方程为

\[dp[i]= \begin{cases} dp[i-1]+a[i]& \text{, dp[i-1]>0}\\ a[i]& \text{dp[i-1]<=0} \end{cases}\]

举样例给大家体会一下
a[i]:-2 11 -4 13 -5 -2
dp[i]: -2 11 7 20 15 13
所以答案是20

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int a[100005];
    for(int i=0;i<n;i++) cin>>a[i];
    int dp[100005];
    dp[0]=a[0];//记得初始化
    int ans=0;
    for(int i=1;i<n;i++)//从1开始
    {
        if(dp[i-1]>0) dp[i]=dp[i-1]+a[i];
        else dp[i]=a[i];
        ans=max(ans,dp[i]);//维护最大值
    }
    cout<<ans;
}

标签:排序,第一周,int,最大值,实验,ans,做法,数据结构,dp
From: https://www.cnblogs.com/swjswjswj/p/18412714

相关文章

  • JAVA进阶-set,Comparable排序,数据结构-树
    day07-set,Comparable排序,数据结构-树泛型Set概述和特点TreeSet集合概述和特点Comparable排序自然排序Comparable的使用使用空参构造创建TreeSet集合自定义Student类实现Comparable接口重写里面的comparaTo方法自然排序简单原理图比较器排序Compara......
  • TDengine 建模实战:手把手教你高效设计数据结构
    ✨作为一款高效简洁的大数据平台,TDengine的使用体验极为极为流畅,用户可以轻松实现数据的实时采集、存储与分析,快速获取所需的信息和洞察。但在追求最佳实践的过程中,我们仍需关注一些关键问题。例如,多个设备是否应该向同一个子表写入数据?在数据列过滤查询与基于标签的过滤查询之间,......
  • 数据结构
    数据结构栈栈,一种基本的先进后出的线性数据结构,手写栈一般有一个指针指向栈顶元素。STL中有个容器叫stack,支持一些功能push,将元素放置在栈顶;top(),输出栈顶元素pop(),弹出栈顶元素size(),访问栈中元素clear,清空详细操作可以见栈手写栈可以用数组模拟栈,代码如下。......
  • 【隐私计算】Cheetah安全多方计算协议-阿里安全双子座实验室
    2PC-NN安全推理与实际应用之间仍存在较大性能差距,因此只适用于小数据集或简单模型。Cheetah仔细设计DNN,基于格的同态加密、VOLE类型的不经意传输和秘密共享,提出了一个2PC-NN推理系统Cheetah,比CCS'20的CrypTFlow2开销小的多,计算效率更快,通信效率更高。主要贡献有两点:基于格......
  • 【数据结构】队列
    队列的概念及结构队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(FirstInFirstOut)入队列:进行插入操作的一端称为队尾出队列:进行删除操作的一端称为队头队列的模拟实现队列也可以数组和链表的结构实现,使用链表的结构......
  • 数据结构与算法-求数的最小深度是多少?
    给定一颗二叉树的头节点head求以head为头的树中,最小深度是多少?publicclassMinHeight{publicstaticclassTreeNode{publicintval;publicTreeNodeleft;publicTreeNoderight;publicTreeNode(intx){val=x;......
  • SSM实验室管理系统
    101开发语言:Java数据库:MySQL5.7技术:SSM工具:IDEA/Ecilpse、Navicat、Maven需求分析1.1需求分析概述生活中的实验室管理系统很复杂,对安全性和完整性要求都很高。在此我运用数据库课上所学知识,结合自己平时的操作业务体验,认为一个合格的实验室管理系统至少应该具备以下几点要......
  • 《DNK210使用指南 -CanMV版 V1.0》第二十四章 LCD显示实验
    第二十四章LCD显示实验1)实验平台:正点原子DNK210开发板2)章节摘自【正点原子】DNK210使用指南-CanMV版V1.03)购买链接:https://detail.tmall.com/item.htm?&id=7828013987504)全套实验源码+手册+视频下载地址:http://www.openedv.com/docs/boards/k210/ATK-DNK210.html5)正点原......
  • C++一元多项式解析、计算、输出(数据结构作业),可直接运行
    //Copyright(c)[email protected]#include<bits/stdc++.h>classPolynomial{private:std::unordered_map<int,int>data_;voidzero_value_optimization(){for(autoiter=data_.begin();iter!=data_.end();){......
  • 数据结构基础讲解(六)——串的专项练习
    本文数据结构讲解参考书目:通过网盘分享的文件:数据结构 C语言版.pdf链接: https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwd=ze8e 提取码:ze8e数据结构基础讲解(五)——队列专项练习-CSDN博客个人主页:樱娆π-CSDN博客目录串的定义串的类型定义、存储结......