搜索内容

包含标签:数据结构 的文章
  • 循环队列的操作
    其他

    循环队列的操作

               
    admin 今天
  • Java剑指 Offer II 090. 环形房屋偷盗(击败100%用户)
    其他

    Java剑指 Offer II 090. 环形房屋偷盗(击败100%用户)

    题目: 一个专业的小偷,计划偷窃一个环形街道上沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组 nums ,请计算 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。 示例 : 输入:nums = [2,3,2] 输出:3 解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。 思路: 跟上一题偷钱区别在于上一题的房子排布是线性结构,隔着偷可以从头到尾 这一次是环形结构,也就是上一次的结构但是在结尾时如果你从第一个房子起偷,你就不能偷最后一个房子。如果你从第二个房子起偷,那么可以偷最后一个房子。判断一下就可以。 复杂度: 时间:循环O(n)。 空间:用了Arrays.copyOfRange,O(n)。 代码: //先处理特殊情况
    admin 今天
  • 数据结构学习方法
    其他

    数据结构学习方法

     
    admin 今天
  • 遗传算法详解 附python代码实现
    其他

    遗传算法详解 附python代码实现

    遗传算法 看了好久才把遗传算法搞懂,附一个链接这个是我看过有关遗传算法讲解最详细的一篇https://blog.csdn.net/ha_ha_ha233/article/details/91364937 什么是遗传算法 遗传算法是用于解决最优化问题的一种搜索算法。从名字来看,遗传算法借用了生物学里达尔文的进化理论:“适者生存,不适者淘汰”,将该理论以算法的形式表现出来就是遗传算法的过程。 主要过程 初始化一个种群,种群中的个体DNA表示种群中的个体进行交叉变异产生后代根据后代中每个个体适应度进行自然选择、优胜劣汰不断迭代产生最优种群 例子 以求解二元函数为例,体会遗传算法如何解决最优化问题 def F(x,y): return 3*(1-x)**2*np.exp(-(x**2)-(y+1)**2)- 10*(x/5 - x**3 - y**5)*np.exp(-x**2-y**2)- 1/
    admin 今天
  • 顺序栈的初始化,入栈,出栈,求栈长度,遍历操作(C语言)
    其他

    顺序栈的初始化,入栈,出栈,求栈长度,遍历操作(C语言)

    #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -2 int i, n, e, j, x, num; //顺序栈 #define MAXSIZE 100 typedef struct { int* top;//栈顶指针 int* base;//栈底指针 int stacksize;//栈可用的最大容量 }SqStack; //1.顺序栈的初始化 int InitSqStack_S(SqStack& S) { S.base = (int*)malloc(sizeof(int) * MAXSIZE); if (!S.base) exit(OVERFLOW);//存储分配失败 S.top = S.base;//栈顶指针等于栈底指针,表示空栈 S.stacksize = MAXSIZE; return OK; } //2.顺序栈的入栈 int SqStackPush_S(SqStack &S, int e) {//将元素
    admin 今天
  • 建立中序线索二叉树,并分别从第一个结点和最后一个结点遍历
    其他

    建立中序线索二叉树,并分别从第一个结点和最后一个结点遍历

    任务 建立一颗中序线索二叉树;分别从第-一个结点和最后一个结点出发输出中序遍历结果;输出某结点的前趋和后继结点 思路: 线索二叉树结构类型 typedef struct treenode{ char data; struct treenode *lchild,*rchild; int ltag,rtag; //记录指针与指向孩子结点还是后继或前驱 tag为0表示孩子,tag为1表示线索 }treenode,*tree; 先建立一个二叉树 //使用先序建立二叉树 void buildtree(tree &t){ char ch; ch = getchar(); if(ch=='#') t = NULL; else{ t = (treenode *)malloc(sizeof(treenode));
    admin 今天
  • Java剑指 Offer II 089. 房屋偷盗(击败100%用户)
    其他

    Java剑指 Offer II 089. 房屋偷盗(击败100%用户)

    题目: 一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组 nums ,请计算 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 示例 : 输入:nums = [1,2,3,1] 输出:4 解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。      偷窃到的最高金额 = 1 + 3 = 4 。 思路: 和上一题基本相同。动态规划 用dp[n]来表示前n座房子能偷得最多的钱 前n座房子最多偷的钱要么就是偷到了n-1座房子,这个时候就不能偷n的钱了 此时dp[n] = dp[n-1]; 还有一种可能性,就是当前房子的钱加上前n-2间房子钱要大于这个前n-1房子钱 此时dp[n] = dp[n-2]+nums[n] 两者取大就可以了 可以从第一间或者第二间房子起偷。 可以优化一下空间复杂度
    admin 今天
  • 学习数据结构笔记(17) — [动态规划(由背包问题引入)]
    其他

    学习数据结构笔记(17) — [动态规划(由背包问题引入)]

    B站学习传送门–>尚硅谷Java数据结构与java算法(Java数据结构与算法) 文章目录 1.情景引入2.背包问题分析3.背包问题的解决 1.情景引入 一个简单的0-1背包问题;规定背包的最大容量是4公斤;并且放入背包的物品不能重复,怎么样让背包的物品价值量最大化? 物品重量价值电脑16000电子琴48000游戏机33000 动态规划算法的思想也是将复杂问题规划分解为小问题,但是和分治算法不同的地方是, 动态规划算法分解得到的子问题有递进关系;子问题的最优解会成为最终的解; 可以这么看;分解得到的子问题的求解是建立在上一个阶段子问题的求解基础上;这些子问题不是相互独立的; 2.背包问题分析 接着回到之前的背包问题; 首先,背包问题就是给定一个固定容量的背包,多个具有不同价值的物品;如何让背包的价值最大? 背包问题可分为01背包问题和完全背包问题; 01背包:规定放入背包的每
    admin 今天
  • 复合型数据结构:(双向循环)链表_第2部分
    其他

    复合型数据结构:(双向循环)链表_第2部分

    本部分实现双向循环链表的: 统计链表中结点个数删除某个结点 (根据结构体中某个成员的值、根据处于链表中的位置) (有头节点、无头结点的处理区别)链表的销毁及野指针处理 双向循环链表_第2部分 1 统计链表中的结点个数1.1 带头结点1.2 不带头结点 2 查找链表中的数据2.1 查找带头结点的链表2.2 查找不带头节点的链表 3 根据位置删除某个节点3.1 带头结点3.1.1 正数第k个位置3.1.2 倒数第k个位置3.1.3 合二为一:过程的抽象 3.2 不带头结点3.2.1 正数第k个位置3.2.2 倒数第k个位置3.2.3 能合二为一吗? 4 销毁链表野指针问题 1 统计链表中的结点个数 1.1 带头结点 int CountingNodesOfListWithHead(node *list){ if(list == NULL){ // Defensi
    admin 今天
  • String Builder (15 分)
    其他

    String Builder (15 分)

    0123456789101112 is a string build up for n=12. Then, in all the digits from index a to index b, count the appearence of c. For the string above, 2 5 is: 2345 Thus the appearence of 3 is 1. Input Format: Four positive numbers, n, a, b and c, where a
    admin 今天
  • 数据结构—图—关键路径—7
    其他

    数据结构—图—关键路径—7

    拓扑排序主要是为解决一个工程能否顺序进行的问题,但有时我们还需要解决工程完成需要的最短时间问题。 如果要对一个流程图获得最短时间,就必须要分析它们的拓扑关系,并且找到当中最关键的流程,这个流程的时间就是最短时间。 在前面讲了AOV网的基础上,我们来介绍一个新的概念。 在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续时间,这种有向图的边表示活动的网,我们称之为AOE网(Activity On Edge Network)。 把AOE网中没有入边的顶点称为始点或源点,没有出边的顶点称为终点或汇点。 由于一个工程,总有一个开始,一个结束,所以正常情况下,AOE网只有一个源点一个汇点。 我们把路径上各个活动所持续的时间之和称为路径长度,从源点到汇点具有最大长度的路径叫关键路径,在关键路径上的活动叫关键活动。 显然图7-9-3的AOE网而言,开始->发动机完成->部
    admin 今天
  • LeetCode刷题笔记 双指针 碰撞指针
    其他

    LeetCode刷题笔记 双指针 碰撞指针

    碰撞指针简介 碰撞指针 Opposite directional:两个指针指向同一线性表,但是遍历方向相反,一个指针指向开头,另一个指向末尾,它们相向移动直到相遇或满足其他特殊条件为止 344 反转字符串 编写一个函数,其作用是将输入的字符串反转过来。 输入一个字符数组,输出将其反转的字符数组 输入:s = [“h”,“e”,“l”,“l”,“o”] 输出:[“o”,“l”,“l”,“e”,“h”] 解析: ​ 本题使用双指针可以快速简单地解决。我们定义一对碰撞指针分别指向字符数组的头和尾,然后循环执行如下两步,直到两指针相遇循环终止: 交换 head 和 tail 指向的元素head 和 tail 相向移动一步 class Solution { public: void reverseString(vector& s) { int head = 0
    admin 今天
  • C++解OJ题——合并两个有序数组(每天一个小技巧)
    其他

    C++解OJ题——合并两个有序数组(每天一个小技巧)

    原题如下:   给你两个按非递减顺序排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。   请你合并 nums2 到 nums1 中,使合并后的数组同样按非递减顺序排列。   注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。 审题:   数组本身有序,将两个数组合并为一个数组,合并后的数组依旧要保持有序。合并到nums1数组中,大小已经给定。并且由其解释的信息要求所设计的算法是一个稳定的算法。 代码设计:   根据题干描述信息可以得出,合并后的数组的最后一个位置的数据是原两个数组中最大的一个数据。而这最大的一个数据来源于两数组有效数据的最后一个的大者。同理
    admin 今天
  • JavaCV 制作字符画
    其他

    JavaCV 制作字符画

    大家好,我是青空。 最近青空在做一些图像处理的工作,主要是使用到了OpenCV。可能有的小伙伴听过OpenCV,OpenCV是通过C++开发的,官方只提供了C++、Python、JS 等版本的API。 Java 使用OpenCV 原生的库,比较麻烦,需要配置一些环境变量。指北君在GitHub上找了一圈,终于找到了一个Java版本的项目 – JavaCV ,JavaCV 直接把OpenCV给嵌入到内部,不再需要其他的环境变量的支持。JavaCV另外包含了FFmpeg、Tesseract等一系列的音视频相关的库。 今天青空就要带大家一起使用 JavaCV 将一张图片转换成一副字符画。 准备工作 我们需要引入 JavaCV的依赖库 org.bytedeco javacv-platform
    admin 今天
  • LeetCode 155. 最小栈
    其他

    LeetCode 155. 最小栈

    好久没刷题了,最近刷题见到这个一个题,题目本身很简单,做一个辅助栈,时间效率跑过100%的用户,但是在讨论区看到 一次面试的时候,面试官要求不开辅助栈的做法,感觉这个值得思考。做法是在栈内记录一个最小值,同时栈内存储于最小值的差值。但任然离不开栈的先进后出性质。 设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。 push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/min-stack 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 /* * @lc app=leetcode.cn id=155 lang=cpp * * [155]
    admin 今天
  • 习题整理12.02
    其他

    习题整理12.02

    假设 A 类有如下定义,设 a 是 A 类的一个实例,下列语句调用哪个是错误的?() 解析:静态方法可以通过类名调用,非静态的需要实例化对象来调用已知一颗二叉树中没有重复值,知道这颗树的前序,中序和后序遍历中的哪些不可以唯一确定这颗二叉树: 解析:已知先序和后序,不能唯一确定二叉树 已知先序或后序,而又知中序,则能唯一确定二叉树 先序、中序相同时,二叉树没有左子树 后序、中序相同时,二叉树没有右子树 后序、先序相同时,只有一个根节点 6.有向图 G 中有 n 个顶点,e 条边,采用邻接表存储,若采用 BFS 方式遍历其时间复杂度为( ) 解析:BFS和DFS都是: 邻接矩阵-O(n^2) 邻接表-O(n+e) 7 .删除非空线性链表中由指针p所指链结点的直接后继结点的过程是依次执行动作()。 解析:link§ 表示读取 p 结点中指针 link 内存储的地址,那么 link§ 读取到的就是 p 结点的直接
    admin 今天
  • C++ STL学习路线及笔记
    其他

    C++ STL学习路线及笔记

    什么是STL C++ STL(标准模板库)是一套功能强大的 C++ 模板类,提供了通用的模板类和函数,这些模板类和函数可以实现多种流行和常用的算法和数据结构,如向量、链表、队列、栈。 C++ 标准模板库的核心包括以下三个组件:容器、算法、迭代器。 容器 ​​​​​​​STL学习笔记 - pyyyyyy - 博客园 (cnblogs.com) vector 是采用倍增思想实现增强型数组; queue 基本数据结构队列,先进先出; stack 基本数据结构——栈,先进后出; string 定义了对字符串操作的一些方法; priority_queue 队列的扩展——优先队列,存入的数据默认按照从大到小排序,还可自定义; deque 队列扩展——双端队列,双端队列中的元素既可以从队首进/出队,也可以从队尾进/出队,可支持像数组下标的方式随机访问; set 数组扩展——其内部元素默认按升序排列,且具有元素不可重复的性质; multiset set集合扩展——有序多重集合,和set不同的是其中元素可以重复; bitset 内部存储
    admin 今天
  • 秋招开发/技术岗常见知识点汇总
    其他

    秋招开发/技术岗常见知识点汇总

    本人目前大四,是一名双非普通二本的计算机专业学生,秋招斩获了10+份offer,投递过上百家公司,有着丰富的笔试、面试经验;我投递的岗位主要有:客户端研发工程师(C++、java)、后端开发工程师(python、java),游戏研发工程师(C/C++)、Android开发工程师(java)、软件测试工程师;这几类岗位基本都拿了offer,这次,我将印象深刻的、比较常见的知识点/试题进行一次汇总,希望警醒自己,也希望给你们助助力,为以后做好准备!!不罗嗦了,开始~ 1.笔试汇总: C/C++类: 这里常考的知识点:1. 求结构体的大小,sizeof(结构体); 例题: struct Student { int i; int j; char c; } ; int main() { printf("%d\n",sizeof(Student)); return 0; } 2. C++多继承相关知识点考查,给一段C++程
    admin 今天
  • 单链表逆置:空间复杂度O(1)
    其他

    单链表逆置:空间复杂度O(1)

    带头结点单链表逆置 从链表(带头结点)首个数据结点开始,重新头插法建表,将节点链接到头结点上 //单链表结点结构 typedef struct LNode { int data; struct LNode* next; }LNode; void Inversion(LNode* head) { LNode* phead=head->next; LNode* q; head->next=NULL; //头结点next指针置空 while(phead!=NULL) { q=phead->next; //利用phead头插法重新建表 phead->next=head->next; head->next=phead; phead=q; } }
    admin 今天
  • CF 2021-12-1
    其他

    CF 2021-12-1

    #include #include #include using namespace std;
    admin 今天
  • 数据结构学习——链表的简易功能实现
    其他

    数据结构学习——链表的简易功能实现

    引入头文件 #include #include #include 结构体定义 typedef struct Node { int data; struct Node *pNext; }NODE,* PNODE; 创建链表 PNODE creat_list(void){ //不存放有效数字的头结点 PNODE pHead = (PNODE)malloc(sizeof(NODE)); if(pHead==NULL){ printf("分配失败"); exit(-1); } //创建尾节点 PNODE pTail = pHead; pTail->pNext = NULL; //动态创建 需要指定有效节点个数 int len; int val;//临时存放用户输入的值 printf("请输入该链
    admin 今天
  • 第十二章 异常-Exception
    其他

    第十二章 异常-Exception

    第十二章 异常-Exception 12.1 异常体系图 12.2 常见的运行时异常 NullPointerException 空指针异常 当应用程序试图在需要对象的地方使用 null 时,抛出该异常, ArithmeticException 数学运算异常 当出现异常的运算条件时,抛出此异常。 ArrayIndexOutOfBoundsException 数组下标越界异常 用非法索引访问数组时抛出的异常。 ClassCastException 类型转换异常 当试图将对象强制转换为不是实例的子类时,抛出该异常。 NumberFormatException 数字格式不正确异常[] 当应用程序试图将字符串转换成一种数值类型,但该字符串不能转换为适当格式时,抛出该异常 12.3 常见的编译异常 编译异常是指在编译期间,就必须处理的异常,否则代码不能通过编译。 12.4 异常处理
    admin 今天
  • 2021SC@SDUSC山东大学软件学院软件工程应用与实践——claygl(源代码分析9)
    其他

    2021SC@SDUSC山东大学软件学院软件工程应用与实践——claygl(源代码分析9)

    2021SC@SDUSC 目录 一.clay.core.LinkedList类概述 二.clay.core.LinkedList类的作用 三.clay.core.LinkedList类源码分析 1.new LinkedList() 2.clear() 3.forEach(cb, context) 4.getAt(idx) 5.getHead() 6.getTail() 7.indexOf(value) → {number} 8.insert(val) → {clay.core.LinkedList.Entry} 9.insertAt(idx, val) → {clay.core.LinkedList.Entry} 10.insertEntry(entry) 11.isEmpty() 12.length() → {number} 13.remove(entry) 14.removeAt(idx) 一.clay.core.LinkedList类概述     clay.core.LinkedList类为简单的
    admin 今天
  • 2021ICPC上海G Edge Groups(树上DP)
    其他

    2021ICPC上海G Edge Groups(树上DP)

    考虑一个菊花图:1号点为中心,其他n-1个点都与1号点直接相连。 计算两个边分成一组,有多少分组方法: 答案是1*3*5*7*…*n 证明过程 现在来考虑一个普通图: 假设A点是B点的父亲 B点有N个儿子(不包含父亲),假设全部都是叶子节点 1:如果N是偶数,那么将这些连接叶子节点的边两两分组,它有1 * 3*5*7 … * N (1-N中的奇数相乘)种分组方法 2:如果N是奇数,它同样有1 * 3 * 5 * … * N(1到N中的奇数相乘)种分组方法,而且必定会剩下一个边无法配对,所以这个剩下的边只好与B点与父亲相连的那条边配对 当A点在进行统计时,假设统计到了A1个奇数节点(N为奇数的B点),统计到了A2个偶数节点(N为偶数的B点),奇数节点已经把连接父亲节点的边给用掉了,所以A点可用于自由组合的边只有连接偶数节点的那些边(即1-A2中的奇数相乘)。 所以,答案就是所有点的自由分配方案的乘积 #pragm
    admin 今天
  • 论文阅读中一些常见的名词解释
    其他

    论文阅读中一些常见的名词解释

    Pretrained model (预训练模型) 一般情况下预训练模型都是大型模型,具备复杂的网络结构,众多的参数量,以及在足够大的数据集下进行训练而产生的模型. 在NLP领域,预训练模型往往是语言模型,因为语言模型的训练是无监督的,可以获得大规模语料,同时语言模型又是许多典型NLP任务的基础,如机器翻译,文本生成,阅读理解等,常见的预训练模型有BERT, GPT, roBERTa, transformer-XL等. Fine-tuning (微调) 根据给定的预训练模型,改变它的部分参数或者为其新增部分输出结构后,通过在小部分数据集上训练,来使整个模型更好的适应特定任务. (后续继续补充)
    admin 今天
  • 链表及常见面试题
    其他

    链表及常见面试题

    链表 单链表 特点: 逻辑上顺序存储,物理上无序存储 头指针根据情况而定,不保存数据,很多操作需要头指针,比如原地反转链表。 每个节点包含 data, Node next保存下个Node public class LinkList { public Node header=new Node(); add{} query{} .... } public class Node{ String data; Node next; Node(Sring data){ this.data=data; } } ​ 常见操作:增删改查。 单链表面试题 1 求链表中的有效节点数? 思路 1:while(true)遍历该链表 直到next==null break,否则Count++ 思路 2:设置两个节点,Fir 走一步,Se
    admin 今天
  • 队列-java
    其他

    队列-java

    队列 什么是队列? 队列是先进先出,first in first out。 实现方式: 数组 队列 数组实现非环形队列:省略。 数组实现环形队列:增加一个length即可。 我的思路: 如果length!=MaxSize 指针可以继续移动 (还可以利用数学取模的方式来实现)
    admin 今天
  • 【代码题 考研数据结构】1-1 线性表–基础
    其他

    【代码题 考研数据结构】1-1 线性表–基础

    文章目录 节点结构 头插法创建单链表 尾插法创建单链表 单链表逆置 输出单链表 统计表长 可运行代码 节点结构 typedef struct Node{ int val; struct Node *next; }Node; 头插法创建单链表 //头插
    admin 今天
  • 时间复杂度问题
    其他

    时间复杂度问题

    算法复杂度分为空间复杂度和时间复杂度。         空间复杂度是指这个算法占用的内存         时间复杂度就是指这个算法的工作量 时间频度:算法花费的时间跟算法执行次数成正比,所以我们计算时间频度都是由执行次数来计算 算法执行次数越多,花费的时间越多。一个算法中执行次数称为时间频度记为T(n) 在时间频度中,n为问题的规模,当n不断变化时,它呈现出来的规律就是时间复杂度O(n)。 比如说:时间频度T(n)=kn+b,那么它的时间复杂度就是O(n),在时间复杂度中,只要是kn+b就代表它跟n是同量级的就可以把它的k和b省略掉 类似的:时间频度T(n)=kn^2+bn的时间复杂度是O(n^2) 一般常用到的时间复杂度和大小排序如下: O(1)
    admin 今天
  • 408数据结构真题2014-41
    其他

    408数据结构真题2014-41

    文章目录 题目AC代码 题目 本题链接:AcWing 3766. 二叉树的带权路径长度 注:链接题目仅代表和本题大体相似 因为是考研笔试,本题代码以C语言去写 AC代码 代码解释:本题要求的是带权路径的长度之和,带权路径的长度 = 权值点 * 该点到根节点的距离,下面举一个栗子去说明这一点: 比如栗子中给的这棵树,带权路径的长度之和 = (12 * 1 + 2 * 1 + 6 * 2 + 4 * 2) = 34 题目中要求的是所有叶节点的带权路径之和,故不包含2这个点,答案为:(12 * 1 + 6 * 2 + 4 * 2) = 32,不难看出,本题其实是要求我们遍历这棵树,我们遍历树的方法可以采用dfs和bfs两种方法,笔试建议采用dfs的写法,dfs写起来要比bfs精简很多! 代码: /** * Definition for a binary tree node. * s
    admin 今天
  • NC88 寻找第K大(堆)
    其他

    NC88 寻找第K大(堆)

    描述 给定一个整数数组,同时给定它的大小n和要找的k,请根据快速排序的思路,找出数组中第k大的数 输入: [1,3,5,2,2],5,3 返回值:2 要求:时间复杂度 O(nlogn)O(nlogn),空间复杂度 O(1)O(1) 解题思路 方法一:sort函数排序 本题是一个排序问题,可选的排序方案很多,其中冒泡、选择等O(n^2)时间的排序方案代价较高,选用快排、堆排、分治算法是比较省时的方案。直接调用c++内置sort函数是最好的办法。 class Solution { public: static bool cmp(const int& a, const int& b) { // 设定比较规则,大数靠前 return a > b; } int findKth(vector a, int n, int K) {
    admin 今天
  • 基础结构之树结构详解
    其他

    基础结构之树结构详解

    树 一)什么是树(tree)    树是n(n≥0)个节点的有限集。当n=0时,称为空树。在任意一个非空树中,有如下特点: 有且仅有一个特定的称为根的节点。 当n>1时,其余节点可分为m(m>0)个互不相交的有限集,每一个集合本身又是一个树,并称为根的子树。  术语:根节点、子树、叶子节点、父节点、孩子节点、兄弟节点、树的高度 二)二叉树 二叉树(binary tree)是树的一种特殊形式。这种树的每个节点最多有2个孩子节点。注意,这里是最多有2个,也可能只有1个,或者没有孩子节点   二叉树的存储 1.链式存储 存储数据的data变量 指向左孩子的left指针 指向右孩子的right指针 2.数组存储   使用数组存储时,会按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或右孩子空缺,则数组的相应位置也空出来,这样可以更方便地在数组中定位二叉树的孩子节点和父节点: 父节点下标 parent,那么左孩子下标为 leftChild = 2
    admin 今天
  • Java剑指 Offer II 088. 爬楼梯的最少成本(击败90.47%用户)
    其他

    Java剑指 Offer II 088. 爬楼梯的最少成本(击败90.47%用户)

    题目: 数组的每个下标作为一个阶梯,第 i 个阶梯对应着一个非负数的体力花费值 cost[i](下标从 0 开始)。 每当爬上一个阶梯都要花费对应的体力值,一旦支付了相应的体力值,就可以选择向上爬一个阶梯或者爬两个阶梯。 请找出达到楼层顶部的最低花费。在开始时,你可以选择从下标为 0 或 1 的元素作为初始阶梯 示例 : 输入:cost = [10, 15, 20] 输出:15 解释:最低花费是从 cost[1] 开始,然后走两步即可到阶梯顶,一共花费 15 。 思路: 简单来说是一个斐波那契数列的改版问题,使用动态规划去解决。 有一个问题就是很多人可能会去递归,递归比较容易理解,但是递归效率比较差,还是建议迭代。 这两个相当于是一个正向一个反向 具体见代码及注释。 复杂度: 时间:循环O(n)。 空间:dp数组O(n)。 代码: public int minCostClimbingStairs(int[] cost) { //用一个dp数组来记录开销 int n
    admin 今天
  • 《轩轩Redis学习笔记》——数据结构与对象
    其他

    《轩轩Redis学习笔记》——数据结构与对象

    文章目录 题引开篇Redis底层数据结构键-值的组织结构哈希冲突rehash一致性rehash的弊端 集合数据操作效率集合的底层数据整数数组双向链表哈希表压缩列表跳表五种数据结构查找的时间复杂度 常见的集合操作及其效率单元素操作范围操作统计操作例外情况小结 数据结构的应用小结思考题 参考资料:蒋德钧老师的《Redis核心技术与实战》、《redis设计与实现 第二版》、《Redis开发与运维》 题引开篇 你知道Redis里的数据结构吗? Redis底层数据结构 Redis的底层数据结构有6种: 简单动态字符串双向链表压缩列表哈希表跳表整数数组 上面6种数据结构也可以简单分成String类(1种)与集合类(5种) 键-值的组织结构 Redis 使用了一个“ 全局哈希表 ”来保存所有键值对。 一个哈希表,其实就是一个数组,数组的每个元素称为一
    admin 今天
  • 素数打表 总结
    其他

    素数打表 总结

    素数打表 总结 首先0和1不是素数。 法一:定义判断 本方法时间复杂度最大,因为有非常多的重复操作。 通过素数的定义直接判断,只能被1和它本身整除的数就是素数了。这种方法适合判断单个数是否为素数,当要求一个范围内素数而这个范围又比较大时,这种方法的时间复杂度就会非常大了。 void init() { int i,j,n; int a[10010],k=0; for(i=2;i<=n;i++) { for(j=2;j
    admin 今天
  • 粗糙集代码相关网站
    其他

    粗糙集代码相关网站

    国际粗糙集协会官网 其中包含国际粗糙集领域知名学者的会议ppt和相关软件。 https://www.roughsets.org/Rseslib 它是一个用 Java 实现的粗糙集和机器学习数据结构、算法和工具的库。 https://rseslib.mimuw.edu.pl/codeforge 该网站中搜索粗糙集关键字可以查询出各种语言实现的粗糙集模型。 http://www.codeforge.cn/ 联合开发网 也可以搜索出很多关于粗糙集的代码。 http://www.pudn.com/百度文库 其中包含很多粗糙集课件。CSDN 粗糙集代码需要积分。 希望能够帮助粗糙集小白快速上手,祝学业顺利。
    admin 今天
  • 1033 旧键盘打字 (20 分)(C++)
    其他

    1033 旧键盘打字 (20 分)(C++)

    Notice: 1.测试点2:先输入s1,s2。并且由于s1可能是空字符串, 所以不能用cin >> s1 >> s2,因为cin >> s1不接收空串。 所以s1需要用getline接收(测试点2)。 2.关于cin、getline()的区别: 简单来说,在接受字符串的时候, cin 遇“空格”、“TAB”、“回车”都结束; getline()可以接收空格并输出。(需包含#include) 具体参考:https://www.cnblogs.com/renzhuang/articles/6993689.html https://blog.csdn.net/caojunling/article/details/1890519 3.getline()的基本用法: 函数原
    admin 今天
  • 03_插入排序
    其他

    03_插入排序

    插入排序原理:从坐标1开始向前比较,如果坐标1比坐标0大/小,交换,从坐标2向前比较,若坐标2比坐标1大/小,交换,此时,坐标1的值是坐标2的值,若坐标1比坐标0大/小,交换,直到出现此坐标比前一个坐标小/大,不满足条件,停止交换……以此类推。每次循环都会排好一部分,第一次循环排好0-1位置的序列,第二次是0-2,第三次是0-3…… 我们可以把插入排序理解为打扑克牌,当我们拿到新的扑克牌a,会将a跟手中的牌进行比较,从右往左比较,找到相应的位置,把扑克牌插入进去即可。 代码: public class demo { public static void main(String[] args) { int nums[] = {4, 8, 2, 9, 1, 5}; insertionSort(nums); print(nums); } /
    admin 今天
  • 数据结构与算法【LeetCode-Offer】:1.4数组—59. 螺旋矩阵 II
    其他

    数据结构与算法【LeetCode-Offer】:1.4数组—59. 螺旋矩阵 II

    原文链接 题目描述 题目链接 解题思路 代码演示: package com.kami.leetcode.arrayStudy; /** * @Description: TODO * @author: scott * @date: 2021年12月02日 9:56 */ public class L_59 { public int[][] generateMatrix(int n){ //创建一个二维数组 int[][] res = new int[n][n]; //左边 int left = 0; //右边 int right = n - 1; //上面 int up = 0; //下面 int bottom = n
    admin 今天
  • 冒泡排序(C++)完整代码
    其他

    冒泡排序(C++)完整代码

    算法学习 本人机械科研dog一枚,对算法感兴趣。这是我自学算法的记录。 第一天:冒泡排序 文章目录 算法学习一、冒泡排序原理?二、核心代码三、算法复杂度分析 一、冒泡排序原理? 1、从后往前依次比较相邻的元素。若是要按照升序排序,则后面的元素比前面的小,就交换这2个元素;降序则相反。 2、对每一对相邻元素作同样的工作,从第一对到最后一对。进行一轮比较交换下来,最后的元素就会是最小(或最大)的数了,这个数就不用参与后面的比较操作了。 3、针对所有的元素重复以上的步骤。 4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 例子如下 二、核心代码 该代码已经进过测试,稳定有效 //函数写在Algorithm这个类里面了,并且是用模板方式编写 //这是为了函数能适应各种类型的数据 template vector Algorithm::bu
    admin 今天
  • 剑指 Offer 46. 把数字翻译成字符串 动态规划 c++
    其他

    剑指 Offer 46. 把数字翻译成字符串 动态规划 c++

    这题类似 70.爬楼梯,动态规划的思想 第 1 步:状态定义 dp[i] 表示长度为i时 有多少种翻译方法。 第 2 步:推导状态转移方程 dp[i]=dp[i−1]【+dp[i−2]】 (1)长度为i-1时若有n种方法,则如果将第i个数字单独加入,就相当于给这n个解法的末尾加一个翻译,总数n不变,所以一开始是dp[i]=dp[i−1] (2)但要注意,加dp[i−2]是有条件的,条件就是第i个数字和第i-1个数字构成的两位数不大于25,比如是‘23’(对应’x’),此时,相当于在dp[i-2]的n个方法后面各加了一个’x’,总数n不变,所以是dp[i]+=dp[i-2] 可以看出该问题的「状态转移方程」如果(1)(2)都满足时就是dp[i]=dp[i−1]+dp[i−2],也就是「斐波拉契数列」的通项公式。 第 3 步:思考初始化 dp[0] 无意义,它也不会被以后的计算过程参考到,因此可以不赋值或者
    admin 今天
  • 邻接矩阵转化为邻接链表——6-1 有向图邻接矩阵转换为邻接表 (10 分)
    其他

    邻接矩阵转化为邻接链表——6-1 有向图邻接矩阵转换为邻接表 (10 分)

    邻接矩阵转化为邻接表 1.邻接矩阵的数据类型描述:2.邻接链表的数据类型定义:3.代码思路:练习题6-1 有向图邻接矩阵转换为邻接表 (10 分) 1.邻接矩阵的数据类型描述: #define MAXVEX 20 typedef char Vextype; typedef struct { int arcs[MAXVEX+1][MAXVEX+1]; Vextype vex[MAXVEX+1]; int vexnum; int arcnum; }AdjMatrix; 2.邻接链表的数据类型定义: typedef struct ArcNode { int adjvex; struct ArcNode *next; }ArcNode; typedef struct { Vextype vexdata; ArcNode *head;
    admin 今天
  • " alt="TCP为什么三次握手">
    其他

    TCP为什么三次握手

    先搞一个简单的生活中的例子打电话: 模拟场景:client要打电话给server 在一个不可靠的信道上建立一个可靠的通话,从理论上来讲至少需要四步。 
    admin 今天
  • 数据结构—图—拓扑排序—6
    其他

    数据结构—图—拓扑排序—6

    拓扑排序主要解决一个工程能否顺序进行的问题。 无环图:图中没有回路 在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称为AOV网(Activity On Vertex Network)。 AOV网中的弧表示活动之间存在的某种制约关系(也可以理解活动要分先后顺序),AOV网中不能有回路。 设G=(V,E)是一个具有n个顶点的有向图,V中的顶点序列v1,v2,…vn,满足若从顶点vi到vj有一条路径,则在顶点序列中顶点vi必在顶点vj之前。则我们称这样的顶点序列为一个拓扑序列。 拓扑排序:就是对一个有向图构造拓扑序列的过程。 构造时会有两个结果,如果此网的全部顶点都被输出,则说明它是不存在环(回路)的AOV网;如果输出顶点数少了,哪怕少了一个,也说明这个网存在环(回路),不是AOV网。 一个不存在回路的AOV网,我们可以将它应用在各种各样的工
    admin 今天
  • 数据结构中的哈希表
    其他

    数据结构中的哈希表

    前言 哈希表是一种非常重要的数据结构,几乎所有的编程语言都有直接或间接的使用到这种数据结构。 介绍 哈希表通常是基于数组进行实现的,但是相对于数组,哈希表有许多的优势: 它可以提供非常快速的插入-删除-查找操作。在哈希表种,无论多少数据,插入和删除值只需要接近常量的时间:即O(1)的时间级。在进行操作时只需要几个机器指令即可完成。其速度比树还要快,基本可以瞬间查找到想要的元素。 但是哈希表也有不足: 哈希表种的数据是没有顺序的,所以不能以一种固定的方式(比如从小到大)来遍历其中的元素。通常情况下,哈希表中的key是不允许重复的,不能放置相同的key,用于保存不同的元素。 那哈希表究竟是什么呢? 这是百度百科对哈希表的描述:散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度
    admin 今天
  • char,String 与int之间的相互转换
    其他

    char,String 与int之间的相互转换

    字符数字转化为int数字 char numChar='5'; int numInt=numChar-'0'; System.out.println(numInt);//5 character数字转化为数字 Character ch2='8'; int nums2=Integer.parseInt(ch2.toString());//表示将ch2用10进制转换 System.out.println(nums2);//8 数字转化为字符 1.这种强制类型转换只是将其转换为对应的ASCII码值 int a=97; char b=(char)a; System.out.println(b);//a 2.将数字转化为字符数字 int num1=8; char ch1=(char)(num1+48); System.out.println(ch1);//8
    admin 今天
  • NC119 最小的K个数(堆)
    其他

    NC119 最小的K个数(堆)

    描述 给出一个长度为n的可能有重复值的数组,找出其中不去重的最小的k个数 例: 输入:[4,5,1,6,2,7,3,8],4 返回:[1,2,3,4] 要求:空间O(N),时间O(nlogn) 解题思路 方法一:直接排序取前k个值 方法二:堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。首先简单了解下堆结构。 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。如下图: 该数组从逻辑上讲就是一个堆结构,我们用简单的公式来描述一下堆的定义就是: 大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 小顶堆:arr[i] <= arr[2i+1] && arr[i] <=
    admin 今天
  • 浙江大学陈越教授数据结构PTA 题目——7-1 词频统计
    其他

    浙江大学陈越教授数据结构PTA 题目——7-1 词频统计

    ????  #include #include #include #include #include #define KEYLENGTH 15//长度超过15的单词将只截取保留前15个单词字符 #define MAXTABLESIZE 111111//允许开辟的最大散列表长度 #define MAXWORDLEN 80 //单词输入的最大长度 typedef char ElementType[KEYLENGTH+1];//链表的数据域是一个字符串 typedef int Index;//散列地址类型 typedef struct LNode *PtrToLNode;//单链表一个结点的定义 struct LNode{ ElementType Data;//结点的数据域是一个字符串 int Count;//存储该单词的出现次数,空头结点的Count用来存储该单链表的结点数 PtrToLNode Next; }; t
    admin 今天
  • chroot_list的说明(FTP)
    其他

    chroot_list的说明(FTP)

    对于/etc/vsftp.conf文件中的3选项的关系结构   如果设置为 chroot_local_user=YES chroot_list_enable=YES(这行可以没有, 也可以有) chroot_list_file=/etc/vsftpd.chroot_list 那么, 凡是加在文件vsftpd.chroot_list中的用户都是不受限止的用户 即可以浏览其主目录的上级目录。 所以, 如果不希望某用户能够浏览其主目录上级目录中的内容,可以如上设置, 然后在文件vsftpd.chroot_list中不添加该用户即可(此时, 在该文件中的用户都是可以浏览其主目录之外的目录的). 或者, 设置如下 chroot_local_user=NO chroot_list_enable=YES(这行必须要有, 否则文件vsftpd.chroot_list不会起作用) chroot_list_file=/etc/vsftpd.chroot_list 然后把所有不希望有这种浏览其主目录之上的各目录权限的用户添加到文件vsftpd.chroo
    admin 今天
  • 6-1 二分查找 (10 分)
    其他

    6-1 二分查找 (10 分)

    本题要求实现二分查找算法。 函数接口定义: Position BinarySearch( List L, ElementType X ); 其中List结构定义如下: typedef int Position; typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last; /* 保存线性表中最后一个元素的位置 */ }; L是用户传入的一个线性表,其中ElementType元素可以通过>、==、<进行比较,并且题目保证传入的数据是递增有序的。函数BinarySearch要查找X在Data中的位置,即数组下标(注意:元素从下标1开始存储)。找到则返回下标,否则返回一个特殊的失败标记NotFound。 裁判测试程序样例: #include #include
    admin 今天