2 楚楚可薇

尚未进行身份认证

我要认证

带着一点火光,吸足氧气,一路燃烧

等级
TA的排名 7k+

数组-堆排序

一、思路数组可以抽象成一个堆结构。堆的深度为log,由一个乱序数组变成一个堆数组时间复杂度为O(nlogn),堆顶元素是最值,每次从堆顶弹出一个元素,重复进行n-1次后,数组有序。下面定义一些堆排序的相关操作:HEAPIFY 建堆:把一个乱序的数组变成堆结构的数组,时间复杂度为 O(nlogn)。 HEAPPOP:从最大堆中取出最大值或从最小堆中取出最小值,并将剩余的数组保持堆结构,...

2019-11-26 19:21:39

树-二叉树的最大深度

来源LeetCode第104题一、思路给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。一棵深度为3的二叉树数据结构在逻辑上可以分为线性结构、非线性结构。很明显,树和图一样都是非线性结构,额外地,图的遍历算法(深度优先遍历和广度优先遍历)对树同样适用。我们来思考一下,如果想要求得树的最大深度,需要什么?如果是深度优先遍历的话,必须找到从...

2019-11-18 17:23:51

树-二叉树遍历

一、思路遍历实际上是按照某种顺序访问结点,比较典型的有先序、中序、后序、层序等。二叉树天然具有子结构,即左子树和右子树同样是二叉树,就是规模更小而已。二叉树三种遍历方式1.1 先序栈S;p= root;while(p || S不空){ while(p){ 访问p节点; p的右子树入S; //暂存右子树 p = p的左子树;...

2019-11-17 20:22:06

删除链表的倒数第N个结点

题目来源LeetCode第19题一、思路假设能够找到倒数第N个结点,想要删除它,必须知道倒数第N+1个结点的位置。由此就形成了两个小技巧。1)使用两根指针分别指向倒数第N个结点个倒数第N+1个结点;2)仅使用1根指针指向倒数第N+1个结点。有可能会修改头指针的值,所以我们使用额外的小技巧——哑结点来统一操作。问题来了,如何找到倒数第N个结点呢?双指针就可以解决了。以下两份代码,一份...

2019-11-17 15:23:24

单链表-归并排序

题目来源148排序链表一、思路在O(nlogn) 时间复杂度和常数级空间复杂度下,对链表进行排序。举例:例1:输入: 4->2->1->3输出: 1->2->3->4例2:输入: -1->5->3->4->0输出: -1->0->3->4->5对单链表进行排序,我们八九不离...

2019-11-17 14:24:39

数组-将有序数组转换为二叉搜索树

题目来源LeetCode第108题一、思路将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。举例:给定有序数组: [-10,-3,0,5,9],1.1 递归分析有序链表转换二叉搜索树TreeNode* sortedArrayToBST(vector<int&...

2019-11-16 20:45:31

单链表-有序链表转换二叉树

题目来源LeetCode第109题一、思路给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。举例,给定的有序链表: [-10, -3, 0, 5, 9],可能的树的形态如下图所示:1.1 递归分析递归三要素:终止条件、执行单元、返回值。其中执行单元是将待解决的问题...

2019-11-16 19:29:45

单链表-回文链表

题目来源LeetCode第234题一、思路请判断一个链表是否为回文链表。举例:例1:输入: 1->2输出: false例2:输入: 1->2->2->1输出: true要求:时间复杂度为O(n),空间复杂度为O(1)(打消了借用栈的念头)。1.1 知识点预备知识:单链表中间结点、单链表的反转1.2 知识点我们先抽象到线...

2019-11-16 14:56:09

单链表-两数相加

题目来源LeetCode第445题一、思路给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。举例:输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)输出: 7 -> 8 -> 0 -> 7抽象至逻辑结构的层面,实际上就是竖式加...

2019-11-16 11:11:04

单链表-奇偶链表

