• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

标签:数据结构

植树节,程序猿种的那些树

1. 二叉搜索树定义二叉搜索树又称二叉查找树,亦称为二叉排序树。设 x 为二叉查找树中的一个节点,x 节点包含关键字 key,节点x 的 key 值记为 key[x] 。如果 y 是 x 的左子树中的一个节点,则 key[y] <= key[x] ;如果 y 是 x 的右子树的一个节点,则 key[y] >= key[x] 。查……

几道和「堆栈、队列」有关的面试算法题

 题目一:有效的括号问题描述给定一个只包括 ‘(‘,’)’,'{‘,’}’,'[‘,’]’ 的字符串,判断字符串是否有效。解题思路这道题让我们验证输入的字符串是否为括号字符串,包括大括号,中括号和小括号。这里我们……

链表算法面试问题?看我就够了!

1 引言单链表的操作算法是笔试面试中较为常见的题目。本文将着重介绍平时面试中常见的关于链表的应用题目。2 输出单链表倒数第 K 个节点2.1 问题描述题目:输入一个单链表,输出此链表中的倒数第 K 个节点。(去除头结点,节点计数从 1 开始)。2.2 两次遍历法2.2.1 解题思想(1)遍历单链表,遍历同时得出链表长度 N 。……

详解什么是平衡二叉树(AVL)(修订补充版)

前言Wiki:在计算机科学中,AVL树是最早被发明的自平衡二叉查找树。在AVL树中,任一节点对应的两棵子树的最大高度差为1,因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logn)。增加和删除元素的操作则可能需要借由一次或多次树旋转,以实现树的重新平衡。AVL 树得名于它的发明者 G. M. Adelso……

准备下次编程面试前你应该知道的数据结构

国外 IT 教育学院 Educative.io 创始人 Fahim ul Haq 写过一篇过万赞的文章《The top data structures you should know for your next coding interview》,总结了程序员面试中需要掌握的 8 种数据结构知识。Fahim ul Haq 曾在 Faceb……

红黑树的理解与Java实现

前言前段时间在研究 JDK1.8 的 hashmap 源码,看到 put 方法的插入环节,遇到了红黑树,不得不停止阅读源码的过程,因为还没掌握红黑树是无法完全读透 hashmap 源码的。红黑树作为一种数据结构,它被应用得非常多,可能很多人不认识它,但其实它已经在默默为我们的代码在发光发热。例如,你只要在 Java 中用到 map,基本上就是……

2019秋招-数据结构笔试选择题整理

数据结构笔试选择题整理1、 一颗二叉树的后序遍历序列为DBFEGCA,中序遍历为DBAFECG,则先序遍历为( )[2019 贝壳]A. ABDCEFGB. ADCDEFGC. ADBFEGCD. ABDCFEG2、设有n个元素进栈序列是1,2,……n,其出栈序列是C1,C2,C3,Cn,若C2=3,以下说法正确的是( )[2019 贝壳]A.……

动画:什么是散列表?

散列表散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。散列函数散列函数,顾名思义,它是一个函数。如果把它定义成 hash(key) ,……

优先队列实现原理分析

优先队列是在实际工程中被广泛应用的一种数据结构,不管是在操作系统的进程调度中,还是在相关的图算法比如Prim算法和Dijkstra算法中,我们都可以看到优先队列的身影,本文我们就来分析一下优先队列的实现原理。优先队列以操作系统的进程调度为例,比如我们在使用手机的过程中,手机分配给来电的优先级都会比其它程序高,在这个业务场景中,我们不要求所……

二叉树的非递归遍历

二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现。在三种遍历中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现……

Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

瑞士计算机科学家Niklaus Wirth在1976年写了一本书,名为《算法+数据结构=编程》。40多年后,这个等式仍被奉为真理。这就是为什么在面试过程中,需要考察软件工程师对数据结构的理解。几乎所有的问题都需要面试者对数据结构有深刻的理解。无论你是初入职场的新兵(刚从大学或者编程培训班毕业),还是拥有几十年经验的职场老鸟。有些……

2-3-4树是如何解决二叉树中非平衡问题的?

我之前写过一篇文章:下次面试若再被问到二叉树,希望你能对答如流!没错,二叉搜索树是个很好的数据结构,可以快速地找到一个给定关键字的数据项,并且可以快速地插入和删除数据项。但是二叉搜索树有个很麻烦的问题,如果树中插入的是随机数据,则执行效果很好,但如果插入的是有序或者逆序的数据,那么二叉搜索树的执行速度就变得很慢。因为当插入数值有序时,二叉树……

红黑树详细分析,看了都说好

 一、红黑树简介  红黑树是一种自平衡的二叉查找树,是一种高效的查找树。它是由 Rudolf Bayer 于1972年发明,在当时被称为对称二叉 B 树(symmetric binary B-trees)。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑……

