Java数据结构和算法（四）——栈 前面我们讲解了数组，数组更多的是用来进行数据的存储，纯粹用来存储数据的数据结构，我们期望的是插入、删除和查找性能都比较好。对于无序数组，插入快，但是删除和查找都很慢，为了解决这些问题，后面我们会讲解比如二叉树、哈希表的数据结构。 而本篇博客讲解的数据结构和算法更多是用作程序员的工具，它们作为构思算法的辅助工具，而不是完全的数据存储工具。这些数据结构的生命周期比数...
Java数据结构和算法（三）——几种常用的排序算法 上一篇博客我们实现的数组结构是无序的，也就是纯粹按照插入顺序进行排列，那么如何进行元素排序，本篇博客我们介绍几种简单的排序算法。1、冒泡排序 这个名词的由来很好理解，一般河水中的冒泡，水底刚冒出来的时候是比较小的，随着慢慢向水面浮起会逐渐增大，这物理规律我不作过多解释，大家只需要了解即可。 冒泡算法的运作规律如下： ①、比较相邻的元素。如果第一...
Java数据结构和算法（九）——高级排序 春晚好看吗？不存在的！！！ 在Java数据结构和算法（三）——冒泡、选择、插入排序算法中我们介绍了三种简单的排序算法，它们的时间复杂度大O表示法都是O(N2)，如果数据量少，我们还能忍受，但是数据量大，那么这三种简单的排序所需要的时间则是我们所不能接受的。接着我们在讲解递归 的时候，介绍了归并排序，归并排序需要O(NlogN)，这比简单排序要快了很多，但是归并排序有个缺点，它...
Java数据结构和算法（十五）——图 前面我们介绍了树这种数据结构，树是由n（n>0）个有限节点通过连接它们的边组成一个具有层次关系的集合，把它叫做“树”是因为它看起来像一棵倒挂的树，包括二叉树、红黑树、2-3-4树、堆等各种不同的树，有对这几种树不了解的可以参考我前面几篇博客。而本篇博客我们将介绍另外一种数据结构——图，图也是计算机程序设计中最常用的数据结构之一，从数学意义上讲，树是图的一种，大家可以对比着...
Java数据结构和算法（十四）——堆 在Java数据结构和算法（五）——队列中我们介绍了优先级队列，优先级队列是一种抽象数据类型（ADT），它提供了删除最大（或最小）关键字值的数据项的方法，插入数据项的方法，优先级队列可以用有序数组来实现，这种实现方式尽管删除最大数据项的时间复杂度为O(1)，但是插入还是需要较长的时间 O(N)，因为每次插入平均需要移动一半的数据项，来保证插入后，数组依旧有序。 本篇博客我们介绍...
Java数据结构和算法（十三）——哈希表 Hash表也称散列表，也有直接译作哈希表，Hash表是一种根据关键字值（key - value）而直接进行访问的数据结构。它基于数组，通过把关键字映射到数组的某个下标来加快查找速度，但是又和数组、链表、树等数据结构不同，在这些数据结构中查找某个关键字，通常要遍历整个数据结构，也就是O(N)的时间级，但是对于哈希表来说，只是O(1)的时间级。 注意，这里有个重要的问题就是如何把关键字转...
Java数据结构和算法（十二）——2-3-4树 通过前面的介绍，我们知道在二叉树中，每个节点只有一个数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树。本篇博客我们将介绍的——2-3-4树，它是一种多叉树，它的每个节点最多有四个子节点和三个数据项。1、2-3-4 树介绍 2-3-4树每个节点最多有四个字节点和三个数据项，名字中 2,3,4 的数字含义是指一个节点可能含有的子节点的个数。对于...
一些简单的算法与数据结构 稀疏数组 int chessArr1[][] = new int[11][11];//11*11的数组int sum = 0;chessArr1[1][2] = 1;//设置两个值chessArr1[2][3] = 2;//打印原数组for(int[] row : chessArr1) {for(int data : row) {System.out.printf("%d\t", data);if(data != 0) sum++;}System.out.println();}//稀疏数组建立int sparseArr[][] = new int[sum + 1][3];sparseArr[0][0] = 11;sparseArr[0][1] = 11;sparseArr[0][2] = sum...
问题描述：给定两个边与坐标轴平行的矩形，分别由左上角与右下角两点指定，即矩形(P1，P2)与(P3，P4)，判断两矩形是否相交。我的思路：假设两矩形的宽高分别是 w1，h1，w2，h2。分别计算两个矩形的中心点 O1，O2，以及 O1 和 O2 之间的水平距离（w）和竖直距离（h）。若 w < ( w1 + w2 ) / 2 且 h < ( h1 + h2 ) / 2，则两个矩形相交，否则不相交。代码实现：/* struct Rect { float x1, y1; // Point 1 float x2, ...
问题描述：从1到n共n个连续有序的数字,任意去掉2个,把剩下的(n-2)个打乱顺序放到了一个整形数组中,求出那两个去掉的数字？不能通过排序实现。这道问题，如果用排序的话是非常简单的，先排序，然后遍历一遍，很容易就能找出去掉的数字，时间复杂度为O（nlogn）。不过题目要求不能排序，所以另一个很容易想到的方法就是两层 for 循环嵌套，第一层循环遍历 1 - n，第二层循环遍历数组，也可以实现。不过时间复杂度有点高，是 O（n^2）...
最近找工作面试，真的是被数据结构和算法给反复吊打了。平时做项目基本都是在写业务逻辑，即使遇到了关于数据结构算法的东西，也是一个接口调用搞定。基础的一些东西反而薄弱了，拿排序算法来说吧，长时间不写，光是记清楚算法复杂度就够呛了，更别说手撸算法了。痛定思痛，决心还是放低心态，从基础做起，把每个算法亲手敲一遍。排序算法是最基础的算法，也是面试官比较容易问到的算法。就像相声演员需要联系 “说学逗唱” 四门基...
数据结构和算法绪论 数据结构： 程序设计 = 数据结构 +算法 数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。 简单来说数据结构就是关系，是数据元素相互之间存在的一种或多种特定关系的集合。 一、逻辑结构: 是指数据对象中数据元素之间的相互关系，也是我们今后最需要关注和讨论的问题。物理结构:是指数据的逻辑结构在计算机中的存储形式。 1.集合结构 2.线性结构 3.树形结构...
任务假设二叉树采用链式方法存储，数据结构定义如下：typedef char DataType; struct node {DataType info ;struct node *lchild , *rchild ; };完成两个函数编写请编写算法计算二叉树T的高度的函数 请编写算法计算二叉树T的叶子结点数的函数已知某二叉树的先根周游序列是：ABDEGCFHIJ，中根周游序列是：DBGEAHFIJC，画出这课二叉树，并给出二叉树的后根周游序列。3.已知了一棵二叉树的顺序存储结构如下，其中空白表示结点不存在。...
1250. 格子游戏? 分析：显然，当出现闭环的时候，就会出现我们当前节点和要到达的节点出现一个闭环 代码：1 #include <bits/stdc++.h>2 3 using namespace std;4 5 const int N = 210;6 7 int n, m;8 int g[N][N], tot;9 int f[N * N]; 10 11 int get(int x) 12 { 13 return f[x] == x ? x : f[x] = get(f[x]); 14 } 15 int main() 16 { 17 cin >> n >> m; 18 for (int i = 1; i <= n; i ++ ) 19 for (int j = 1; j <=...
大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。64根柱子移动完毕之日，就是世界毁灭之时。def hanio(n,a,b,c): if n > 0: hanio(n-1,a,c,b) print(moving from %s to %s%(a,c)) hanio(n-1,b,a,c)hanio(2,A,B,C) 汉诺塔移...