题目来源一、思路给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。举例:例1:输入: 1->2->3->4->5->NULL输出: 1->3->5->2->4->NULL例2:输入: 2->1->3->5-...

2019-11-15 20:13:54

单链表-链表的中间结点

一、思路给定单链表,返回链表的中间结点。如果有两个中间结点(总结点个数为偶数),则返回第二个中间结点。举例:例子1:输入:[1,2,3,4,5]输出:结点 3例子2:输入:[1,2,3,4,5,6]输出:结点 4从以上两个例子可以总结出全体,因为结点个数非奇即偶。如果是数组的话,我们会利用下标间的关系——n/2即可(n为数组元素个数),但是单链表不满足随机存取的要求(...

2019-11-15 19:23:26

单链表-删除所有给定值为val的所有结点

一、思路删除链表中等于给定值val的所有节点。举例:输入: 1->2->6->3->4->5->6, val = 6输出: 1->2->3->4->51.1 迭代分析为了统一对不带头结点的单链表的结点的操作,额外使用哑结点。使用指针prev始终指向判断是否删除的结点的前驱,如果条件满足,删除prev->next...

2019-11-15 16:34:46

单链表-反转

一、思路描述:反转一个单链表。举例:输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL1.1 迭代分析单链表无法直接向后指,因为只有1个next域。所以需要使用指针prev作为指针current(需要逆置的结点)的前驱指针。为了防止逆置之后断链,额外需要一个save指针保存逆置前...

2019-11-15 16:20:16

单链表-链表相交问题

题目来源:LeetCode160求两单链表的交点一、思路举例1-相交的情形举例2-不相交的情形如果两个链表没有交点,返回 null. 在返回结果后,两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。1.1 知识点直观感觉,如果两条链表有交点,那么由于单链表的关系(只有唯一后继),交点之后都...

2019-11-15 15:18:22

单链表-插入排序

一、思路写在前面,递归和迭代的分析是不同的,如果我们希望利用递归实现,就掌握与递归有关的知识点;如果我们希望用迭代实现,就掌握与迭代有关的知识点。先掌握一种,然后掌握另一种。1.1 知识点1 单链表单链表是一种只能前进,不能后退的链表。为了找到当前结点的前一个,必须有一个前驱指针紧紧跟随。很明显,可以用栈(用户栈或者系统栈)帮助我们找到前驱结点。1.2 知识点 插入排序让我们先...

2019-11-14 15:58:35

数据结构考研3_荷兰国旗问题

一、题目描述设有一个仅由红、白、蓝三种颜色的条块组成的条块序列,请编写一个时间复杂度为O(n)的算法,使得这些条块按照红、白、蓝的顺序排好,即排成荷兰国旗的图案。1.1 思路顺序扫描线性表(图上反映为从上到下),将红色条块交换到线性表的最前面,蓝色条块交换到线性表的最后面。设立三个指针,low和high标记中间条块(即白色条块)的范围,low之前的全部为红色,high之后的全部为...

2019-06-28 20:21:25

数据结构考研2_中位数问题

利用划分函数快速查找中位数。

2019-06-28 19:11:56

数据结构考研博客目录

数据结构编程题数据结构考研1_找到第K小的数字数据结构考研2_中位数问题数据结构考研3_荷兰国旗问题

2019-06-28 17:14:40

数据结构考研1_找到第K小的数字

一、思路分析针对下标从零开始,没有哨兵位。如果采用快速排序中的划分思想,该思想结合具体问题(找到第k小)形成的思路如下:按照一定规则选取枢轴元素(固定位置法、三数取中法、随机数法等),对枢轴元素进行划分。枢轴元素下标记为pivotIndex,在序列中排第seq = pivotIndex+1小。当seq == k,找到并返回; 当seq < k,在后半子序列中查找第 k-seq ...

2019-06-28 17:10:55

内存管理方案视频课

https://www.bilibili.com/video/av35170969/?spm_id_from=333.788.videocard.1

2019-06-06 12:10:14

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。