读完这篇,希望你能真正理解什么是哈希表

哈希表也称为散列表,是根据关键字值(key value)而直接进行访问的数据结构。也就是说,它通过把关键字值映射到一个位置来访问记录,以加快查找的速度。这个映射函数称为哈希函数(也称为散列函数),映射过程称为哈希化,存放记录的数组叫做散列表。比如我们可以用下面的方法将关键字映射成数组的下标:arrayIndex=hugeNumber%arra……

一文读懂 AVL 树

背景AVL 树是一棵平衡的二叉查找树,于 1962 年,G. M. Adelson-Velsky 和 E. M. Landis 在他们的论文《An algorithm for the organization of information》中发表。所谓的平衡之意,就是树中任意一个结点下左右两个子树的高度差不超过 1。(本文对于树的高度约……

二叉树实战 22 题,速度收藏吧!

先上二叉树的数据结构:classTreeNode{    int val;    //左孩子    TreeNode left;    //右孩子    TreeNode right;}二叉树的题目普遍可以用递归和迭代的方式来解1. 求二叉树的最大深度intmaxDeath(TreeNode node){    i……

动态图展示常用数据结构的特点和基本操作

最近在整理数据结构方面的知识,系统化看了下Java中常用数据结构,突发奇想用动画来绘制数据流转过程。主要基于jdk8,可能会有些特性与jdk7之前不相同,例如LinkedList LinkedHashMap中的双向列表不再是回环的。HashMap中的单链表是尾插,而不是头插入等等,后文不再赘叙这些差异,本文目录结构如下: 1. Lin……

堆其实是个很简单的数据结构

说到堆这种数据结构,很多人的第一反应是感觉很复杂,其实不然,堆就是个优先级队列而已,或者,堆其实就是一种树。本文先讲原理,后面给出堆的实现代码。优先级队列可以用有序数组来实现,这种做法的问题是,尽管删除最大数据项的时间复杂度为O(1),但是插入还是需要较长的O(N)时间,这是因为必须移动数组中平均一半的数据项以插入新数据项,并在完成插入后,数……

初学者应该了解的数据结构:Array、HashMap 与 List

当开发程序时,我们(通常)需要在内存中存储数据。根据操作数据方式的不同,可能会选择不同的数据结构。有很多常用的数据结构,如:Array、Map、Set、List、Tree、Graph 等等。(然而)为程序选取合适的数据结构可能并不容易。因此,希望这篇文章能帮助你了解(不同数据结构的)表现,以求在工作中合理地使用它们。本文主要聚焦于线性的数据结构……

可以管理时间的二叉堆

面试官:写一个堆排吧我心想:堆排是什么鬼理解堆排,首先要理解二叉堆。理解了二叉堆的“下沉”操作,基本上就可以理解堆排了。今天我们来看一看什么是堆,以及堆的一般操作优先级队列近日,谦子遇到了烦心事,于是找老师去诉苦了老师,最近好烦啊……

堆和堆的应用:堆排序和优先队列

1.堆堆(Heap))是一种重要的数据结构,是实现优先队列(Priority Queues)首选的数据结构。由于堆有很多种变体,包括二项式堆、斐波那契堆等,但是这里只考虑最常见的就是二叉堆(以下简称堆)。堆是一棵满足一定性质的二叉树,具体的讲堆具有如下性质:父节点的键值总是不大于它的孩子节点的键值(小顶堆), 堆可以分为小顶堆和大顶堆,这里以小……

单链表有环问题

小咖是某某计算机专业的学生。linglingling,伴随这铃声,同学们都准时来上课了。老师:这节课是计算机课,我们学习了单链表,请同学说一下什么是单链表。同学们纷纷举起了手。好,小白你来说。小白:单链表是一种线性表,它的存储单元可以不是连续的,从头节点开始,每个节点都有一个指针,指向下一个节点,最后一个节点指向null,头节点不被指……

二叉查找树实现原理分析

引言二叉查找树是一种能将链表插入的灵活性和有序数组查找的高效性结合起来的一种重要的数据结构,它是我们后面学习红黑树和AVL树的基础,本文我们就先来看一下二叉查找树的实现原理。二叉查找树的定义二叉查找树最重要的一个特征就是:每个结点都含有一个Comparable的键及其相关联的值,该结点的键要大于左子树中所有结点的键,而小于右子树中所有……

史上最清晰的红黑树讲解(上)

本文以Java TreeMap为例,从源代码层面,结合详细的图解,剥茧抽丝地讲解红黑树(Red-Black tree)的插入,删除以及由此产生的调整过程。总体介绍Java TreeMap实现了SortedMap接口,也就是说会按照key的大小顺序对Map中的元素进行排序,key大小的评判可以通过其本身的自然顺序(natural ord……

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00