- 博客(66)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 二叉搜索树和有序数组的转换
二叉搜索树的特点：中序遍历的序列是一个有序序列/数组。这里主要展示有序数组转换为二叉搜索树，但是这样的二叉搜索树为多个。所以这里可以参看leetcode 108.将有序数组转换为二叉搜索树，加上了“平衡的条件”，尽管此时二叉搜索树的个数还是多个，但是在构造BST时很方便。只需要“不断的折半”即可。参考代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode
2020-07-17 00:06:13
667
原创 以1-N为节点的二叉搜索树的个数和生成对应的二叉搜索树
输入: 3输出: 5解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:要满足是二叉搜索树，以i为root， 左子树的个数为i-1(比i小的数)，右子树的个数为n-i(比i大的数)。此时如果出现个数为0，表示空树，记作1；只有一个节点，表示只有根的树，也记作1.f(i)=f(i-1)*f(n-i) (一一组合配对构成整个二叉搜索树)所以1-n为节点构成的二叉搜索树的个数为：参看代码：class Solution {public: int numTr
2020-07-16 23:44:07
957
原创 数组中第K大(小)的元素
在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。这是一道排序问题？但是当数组元素N很大时，采用一般O(N^2)的排序算法(如冒泡排序)一定会超时。所以这里可以使用快排和堆排。这里快排和堆排的思想就不详细介绍了，有兴趣的可以去看我的其他文章或者直接baidu一下。1.直接快速排序，对整个数组进行排序lass Solution {public: int findKthLargest(vector<int..
2020-07-06 22:37:18
390
原创 拓扑排序
什么是拓扑排序？此处采用百度百科的解释：执行步骤：循环执行以下两步，直到不存在入度为0的顶点为止。(1) 选择一个入度为0的顶点并输出之；(2) 从网中删除此顶点及所有出边。循环结束后，若输出的顶点数小于网中的顶点数，则输出“有环路”信息，否则输出的顶点序列就是一种拓扑序列。一个简单的实例(过程)：实现：利用邻接矩阵表示两者的关系。将上述示例中的图用邻接矩阵表示：参考代码：#include<iostream>#include<cs
2020-06-24 00:36:50
238
原创 链表中的双指针
链表中的双指针，一般是指初始时设置两个移动指针，它们可能以不同的初始状态或不同的移动方式进行移动。1.删除链表的倒数第N个节点题目描述：给定一个链表，删除链表的倒数第n个节点，并且返回链表的头结点。示例：给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5.说明：给定的 n保证是有效的。进阶：你能尝试使用一趟扫描实现吗？思路：不同的初始状态，一个指针从头开始移动，一个...
2020-06-23 11:59:19
1183
原创 滑动窗口(一)
什么是滑动窗口？大致就是如下图:维护left和right两个指针，在整个区间内，通过改变左右指针的移动，找到满足条件的区间(很多时候是最佳区间)。所以窗口的大小是在移动过程中改变的。目的：常用于将嵌套的循环问题，转换为单循环问题，降低时间复杂度。常用于解决数组/字符串的子元素问题。问题1及解决思路：1.先计算出前K个元素的和(即arr[0] + ...+ arr[k-1])。2.从i=k to arr.size() - 1, sum += arr[i] - arr[i-k]; /
2020-06-18 21:37:11
333
原创 单调栈
什么是单调栈？这个概念是在leetcode做题时接触的，就是通过栈的push()和pop()操作，维护一个有序的序列(依次出栈的元素)。如：7 4 3 8 10 9 13下面则通过leetcode中的题目来说明它如何在问题中使用?739. 每日温度题目描述:请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用0来代替。例如，给定一个列表temperatures = [73, 74, 75...
2020-06-12 21:06:25
199
原创 并查集(Union-find set)
它是一种维护集合的数据结构,它的名字"并" "查" "集" 。即 union / find / set。并查集产生的每个集合都是一棵树(tree) 。基本操作：1.合并两个集合union。2.判断两个元素是否在一个集合中find。实现：利用一个数组int father[N];其中父节点自身也在1-N之中用来记录父节点：即father[i]表示的i节点的父亲节点。当a和b的father[a]==father[b]时，a和b才是联通的。初始化：void init(int fa[], i..
2020-06-08 20:13:36
365
原创 递归模拟哈诺塔移动过程
汉诺塔问题：https://baike.baidu.com/item/%E6%B1%89%E8%AF%BA%E5%A1%94/3468295?fr=aladdin思路：先借助C将A上面n-1个盘子移到B中；然后将A上最大的盘子移到C中；再借助A将B上的n-1个盘子移动到C上。#include<iostream>using namespace std;void mov...
2020-05-05 21:18:28
245
原创 *p, *&p, &*p的区别
#include<iostream>using namespace std;int main(){ //&: 取地址(引用), *取值(解引用) int a = 10; int *p = &a; //&a: 取a的地址值, p是一个指针，指向a cout << "*p=" << *p << ", p=" &...
2020-05-01 22:57:57
2847
原创 LRU缓存机制
本文借助leetcode中的一道题目，来介绍LRU的相关知识，以及如何实现它。leetcode 146:问题：运用你所掌握的数据结构，设计和实现一个LRU(最近最少使用)缓存机制。它应该支持以下操作: 获取数据get和写入数据put。获取数据get(key)：如果密钥(key)存在于缓存中，则获取密钥的值(总是正数), 否则返回-1。写入数据put(key, value)：如果密钥不存...
2019-11-02 12:46:25
218
原创 前序序列和中序序列、中序序列和后序序列生成二叉树
今天分享的内容，也是结合leetcode中的两题，大家可以理清思路后可以去平台做一下题，检验一下成果。首先我们还是得理解三种遍历方式的特征：preorder: 先序遍历中，先遍历root，也就是说在先序序列中的第一个元素即原二叉树的root节点。同理，在postorder中，由于先遍历left & right 也就是说后序序列中的最后一个元素是二叉树的root节点。inor...
2019-10-27 16:06:14
2942
原创 树的三种遍历方式的实现(递归&非递归&C++)
本篇文章结合结合leetcode(94、144、145 二叉树的中序、前序、后序遍历方式)中的三道题，介绍树的前序、中序、后序遍历的递归和非递归实现。先简单介绍一下，三种方式遍历时的特征:preorder: root left right.inorder: left root rightpostorder: left right root描述一个二叉树:/*** Defi...
2019-10-27 15:33:04
489
原创 蓄水池采样问题(Reservoir sampling question)
问题: 在给定的但未知其大小的数据集中，随机等概率的抽取一个元素。分析: 如果知道数据集的大小，可以直接rand() % len得到一个确切的位置。所以未知长度时，即可使用蓄水池采样。算法思路: 总是选择第一个对象，以的概率选中第二个数据，依次类推... 以的概率选中第m个数据。此时可以保证被选中的概率为。第m个被选中，那么就是说后面的都不被选中(第m个数据不被选中，前m - 1个随机选...
2019-10-15 23:25:21
211
原创 OJ常规题------利用结构体解决学生成绩排序的问题
此类问题一般是输入N个学生的个人信息，一般包括学生的姓名、学号、年纪、成绩......这些信息，我们将每个学生的这些信息组合起来，利用Struct声明一个结构体，将它的信息作为其成员变量。然后我们根据它的排序要求编写进行计较规则的方法，取名cmp()。再调用系统的sort函数即可（需要加声明：#include<algorithm>）。通过几个例题来看一下这类问题的解题思路。提示...
2018-07-16 23:04:06
2220
1
原创 反射(Reflection)总结
一、基础概念1、反射（Reflection）就是将一个Java类中的每一个成分解析成一个Java类。Java类用一个Class类的对象表示，其中一个类的基本组成成分：成员变量、方法、构造方法等信息用一个个的类来表示。而这个类的Class类选举要提供一系列的方法来获取其中的变量、方法等信息，这些信息使用 类的实例对象 来表示， 分别有Field、Constructor、Method、Pack...
2018-07-08 17:57:07
311
原创 大数排序+大数相加+大数相乘
在我们通常遇到的数的计算中，往往范围比较小，int、long、long long等就可以满足，但是在一些题目或者特殊情况时，我们遇到的数位数很长，基本的一些数据类型显然不满足，所有采用字符型数组输入这个数字，进行一些计算。(char [] 或者string；注意：char[]结尾一定要有'\0'字符)。下面通过三个例题介绍一些大数的相关操作。1、大数排序我们可以利用输入字符串的长度对这些数进行比较...
2018-07-03 17:49:53
473
原创 给出描述的n个节点，求其邻居节点以及判断两个节点是否有直接联系
具体描述：txt文件中存储n个节点直接的联系，形如1,2表示节点1和节点2直接联系，或者说他们是邻居。有很多组这样的数据，要求将这些节点读出来进行存储。然后实现输入节点号，输出它的邻居节点。以及输入两个节点ID号，判断他们是否直接相连。分布解析这个题目要求。1、先读取txt文件中的数据,用ArrayList<Integer[]>将每一行数据存储下来。然后给这些数据构建数据关系。去读这个...
2018-06-23 14:00:27
5529
原创 求解组合数取模---拓展欧几里德和费马小定理求解逆元
组合数：C(n, m) ; 组合数取模：C(n, m) % mod，mod是一个很大的数。1.公式：2.性质：（1）C(n,m)= C(n,n-m) 其中有C(n, 0) = 1; （2）C(n,m)=C(n-1,m-1)+C(n-1,m)。可以用作递归中的公式。性质2和杨辉三角的相似性（核心部分就是利用了性质2）。例题：打印杨辉三角：#include<i...
2018-06-13 15:24:41
751
原创 动态规划解决---最长递减（或递增）序列
定义：在一个没有排好序的数组中，找最长的单调递减或单调递增的序列。解题思路：通过动态规划解题。假设从0--（i - 1)已经构成了长度为s的递减序列，且这些序列中的末尾值中的最大值为t;1、如果a[i] < t，则假如到这个序列中去，长度变为s + 1。对应的末尾值变为a[i]。2、如果a[i] == t， 则说明从0 - i 的最长序列长度为s。3、如果a[i] > t，a[i]不一...
2018-06-10 20:28:43
2588
原创 （C语言）链表的实现集合的相关操作
集合的特征：确定性/ 互异性/ 无序性。常见的操作：1、查找集合中是否包含这个数据元素：Contains();2、添加一个新成员数据，集合中不能存在这个元素。AddMember();3、删除指定元素， 找到这个元素， 删除；如果没找到，则提示没找到，返回0（表示false）。Delete();4、合并两个集合，不能有相同的元素。5、求交集，找相同的元素。6、求差集，例如：A{1, 2, 3}。B{...
2018-06-01 22:38:43
2331
1
原创 python基础及实现词法分析器的基本实现
python基础：1、list的使用，即列表。定义：list(列表名) = []；如下还有对他的遍历，这里的word算是定义了一个变量去存储res[i]的值：# -*- coding: cp936 -*-if __name__=="__main__": res = [] res = ["hello", "you", "are", "good"] i = 0#对列表...
2018-05-24 21:22:35
14006
4
原创 图的基本概念及存储结构
图的基本概念：定义：图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V(vertex)是图G中顶点的集合，E(edge)是图G中边的集合。分类：1、按有无方向分类：有向图和无向图。无向图由顶点和边组成，有向图由顶点和弧组成， 弧有弧头(head)和弧尾(tail)两部分。2、如果任意的两个顶点之间都存在边，叫完全图；有向的图叫有向完全图。...
2018-05-22 16:42:17
1793
原创 前缀、中缀、后缀表达式及中缀转后缀表达式
前缀表达式：不含括号的算术表达式，而且是将运算符写在前面，操作数写在后面的表达式。求法：首先从右往左扫描表达式，从右边第一个字符判断，如果当前字符是数字，则一直到字符串的末尾再记录下来；如果是运算符，则将右边最近的两个数字串做相应的运算，以此作为一个新串并记录下来。一直扫描到最左端停止。例子：（a + b)* (c + d) : *+ab+cd。理解：根据优先级，把数字位置不同，有那两个可以做运...
2018-05-19 23:38:26
4461
1
原创 查找（一）-----顺序表的顺序查找和折半查找
顺序表的顺序查找：基于顺序表，查找指定的key元素， 给出三种：返回它的索引值（否则返回-1）， 判断是否存在这个值（存在返回true， 否则false），查找（存在返回这个元素的值， 不存在返回-1）。就是对这个顺序表进行遍历。从第一个元素开始和指定的元素做比较。参考代码：public class SeqSearch<T> { public static void main(St...
2018-05-16 11:13:51
15859
1
原创 hashcode和equals
hash算法简介：举例，假如有一个集合，让你查找这个集合中是否包含某个元素？常规的就是遍历这个集合，集合中的元素equals(指定元素时， 则返回true， 否则返回false。但是当这个集合很大呢？有几万个，甚至几十万个元素呢？这时遍历显然效率极低。所以有人发明了哈希算法，将这个集合分成若干个区域， 每个区域可以看成一个桶，对应的是一个哈希码，对象是根据它的计算出的哈希码存入对应的区域，所以查找...
2018-05-09 20:25:12
117
原创 矩阵的转置和旋转
转置：转置很简单的，就是a[i][j] -- > a[j][i]即可。可以开辟一个新的二维数组。b[i][j] = a[j][i]即可。例题：输入一个N*N的矩阵，将其转置后输出。要求：不得使用任何数组(就地逆置)。此时应该怎么办呢？只要根据题目要求，直接输出就可以啦！（解释一下，为什么我的输出部分要写成下面这样，把最后一列单独输出出来， 那是因为在大多数的oj上，运行通过的要求是最后一列输...
2018-05-07 21:23:01
4918
原创 快速幂
这里介绍的是求a^b的运算。常规思路：b个a相乘。int pow(int a, int b){ int ans = 1; for(int i = 1; i <= b; i ++){ ans *= a; } return ans;} 但是当b很大时，复杂度很高，所以可以通过分奇偶来讨论。当b是奇数时， a^b = a ^ (b/2) * a^(b/2) * a；当b是偶数时，a^...
2018-05-02 17:52:24
116
原创 红黑树（三）
删除操作1. 在纯函数式的环境下，纯函数式的数据结构决定了树不是真的被改变了，实际上是重建一棵树。（大多数函数式编程环境使用一种名叫Persistent的方法，可以复用树中没有改变的部分，从而减小重建的开销）。利用一个双重黑色的引入。将删除节点的颜色（黑色）保存在其父节点中，如果父节点红色，则染成黑色，如果父节点是黑色，就是双重黑色。删除的过程：1、如果删除的这个节点是根节点，root = nul...
2018-04-28 20:30:09
127
原创 动态规划及实例
01背包问题：一个容量为C的背包，n个物品，他们的重量分别是w[i],价值分别是v[i],怎样选择装入的物品使价值最大？分析：面对每个物品，我们只有选择拿取或者不拿两种选择，不能选择装入某物品的一部分，也不能装入同一物品多次。所以声明一个 大小为 m[n][c] 的二维数组，m[ i ][ j ] 表示 在面对第 i 件物品，且背包容量为 j 时所能获得的最大价值 ，那么我们可以很容易分析得出...
2018-04-26 21:48:17
507
原创 日期处理
日期的标准输出格式：yyyymmdd（y : year, m : month, d: day），例如：2000-05-01。闰年的计算：什么是闰年？即年份可以被4整除但不能被100整除，或者可以被400整除。判断闰年的参考代码：bool isLeapYear(int year){ return (year % 4 == 0 && year % 100 != 0) || (year...
2018-04-24 21:47:04
157
原创 红黑树（二）
红黑树的插入操作1. 以排序二叉树的方法插入新节点，并将它设置为红色。设置红色：如果设置黑色，会导致根节点到叶子节点的路径上多出一个额外的黑节点，这样会很难调整。但是设置为红色可能会导致出现两个连续的红色节点（违反了性质4），因此需要通过颜色转换和树旋转来进行调整。2. 颜色转换和树旋转新插入的节点N, N的父亲节点设置为P，P的兄弟节点设置为B,P的附近点设置为G。(可以理解为newnode,p...
2018-04-22 23:05:35
153
2
原创 约数的个数
题目描述：输入n个整数,依次输出每个数的约数的个数。输入描述：输入的第一行为N，即数组的个数(N<=1000)，接下来的1行包括N个整数，其中每个数的范围为(1<=Num<=1000000000)，当N=0时输入结束。输出描述：可能有多组输入数据，对于每组输入数据，输出N行，其中每一行对应上面的一个数的约数的个数。分析：如何求一个数的约数个数，常规的就是从1- n（表示这个数本身...
2018-04-21 23:10:51
4596
原创 红黑树（一）
之前一篇讲关于二叉搜索树的文章（参看：点击打开链接），但是存在一个问题，在最坏情况下，插入的节点本身就是有序的，要么是从大到小排列，要么是从小到大排列，那最后得到的排序二叉树将会变成链表。这样其检索效率特别差。如图：为了改进这种不足，Rudolf Bayer于1972年发明了另一种改进后的排序二叉树，他将这种树称为“对称二叉树”，红黑树后来被人提出命名。在二叉树的基础上增加了这些要求：1.每个节点...
2018-04-19 21:41:20
124
原创 大整数阶乘
题目描述： 输入一个正整数N，输出N的阶乘。输入描述：正整数N(0<=N<=1000)。输出描述： 输入可能包括多组数据，对于每一组输入数据，输出N的阶乘。分析：思路和一般求阶乘没有区别，只是数大到一定范围，就会超过范围。所以需要使用数组存储数据，注意最后输出时，是倒序输出就可以了。参考代码：#include<iostream>using namespace std;/...
2018-04-18 22:54:49
270
原创 桶排序
桶排序的原理和计数排序类似，可以说是计数排序的升级版。他利用了函数映射关系，将输入的值映射到对应的桶里面去。所以他的高效就在于这个映射函数的确定。所以需要做到如下两点：1.在额外空间充足的情况下，尽量增大桶的数量。2.使用映射函数能将输入的N个数据均匀的分配到K个桶中去。此外就是对于桶中的数据元素的排序时，使用哪种比较排序的算法比较好，对性能的影响至关重要。什么时候最快：当输入数据可以均匀分配到每...
2018-04-16 20:21:07
156
原创 计数排序
计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并...
2018-04-16 20:08:40
133
原创 线性表（三）--- 双向链表
就是给每个节点保留两个引用prev和next,其中prev指向前一个节点，next指向后一个节点。该链表既可以向后依次访问每个节点，也可以向前其次访问每个节点，以这种形式保存的节点称为双向链表。查找：既可以从header(头节点)，也可以从tail(尾节点)开始寻找指定的节点。一般的是根据搜索的index值来判断跟接近于头节点还是尾节点。即比较index和size(链表的大小)/2的大小。若是in...
2018-04-11 20:08:40
241
原创 斐波那契数列
这次介绍的是以斐波那契数列为原型，解决大家在一些编程题中遇到的。如上楼梯。斐波那契数列在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=1，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）参考代码：int Fibonacci(int n){ int fib[n + 1]; fib[0] = 0; fib[1] = 1; for(int i = 2; ...
2018-04-09 19:28:02
200
原创 线性表（二）--- 单链表
链式存储结构的线性表 简称为链表。是采用一组地址任意的存储单元存放线性表中的元素数据。它需要在每一个数据元素里保存一个引用下一个数据元素的引用 --- 指针。单链表 --- 每个节点只保留一个引用， 该引用指向当前节点的下一个节点， 没有引用指向头节点， 尾节点的next引用为null。建立的方法 ： 1.头插法 ： 该方法从一个空表开始， 不断创建新节点，将数据元素存入节点的data域中， 然后...
2018-04-04 22:55:48
128
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人