转载自 力扣 剑指Offer 第五题 思路整理：大致方法： 双指针此想法来自于JS题解点赞量最高的大佬 膜拜大佬~首先我们要了解 英文的空格符 占了一个字符单位 中文的空格符 占了两个字符单位此题 为英文空格符题中 将空格替换成 '%20'占了三个字符单位本题运用双指针 需要比较原字符串长度 和 新占位字符串长度的关系空格 占 1单位 %20 占3单位 我们记录下原字符串 中空格的数量 得出关系newLength=oldLength+count*2我们得出了...
二分查找的基本模板（升序数组） int binarySearch(vector<int>&nums,int target) {//维护两个索引，初始时指向数组两端int left = 0;int right = nums.size()-1;int idx; //目标元素的索引while(left<=right){idx = (left+right)/2;//查找位于最中间的元素,若left+right过大,会有溢出的可能,可以换成left+(right-left)/2if(nums[idx]<target){left = idx + 1;//当前元素比目标元素小,则目标元素在当前元素索引的右边部分}else if(...
哈希表（hash table ） 是一种根据关键字直接访问内存存储位置的数据结构，通过哈希表，数据元素的存放位置和数据元素的关键字之间建立起某种对应关系，建立这种对应关系的函数称为哈希函数 。 常用方法： put(key, value) 插入&修改操作get(key) 获取元素remove(element) 删除元素size() 查看集合元素个数其它：自动扩容/缩容 // 封装哈希表类 function HashTable() {// 属性: 数组（链址法）、 记录当前数组元素个数、 数组长度t...
为什么要使用链表？ 我们在某些场合使用顺序表插入，删除大量元素时需要移动大量的数据，这会将整个程序的执行效率减弱，数据量大的时候无论是添加元素还是删除元素，毫无疑问是对整个数据的乾坤大挪移所以有没有一种方法可以在插入和删除元素的时候不用对整个数据移动？不必再练什么乾坤大挪移，宽敞、是每个成功男人背后都应给征服的邻域，效率、是每个成功靓仔背后都应该掌握的技巧。 什么是链表？ 链表是线性表的链性存储方式，...
栈（stack） 又名堆栈 ，数据特点：后进先出。由于其数据形式特点，故用 数组搭建。 常用方法有： push() 入栈pop() 出栈peek() 查看栈顶元素isEmpty() 判断是否为空length() 获取栈中元素的个数toString() 方法 // 封装栈类 function Stack {// 栈中的属性this.items = [];// 栈的相关操作// 1 将元素压入栈Stack.prototype.push = function (element) {this.items.push(element)}// 2 从栈中取出元素Stack.prototype.pop = funct...
##BF算法 算法思路比较简单,跟KMP比简直幼儿园级别的,可以指定主串中查找的起始位置,每次匹配失败指针回溯主串指针i=i-j+1,子串指针j=1 #include <iostream> using namespace std; int Index_BF(string A, string B, int pos) {int i = pos, j = 0;while (i < A.length() && j < B.length()) {//两个字符串均为比较到串尾（只有有一个到串尾就跳出循环） if (A[i] == B[j]) {i++;j++;}else {//匹配失败指针回溯i = i - j + 1;j = 0...
###递归算法NB #include <iostream> using namespace std;typedef char BTDataType;typedef struct BiTNode {BTDataType data;struct BiTNode* lchild, * rchild; }BiTNode, * BiTree;//按先序次序输入二叉树结点的值(一个字符),创建二叉链表表示的二叉树T void CreateBiTree(BiTree& T) {char ch;cin >> ch;if (ch == '#') T = NULL; //递归结束,建空树else{T = new BiTNode; //生成根结点T->data = ch; //根节点数据域置为...
树 定义 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点： 有一个特殊的结点叫根节点，根节点没有 前驱节点。 除根节点外，其余节点被分为M（M>0）个互不相交的集合T1，T2…Tm，其中每一个集合Ti(1<=i<=m)有是一颗与树类似的子树，每颗子树的根节点有且只有一个前驱，可以有0个或者多个后继。 树是递...
复杂度分析与稳定性最好情况时间复杂度最坏情况时间复杂度平均情况时间复杂度// n 表示数组 array 的长度 int find(int[] array, int n, int x) { int i = 0; int pos = -1; for (; i < n; ++i) { if (array[i] == x) { pos = i; break; } } return pos; }因为，要查找的变量 x 可能出现在数组的任意位置。如果数组中第一个元素正好是要查找的变量 x，那就不需要继续遍历剩下的 n-1 个数据了，那时...
第五章 散列 5.1 基本思想5.2 散列函数5.3 分离链接法5.4 不使用链表的散列表5.4.1 线性探测5.4.2 平方探测5.4.3 双散列 5.5 再散列小结散列表的实现常称为 散列（hashing），是一种用于常数平均时间执行插入、删除和查找的技术。5.1 基本思想 理想的散列表数据结构只不过是包含一些项的具有固定大小的数组。 把表的大小记作TableSize，并将其理解为散列数据结构的一部分而不仅仅是浮动于全局的某个变量。将每个键映射到从0到Table...
数据结构与算法综合实验-图与景区信息管理系统 任务描述 有一个景区，景区里面有若干个景点，景点之间满足以下条件： 1）某些景点之间铺设了道路(相邻) 2）这些道路都是可以双向行驶的(无向图) 3）从任意一个景点出发都可以游览整个景区(遍历连通图)功能需求源代码如下： main.cpp #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include"Tourism.h" #include"Graph.h" using namespace std;Graph m_Graph;int main(void) {...
1. 写在前面 今天这篇文章复习栈和队列的相关题目了，栈和队列也是两种非常重要的数据结构，在很多地方都会看到，比如非常重要的dfs和bfs中就是分别用的这两个结构，关于这块的题目，我之前刷的不多， 但是这里有几个很重要的结构，单调栈， 单调队列，一些经典的中等偏上的题目要靠它们来搞定，所有这里会重点看看这几个东西的使用。 关于栈，我们需要了解： 特点： 栈的最大特点就是后进先出（LIFO）。对于栈中的数据来说，所有操...
学习笔记：数据结构与算法（十三）：赫夫曼树 图定义其他的相关概念图的存储结构邻接矩阵（无向图）邻接矩阵（有向图）邻接矩阵（网）图 定义 图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为G（V,E），其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。 注意： 图中数据元素称为顶点（Vertex）强调图的顶点集合V要有穷非空图中，任意两个顶点都可能有关系，逻辑关系用边来表示，边集可以是空的。 ...
数据结构与算法系列 数据结构与算法之哈希表 数据结构与算法之跳跃表 数据结构与算法之字典树 数据结构与算法之2-3树 数据结构与算法之平衡二叉树 数据结构与算法之红黑树 带你手撸红黑树，小泉憋大招了 数据结构与算法之堆 数据结构与算法之十大经典排序 数据结构与算法之二分查找三模板 数据结构与算法之动态规划 数据结构与算法之回溯算法 数据结构与算法之Morris算法 数据结构与算法之贪心算法 数据结构与算法之拓扑排序 数据结...
1. 插入排序原理 插入排序类似于我们斗地主的时候摸扑克牌。摸牌的时候，我们都会把牌给从左到右依照从小到大的顺序排好序，这样出牌的时候就比较清楚明了。牌堆类比为一个数组，从牌堆中摸取第1张牌，放入手中，这时候因为手里本来就没有牌，所以不用比较排序直接拿到手中，假设摸到的牌是红桃10。接着从牌堆中摸取第二张牌（黑桃3）这时你下意识就会拿这张牌和你手上的牌比较，然后将其插入到正确的位置（插入到红桃10的左边）。...