数据结构

之前一直总是简单的想将分数化为小数进行计算，其实使用相应的结构进行分子分母的分开保存，可以有奇效；分数的存储：struct Fraction{ int up; int down;};其中up代表分子，down代表分母；对于分数，有基本的几个规则：1.正负号挂在分子上；2.当分数表示0的时候，分子为0，分母为1；3.分子分母必须达到最简，也就是没有1以外的公约数；当分数进行四则运算的时候，也是基于这三条的性质来进行化简；Fraction reduction(Fraction result){ if(result.down<0){ result.up=-result.up; result.down=-result.down; } if(result.up==0){ result.down=1; }else{ int d=gcd(abs(result.up),abs(result.down)); result.up/=d; result.down/=d; } return result;}其中值得注意的是进行最大公约数计算的时候一定要注意注意分子可能为负，所以要进行绝对值的提前处理；分数的四则运算：在上述化简函数的基础上，我们就可以根据该规则进行相应的四则运算，四则运算严格遵循计算的通分规律；1.加法运算：Fraction add(Fraction f1,Fraction f2){ Fraction result; result.up=f1.upf2.down+f2.upf1.down; result.down=f1.downf2.down; return reduction(result);}2.减法运算：Fraction minu(Fraction f1,Fraction f2){ Fraction result; result.up=f1.upf2.down-f1.downf2.up; result.down=f1.downf2.down; return reduction(result);}3.乘法运算Fraction multi(Fraction f1,Fraction f2){ Fraction result; result.up=f1.upf2.up; result.down=f2.downf2.down; return reduction(result);}4.除法运算：Fraction divide(Fraction f1,Fraction f2){ Fraction result; result.up=f1.upf2.down; result.down=f2.upf2.down; return reduction(result);}值得注意的是这里采用的除法的倒数计算；分数的输出形式：对于一个正常形式的分数，往往有三种形式：1.整数：此时只输出分子（由于程序代码里对分子分母进行化简，所以如果有整数分母一定为1）；2.真分数：此时按照a/b的格式输出；3.假分数：此时应该在按照带分数的格式输出，并且符号在前；代码如下：void showResult(Fraction r){ r=reduction(r); if(r.down==1) printf("%lld",r.up); else if(abs(r.up)>r.down){ printf("%d %d/%d",r.up/r.down,abs(r.up)%r.down,r.down); }else{ printf("%d/%d",r.up,r.down); }}值得注意的是当进行带分数计算的时候，计算其后真分数余数的时候，一定要注意abs绝对值得处理； ...

【主页】 apachecn.org【Github】@ApacheCN暂时下线: 社区暂时下线: cwiki 知识库自媒体平台微博：@ApacheCN知乎：@ApacheCNCSDN简书OSChina博客园我们不是 Apache 的官方组织/机构/团体，只是 Apache 技术栈（以及 AI）的爱好者！合作or侵权，请联系【fonttian】<fonttian@gmail.com> | 请抄送一份到 <apachecn@163.com>PyTorch 1.0 中文文档和教程教程部分：认领：36/37，翻译：28/37；文档部分：认领：29/39，翻译：15/39参与方式：https://github.com/apachecn/p…整体进度：https://github.com/apachecn/p…项目仓库：https://github.com/apachecn/p…章节贡献者进度教程部分–Deep Learning with PyTorch: A 60 Minute Blitz@bat67100%What is PyTorch?@bat67100%Autograd: Automatic Differentiation@bat67100%Neural Networks@bat67100%Training a Classifier@bat67100%Optional: Data Parallelism@bat67100%Data Loading and Processing Tutorial@yportne13100%Learning PyTorch with Examples@bat67100%Transfer Learning Tutorial@jiangzhonglian100%Deploying a Seq2Seq Model with the Hybrid Frontend@cangyunye100%Saving and Loading Models@sfyumi What is <cite>torch.nn</cite> really?@lhc741 Finetuning Torchvision Models@ZHHAYO100%Spatial Transformer Networks Tutorial@PEGASUS1993100%Neural Transfer Using PyTorch@bdqfork100%Adversarial Example Generation@cangyunye100%Transfering a Model from PyTorch to Caffe2 and Mobile using ONNX@PEGASUS1993100%Chatbot Tutorial@a625687551100%Generating Names with a Character-Level RNN@hhxx2015100%Classifying Names with a Character-Level RNN@hhxx2015100%Deep Learning for NLP with Pytorch@BreezeHavana Introduction to PyTorch@guobaoyo100%Deep Learning with PyTorch@bdqfork100%Word Embeddings: Encoding Lexical Semantics@sight007100%Sequence Models and Long-Short Term Memory Networks@ETCartman100%Advanced: Making Dynamic Decisions and the Bi-LSTM CRF@JohnJiangLA Translation with a Sequence to Sequence Network and Attention@mengfu188100%DCGAN Tutorial@wangshuai9517 Reinforcement Learning (DQN) Tutorial@BreezeHavana Creating Extensions Using numpy and scipy@cangyunye100%Custom C++ and CUDA Extensions@Lotayou Extending TorchScript with Custom C++ Operators Writing Distributed Applications with PyTorch@firdameng PyTorch 1.0 Distributed Trainer with Amazon AWS@yportne13100%ONNX Live Tutorial@PEGASUS1993100%Loading a PyTorch Model in C++@talengu100%Using the PyTorch C++ Frontend@solerji100%文档部分–Autograd mechanics@PEGASUS1993100%Broadcasting semantics@PEGASUS1993100%CUDA semantics@jiangzhonglian100%Extending PyTorch@PEGASUS1993 Frequently Asked Questions@PEGASUS1993 Multiprocessing best practices@cvley100%Reproducibility@WyattHuang1 Serialization semantics@yuange250100%Windows FAQ@PEGASUS1993 torch@ZHHAYO torch.Tensor@hijkzzz100%Tensor Attributes@yuange250100%Type Info@PEGASUS1993100%torch.sparse@hijkzzz100%torch.cuda@bdqfork100%torch.Storage@yuange250100%torch.nn@yuange250 torch.nn.functional@hijkzzz100%torch.nn.init@GeneZC100%torch.optim@qiaokuoyuan Automatic differentiation package - torch.autograd@gfjiangly Distributed communication package - torch.distributed Probability distributions - torch.distributions@hijkzzz Torch Script Multiprocessing package - torch.multiprocessing@hijkzzz100%torch.utils.bottleneck torch.utils.checkpoint torch.utils.cpp_extension torch.utils.data torch.utils.dlpack torch.hub torch.utils.model_zoo torch.onnx@guobaoyo100%Distributed communication package (deprecated) - torch.distributed.deprecated torchvision Reference@BXuan694 torchvision.datasets@BXuan694 torchvision.models@BXuan694 torchvision.transforms@BXuan694 torchvision.utils@BXuan694 HBase 3.0 中文参考指南认领：2/31，翻译：0/31参与方式：https://github.com/apachecn/h…整体进度：https://github.com/apachecn/h…项目仓库：https://github.com/apachecn/h…章节译者进度Preface Getting Started Apache HBase Configuration Upgrading The Apache HBase Shell Data Model HBase and Schema Design@RaymondCode RegionServer Sizing Rules of Thumb HBase and MapReduce Securing Apache HBase Architecture In-memory Compaction Backup and Restore Synchronous Replication Apache HBase APIs Apache HBase External APIs Thrift API and Filter Language HBase and Spark@TsingJyujing Apache HBase Coprocessors Apache HBase Performance Tuning Troubleshooting and Debugging Apache HBase Apache HBase Case Studies Apache HBase Operational Management Building and Developing Apache HBase Unit Testing HBase Applications Protobuf in HBase Procedure Framework (Pv2): HBASE-12439 AMv2 Description for Devs ZooKeeper Community Appendix Airflow 中文文档认领：23/30，翻译：23/30。参与方式：https://github.com/apachecn/a…整体进度：https://github.com/apachecn/a…项目仓库：https://github.com/apachecn/a…章节贡献者进度1 项目 2 协议-100%3 快速开始@ImPerat0R_100%4 安装@Thinking Chen100%5 教程@ImPerat0R_100%6 操作指南@ImPerat0R_100%7 设置配置选项@ImPerat0R_100%8 初始化数据库后端@ImPerat0R_100%9 使用操作器@ImPerat0R_100%10 管理连接@ImPerat0R_100%11 保护连接@ImPerat0R_100%12 写日志@ImPerat0R_100%13 使用Celery扩大规模@ImPerat0R_100%14 使用Dask扩展@ImPerat0R_100%15 使用Mesos扩展（社区贡献）@ImPerat0R_100%16 使用systemd运行Airflow@ImPerat0R_100%17 使用upstart运行Airflow@ImPerat0R_100%18 使用测试模式配置@ImPerat0R_100%19 UI /截图@ImPerat0R_100%20 概念@ImPerat0R_100%21 数据分析@ImPerat0R_100%22 命令行接口@ImPerat0R_100%23 调度和触发器@Ray100%24 插件@ImPerat0R_100%25 安全 26 时区 27 实验性 Rest API@ImPerat0R_100%28 集成 29 Lineage 30 常见问题 31 API 参考 UCB CS61b Java 中的数据结构认领：0/12，翻译：0/12参与方式：https://github.com/apachecn/c…整体进度：https://github.com/apachecn/c…项目仓库：https://github.com/apachecn/c…标题译者进度一、算法复杂度 二、抽象数据类型 三、满足规范 四、序列和它们的实现 五、树 六、搜索树 七、哈希 八、排序和选择 九、平衡搜索 十、并发和同步 十一、伪随机序列 十二、图 UCB Prob140 面向数据科学的概率论认领：23/25，翻译：17/25参与方式：https://github.com/apachecn/p…整体进度：https://github.com/apachecn/p…项目仓库：https://github.com/apachecn/p…标题译者翻译进度一、基础飞龙100%二、计算几率飞龙100%三、随机变量飞龙100%四、事件之间的关系@biubiubiuboomboomboom100%五、事件集合@PEGASUS1993>0%六、随机计数@viviwong100%七、泊松化@YAOYI626100%八、期望@PEGASUS199350%九、条件（续）@YAOYI626100%十、马尔科夫链喵十八100%十一、马尔科夫链（续）喵十八100%十二、标准差缺只萨摩 100%十三、方差和协方差缺只萨摩 100%十四、中心极限定理喵十八100%十五、连续分布@ThunderboltSmile十六、变换十七、联合密度@Winchester-Yi100%十八、正态和 Gamma 族@Winchester-Yi100%十九、和的分布平淡的天100%二十、估计方法平淡的天100%二十一、Beta 和二项@lvzhetx100%二十二、预测@lvzhetx50%二十三、联合正态随机变量二十四、简单线性回归@ThomasCai100%二十五、多元回归@lanhaixuan100%翻译征集要求：机器学习/数据科学相关或者编程相关原文必须在互联网上开放不能只提供 PDF 格式（我们实在不想把精力都花在排版上）请先搜索有没有人翻译过请回复本文。赞助我们 ...

使用的就是分块思想，之前写过总结，所以不再赘述；代码如下：#include<iostream>#include<stdlib.h>#include<stdio.h>#include<stack>#include<cstring>using namespace std;const int maxn=100010;const int sqrN=316;stack<int>st;int block[sqrN];int table[maxn];void peekMedian(int K){ int sum=0; int idx=0; while(sum+block[idx]<K){ sum+=block[idx++]; } int num=idx*sqrN; while(sum+table[num]<K){ sum+=table[num++]; } printf("%d\n",num);}void push(int x){ st.push(x); block[x/sqrN]++; table[x]++;}void pop(){ int x=st.top(); st.pop(); block[x/sqrN]–; table[x]–; printf("%d\n",x);}int main(){ int x,query; memset(block,0,sizeof(block)); memset(table,0,sizeof(table)); char cmd[20]; scanf("%d",&query); for(int i=0;i<query;i++){ scanf("%s",cmd); if(strcmp(cmd,“Push”)==0){ scanf("%d",&x); push(x); }else if(strcmp(cmd,“Pop”)==0){ if(st.empty()==true){ printf(“Invalid\n”); }else{ pop(); } }else{ if(st.empty()==true){ printf(“Invalid\n”); }else{ int K=st.size(); if(K%2==1) K=(K+1)/2; else K=K/2; peekMedian(K); } } } system(“pause”); return 0;} ...

刚刚做A1057 Stack题的时候遇到超时问题，查阅了相关的资料，发现这道题最优的两种做法分别是分块思想和树状数组；这章先介绍一下分块思想：首先分块思想针对的是在线队列，也就是会对队列进行修改和操作，包括树状数组针对的也是这个问题；其实分块思想下的一个典型问题就是实时查询序列元素第K大的问题。分块思想的本质就是将序列按照索引划分为不同的块，所以每个元素就有隶属的块；在每一块中，为每一个元素建立hash数组，用来存储每个元素的重复个数。当我们需要查询第k大问题的时候，就可以先通过每一块的元素个数，计算它在那一块，再通过块中的每一个元素的hash值，从而判断需要查询的第k个元素是哪一个元素；使用分块思想的优势就是可以通过分块来计算相应的值，省去了排序的步骤；例如对于我们A1057题，最蠢最笨的思路就是把序列提出来，排序，然后找第k个值，这样就徒劳的增加了时间复杂度；具体的分块计算策略如下所示：1.当我们的序列长度为n，出最后的一块，剩下的每块中的元素应该为√n(向下取整)，并且块数应该为√n(向上取整)。之所以对块数向上取整的目的是将最后不满的块独立划分为一块；2.同时，我们建立两个数组，一个为block数组，一个为table数组；其中，block[i]代表的第i个块中所含有的元素个数，table[i]代表的是所有序列中第i个元素所现在存在的重复个数；例如，我们当前分了316块，我们可以添加和查询以及删除元素；当我们添加元素的时候，应该先寻找在那一块，例如304/316=0，代表304号元素在第0块，block[0]++,table[304]++；当我们需要查询第k个元素的时候，我们需要对比每一个块，也就是block[i]，看看在第几块中，找到在第几块的的时候，逐个枚举属于该块的table[i]，看看是第k个元素是否是i;删除元素同理，寻找在第几块，相应的block[i]–，table[j]++;

1.包含min函数的栈定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。思路1.定义两个栈，一个栈用于存储数据，另一个栈用于存储每次数据进栈时栈的最小值.2.每次数据进栈时，将此数据和最小值栈的栈顶元素比较，将二者比较的较小值再次存入最小值栈.4.数据栈出栈，最小值栈也出栈。3.这样最小值栈的栈顶永远是当前栈的最小值。代码var dataStack = [];var minStack = []; function push(node){ dataStack.push(node); if(minStack.length === 0 || node < min()){ minStack.push(node); }else{ minStack.push(min()); }}function pop(){ minStack.pop(); return dataStack.pop();}function top(){ var length = dataStack.length; return length>0&&dataStack[length-1]}function min(){ var length = minStack.length; return length>0&&minStack[length-1]}2.栈的压入、弹出序列输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）思路1.借助一个辅助栈来存储数据。2.将pushV中的数据依次入栈。3.出栈有可能在任意一次入栈后进行，当出栈数据不再位于栈顶，继续入栈。4.所以设置一个索引，记录当前出栈的位置，每次出栈索引+1。5.当所有数据入栈完成，如果出栈顺序正确，那么辅助栈应该为空。代码 function IsPopOrder(pushV, popV) { if (!pushV || !popV || pushV.length == 0 || popV.length == 0) { return; } var stack = []; var idx = 0; for (var i = 0; i < pushV.length; i++) { stack.push(pushV[i]); while (stack.length && stack[stack.length - 1] == popV[idx]) { stack.pop(); idx++; } } return stack.length == 0; }3.题二叉树的后续遍历输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。思路1.后序遍历：分成三部分：最后一个节点为跟节点，第二部分为左子树的值比跟节点都小，第三部分为右子树的值比跟节点都大。2.先检测左子树，左侧比跟节点小的值都判定为左子树。3.除最后一个节点外和左子树外的其他值为右子树，右子树有一个比跟节点小，则返回false。4.若存在，左、右子树，递归检测左、右子树是否复合规范。代码 function VerifySquenceOfBST(sequence) { if (sequence && sequence.length > 0) { var root = sequence[sequence.length - 1] for (var i = 0; i < sequence.length - 1; i++) { if (sequence[i] > root) { break; } } for (let j = i; j < sequence.length - 1; j++) { if (sequence[j] < root) { return false; } } var left = true; if (i > 0) { left = VerifySquenceOfBST(sequence.slice(0, i)); } var right = true; if (i < sequence.length - 1) { right = VerifySquenceOfBST(sequence.slice(i, sequence.length - 1)); } return left && right; } }4.二叉树中和为某一值的路径输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)思路1.使用前序遍历2.使用一个辅助栈来存储当前路径里的数据3.记录一个当前路径的和4.遍历到当前节点后，当前值入路径栈，和加当前值5.递归左孩子右孩子节点6.遍历完一个节点，退回到上一个节点，从路径栈中移除当前的值，和减当前值代码 function FindPath(root, expectNumber) { var result = []; if (!root) { return result; } findPath(root, expectNumber, [], 0, result); return result; } function findPath(node, expectNumber, vector, sum, result) { vector.push(node.val); sum += node.val; var isLeaf = !node.left && !node.right; if (isLeaf && sum === expectNumber) { result.push(vector.slice(0)); } if (node.left) { findPath(node.left, expectNumber, vector, sum, result); } if (node.right) { findPath(node.right, expectNumber, vector, sum, result); } vector.pop(); } ...

水题，还是字典排序，没神马好说的；#include<iostream>#include<stdlib.h>#include<stdio.h>#include<string>#include<cstring>#include<vector>#include<algorithm>using namespace std;using std::vector;const int maxn=100010;struct people{ int age; char name[9]; int worth;}mem[maxn];bool cmp(people a,people b){ if(a.worth==b.worth){ if(a.age==b.age){ return strcmp(a.name,b.name)<0; }else{ return a.age<b.age; } }else{ return a.worth>b.worth; }}int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ scanf("%s %d %d",mem[i].name,&mem[i].age,&mem[i].worth); } sort(mem,mem+n,cmp); for(int i=0;i<m;i++){ printf(“Case #%d:\n”,i+1); int _max,_min,M; bool flag=false; scanf("%d%d%d",&M,&_min,&_max); for(int j=0;j<n&&M>0;j++){ if(mem[j].age>=_min&&mem[j].age<=_max){ printf("%s %d %d\n",mem[j].name,mem[j].age,mem[j].worth); flag=true; M–; } } if(!flag) printf(“None\n”); } system(“pause”); return 0;}

这道题又一次的戳到了我的盲区；一定要注意sort和cmp的返回值；其实可以这么理解；对于cmp，我们的目的是让数据按照给出的形式进行排序，例如我们想让序列递增，则排序的方式就为：a<b；这样序列中处处都是a<b;同理，如果构建了struct，其中包括一个string，我们希望整个序列按照字典序递增，该怎么办？这个时候就要用到strcmp函数来做辅助；默认情况下strcmp(a,b)，当a的字典序大于b的时候，返回的就是1，等于为0，小于返回-1；所以如果a>b,则strcamp(a,b)>0但是我们希望的是递增，也就是a<b,所以对应的情况就是strcamp(a,b)返回-1,所以这个时候应该返回的判定条件就是strcmp(a,b)<0，也就是符合字典序a<b的那种情况；#include<iostream>#include<stdlib.h>#include<stdio.h>#include<string>#include<cstring>#include<vector>#include<algorithm>using namespace std;using std::vector;const int maxn=100010;struct node{ int id; char name[9]; int grade;}mem[maxn];bool cmp1(node a,node b){ return a.id<b.id;}bool cmp2(node a,node b){ if(strcmp(a.name,b.name)==0) return a.id<b.id; else return strcmp(a.name,b.name)<0;}bool cmp3(node a,node b){ if(a.grade==b.grade) return a.id<b.id; else return a.grade<b.grade;}int main(){ int n,c; scanf("%d%d",&n,&c); for(int i=0;i<n;i++){ scanf("%d %s %d",&mem[i].id,&mem[i].name,&mem[i].grade); } if(c==1){ sort(mem,mem+n,cmp1); }else if(c==2){ sort(mem,mem+n,cmp2); }else{ sort(mem,mem+n,cmp3); } for(int i=0;i<n;i++){ printf("%06d %s %d\n",mem[i].id,mem[i].name,mem[i].grade); } system(“pause”); return 0;}

简单的大数问题，long long并不能容纳21位数字，这是刚开始没有注意到的#include<iostream>#include<stdlib.h>#include<stdio.h>#include<string>#include<cstring>#include<vector>using namespace std;using std::vector;char s[21];int mem[10]={0};int main(){ vector<int>v; scanf("%s",s); for(int i=0;i<strlen(s);i++){ mem[s[i]-‘0’]++; } //进行乘2大数运算； int ct=0; for(int i=strlen(s)-1;i>=0;i–){ int a=(s[i]-‘0’)*2+ct; ct=a/10; v.push_back(a%10); } if(ct!=0) v.push_back(ct); for(int i=v.size()-1;i>=0;i–){ mem[v[i]]–; } bool flag=true; for(int i=0;i<10;i++){ if(mem[i]!=0){ flag=false; break; } } if(flag){ cout<<“Yes”<<endl; for(int i=v.size()-1;i>=0;i–){ cout<<v[i]; } cout<<endl; }else{ cout<<“No”<<endl; for(int i=v.size()-1;i>=0;i–){ cout<<v[i]; } cout<<endl; } system(“pause”); return 0;}

这道题有点像优先队列的思想，简而言之就是挑选最小的入队处理，如果有多个队列就进行多个队列的处理；借鉴的思想是采用记录每个队列中的任务完成时间，然后在读入任务的时候进行轮询，选择结束时间最小的那个队列，然后进行处理和等待时间的计算；代码如下：#include <iostream>#include<stdlib.h>#include<stdio.h>#include <vector>#include <algorithm>using namespace std;struct node { int come, time;} tempcustomer;bool cmp1(node a, node b) { return a.come < b.come;}int main() { int n, k; scanf("%d%d", &n, &k); vector<node> custom; for(int i = 0; i < n; i++) { int hh, mm, ss, time; scanf("%d:%d:%d %d", &hh, &mm, &ss, &time); int cometime = hh * 3600 + mm * 60 + ss; if(cometime > 61200) continue; tempcustomer = {cometime, time * 60}; custom.push_back(tempcustomer); } sort(custom.begin(), custom.end(), cmp1); vector<int> window(k, 28800); double result = 0.0; for(int i = 0; i < custom.size(); i++) { int tempindex = 0, minfinish = window[0]; for(int j = 1; j < k; j++) { if(minfinish > window[j]) { minfinish = window[j]; tempindex = j; } } if(window[tempindex] <= custom[i].come) { window[tempindex] = custom[i].come + custom[i].time; } else { result += (window[tempindex] - custom[i].come); window[tempindex] += custom[i].time; } } if(custom.size() == 0) printf(“0.0”); else printf("%.1f", result / 60.0 / custom.size()); system(“pause”); return 0;} ...

这道题而可以说是比较难的一道题，如果采用常规遍历，会出现时长或者溢出的问题；示例中给出的思路很值得借鉴；个人通过该示例有以下几个不同理解：1.有时候两个不同进制的数对比，我们可以进行进制，转化十进制来进行比较；2.对于有些枚举或者寻找问题，为了不进行枚举遍历，我们应该第一时间想到二分查找；对于第一点，这个在题目中有所体现，我们都是将其转化为相应的十进制下，然后进行比较，看是否相同；在这个途中，有个难点：对于未知进制数，我们应该如何推断，一定要注意溢出问题；在本题目中，并没有对进制有限定，如果按照常规进制计算，就会发生int或这longlong溢出，这一点要注意；而对于未知进制数，我们就可以让二分派上用场；本题目的根本就是进制枚举，所以我们可以规定进制的上界和下界，从而通过二分来寻找一个进制，使得通过改进之转换的数和给定的数相同，来达到最终的结果；那么问题又来了，上界和下界如何确定？下界好说，下界就可以取整个数字序列中最大的数，加一就是下界。例如对于一个位15，最起码应该是16进制；而对于上界，比较难以理解，上界取另一个数字在十进制下的值，加一就是上界；举个例子说明一下，假如另一个数字十进制下是156，如果当前给出的值是1，那么多少进制可以让其和156相等，答案就是156进制，由于在二分查找下，我们输入的序列大原本序列1位，所以还需要+1；详细代码如下所示：#include<iostream>#include<stdlib.h>#include<stdio.h>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;LL inf=(1LL<<63)-1;char n1[20],n2[20],temp[20];int m[256];void init(){ for(char c=‘0’;c<=‘9’;c++){ m[c]=c-‘0’; } for(char c=‘a’;c<=‘z’;c++){ m[c]=c-‘a’+10; }}LL convert2num10(char a[],LL radix,LL t){ LL ans=0; int len=strlen(a); for(int i=0;i<len;i++){ ans=ans*radix+m[a[i]]; if(ans<0||ans>t) //ans<0为大到溢出的情况 return -1; } return ans;}int findLargestDigit(char N2[]){ int ans=-1; int len=strlen(N2); for(int i=0;i<len;i++){ if(m[N2[i]]>ans){ ans=m[N2[i]]; } } return ans+1;}int cmp(char n2[],LL radix,LL t){ int len=strlen(n2); LL num=convert2num10(n2,radix,t); if(num<0) return 1; if(t==num) return 0; else if(t>num) return -1; else return 1;}LL binarySearch(char n2[],LL left,LL right,LL t){ LL mid; while(left<=right){ mid=(left+right)/2; int flag=cmp(n2,mid,t); if(flag==0) return mid; else if(flag==-1) left=mid+1; else right=mid-1; } return -1;}int main(){ init(); int tag,radix; scanf("%s%s%d%d",n1,n2,&tag,&radix); if(tag==2){ strcpy(temp,n1); strcpy(n1,n2); strcpy(n2,temp); } LL t=convert2num10(n1,radix,inf); //将N1从radix进制转化为10进制； LL low=findLargestDigit(n2); //low是序列中最大的数，也就是可以比较的最小进制，例如110，则合法的进制最小都未进制 LL high=max(low,t)+1; //high是上界 LL ans=binarySearch(n2,low,high,t); if(ans==-1) printf(“Impossible\n”); else printf("%lld\n",ans); system(“pause”); return 0;} ...

Leetcode 95不同的二叉搜索树 II输入: 3输出:[ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3]]解释:以上的输出对应以下 5 种不同结构的二叉搜索树： 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3Leetcode 86不同的二叉搜索树给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？示例:输入: 3输出: 5解释:给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3题解搜索二叉树(BST)的定义若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。给点一个数，去构造BST.[1, 2, 3]可以把这个数列做左子树和右子树的划分:[1] [2, 3][1, 2] [3][1, 2] [2, 3] 又可以做左子树和右子树的划分.这是一个递归的过程.把递归的结果构造起来,即可成为答案./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public List<TreeNode> generateTrees(int n) { if (n == 0) return new ArrayList<>(); return generateBST(1, n); } private List<TreeNode> generateBST(int left, int right) { List<TreeNode> res = new LinkedList<>(); if (left > right) { // 划分不到的时候,这时候填null. res.add(null); return res; } for (int i = left; i <= right; i++) { List<TreeNode> leftTrees = generateBST(left, i - 1); List<TreeNode> rightTrees = generateBST(i + 1, right); for (TreeNode leftTree : leftTrees) { for (TreeNode rightTree : rightTrees) { // 注意,每个循环都要构造新的节点,不能在for 循环外面生成. TreeNode root = new TreeNode(i); root.left = leftTree; root.right = rightTree; res.add(root); } } } return res; }}如果只需要数目,不需要生成具体的BST的话,只要能求出左子树有几种构造,右子树有几种构造,就可以最终确定.而确定左子树和右子树的问题的时候,又可以划分为子问题.eg:求 [1,2,3,4] 依赖于:[1,2,3] [2,3,4]又依赖于:[1,2] [2,3] [3,4]的构造有几种.class Solution { public int numTrees(int n) { int[] res = new int[n + 2]; res[0] = 1; res[1] = 1; // 没有左子树和右子树 res[2] = 2; for (int i = 3; i <= n; i++) { // 从3求到n for (int j = 1; j <= i; j++) { // 求解过程中,需要依赖于之前的解,状态转移方程为每一种划分的左子树和右子树的构造方法乘积. res[i] += res[j - 1] * res[i - j]; } } return res[n]; }} ...

简单的一道题，想到的有两种方法方法一：二分查找；由于是两个数和，所以我们从i=1开始枚举，在剩下的i+1~n序列中找到m-a[i]的数，是一个递增不重复序列的查找问题，之前二分法总结过，所以不再赘述；代码如下：#include<iostream>#include<stdlib.h>#include<stdio.h>#include<algorithm>using namespace std;const int maxn=100010;int coin[maxn];int n,m;int binarySearch(int l,int r,int x){ while(l<=r){ int mid=(l+r)/2; if(coin[mid]==x) return mid; else if(coin[mid]>x){ r=mid-1; }else{ l=mid+1; } } return -1;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&coin[i]); } int a,b; int r=-1; sort(coin+1,coin+n+1); for(int i=1;i<n;i++){ a=coin[i]; b=m-coin[i]; r=binarySearch(i+1,n+1,b); if(r!=-1){ break; } } if(r==-1){ printf(“No Solution\n”); }else{ printf("%d %d",a,b); } system(“pause”); return 0;}第二种方法：two points；注意的点是避免i=j使得重复加同一个值从而导致错误答案；#include<iostream>#include<stdlib.h>#include<stdio.h>#include<algorithm>using namespace std;const int maxn=100010;int coin[maxn];int n,m;int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&coin[i]); } int a,b; int r=-1; sort(coin+1,coin+n+1); int i=1,j=n; int sum; bool flag=false; while(i<j){ sum=coin[i]+coin[j]; if(sum==m){ flag=true; break; } else if(sum>m){ j–; }else{ i++; } } if(!flag){ printf(“No Solution\n”); }else{ printf("%d %d",coin[i],coin[j]); } system(“pause”); return 0;} ...

这道题可以利用二分来做，其实个人觉得动态规划也可以；利用二分的前提条件就是该序列是一个不下降序列；所以我们可以先构建一个sum数组，存放1-i的和值；当然题目中要计算i-j子序列的值，其实这个可以利用sum数组来计算，该子序列的和就是sum[j]-sum[i]；所以我们就相当于对sum和二分序列寻找sum[i]+x，其中，x为题目前提给出的和值；对于二分算法，使用大于x和大于等于x的两种都可以，示例给出的是大于x，然后通过判断j-1位是不是可以使得子序列和等于x;个人觉得麻烦，还是使用大于等于x较为简单；其实这道题的关键还是怎么转化数组使得其能够用二分法进行解决；还有一个问题，如果不仅仅包括0-n位，会出现第n位元素无法进行判断的情况，所以包括的序列一定要为1~n+1，这样就可以有效的使得随后一位进行计算，使得小于x的时候出现第n+1位无效位，从而根据位数是否无效来剔除这种意外之外的情况；算法实现如下，使用的是大于等于x：#include<iostream>#include<stdlib.h>#include<stdio.h>using namespace std;const int maxn=100010;int a[maxn],sum[maxn];int n,m,ns=100000010;int binarySearch(int l,int r,int x){ while(l<r){ int mid=(l+r)/2; if(sum[mid]>=x){ r=mid; }else{ l=mid+1; } } return l;}int main(){ scanf("%d",&n); scanf("%d",&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } sum[0]=0; for(int i=1;i<=n;i++){ sum[i]=sum[i-1]+a[i]; } //此时sum递增； for(int i=1;i<=n;i++){ int j=binarySearch(i,n+1,sum[i-1]+m); if(sum[j]-sum[i-1]==m){ //如果存在和s相等的数； ns=m; break; }else if(j<=n&&sum[j]-sum[i-1]<ns){ ns=sum[j]-sum[i-1]; } } for(int i=1;i<=n;i++){ int j=binarySearch(i,n+1,sum[i-1]+ns); if(sum[j]-sum[i-1]==ns){ printf("%d-%d\n",i,j); } } system(“pause”); return 0;}

概述这是一种就地比较排序算法。这里，维护一个始终排序的子列表。例如，维护数组的下半部分以进行排序。要在此已排序的子列表中“插入”的元素必须找到其适当的位置，然后必须将其插入其中。因此名称，插入排序。按顺序搜索数组，移动未分类的项并将其插入已排序的子列表（在同一数组中）。该算法不适用于大数据集，因为其平均和最差情况复杂度为0（n 2），其中n是项目数。插入排序如何工作？我们以一个未排序的数组为例。插入排序比较前两个元素。它发现14和33都已按升序排列。目前，14位于已排序的子列表中。插入排序向前移动并将33与27进行比较。并发现33不在正确的位置。它将33与27交换。它还检查已排序子列表的所有元素。在这里，我们看到排序的子列表只有一个元素14，而27大于14.因此，排序的子列表在交换后仍然排序。到目前为止，我们在已排序的子列表中有14和27。接下来，它将33与10进行比较。这些值不是按排序顺序排列的。所以我们互换它们。但是，交换使27和10未分类。因此，我们也交换它们。我们再次以未排序的顺序找到14和10。我们再次交换它们。到第三次迭代结束时，我们有一个包含4个项目的已排序子列表。此过程将继续，直到排序的子列表中包含所有未排序的值。现在我们将看到插入排序的一些编程方面。算法现在我们对这种排序技术的工作原理有了更大的了解，因此我们可以推导出简单的步骤来实现插入排序。Step 1 − If it is the first element, it is already sorted. return 1;Step 2 − Pick next elementStep 3 − Compare with all elements in the sorted sub-listStep 4 − Shift all the elements in the sorted sub-list that is greater than the value to be sortedStep 5 − Insert the valueStep 6 − Repeat until list is sorted伪代码procedure insertionSort( A : array of items ) int holePosition int valueToInsert for i = 1 to length(A) inclusive do: /* select value to be inserted */ valueToInsert = A[i] holePosition = i /*locate hole position for the element to be inserted / while holePosition > 0 and A[holePosition-1] > valueToInsert do: A[holePosition] = A[holePosition-1] holePosition = holePosition -1 end while / insert the number at hole position */ A[holePosition] = valueToInsert end forend procedureC代码#include <stdio.h>#include <stdbool.h>#define MAX 7int intArray[MAX] = {4,6,3,2,1,9,7};void printline(int count) { int i; for(i = 0;i < count-1;i++) { printf("="); } printf("=");}void display() { int i; printf("["); // navigate through all items for(i = 0;i < MAX;i++) { printf("%d “,intArray[i]); } printf(”]");}void insertionSort() { int valueToInsert; int holePosition; int i; // loop through all numbers for(i = 1; i < MAX; i++) { // select a value to be inserted. valueToInsert = intArray[i]; // select the hole position where number is to be inserted holePosition = i; // check if previous no. is larger than value to be inserted while (holePosition > 0 && intArray[holePosition-1] > valueToInsert) { intArray[holePosition] = intArray[holePosition-1]; holePosition–; printf(" item moved : %d" , intArray[holePosition]); } if(holePosition != i) { printf(" item inserted : %d, at position : %d" , valueToInsert,holePosition); // insert the number at hole position intArray[holePosition] = valueToInsert; } printf(“Iteration %d#:",i); display(); } }void main() { printf(“Input Array: “); display(); printline(50); insertionSort(); printf(“Output Array: “); display(); printline(50);}输出Input Array: [4 6 3 2 1 9 7 ]==================================================Iteration 1#:[4 6 3 2 1 9 7 ] item moved : 6 item moved : 4 item inserted : 3, at position : 0Iteration 2#:[3 4 6 2 1 9 7 ] item moved : 6 item moved : 4 item moved : 3 item inserted : 2, at position : 0Iteration 3#:[2 3 4 6 1 9 7 ] item moved : 6 item moved : 4 item moved : 3 item moved : 2 item inserted : 1, at position : 0Iteration 4#:[1 2 3 4 6 9 7 ]Iteration 5#:[1 2 3 4 6 9 7 ] item moved : 9 item inserted : 7, at position : 5Iteration 6#:[1 2 3 4 6 7 9 ]Output Array: [1 2 3 4 6 7 9 ]==================================================总结一个for和一个while循环，for用于遍历已经排序好的数组，while用于遍历未排序的数组。进行交换。代码如下// 插入排序public class insertSort { public static void sort(int[] numbers){ // 其中insert为要插入的数据 int i, j , insert; // 从数组的第二个元素开始循环数组中的元素插入 for(i = 1; i < numbers.length; i++){ // 用于保存被替换的值 insert = a[i]; // 用于保存已经排序好的列表 j = i - 1; // 寻找剩余列表的数组，用于进行插入 while(j >= 0 && insert < a[j]){ // 把待插入的位置挪开 a[j + 1] = a[j]; j–; } // 进行插入 a[j + 1] = insert; } }}核心在于维护两个，一个用于已经排序好的，一个用于没有排序好的。 ...

虽然二分法很简单，但是之前并没有对其有过太多的注意，只是把它当成一个查找元素的方法来应用，但是随着后面做题的深入，发现二分法也有很多讲究，所以这里做一个总结归纳一下；一、二分法的基础概念：二分法研究的序列可以分为重复或者非重复序列，其序列要求都是递增有序的；对于非重复序列，我们可以很简单的给出相应的推理和逻辑；例如，我们如果要在一个严格递增序列中查找给定的x，就可以有以下代码：int binarySearch(int A[],int left,int right,int x){ int mid; while(left<=right){ mid=(left+right)/2; if(A[mid]==x) return mid; else if(A[mid]>x){ right=mid-1; }else{ left=mid+1; } } return -1;}注意两点：1.判定条件left<=right,有的情况下写成left<right，这个需要视情况而定；2.当left和right达到一定程度的时候，如果简单相加计算mid的时候，可能会导致溢出，所以往往比较保险的办法就是：mid=left+(right-left)/2这样就可以很好的避免溢出，从而保证能够进行mid的计算；上述针对的是递增非重复序列，如果重复序列，我们又该作何思考？例如示例中给出的问题，如果给出一个重复的递增序列A，我们需要求出第一个大于等于x的位置L以及第一个大于x的元素的位置R；这是两个小问题，首先先进行第一个小问题的求解：找出第一个大于等于x的位置L；其实对于这个问题，前提就已经默认了，必有L存在，所以判定条件就会发生相应的变化；int lower_bound(int A[],int left,int right,int x){ int mid; while(left<right){ mid=(left+right)/2; if(A[mid]>=x){ right=mid-1; }else{ left=mid+1; } } return left;}这里我们可以看出变了两个条件，第一个是left<right，第二个是A[mid]>=x；对于第一个条件的改变，我们可以理解为把符合条件的元素夹出来，当循环终止的时候，必有left=right,此时两个索引指向同一个元素，该元素就是我们在寻找的元素；而对于第二个条件的改变，则是由于题目性质决定的；如果中间点大于等于x，则我们可以认为要寻找的第一个x在mid的左边，所以right=mid。即使在等于条件下，由于right=mid，所以还是可以保证要寻找的数在[left,right]区间内；这一点和之前的mid+1和mid-1完全不同，其根本原因是序列内元素是否唯一；如果难以判别使用哪种方法，则每次及逆行mid迭代的时候，一定要试一试边界是否能够像预期那样包括进行需要寻找的元素；第二个自问题就是求序列中第一个大于x的位置;对于这个问题，我们仍然需要关注的是判定条件;代码如下：int upper_bound(int A[],int left,int right,int x){ int mid; while(left<right){ mid=(left+right)/2; if(A[mid]>x){ right=mid; }else{ left=mid+1; } } return left;}对于个算法，同样的我们需要left==right来将符合的值夹出来；当A[mid]>x时，由于我们寻找的时大于x的值，此时该值必在mid的左边，同样的，如果mid就是大于x的值，也应该包括进去，所以此时，right=mid;当A[mid]<=x时，由于我们寻找的是一个大于x的值，所以mid不必包括进去，left=mid+1;总的来说，上述推举的方法，都在解决一个核心问题：在该序列中，找到第一个符合该条件的值；二、二分法的主要应用：1.利用二分法求某数字的近似值：这个问题其实很经典，自己以前碰到过几次；例如：求解根号2的近似值，要求精度在10^-5；这个问题就可以利用该方法进行计算；首先我们需要构建目标函数F(x)=x^2，从而转换成1~2区间内的实数计算；设置边界left=1，right=2，来利用函数进行逼近；代码如下：const double eps=1e-5;double f(double x){ return xx;}int binarySearch(){ double left=1; double right=2; double mid; while(right-left>1e-5){ mid=(right+left)/2; if(f(mid)>2){ right=mid; }else{ left=mid; } } return mid;}2.快速幂：快速幂就是给出三个整数a,b,m,求得a^b%m；这个问题也可以采用二分思想来进行递归计算；若b是奇数：a^b=aa^(b-1)若b是偶数：a^b=a^(b/2)a^(b/2);代码如下：long long binarypow(long long a,long long b,long long m){ if(b==0) return 1; if(b%2==1) return abinarypow(a,b-1,m)%m; else{ long long mul=binarypow(a,b/2,m); return mul*mul%m; }}注意上述的mul，不要单纯计算两次a^(b/2),而使用mul，这样可以适当的介绍时间复杂度； ...

该题目有两种解法，都是动态规划中特别经典的解法，一种是最长不下降子序列，一种是最长公共子序列；第一种方法对于该题目其实有点取巧的感觉；首先，注意一点，对于最长不下降子序列来说，其序列的元素一定是非递减的，所以我们的当务之急是如何将值转换为递增序列，从而使得算法能够继续进行；对于这个问题，我们可以使用hashtable进行处理，也就是利用hashtable重新使得值递增；这里需要注意一下，子序列递增研究的是不连续的子序列，连续的子序列其实可以用前面的KMP算法来及进行解决；对于该问题，首当其中的还是状态转移方程。由于该问题还是从0开始研究，所以仍然设置一个一维数组dp来储存中间的状态；大致思路是限定一个子串序列，然后选择一个，从第一个开始进行轮询，这里有点像插入排序的感觉；其状态转移方程为dp[i]=max(1,dp[j]+1);该方程可以理解将第i个元素排在j后面，从而继承j之前的子串序列的长度，1为单个元素的序列长度；代码如下：#include<iostream>#include<stdio.h>#include<stdlib.h>#include<algorithm>using namespace std;const int maxc=210;const int maxn=10010;int Hashtable[maxc];int a[maxn],dp[maxn];int main(){ int n,m,x; scanf("%d%d",&n,&m); memset(Hashtable,-1,sizeof(Hashtable)); for(int i=0;i<m;i++){ scanf("%d",&x); Hashtablet[x]=i; } int L,num=0; scanf("%d",&L); for(int i=0;i<L;i++){ scanf("%d",&x); if(Hashtable[x]>=0){ a[num++]=Hashtable[x]; //进行hashtable的相应转换 } } int ans=-1; for(int i=0;i<num;i++){ dp[i]=1; for(int j=0;j<i;j++){ if(a[j]<=a[i]&&dp[i]<dp[j]+1){ dp[i]=dp[j]+1; } } ans=max(ans,dp[i]); } printf("%d\n",ans); return 0;}第二种不太好理解，所以这里先不再赘述，主要是不能理解为什么公共部分可以重复输出；

这道题也是动态规划的几大问题之一，也就是最大连续序列和问题；对于这个问题，我们需要考虑的首先还是转换方程的问题：我们设置一个dp数组，dp[i]代表的是到当前的最大序列和。所以有转换方程：dp[i]=max(a[i],dp[i-1]+a[i])所以边界就是dp[0]=a[0]，然后从1开始计算；代码如下：#include<iostream>#include<stdlib.h>#include<stdio.h>#include<cstring>#include<string>using namespace std;const int maxn=1010;string data;int matrix[maxn][maxn];int main(){ getline(cin,data); int len=data.size(); for(int i=0;i<len;i++){ matrix[i][i]=1; } int ans=1; for(int i=1;i<len;i++){ if(data[i-1]==data[i]){ matrix[i-1][i]=1; ans=2; } } for(int L=3;L<=len;L++){ for(int i=0;i+L-1<len;i++){ int j=i+L-1; if(data[i]==data[j]&&matrix[i+1][j-1]==1){ matrix[i][j]=1; ans=L; } } } printf("%d\n",ans); system(“pause”); return 0;}

这道题是动态规划几大问题的其中一种，为最长回文子串问题；动态规划个人来说，觉得最重要的就是建立状态转移方程。对于方程变量，我认为最重要的是有几个构成的关键变量；对于这道题，我们着手于i~j个字符，所以关注点在于i和j，所以我们建立一个二维矩阵来保存动态规划途中的计算值。对于dpi，其值为1时，意为i-j的字串是回文子串，为其他值则不是；对于状态转移方程，我们可以这样想：对于一个回文子串，其子串也是回文子串，所以就有方程转移的定律：dpi=dpi+1接下来就是如何遍历；对于遍历，我们一定要保证从边界开始，并且现有计算状态必须建立在已有建立状态之上。由于转换方程的特殊性，i,j两个坐标都像两边扩散，所以我们可以根据L，也就是子串的长度来进行计算；先将单个字符相应的值置为1，然后L=2…..至L=n;在途中记录子串的长度；代码如下所示：#include<iostream>#include<stdlib.h>#include<stdio.h>#include<cstring>#include<string>using namespace std;const int maxn=1010;string data;int matrix[maxn][maxn];int main(){ getline(cin,data); int len=data.size(); for(int i=0;i<len;i++){ matrix[i][i]=1; } int ans=1; for(int i=1;i<len;i++){ if(data[i-1]==data[i]){ matrix[i-1][i]=1; ans=2; } } for(int L=3;L<=len;L++){ for(int i=0;i+L-1<len;i++){ int j=i+L-1; if(data[i]==data[j]&&matrix[i+1][j-1]==1){ matrix[i][j]=1; ans=L; } } } printf("%d\n",ans); system(“pause”); return 0;}

KMP算法其实理解起来也不难，只不过很多过于公式化的讲解以及太过晦涩的说法会让人一头雾水；KMP算法主要是判断一个字符串是否是另一个字符串的字串；对于这两个字符串，在算法描述中有固定的称谓：我们把最长的字符串称为text，需要判定的子串称为模式pattern;对于这个问题，其实最容易想到的就是暴力枚举：即text字符串逐个字符判定，若当前第i字符和pattern首字符一样，进行pattern第二位的判定，如果中间有一个字符不同，则结束本轮判断，重新判断第i+1个字符；该方法会达到O(m*n)级别；而KMP算法就是处理该问题的更优算法，复杂度只有O(m+n);其实我们可以大致推断出暴力枚举的缺陷点，其根本的问题就是回溯。由于pattern字符串有可能会有某些规律，使得我们判断第i个字符失败的时候，不用从i+1个开始重新判断，只需要判断i+k个，而KMP算法就是描述如何进行更优判断；首先接触KMP算法，我们要理解NEXT数组，NEXT数组针对的是pattern字符串，描述的是当前字符串的最长的相同前缀和后缀的长度；例如:ababa,其最长的相同前缀后缀就是aba，这个自己看一看就很清楚；而NEXT数组保存的就是这些值。NEXT数组索引是当前0~i子字符串的长度，其相应的数组值就是该长度下的相同前后缀的长度k；这里其实可以注意一下，由于给出的字符串坐标索引是从0开始，所以k也可以认为是最长前缀的最后一位的下标；对于这个数组，我们其实可以依次算出来，但是如果用程序化的语言描述，则应该使用递推来进行；具体代码如下：void getNext(char s[],int len){ int j=-1; next[0]=-1; for(int i=1;i<len;i++){ while(j!=-1&&s[i]!=s[j+1]){ j=next[j]; } if(s[i]==s[j+1]){ j++; } next[i]=j; }}对于上述代码，可能有点不清晰，所以讲解一下：首先我们必定是从字符串开头算起，对于一个字符，我们无法计算他的前后缀，所以设置-1，意为，没有前后缀；后续则从第二个字符进行判断；首先理解j，j就是当前第i个字符需要比较的字符，为什么要比较，原因如下；假如出现如下情况：我们当前j指向的是b，需要比较的i指向的是b，如果这两个相同，则前缀后缀都变成了abb，其实j存在的意义就是判断能否继承之前的前后缀性质，既然i-1,i-2和j-1,j-2一样，都是ab，那么如果下一位i和j都一样，那么就是i,i-1,i-2和j,j-1,j-2一样，都为abb，则后缀前缀都变成abb；之前说过，NEXT的内容代表的是相应长度下的最长前缀长度，因此，在相同的情况下，长度为i的串的前缀最大长度就应该是上述代码最后一行的next[i]=j；相等情况下很好理解，关键在于不想等情况的理解；自己参阅相关的文献。。。还想破头想了好久，发现不相等的情况其实就是两种情况的一种递归情况：借用该博客下的一张图：其实说白了，当不相等就是一个向左递归找更小的序列，看能不能使得子序列里能够出现相同的前缀后缀；对于上述可能理解有点困难，可以举一个例子来看：假如有一个字符串ccacbccace；i指向e，j+1指向b；此时进行判断，不相等；此时NEXT[j]就是ccac的最长前缀的最后一个索引，也就是1，这个时候在进行j+1和i的判断；为什么要这样，原因在于根本来说，因为出去i和j，前缀和后缀相等，所以判断前缀ccac也就相当于判断后缀ccac，所以前缀ccac的第一个需要判断的c，该字符串的后缀也必定有；当然，当时自己想到了另一种情况试图推翻，但是这种情况也无需考虑；例如：ccabd,那么此时d前面不就和前缀不相同了？其实这种情况不可能出现，因为前面j指向第二个c，所以比较的仍然是第一个元素；所以总的来说，这就是一个递归向前的求更小前缀长度的操作。一旦向前得到的子序列有相同前缀和后缀，则第i个元素之前的后缀必定和该求得的前缀相同。否则，只能比较第一个元素，不可能得到更小的相同前缀后缀；所以，next数组求解就很简单；接下来就是ＫＭＰ算法，该算法就是利用NEXT函数求解；说到底KMP算法就是利用pattern的前后缀来进行操作的。如上所示：：如果D和空格不匹配，此时由于ABCDAB有相同的前后缀所以替换的时候就把前缀和后缀重合，从而移动了j-next[j]个距离，从而到达以下位置：所以也不难，主要是要怎么理解Next数组；相应代码如下所示：bool KMP(char text[],char pattern[]){ int n=strlen(text),m=strlen(pattern); getNext(pattern,m); int j=-1; for(int i=0;i<n;i++){ while(j!=-1&&text[i]!=pattern[j+1]){ j=next[j]; } if(text[i]==pattern[j+1]){ j++; } if(j==m-1){ return; } } return false;}如果需要重复计数：int KMP(char text[],char pattern[]){ int n=strlen(text),m=strlen(pattern); getNext(pattern,m); int j=-1; int ans=0 for(int i=0;i<n;i++){ while(j!=-1&&text[i]!=pattern[j+1]){ j=next[j]; } if(text[i]==pattern[j+1]){ j++; } if(j==m-1){ ans++; j=next[j]; } } return ans;}

还是贪心算法应用；建立string的数组，输入之后，两两进行比较，a+b>b+a，则两两交换位置，将每个string放到合适的位置，从而使得局部最优，变为整体最优；这里示例代码使用的是sort函数，个人不太清楚这个机制，但是总的来说，这个题目的string排序和相邻元素相互比较从而交换的方式相同；具体代码如下所示:#include<iostream>#include<stdlib.h>#include<stdio.h>#include<algorithm>#include<string>using namespace std;const int maxn=10010;string str[maxn];bool cmp(string a,string b){ return a+b<b+a;}int main(){ int n; cin>>n; for(int i=0;i<n;i++){ cin>>str[i]; } sort(str,str+n,cmp); string ans; for(int i=0;i<n;i++){ ans+=str[i]; } while(ans.size()!=0&&ans[0]==‘0’){ ans.erase(ans.begin()); } if(ans.size()==0) cout<<0; else cout<<ans; system(“pause”); return 0;}

这道题的题目和之前的PAT题目相同，也是采用打表的方法；先预先算好所有的元素；建立两个数组，left，right；left从左到右遍历，索引index装从左到index中最大的元素；right从右到左遍历，索引index装从右到index中最小元素；之后从0~n比较left，right相应的成员，也就是看左边最大和右边最小是否符合题目规范#include<iostream>#include<stdlib.h>#include<stdio.h>using namespace std;const int maxn=100010;const int INF=0x3fffffff;int data[maxn];int left1[maxn];int right1[maxn];int ans[maxn];int num=0;int n;int main(){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&data[i]); } left1[0]=0; for(int i=1;i<n;i++){ left1[i]=max(left1[i-1],data[i-1]); } right1[n-1]=INF; for(int i=n-2;i>=0;i–){ right1[i]=min(right1[i+1],data[i+1]); } for(int i=0;i<n;i++){ if(left1[i]<data[i]&&right1[i]>data[i]){ ans[num++]=data[i]; } } printf("%d\n",num); for(int i=0;i<num;i++){ printf("%d",ans[i]); if(i<num-1) printf(" “); } printf("\n”); system(“pause”); return 0;}

起先自己想尝试性的直接排序找中位数，内存直接超限；其实这道题可以采用归并排序的思路来做：但是示例依旧白给。。。不过还是展现了一种思想，代码如下：#include<iostream>#include<stdlib.h>#include<stdio.h>#include<vector>#include<algorithm>using namespace std;using std::vector;const int maxn=1000010;const int INF=0x7fffffff;int a[maxn];int b[maxn];int main(){ int n,m; scanf("%d",&n); int index=0; for(int i=0;i<n;i++){ scanf("%d",&a[i]); } scanf("%d",&m); for(int i=0;i<m;i++){ scanf("%d",&b[i]); } a[n]=b[m]=INF; int i=0,j=0,ct=0; int mid=(m+n-1)/2; while(ct<mid){ if(a[i]<b[j]){ i++; }else j++; ct++; } if(a[i]<b[j]){ printf("%d\n",a[i]); }else{ printf("%d\n",b[j]); } system(“pause”); return 0;}网上给出了一种示例，能够完全AC；#include <iostream>using namespace std;int k[200005];int main(){ int n, m, temp, count = 0; cin >> n; for (int i = 1; i <= n; i++) scanf("%d", &k[i]); k[n + 1] = 0x7fffffff; cin >> m; int midpos = (n + m + 1) / 2, i = 1; for (int j = 1; j <= m; j++) { scanf("%d", &temp); while (k[i] < temp) { count++; if (count == midpos) cout << k[i]; i++; } count++; if (count == midpos) cout << temp; } while (i <= n) { count++; if (count == midpos) cout << k[i]; i++; } return 0;}具体的思路就是，输入第一个序列；在输入第二个序列的时候进行判断，主要的判断逻辑为：如果输入的值小于第一个序列的相应值，cout++，跳过该值；如果大于相应值，进行向后判断，cout计算增加的值；如果发现途中cout的值等于中点值，直接进行输出，程序停止； ...

关于hashCodehashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，hashCode是用来在散列存储结构中确定对象的存储地址的.1.hashcode是用来查找的，如果你学过数据结构就应该知道，在查找和排序这一章有例如内存中有这样的位置0 1 2 3 4 5 6 7 而我有个类，这个类有个字段叫ID,我要把这个类存放在以上8个位置之一，如果不用hashcode而任意存放，那么当查找时就需要到这八个位置里挨个去找，或者用二分法一类的算法。但如果用hashcode那就会使效率提高很多。我们这个类中有个字段叫ID,那么我们就定义我们的hashcode为ID％8，然后把我们的类存放在取得得余数那个位置。比如我们的ID为9，9除8的余数为1，那么我们就把该类存在1这个位置，如果ID是13，求得的余数是5，那么我们就把该类放在5这个位置。这样，以后在查找该类时就可以通过ID除 8求余数直接找到存放的位置了。2.但是如果两个类有相同的hashcode怎么办那（我们假设上面的类的ID不是唯一的），例如9除以8和17除以8的余数都是1，那么这是不是合法的，回答是：可以这样。那么如何判断呢？在这个时候就需要定义 equals了。也就是说，我们先通过 hashcode来判断两个类是否存放某个桶里，但这个桶里可能有很多类，那么我们就需要再通过 equals 来在这个桶里找到我们要的类。那么。重写了equals()，为什么还要重写hashCode()呢？想想，你要在一个桶里找东西，你必须先要找到这个桶啊，你不通过重写hashcode()来找到桶，光重写equals()有什么用啊理解了hashCode我们来理解HashMapHashMap概述HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。内部存储HashMap的内部存储是一个数组（bucket），数组的元素Node实现了是Map.Entry接口(hash, key, value, next)，next非空时指向定位相同的另一个Entry，如图：关于hashCodehashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，hashCode是用来在散列存储结构中确定对象的存储地址的.1.hashcode是用来查找的，如果你学过数据结构就应该知道，在查找和排序这一章有例如内存中有这样的位置0 1 2 3 4 5 6 7 而我有个类，这个类有个字段叫ID,我要把这个类存放在以上8个位置之一，如果不用hashcode而任意存放，那么当查找时就需要到这八个位置里挨个去找，或者用二分法一类的算法。但如果用hashcode那就会使效率提高很多。我们这个类中有个字段叫ID,那么我们就定义我们的hashcode为ID％8，然后把我们的类存放在取得得余数那个位置。比如我们的ID为9，9除8的余数为1，那么我们就把该类存在1这个位置，如果ID是13，求得的余数是5，那么我们就把该类放在5这个位置。这样，以后在查找该类时就可以通过ID除 8求余数直接找到存放的位置了。2.但是如果两个类有相同的hashcode怎么办那（我们假设上面的类的ID不是唯一的），例如9除以8和17除以8的余数都是1，那么这是不是合法的，回答是：可以这样。那么如何判断呢？在这个时候就需要定义 equals了。也就是说，我们先通过 hashcode来判断两个类是否存放某个桶里，但这个桶里可能有很多类，那么我们就需要再通过 equals 来在这个桶里找到我们要的类。那么。重写了equals()，为什么还要重写hashCode()呢？想想，你要在一个桶里找东西，你必须先要找到这个桶啊，你不通过重写hashcode()来找到桶，光重写equals()有什么用啊理解了hashCode我们来理解HashMapHashMap概述HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。内部存储HashMap的内部存储是一个数组（bucket），数组的元素Node实现了是Map.Entry接口(hash, key, value, next)，next非空时指向定位相同的另一个Entry，如图：HashMap实现存储和读取存储public V put(K key, V value) { // HashMap允许存放null键和null值。 // 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。 if (key == null) return putForNullKey(value); // 根据key的keyCode重新计算hash值。 int hash = hash(key.hashCode()); // 搜索指定hash值在对应table中的索引。 int i = indexFor(hash, table.length); // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { // 如果发现已有该键值，则存储新的值，并返回原始值 V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 如果i索引处的Entry为null，表明此处还没有Entry。 modCount++; // 将key、value添加到i索引处。 addEntry(hash, key, value, i); return null; }根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。hash(int h)方法根据key的hashCode重新计算一次散列。此算法加入了高位计算，防止低位不变，高位变化时，造成的hash冲突。 static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }HashMap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表，这样就大大优化了查询的效率。根据上面 put 方法的源代码可以看出，当程序试图将一个key-value对放入HashMap中时，程序首先根据该 key的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry的 value，但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。具体如何根据hash计算下标呢，参见JDK 源码中 HashMap 的 hash 方法原理是什么？获取 public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。HashMap的resize当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过160.75=12的时候，就把数组的大小扩展为216=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，不过上面annegu已经说过，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.751000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适，既考虑了&的问题，也避免了resize的问题。1.8的优化Java8做的改变:1.HashMap是数组+链表+红黑树(JDK1.8增加了红黑树部分),当链表长度>=8时转化为红黑树在JDK1.8版本中,对数据结构做了进一步的优化,引入了红黑树。而当链表长度太长(默认超过8)时，链表就转换为红黑树，利用红黑树快速增刪改查的特点提高HashMap的性能，其中会用到红黑树的插入、刪除、查找等算法。java8 中对hashmap护容不是重新计算所有元素在数组的位置，而是我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap"。面试中通常被问到的。HashMap高并发情况下会出现什么问题? 扩容问题HashMap的存放自定义类时，需要实现自定义类的什么方法?hashCode和equals.通过hash(hashCode)然后模运算(其实是与的位操作)定位在Entry数组中的下标，然后遍历这之后的链表，通过equals比较有没有相同的key,如果有直接覆盖value,如果没有就重新创建一一个Entry。hashmap为什么可以插入空值?HashMap中添加key == null的Entry时会调用putForNullKey方法直接去遍历table[0]Entry链表，寻找e.key == null的Entry或者没有找到遍历结束如果找到了e.key==null,就保存null值对应的原值oldValue,然后覆盖原值，并返回oldValue如果在table[O]Entrty链表中没有找到就调用addEntry方法添加一个key为null的Entry Hashmap 为什么线程不安全(hash 碰撞和扩容导致)HashMap扩容的的时候可能会形成环形链表，造成死循环。 ...

这一道题是贪心算法中接触到的比较难的题目，关键是难以归纳出具体的做法步骤，这里详解以下示例给出的步骤：首先，将加油站进行距离排序；示例将选择可到达范围内的下一节点分为了两种情况：1.如果在可到达范围内第一次出现了低于当前油价的站点，则到达该站点；这个选择的依据是，如果我们在a,有a->b->c，b站点油价便宜，所以我们应该去b加油再跑到c，而不是加a站的油跑到c。2.如果第一种情况没有出现，所有可达站点油价都比当前站点贵，则我们应该找到可达站点油价最小的那一个，作为下一站。但是这里有一个非常重要的操作，就是加满油再去；这个操作的依据是：如果我们在a,有a->b->c，b站点油价比a贵，如果我们从a加满到b，剩下v升油，比没加满从b到c可以省钱，所以应该先在a加满，去b，从而在及进行判断；整体来说，每到一个站点判断一次，只判断当前站点到下一站点的最优解，从而使得通过贪心算法达到整体最优；代码如下所示：#include<iostream>#include<stdlib.h>#include<stdio.h>#include<vector>#include<cmath>#include<algorithm>using namespace std;using std::vector;const int maxn=510;const int INF=10000000000;struct station{ double dis; double price;}st[maxn];bool cmp(station a,station b){ return a.dis<b.dis;}int main(){ int n; double Cmax,D,Davg; scanf("%lf%lf%lf%d",&Cmax,&D,&Davg,&n); for(int i=0;i<n;i++){ scanf("%lf%lf",&st[i].price,&st[i].dis); } st[n].dis=D; st[n].price=0; sort(st,st+n,cmp); if(st[0].dis!=0){ printf(“The maximum travel distance = 0.00\n”); }else{ int now=0;//现在的站点； double ans=0;//总花费 double nowTank=0;//当前油箱余量； double MAX=Cmax*Davg;//最大行走距离； while(now<n){ //先进行最小站点的选择； int next_station=-1; double min_price=INF; for(int i=now+1;i<=n&&st[i].dis-st[now].dis<=MAX;i++){ if(st[i].price<min_price){ min_price=st[i].price; next_station=i; if(st[i].price<st[now].price){ //如果小于当前起点的油价，直接退出 break; } } } //已经获得下一站的目的； if(next_station==-1) break;//没有找到下一站 double need=(st[next_station].dis-st[now].dis)/Davg;//到下一站所需要的油量 if(min_price<st[now].price){ //如果是低于当前节点的中继站 if(nowTank<need){ //如果当前油量不支持到达下一站 ans+=(need-nowTank)*st[now].price; nowTank=0; }else{ nowTank-=need; } }else{ //到了更远的一站； //当前站油便宜，直接拉满 ans+=(Cmax-nowTank)*st[now].price; nowTank=Cmax-need; } now=next_station; } if(now==n){ printf("%.2f\n",ans); }else{ printf(“The maximum travel distance = %.2f\n”,st[now].dis+MAX); } } system(“pause”); return 0;} ...

这道题的贪心思路就是分两个情况，一个大于零，一个小于零，分别进行排序，大的乘大的；对于代码里，我们直接对其进行sort排序，然后分两种情况，一个负数，一个正数；对于负数，采用的是同时两个序列从最小的开始选取，直到有一个队列穷举完毕；正数情况类似；但是需要注意的是一定要从头遍历，从而以防出现元素漏掉的情况；代码如下#include<iostream>#include<stdlib.h>#include<stdio.h>#include<algorithm>using namespace std;const int maxn=100010;int coupon[maxn],product[maxn];int main(){ int n,m; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&coupon[i]); } scanf("%d",&m); for(int i=0;i<m;i++){ scanf("%d",&product[i]); } sort(coupon,coupon+n); sort(product,product+m); int i=0,j,ans=0; while(i<n&&i<m&&coupon[i]<0&&product[i]<0){ ans+=coupon[i]*product[i]; i++; } i=n-1; j=m-1; while(i>=0&&j>=0&&coupon[i]>0&&product[j]>0){ ans+=coupon[i]*product[j]; i–,j–; } printf("%d\n",ans); system(“pause”); return 0;}

简单的贪心问题，和背包问题类似，这里不再赘述#include<iostream>#include<stdlib.h>#include<stdio.h>#include<vector>#include<cmath>#include<algorithm>using namespace std;using std::vector;const int maxn=1010;struct node{ double num; double price;};bool cmp(node a,node b){ return a.price>b.price;}node moc[maxn];int n;double m;int main(){ double p; scanf("%d%lf",&n,&m); for(int i=0;i<n;i++){ scanf("%lf",&moc[i].num); } for(int i=0;i<n;i++){ scanf("%lf",&p); moc[i].price=p/moc[i].num; } sort(moc,moc+n,cmp); double money=0; for(int i=0;i<n;i++){ if(m==0) break; if(moc[i].num<=m){ money+=moc[i].pricemoc[i].num; m-=moc[i].num; }else{ money+=mmoc[i].price; m=0; } } printf("%.2f\n",money); system(“pause”); return 0;}

之前在博客里总结过贪心算法的相关注意概念，但是由于当时理解不够，并没有很好的总结区间贪心问题，所以在这里做一个总结：区间贪心算法总的来说有两大题型，一个是区间不相交问题，一个是区间选点问题；其实第二种问题是第一种问题的子问题，并且对于贪心算法中的概念一定要有所体会；一、区间不相交区间不相交问题就是对给定的一些开区间中，尽可能多的选择开区间，使得这些开区间两两没有交集；对于这个问题，首先要理解重叠区间的概念，也就是对于下列图片所给的情况：当出现这钟情况的时候，我们应该优先选择I1，因为这样的话就可以给其他区间腾出很多的空闲位置；其次，当消除了所有子区间重叠问题的时候，我们会有如下的情况出现：对于这种情况，我们采用的是对各个区间按照左端点的大小进行排序，此时就会形成上图的情况，每个区间的有右边节点有序；代码如下所示:#include<stdlib.h>#include<stdio.h>#include<algorithm>using namespace std;const int maxn=110;struct Inteval{ int x,y;}I[maxn];bool cmp(Inteval a,Inteval b){ if(a.x!=b.x) return a.x>b.x;//左端从大到小进行排序 else return a.y<b.y;//有段从小到大进行排序}int main(){ int n; while(scanf("%d",&n),n!=0){ for(int i=0;i<n;i++){ scanf("%d%d",&I[i].x,&I[i].y); } sort(I,I+n,cmp); int ans=1,lastX=I[0].x; for(int i=1;i<n;i++){ if(I[i].y<=lastX){ //该情况下为不相交区间 lastX=I[i].x; ans++; } } } system(“pause”);}其实最难理解的应该是代码中的处理，这里给出详细的解释：首先来看排序函数bool cmp(Inteval a,Inteval b){ if(a.x!=b.x) return a.x>b.x;//左端从大到小进行排序 else return a.y<b.y;//有段从小到大进行排序}这里之所以要在左端大小相同的情况下对右端进行递增排序，是为了找出包含区间中的最小的子区间；这样进行排序的时候，就会变成存在包含关系的区间在一起，但是首位肯定是包含区间中的最小区间；之后就是主体处理；while(scanf("%d",&n),n!=0){ for(int i=0;i<n;i++){ scanf("%d%d",&I[i].x,&I[i].y); } sort(I,I+n,cmp); int ans=1,lastX=I[0].x; for(int i=1;i<n;i++){ if(I[i].y<=lastX){ //该情况下为不相交区间 lastX=I[i].x; ans++; } } }这里注意for循环，其实就是对数组进行上述分析的第二部处理，从右向左，寻找不重合的区间（由于排序函数的操作，找到的必定是重合区间中的最小区间），循环从而使得每次选择出来的都是最小的不重合的区间；个人认为，区间不重叠的贪心思路主要体现在寻找最小的包含区间上；对于每一块有重合情况的区间，我们只需要找出每一块的重合区间中的最小区间，就可以组合成不重叠的区间，并且这些区间肯定数目最大，符合题意；二、区间选点区间选点可以视为第一种问题的衍生问题，目的是将给出开区间（注意，这里是开区间）中选择点，使得每个区间都至少有一个点；该问题也涉及重叠区间的问题。还是一样，当上述情况发生的时候，我们如果点放在I1内，就会使得I2内也存在点；所以根本上来说，我们还是寻找重叠区间内最小的区间；因此，我们采用的还是第一类问题的操作，但是需要注意的就是点的选取；对于有序的序列，我们应该把点选在左端点，而不是右端点；关于这个问题，可以这样想:对于上述情况，如果选取右端点，就会出现选择两个的情况，但是如果选取左端点，就只用选取一个；所以，只需要对之前的代码进行修改，修改一个判定条件；将I[i].y<=lastX修改为I[i]<lastX即可

这一篇是接上一篇文章二叉树的基本运算二叉树的遍历二叉树遍历分为三种：前序、中序、后序:前序遍历：根结点 -> 左子树 -> 右子树中序遍历：左子树 -> 根结点 -> 右子树后序遍历：左子树 -> 右子树 -> 根结点另外还有一种层次遍历，即每一层都从左向右遍历。譬如，对于下面的二叉树前序遍历：abdefgc中序遍历：debgfac后序遍历：edgfbca层次遍历：abcdfeg实现方法因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点中序遍历go实现// 中序遍历，用栈实现func inOrderBinaryTree1(root *BinaryTreeNode) { if root == nil { return } stack := []*BinaryTreeNode{} top := -1 for top >= 0 || root != nil { for root != nil { stack = append(stack, root) top++ root = root.lChild } item := stack[top] stack = stack[:top] top– // 出栈 fmt.Print(item.data) if item.rChild != nil { root = item.rChild } }} ...

队列的定义队列是遵循先进先出原则的一组有序的项，与栈的不同的是，栈不管是入栈还是出栈操作都是在栈顶操作，队列则是在队尾添加元素，队顶移除，用一个图来表示大概是这样事的：用一个更形象的例子就是：排队服务，总是先排队的人会先接受服务，当然不考虑插队的情况队列的创建与栈的创建类似，首先创建一个表示队列的函数，然后定义一个数组用来保存队列里的元素：function Queue() { let items = []}创建队列后需要为其定义一些方法，一般来说队列包含以下方法：enqueue(element)：向队的尾部添加一个新的项dequeue()：移除队列第一项，并返回被移除的元素front()：返回队列第一项，队列不做任何变动isEmpty()：如果队列中没有任何元素返回true，否则返回falsesize()：返回队列包含的元素个数具体实现：function Queue() { let items = [] // 向队列的尾部添加新元素 this.enqueue = function (element) { items.push(element) } // 遵循先进先出原则，从队列的头部移除元素 this.dequeue = function () { return items.shift() } // 返回队列最前面的项 this.front = function () { return items[0] } // 返回队列是否为空 this.isEmpty = function () { return items.length === 0 } // 返回队列的长度 this.size = function () { return items.length } // 打印队列，方便观察 this.print = function () { console.log(items.toString()) }}队列的使用接下来让我们看看队列的使用：let queue = new Queue()queue.enqueue(‘a’)queue.enqueue(‘b’)queue.enqueue(‘c’)queue.dequeue()queue.print()首先向队列中添加三个元素：a,b,c,然后移除队列中的一个元素，最后打印现有队列，让我们一起图解这个过程：es6实现Queue和实现Stack类一样，也可以用es6的class语法实现Queue类，用WeakMap保存私用属性items，并用闭包返回Queue类，来看具体实现：let Queue = (function () { let items = new WeakMap class Queue { constructor () { items.set(this, []) } enqueue (element) { let q = items.get(this) q.push(element) } dequeue () { let q = items.get(this) return q.shift() } front () { let q = items.get(this) return q[0] } isEmpty () { let q = items.get(this) return q.length === 0 } size () { let q = items.get(this) return q.length } print () { let q = items.get(this) console.log(q.toString()) } } return Queue})()let queue = new Queue()queue.enqueue(‘a’)queue.enqueue(‘b’)queue.enqueue(‘c’)queue.dequeue()queue.print()优先队列优先队列顾名思义就是：队列中的每个元素都会有各自的优先级，在插入的时候会根据优先级的高低顺序进行插入操作，和前面队列实现有点不太一样的地方，队列中的元素多了有先级的属性，下面来看具体代码：function PriorityQueue() { let items = [] // 队列元素，多定义一个优先级变量 function QueueElement(element, priority) { this.element = element this.priority = priority } this.enqueue = function (element, priority) { let queueElement = new QueueElement(element, priority) let added = false for (let i = 0; i < items.length; i++) { //数字越小优先级越高 if (queueElement.priority < items[i].priority) { items.splice(i, 0, queueElement) added = true break } } if (!added) { items.push(queueElement) } } this.dequeue = function () { return items.shift() } this.front = function () { return items[0] } this.isEmpty = function () { return items.length === 0 } this.size = function () { return items.length } this.print = function () { for (let i = 0; i < items.length; i++) { console.log(${items[i].priority}-${items[i].element}) } }}let priorityQueue = new PriorityQueue()priorityQueue.enqueue(‘a’, 3)priorityQueue.enqueue(‘b’, 2)priorityQueue.enqueue(‘c’, 1)priorityQueue.dequeue()priorityQueue.print()入队时如果队列为空直接加入队列，否则进行比较，priority小的优先级高，优先级越高放在队列的越前面，下面用一个图来看调用过程：循环队列循环队列顾名思义就是：给定一个数，然后迭代队列，从队列开头移除一项，然后再将其加到队列末尾，当循环到给定数字时跳出循环，从队首移除一项，直至剩余一个元素，下面来看具体代码：unction Queue() { let items = [] this.enqueue = function (element) { items.push(element) } this.dequeue = function () { return items.shift() } this.front = function () { return items[0] } this.isEmpty = function () { return items.length === 0 } this.size = function () { return items.length } this.print = function () { console.log(items.toString()) }}function loopQueue(list, num) { let queue = new Queue() for (let i = 0; i<list.length; i++) { queue.enqueue(list[i]) } while (queue.size() > 1) { for (let j = 0; j<num; j++) { queue.enqueue(queue.dequeue()) } let out = queue.dequeue() console.log(‘出队列：’ + out) } return queue.dequeue()}console.log(’last：’ + loopQueue([‘a’, ‘b’, ‘c’, ’d’, ’e’], 3))总结这篇文章主要对队列做了简单介绍，对队列以及相关应用做了简单实现。如果有错误或不严谨的地方，欢迎批评指正，如果喜欢，欢迎点赞。 ...

题目定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。思路1.定义两个栈，一个栈用于存储数据，另一个栈用于存储每次数据进栈时栈的最小值.2.每次数据进栈时，将此数据和最小值栈的栈顶元素比较，将二者比较的较小值再次存入最小值栈.4.数据栈出栈，最小值栈也出栈。3.这样最小值栈的栈顶永远是当前栈的最小值。代码var dataStack = [];var minStack = []; function push(node){ dataStack.push(node); if(minStack.length === 0 || node < min()){ minStack.push(node); }else{ minStack.push(min()); }}function pop(){ minStack.pop(); return dataStack.pop();}function top(){ var length = dataStack.length; return length>0&&dataStack[length-1]}function min(){ var length = minStack.length; return length>0&&minStack[length-1]}

平衡二叉树AVL，写过总结，这里不再赘述；#include<iostream>#include<stdlib.h>#include<stdio.h>#include<vector>#include<algorithm>#include<queue>using namespace std;using std::vector;using std::queue;const int maxn=30;int data[maxn];struct node{ int data; int height; node* lchild; node* rchild;};node* root;node* newNode(int x){ node* root=new node; root->data=x; root->height=1; root->lchild=NULL; root->rchild=NULL; return root;}int getHeight(node* root){ if(root==NULL) return 0; return root->height;}void updateHeight(node* root){ root->height=max(getHeight(root->lchild),getHeight(root->rchild))+1;}void L(node* &root){ node* temp=root->rchild; root->rchild=temp->lchild; temp->lchild=root; updateHeight(root); updateHeight(temp); root=temp;}void R(node* &root){ node* temp=root->lchild; root->lchild=temp->rchild; temp->rchild=root; updateHeight(root); updateHeight(temp); root=temp;}int getBalanceFactor(node* root){ return getHeight(root->lchild)-getHeight(root->rchild);}void insert_node(node* &root,int v){ if(root==NULL){ root=newNode(v); return; } if(v<root->data){ insert_node(root->lchild,v); updateHeight(root); if(getBalanceFactor(root)==2){ if(getBalanceFactor(root->lchild)==1){ R(root); }else if(getBalanceFactor(root->lchild)==-1){ L(root->lchild); R(root); } } }else{ insert_node(root->rchild,v); updateHeight(root); if(getBalanceFactor(root)==-2){ if(getBalanceFactor(root->rchild)==-1){ L(root); }else if(getBalanceFactor(root->rchild)==1){ R(root->rchild); L(root); } } }}node* create(int data[],int n){ node* root=NULL; for(int i=0;i<n;i++){ insert_node(root,data[i]); } return root;}int main(){ int n,; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&data[i]); } root=create(data,n); printf("%d\n",root->data); system(“pause”); return 0;} ...

这道题自己起先想到的思路是根据完全二叉树性质，找出左右子树，递归进行；但是示例给出的思想很值得学习；对于一个二叉搜索树，其中序序列必递增的，所以可以利用这一点；我们先对输入的节点序列进行递增排序，之后我们对一个空的数组进行中序遍历，每遇到一个节点，就把相应的递增序列的值保存进去；这是一种对空序列进行中序序列建树的思想，很值得借鉴；#include<iostream>#include<vector>#include<stdlib.h>#include<stdio.h>#include<algorithm>using namespace std;using std::vector;int n;const int maxn=1010;int number[maxn];int CBT[maxn];int index=0;void inorder(int root){ if(root>n) return; inorder(2root); CBT[root]=number[index++]; inorder(2root+1);}int main(){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&number[i]); } sort(number,number+n); inorder(1); for(int i=1;i<=n;i++){ printf("%d",CBT[i]); if(i<n) printf(" “); } system(“pause”); return 0;}

和完全二叉排序树那道题类似，采用的方法还是中序遍历空树填节点的方法；代码如下：#include<iostream>#include<stdlib.h>#include<stdio.h>#include<vector>#include<algorithm>#include<queue>using namespace std;using std::vector;using std::queue;const int maxn=110;struct node{ int data=-1; int lchild=-1; int rchild=-1;}Node[maxn];int n;vector<int>input;vector<int>output;int index=0;void inorder(int root){ if(root==-1) return; inorder(Node[root].lchild); Node[root].data=input[index++]; inorder(Node[root].rchild);}void layer(int root){ queue<int>q; q.push(root); while(!q.empty()){ int x=q.front(); q.pop(); output.push_back(Node[x].data); if(Node[x].lchild!=-1){ q.push(Node[x].lchild); } if(Node[x].rchild!=-1){ q.push(Node[x].rchild); } }}int main(){ int a,b; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d%d",&a,&b); Node[i].lchild=a; Node[i].rchild=b; } for(int i=0;i<n;i++){ scanf("%d",&a); input.push_back(a); } sort(input.begin(),input.end()); inorder(0); layer(0); for(int i=0;i<n;i++){ if(i==0) printf("%d",output[i]); else printf(" %d",output[i]); } system(“pause”); return 0;}

简单的不用考虑平衡的二叉查询树；我发现我有读题障碍症。。。#include<iostream>#include<stdlib.h>#include<stdio.h>#include<vector>using namespace std;using std::vector;int n;struct node{ int data; node* lchild; node* rchild;};vector<int>input;vector<int>inorder_;vector<int>change_inorder_;vector<int>postorder_;vector<int>change_postorder_;node* newNode(int x){ node* root=new node; root->lchild=NULL; root->data=x; root->rchild=NULL; return root;}void insert(node* &root,int x){ if(root==NULL){ root=newNode(x); return ; } if(x<root->data){ insert(root->lchild,x); }else{ insert(root->rchild,x); } return ;}void inorder(node* root,vector<int>& vi){ if(root==NULL) return; vi.push_back(root->data); inorder(root->lchild,vi); inorder(root->rchild,vi);}void postorder_change(node* root){ if(root==NULL) return; postorder_change(root->lchild); postorder_change(root->rchild); swap(root->lchild,root->rchild);}void postorder(node* root,vector<int>& vi){ if(root==NULL) return; postorder(root->lchild,vi); postorder(root->rchild,vi); vi.push_back(root->data);}int main(){ int mem; node* root=NULL; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&mem); insert(root,mem); input.push_back(mem); } inorder(root,inorder_); postorder(root,postorder_); postorder_change(root); inorder(root,change_inorder_); postorder(root,change_postorder_); if(inorder_==input){ printf(“YES\n”); for(int i=0;i<postorder_.size();i++){ if(i==0){ printf("%d",postorder_[i]); }else{ printf(" %d",postorder_[i]); } } }else if(input==change_inorder_){ printf(“YES\n”); for(int i=0;i<change_postorder_.size();i++){ if(i==0){ printf("%d",change_postorder_[i]); }else{ printf(" %d",change_postorder_[i]); } } }else{ printf(“NO\n”); } system(“pause”); return 0;} ...

作为开发人员，我们都希望在完成功能的基础上让代码运行的更快、更省空间，那如何衡量编写的代码是否更有效率，这就需要我们学会如何分析代码时间复杂度和空间复杂度．什么是复杂度分析执行时间和占用空间是代码性能的２个评判标准，我们分别用时间复杂度和空间复杂度去描述这２个标准，二者统称复杂度，复杂度描述的是算法执行时间（或占用空间）随数据规模的增长关系．为什么需要复杂度分析有人可能想问我代码运行一下不就知道他执行多长时间了吗，为什么还需要复杂度分析，确实你能够通过这种方法评估出代码的执行效率，但是这样会有一些局限性．1.测试结果太过于依赖测试环境同一段代码在不同处理器的机器上运行结果是显然不一样的，这时就不知道应该参考哪个测试结果．2.测试结果受到数据规模的影响很大两段不同的代码在数据量比较小的时候可能相差甚微，无法真实反映代码的性能问题．所以我们需要一个不依赖测试环境同时也不需要有具体的测试数据就能粗略的估计代码的执行效率的方法，也就是复杂度分析．如何进行复杂度分析大O复杂度表示法先看一段代码，求1,2,3…n的累加和int calc(int n) { int sum = 0;　//第一行 for(int i = 1; i <=n; i++) { sum = sum + i; } return sum;}我们来评估一下这段代码的执行时间，假设每行执行的时间一样，为row_time．第1行需要一个row_time的执行时间，第2，3行分别执行了n次，所以需要2n＊row_time的执行时间，所以这段代码加起来总共的执行时间为(2n+1)＊row_time，虽然我们并不知道row_time的具体时间，但我们发现代码的总执行时间T(n)与代码的执行次数ｎ成正比．我们可以用公式来表示T(n) = O(f(n))T(n)代表代码的总执行时间，f(n)代表代码的执行次数，O代表T(n)与f(n)成正比．所以上面的例子中，T(n) = O(2n+1)，我们可以看出大O时间复杂度表示代码执行时间随数据规模的变化趋势，我们简称为时间复杂度．当n很大时，公式中的常量，系数都可以忽略不计，并不会对变化趋势有太大影响，我们只需记下一个最大量级即可，那么刚刚的例子最后就可以记为T(n) = O(n)那以后的代码如何去分析其时间复杂度呢，我们有以下法则：1.看代码执行次数最多的一段，比如循环2.多段代码取最大量级，比如单循环和多重循环，应取多重循环的复杂度3.嵌套代码复杂度等于嵌套内外代码复杂度的乘积，比如递归和多重循环等平时我们有一些常用的复杂度级别，比如O(1) (常数阶)、O(logn) (对数阶)、O(n) (线性阶)、O(nlogn) (线性对数阶)、O(n²) (平方阶)了解了时间复杂度，那么空间复杂度也不难理解了，时间复杂度表示的是算法执行时间随数据规模增长的变化关系，那空间复杂度则表示的是算法存储空间随数据规模增长的变化关系．总结复杂度用来分析算法执行效率与数据规模增长的变化关系，越高阶复杂度的的算法执行效率也就越低，上面列举的复杂度级别从低到高分别为O(1)、O(logn)、O(n)、O(nlogn)、O(n²)．

并查集的应用，但是一上来有点蒙蔽，因为这次多了一个媒介，通过活动来判断人员是否在一个集合；有一个示例思路：构建活动的集合，首次发现在该活动的人员，将对应活动索引的内容设置为该人员编号；如果后面输入还有该活动，就将具有该活动的人员和数组内的人员进行并查集合并；大致代码如下所示：#include<stdio.h>#include<stdlib.h>#include<algorithm>using namespace std;const int N=1010;int course[N]={0};int father[N];int isRoot[N]={0};void init(int n){ for(int i=1;i<=n;i++){ father[i]=i; isRoot[i]=0; }}int findfather(int x){ int a=x; while(x!=father[x]){ x=father[x]; } //进行并查集路径的压缩 while(a!=father[a]){ int z=a; a=father[a]; father[z]=x; } return x;}void Union(int a,int b){ int faA=findfather(a); int faB=findfather(b); if(faA!=faB) father[faA]=faB;}bool cmp(int a,int b){ return a>b;}int n,h;int main(){ scanf("%d",&n); init(n); for(int i=1;i<=n;i++){ int num; scanf("%d:",&num); for(int j=0;j<num;j++){ scanf("%d",&h); if(course[h]==0){ course[h]=i; } Union(i,findfather(course[h])); } } for(int i=1;i<=n;i++){ isRoot[findfather(i)]++; } int ans=0; for(int i=1;i<=n;i++){ if(isRoot[i]!=0){ ans++; } } printf("%d\n",ans); sort(isRoot+1,isRoot+n+1,cmp); for(int i=1;i<=ans;i++){ printf("%d",isRoot[i]); if(i<ans) printf(" “); } system(“pause”); return 0;} ...

也不难，使用DFS就能很好的解决问题；对于DFS的途中节点记录有两种方法，这个需要注意一下:1.使用vector模拟栈，每次递归的时候压栈或者弹栈，遇到符合要求的时候直接复制该栈保存；2.使用path数组，并且利用numnode来追踪path数组的长度，其中path[i]代表路径上第i个节点的编号。由于numnode限制了path的长度，所以无需弹栈或者入站操作，只需要覆盖即可；关于本题判断还有一个优化，就是在过程中每次sum>s直接弹出，比之前自己想判断叶子节点优化了不少；完整代码如下所示：#include<iostream>#include<stdlib.h>#include<stdio.h>#include<vector>#include<algorithm>using namespace std;using std::vector;const int maxn=110;int n,m,s;int path[maxn];struct node{ int weight; vector<int>child;}table[maxn];bool cmp(int a,int b){ return table[a].weight>table[b].weight;}void DFS(int index,int numNode,int sum){ if(sum>s) return; if(sum==s){ if(table[index].child.size()!=0) return; for(int i=0;i<numNode;i++){ printf("%d",table[path[i]].weight); if(i<numNode-1) printf(" “); else printf("\n”); } return; } for(int i=0;i<table[index].child.size();i++){ path[numNode]=table[index].child[i]; DFS(table[index].child[i],numNode+1,sum+table[table[index].child[i]].weight); }}int main(){ int root,leaf,num; scanf("%d%d%d",&n,&m,&s); for(int i=0;i<n;i++){ scanf("%d",&table[i].weight); } for(int i=0;i<m;i++){ scanf("%d%d",&root,&num); for(int j=0;j<num;j++){ scanf("%d",&leaf); table[root].child.push_back(leaf); } sort(table[root].child.begin(),table[root].child.end(),cmp); } path[0]=0; DFS(0,1,table[0].weight); system(“pause”); return 0;}

还是数层数和数节点的问题，个人觉得用BFS比较好；当然用DFS也能做，具体的思路就是建立层数数组，深度遍历到x层的时候，如果是叶子节点就leaf[x]++，如果不是就不管，继续跳过；代码片段可以这样：void DFS(int index,int h){ max_h=max(h,max_h); if(G[index].size()==0){ leaf[h]++; return; } for(int i=0;i<G[index].size();i++){ DFS(G[index][i],h+1); }}BFS代码如下所示：#include<iostream>#include<stdlib.h>#include<stdio.h>#include<vector>#include<queue>using namespace std;using std::vector;using std::queue;const int maxn=110;int n,m;int leaf[maxn]={0};//每层leaf个数vector<int> table[maxn];int BFS(int x){ int layer=0; queue<int>q; q.push(x); while(!q.empty()){ int num=0; int length=q.size(); layer++; for(int i=0;i<length;i++){ int id=q.front(); q.pop(); if(table[id].size()==0){ num++; } for(int j=0;j<table[id].size();j++){ q.push(table[id][j]); } } leaf[layer]=num; } return layer;}int main(){ int root,l,num; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d %d",&root,&num); for(int j=0;j<num;j++){ scanf("%d",&l); table[root].push_back(l); } } int layer=BFS(1); for(int i=1;i<=layer;i++){ if(i==1) printf("%d",leaf[i]); else printf(" %d",leaf[i]); } system(“pause”); return 0;} ...

思路借鉴了之前的图的层数，发现这个贼好用；关键在于输出浮点数的格式，这个要注意一下#include<iostream>#include<stdlib.h>#include<stdio.h>#include<vector>#include<queue>#include<math.h>using namespace std;using std::vector;using std::queue;const int maxn=100010;struct node{ double data; vector<int>child; int layer=0;}Node[maxn];int n;double p,r;vector<int>leaf;void BFS(int x){ int layer=0; queue<int>q; q.push(x); while(!q.empty()){ layer++; int index; int length=q.size(); for(int i=0;i<length;i++){ index=q.front(); q.pop(); Node[index].layer=layer; for(int j=0;j<Node[index].child.size();j++){ q.push(Node[index].child[j]); } } }}int main(){ int num; scanf("%d%lf%lf",&n,&p,&r); for(int i=0;i<n;i++){ scanf("%d",&num); if(num==0){ scanf("%lf",&Node[i].data); leaf.push_back(i); }else{ for(int j=0;j<num;j++){ int child; scanf("%d",&child); Node[i].child.push_back(child); } } } BFS(0); double sum; for(int i=0;i<leaf.size();i++){ sum+=pow(1+r/100,Node[leaf[i]].layer-1)Node[leaf[i]].data; } printf("%.1f\n",sump); system(“pause”); return 0;}

并查集用多了。。。第一时间想到的是并查集却没有想到静态数组，这是一个比较大的失误；这道题的关键在于如下几个点：1.如何保存输入的树；2.如何寻找根节点；3.如何完成树的反转；1，2两点都很容易解决，可能比较难一点的是第三点；其实第三点也不难，我们观察一下就可以知道，树的反转本身就是在后序遍历的过程中对左右子树进行对换，就可以很轻松的得到反转后的树；总体代码如下所示：#include<stdio.h>#include<stdlib.h>#include<queue>#include<algorithm>using namespace std;const int maxn=110;struct node{ int lchild; int rchild;}Node[maxn];bool noRoot[maxn]={false};int n,num=0;void print(int id){ printf("%d",id); num++; if(num<n) printf(" “); else printf("\n”);}void inOrder(int root){ if(root==-1) return; inOrder(Node[root].lchild); print(root); inOrder(Node[root].rchild);}void postOrder(int root){ if(root==-1) return; postOrder(Node[root].lchild); postOrder(Node[root].rchild); swap(Node[root].lchild,Node[root].rchild);}void BFS(int root){ queue<int>q; q.push(root); while(!q.empty()){ int now=q.front(); q.pop(); print(now); if(Node[now].lchild!=-1) q.push(Node[now].lchild); if(Node[now].rchild!=-1) q.push(Node[now].rchild); }}int strTonum(char c){ if(c==’-’) return -1; else{ noRoot[c-‘0’]=true; return c-‘0’; }}int findRoot(){ for(int i=0;i<n;i++){ if(noRoot[i]==false){ return i; } }}int main(){ char lchild,rchild; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%*c%c %c",&lchild,&rchild); Node[i].lchild=strTonum(lchild); Node[i].rchild=strTonum(rchild); } int root=findRoot(); postOrder(root); BFS(root); num=0; inOrder(root); system(“pause”); return 0;} ...

和刚刚之前的那道题类似，只不过多考察了一个四大遍历输出中的一个；自己跟个智障一样检查了一个小时，结果发现少了一个返回指针，真是干他娘的；#include<iostream>#include<stdlib.h>#include<stdio.h>#include<stack>#include<cstring>#include<vector>using namespace std;using std::vector;const int maxn=40;int n;vector<int>pre;vector<int>in;stack<int>s;struct node{ int data; node* lchild; node* rchild;};node* create(int prel,int prer,int inl,int inr){ if(prel>prer) return NULL; node* root=new node; root->data=pre[prel]; int i; for(i=inl;i<=inr;i++){ if(in[i]==pre[prel]) break; } int lnum=i-inl; root->lchild=create(prel+1,prel+lnum,inl,i-1); root->rchild=create(prel+lnum+1,prer,i+1,inr); return root;}int num=0;void postorder(node* root){ if(root==NULL) return; postorder(root->lchild); postorder(root->rchild); printf("%d",root->data); num++; if(num<n) printf(" “);}int main(){ scanf("%d”,&n); char str[5]; int x; for(int i=0;i<2n;i++){ scanf("%s",str); if(strcmp(str,“Push”)==0){ scanf("%d",&x); pre.push_back(x); s.push(x); }else{ in.push_back(s.top()); s.pop(); } } node root=create(0,n-1,0,n-1); postorder(root); system(“pause”); return 0;} ...

上一篇：JS数据结构与算法_链表写在前面说明：JS数据结构与算法 系列文章的代码和示例均可在此找到一、集合Set1.1 集合数据结构集合set是一种包含不同元素的数据结构。集合中的元素成为成员。集合的两个最重要特性是：集合中的成员是无序的；集合中不允许相同成员存在计算机中的集合与数学中集合的概念相同，有一些概念我们必须知晓：不包含任何成员的集合称为空集；包含一切可能的成员为全集如果两个成员完全相同，则称为两个集合相等如果一个集合中所有的成员都属于另一个集合，则前一个集合被称为后一个集合的子集另外还有交集/并集/差集，下面会一一实现1.2 集合的实现一般集合包含下面几个方法：add 向集合添加一个新的项remove 从集合移除一个值has 如果值在集合中，返回true，否则返回falseclear 移除集合中的所有项size 返回集合所包含元素的数量。与数组的length属性类似values 返回一个包含集合中所有值的数组union 两个集合的并集intersection 两个集合的交集difference 两个集合的差集isSubsetOf 判断是否为子集下面将基于对象实现基础的集合（数组和队列也可实现集合，点击查看）class Set { constructor() { this._items = {}; this._length = 0; } // 添加成员时，如果已有成员则不操作。以[value: value]的形式存储在对象中 add(value) { if (this.has(value)) return false; this._items[value] = value; this._length += 1; return true; } // 移除成员时，如果没有对应成员则不操作 remove(value) { if (!this.has(value)) return false; delete this._items[value]; this._length -= 1; return true; } values() { return Object.values(this._items); } has(value) { return this._items.hasOwnProperty(value); } clear() { this._items = {}; this._length = 0; } size() { return this._length; } isEmpty() { return !this._length; }}（1）并集的实现将两个集合中的元素依次添加至新的集合中，并返回改集合// 并集union(otherSet) { const unionSet = new Set(); const values = this.values(); values.forEach(item => unionSet.add(item)); const otherValues = otherSet.values(); otherValues.forEach(item => unionSet.add(item)); return unionSet;}（2）交集的实现以集合A作为参考，遍历集合B依次对比成员，B中的成员存在A中则添加至新集合C中，最后返回C// 交集intersection(otherSet) { const intersectionSet = new Set(); const values = this.values(); values.forEach(item => { if (otherSet.has(item)) { intersectionSet.add(item); } }) return intersectionSet;}（3）差集的实现以集合A作为参考，遍历集合B依次对比成员，B中的成员不存在A中则添加至新集合C中，最后返回C// 差集difference(otherSet) { const differenceSet = new Set(); const values = this.values(); values.forEach(item => { if (!otherSet.has(item)) { differenceSet.add(item); } }) return differenceSet;}注意：A.difference(B)与B.difference(A)计算参考不同（4）子集的实现以集合A作为参考，遍历集合B依次对比成员，B中的所有成员均存在A中则为其子集，否则不是// 子集isSubsetOf(otherSet) { if (this.size() > otherSet.size()) return false; const values = this.values(); for (let i = 0; i < values.length; i += 1) { const item = values[i]; if (!otherSet.has(item)) return false; } return true;}1.3 ES6中的SetES6中提供了新的数据结构Set，它类似于数组，但是成员的值都是唯一的，没有重复的值提供了一下几个方法：add(value) 添加某个值，返回Set结构本身delete(value) 删除某个值，返回一个布尔值，表示删除是否成功has(value) 返回一个布尔值，表示该值是否为Set的成员clear() 清除所有成员，没有返回值size 属性，返回成员总数创建：直接通过数组创建：new Set([1,2,3,4])先实例再添加：const set = new Set(); set.add(1);遍历：keys() 返回键名的遍历器values() 返回键值的遍历器entries() 返回键值对的遍历器forEach()/for-of 使用回调函数遍历每个成员二、字典Dictionary2.1 字典数据结构集合表示一组互不相同的元素(不重复的元素)。在字典中，存储的是键-值对，其中键名是用来查询特定元素的。字典和集合很相似，集合以值-值对的形式存储元素，字典则是以键-值对的形式来存储元素。字典也称作映射类比：电话号码簿里的名字和电话号码。要找一个电话时，先找名字，名字找到了，紧挨着他的电话号码也就想找到了，这里的键是指你用来查找的东西，值时查找得到的结果2.2 字典的实现一般字典包括下面几种方法：set(key,value) 向字典中添加新元素remove(key) 通过使用键值来从字典中移除键值对应的数据值has(key) 如果某个键值存在于这个字典中，则返回true，反之则返回falseget(key) 通过键值查找特定的数值并返回clear() 将这个字典中的所有元素全部删除size() 返回字典所包含元素的数量。与数组的length属性类似keys() 将字典所包含的所有键名以数组形式返回values() 将字典所包含的所有数值以数组形式返回下面将基于对象实现基础的字典class Dictionary { constructor() { this._table = {}; this._length = 0; } set(key, value) { if (!this.has(key)) { this._length += 1; } this._table[key] = value; } has(key) { return this._table.hasOwnProperty(key); } remove(key) { if (this.has(key)) { delete this._table[key]; this._length -= 1; return true; } return false; } get(key) { return this._table[key]; } clear() { this._table = {}; this._length = 0; } size() { return this._length; } keys() { return Object.keys(this._table); } values() { return Object.values(this._table); }}这里添加成员时，并未考虑key为对象的情况，以至于会出现如下情况：const obj = {};obj[{a: 1}] = 1;obj[{a: 2}] = 2;console.log(obj[{a: 1}]); // 2// 对象形式的键会以其toSting方法的结果存储obj; // {[object Object]: 2}在ES6中支持key值为对象形式的字典数据结构Map，其提供的方法如下：提供了一下几个方法：set(key, value) set方法设置键名key对应的键值为value，然后返回整个Map结构get(key) get方法读取key对应的键值，如果找不到key，返回undefineddelete(value) 删除某个值，返回一个布尔值，表示删除是否成功has(value) 返回一个布尔值，表示该值是否为Map的成员clear() 清除所有成员，没有返回值size 属性，返回成员总数创建：直接通过数组创建：const map = new Map([ [’name’, ‘张三’], [’title’, ‘Author’] ]);先实例再添加：const map = new Map();遍历：keys() 返回键名的遍历器values() 返回键值的遍历器entries() 返回键值对的遍历器forEach()/for-of 使用回调函数遍历每个成员三、哈希表/散列表3.1 哈希表数据结构散列表也叫哈希表（HashTable也叫HashMap），是Dictionary类的一种散列表实现方式（1）哈希表有何特殊之处：数组的特点是寻址方便，插入和删除困难；而链表的特点是寻址困难，插入和删除方便。哈希表正是综合了两者的优点，实现了寻址方便，插入删除元素也方便的数据结构（2）哈希表实现原理哈希表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位下面是将key中每个字母的ASCII值之和作为数组的索引（哈希函数）的图例：（3）数组的长度为什么选择质数书中有如下说明：散列函数的选择依赖于键值的数据类型。如果键是整数，最简单的散列函数就是以数组的长度对键取余。在一些情况下，比如数组的长度为10，而键值都是10的倍数时，就不推荐使用这种方式了。这也是数组的长度为什么要是质数的原因之一。如果键是随机的整数，而散列函数应该更均匀地分布这些键，这种散列方式称为除留余数法3.2 哈希表的实现我们为哈希表实现下面几个方法：hashMethod 哈希函数，将字符串转换成索引put 添加键值get 由键获取值remove 移除键class HashTable { constructor() { this._table = []; } // 哈希函数【社区中实践较好的简单哈希函数】 hashMethod(key) { if (typeof key === ’number’) return key; let hash = 5381; for (let i = 0; i < key.length; i += 1) { hash = hash * 33 + key.charCodeAt(i); } return hash % 1013; } put(key, value) { const pos = this.hashMethod(key); this._table[pos] = value; } get(key) { const pos = this.hashMethod(key); return this._table[pos]; } remove(key) { const pos = this.hashMethod(key); delete this._table[pos]; } print() { this._table.forEach((item, index) => { if (item !== undefined) { console.log(index + ’ –> ’ + item); } }) }}当然了，一个简单的哈希函数，将不同的字符串转换成整数时，很有可能会出现多个不同字符串转换后对应同一个整数，这个就需要进行冲突的处理3.3 处理冲突的方法（1）分离链接分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突的最简单的方法，但是它在HashTable实例之外还需要额外的存储空间（2）线性探查当想向表中某个位置加入一个新元素的时候，如果索引 为index的位置已经被占据了，就尝试index+1的位置。如果index+1的位置也被占据了，就尝试 index+2的位置，以此类推四、bitMap算法4.1 bitMap数据结构bitMap数据结构常用于大量整型数据做去重和查询，《Bitmap算法》这篇文章中是基于Java语言及数据库优化进行解释的图文教程bitMap是利用了二进制来描述状态的一种数据结构，下面介绍其简单的原理：（1）思考下面的问题街边有8栈路灯，编号分别是1 2 3 4 5 6 7 8 ，其中2号，5号，7号，8号路灯是亮着的，其余的都处于不亮的状态，请你设计一种简单的方法来表示这8栈路灯亮与不亮的状态。路灯 1 2 3 4 5 6 7 8状态 0 1 0 0 1 0 1 1将状态转化为二进制parseInt(1001011, 2);结果为75。一个Number类型的值为32个字节，它可以表示32栈路灯的状态。这样在大数据量的处理中，bitMap就有很大的优势。（2）位运算介绍按位与&: 3&7=3【011 & 111 –> 011】按位或|: 3|7=7【011 | 111 –> 111】左位移<<: 1<<3=8【1 –> 1000】（3）实践一组数，内容以为 3,6,7,9，请用一个整数来表示这些四个数var value = 0;value = value | 1<<3; // 1000value = value | 1<<6; // 1001000value = value | 1<<7; // 11001000value = value | 1<<9; // 1011001000console.log(value); // 712这样，十进制数712的二进制形式对应的位数为1的值便为数组中的树值4.2 bitMap的实现通过上面的介绍，我们可以实现一个简单的bitMap类，有下面两个方法：addMember添加成员isExist成员是否存在分析：单个数值既能表示0~32的值，若以数组作为基础，bitMap能容纳的成员由数组长度决定64*数组长度addMember添加成员：数组/位数向下取整表示所在索引，数组/位数取余表示所在二进制的位数isExist成员是否存在：添加成员的反向计算我们先实现基础读写位的方法export const BIT_SIZE = 32;// 设置位的值export function setBit(bitMap, bit) { const arrIndex = Math.floor(bit / BIT_SIZE); const bitIndex = Math.floor(bit % BIT_SIZE); bitMap[arrIndex] |= (1 << bitIndex);}// 读取位的值export function getBit(bitMap, bit) { const arrIndex = Math.floor(bit / BIT_SIZE); const bitIndex = Math.floor(bit % BIT_SIZE); return bitMap[arrIndex] & (1 << bitIndex);}进而根据上面的方法得到下面的类class BitMap { constructor(size) { this._bitArr = Array.from({ length: size }, () => 0); } addMember(member) { setBit(this._bitArr, member); } isExist(member) { const isExist = getBit(this._bitArr, member); return Boolean(isExist); }}// 验证const bitMap = new BitMap(4);const arr = [0, 3, 5, 6, 9, 34, 23, 78, 99];for(var i = 0;i < arr.length;i++){ bitMap.addMember(arr[i]);}console.log(bitMap.isExist(3)); // trueconsole.log(bitMap.isExist(7)); // falseconsole.log(bitMap.isExist(78)); // true注意：这种结构也有其局限性数据集要求较为紧凑，[1, 1000000]这种结构空间利用过低，不利于发挥bitMap的优势仅对整数有效（当然，我们可以通过哈希函数将字符串转换为整型）4.3 bitMap的应用（1）大数据排序要求：有多达10亿无序整数，已知最大值为15亿，请对这个10亿个数进行排序分析：大数据的排序，传统的排序方式相对内存占用较大，使用bitMap仅占原内存的(JS中为1/64，Java中为1/32)实现：模拟大数据实现，如下（最大值为99）const arr = [0, 6, 88, 7, 73, 34, 10, 99, 22];const MAX_NUMBER = 99;const ret = [];const bitMap = new BitMap(4);arr.forEach(item => { bitMap.addMember(item); })for (let i = 0; i <= MAX_NUMBER; i += 1) { if (bitMap.isExist(i)) ret.push(i);}console.log(ret); // [ 0, 6, 7, 10, 22, 34, 73, 88, 99 ]（2）两个集合取交集要求：两个数组，内容分别为[1, 4, 6, 8, 9, 10, 15], [6, 14, 9, 2, 0, 7]，请用BitMap计算他们的交集分析：利用isExist()来筛选相同项实现：const arr1 = [1, 4, 6, 8, 9, 10, 15];const arr2 = [6, 14, 9, 2, 0, 7];const intersectionArr = []const bitMap = new BitMap();arr1.forEach(item => bitMap.addMember(item))arr2.forEach(item => { if (bitMap.isExist(item)) { intersectionArr.push(item); }})console.log(intersectionArr); // [6, 9]BitMap数据结构的用法原不止如此，我们可以通过哈希函数将字符串转换成整数，再进行处理。当然，我们应该始终牢记BitMap必须是相对较为紧密的数字，否则无法发挥BitMap的最大功效上一篇：JS数据结构与算法_链表 ...

前言数组是 JS 中最常用的数据结构，它可以在任意位置添加或删除数据。栈是另外一种数据结构，类似于数组，但是在添加或删除数据时更加灵活。栈数据结构栈是一种 后进先出（LIFO） 的数据结构。新添加或待删除的元素都保存在栈的一端，叫 栈顶 ，另一端就叫做 栈底 。在栈中，新元素都靠近栈顶，就元素都靠近栈底。创建栈可以用数组来模拟一个栈结构：function Stack() { let items = [] // 栈的属性和方法}需要实现的方法：push(element): 添加一个元素到栈顶pop(): 移除栈顶的元素，并返回该元素peek(): 仅仅返回栈顶的元素clear(): 清空栈size(): 返回栈中的元素的个数isEmpty(): 判断栈是否为空// 向栈中添加元素this.push = function (element) { items.push(element)}// 从栈中移除元素this.pop = function () { return items.pop()}// 查看栈顶元素this.peek = function () { return items[item.length - 1]}// 检查栈是否为空this.isEmpty = function () { return !!item.length}// 清空栈中的元素this.clear = function () { items = []}// 返回栈的大小this.size = function () { return items.length}// 打印栈this.print = function () { console.log(items.toString())}ES6 与 栈ES6 的写法：class Stack { constructor() { this.items = [] } push (element) { this.items.push(element) } // … 其他方法}ES6 的类是基于原型的，虽然基于原型的类比基于函数的类更节省内存，但是却不能声明私有变量，所以变量 items 是公共的。这种情况下，可以直接通过修改 items 来修改栈中的数据，这是无法避免的。用 ES6 的限定作用域 Symbol 实现类ES6 新增了 Symbol 基础类型，它是不可变的，也可以作用对象的属性。let _items = Symbol()class Stack { constructor() { this[_items] = [] } // … 其他方法}上面这个例子创建了一个假的私有属性，不能完全规避上面提到的问题，因为 ES6 新增的 Object.getOwnPropertySymbols 方法能够取到类里面声明的所有 Symbols 属性，比如：let stack = new Stack()stack.push(66)stack.push(88)let objectSymbols = Object.getOwnPropertySymbols(stack)console.log(objectSymbols.length) // 1console.log(objectSymbols[0]) // Symbol()stack[objectSymbols[0]].push(1)stack.print() // 66 88 1通过访问 stack[objectSymbols[0]] 是可以访问 _items 的，并且可以对 _items 进行任意操作。用 ES6 的WeakMap 实现类有一种数据类型可以确保属性是私有的，这就是 WeakMap 。WeakMap 可以存储键值对，其中键是对象，值可以是任意数据类型。const items = new WeakMap()class Stack { constructor() { items.set(this, []) } push(element) { let s = items.get(this) s.push(element) } pop() { let s = items.get(this) return s.pop() } // … 其他方法}现在，Stack 中的 items 是私有的了，但是 items 是在 Stack 类以外声明的，还是可以被改动，所以需要借助闭包来实现一层封装：let Stack = (function () { const items = new WeakMap() class Stack { constructor() { items.set(this, []) } // … 其他方法 return Stack}})()### 用栈解决实际问题 栈在 JS 中应用还是十分广泛的，比如 调用栈 。进制转换也是很常见的例子，可以用 栈 来处理，比如要把十进制转化成二进制，可以将该十进制数字和2整除，直到结果是 0 为止。function divideBy2 (decNumber) { var remStack = new Stack(), rem, binaryString = ’’ while (decNumber > 0) { rem = Math.floor(decNumber % 2) remStack.push(rem) decNumber = Math.floor(decNumber / 2) } while (!remStack.isEmpty()) { binaryString += remStack.pop().toString() } return binaryString}这个例子中，当结果满足和2做整除的条件是，会取得当前结果和2的余数，放到栈里，然后让结果继续和2做整除。#### 改进算法 把上面的例子改成十进制转成任意进制的：function baseConverter(decNumber, base) { var remStack = new Stack(), rem, binaryString = ‘’, digits = ‘0123456789ABCDEF’ while (decNumber > 0) { rem = Math.floor(decNumber % base) remStack.push(rem) decNumber = Math.floor(decNumber / base) } while (!remStack.isEmpty()) { binaryString += digits[remStack.pop()] } return binaryString} ...

栈的定义什么是栈？栈是一种遵循后进先出原则的有序集合，新添加的或者待删除的元素都保存在栈的同一端，称为栈顶，另一端称为栈底，在栈里，新元素靠近栈顶，旧元素靠近栈底，用个图来看大概这样式的：用一个更形象的例子来说明：上网的时候，每点击一个超链接，浏览器都会打开一个新的页面，并且压入到一个访问历史栈中，你可以不断的点击打开新的页面，但总是可以通过回退重新访问以前的页面，从浏览器的访问历史栈中弹出历史网页地址，从栈顶弹出，总是最新的最先弹出栈的创建首先创建一个类用来表示栈，接着声明一个数组用来保存栈里的元素：function Stack() { let items = [] // 方法声明}创建好栈之后，需要为栈声明一些方法，栈一般会包含以下几个方法：push(): 添加新元素到栈顶pop(): 移除栈顶的元素，同时返回被移除的元素peek(): 返回栈顶的元素，不对栈做任何修改isEmpty(): 如果栈里没有任何元素就返回true，否则返回falseclear(): 移除栈里的所有元素size(): 返回栈里的元素个数具体实现：function Stack() { let items = [] // 添加元素到栈顶，也就是栈的末尾 this.push = function (element) { items.push(element) } // 栈的后进先出原则，从栈顶出栈 this.pop = function () { return items.pop() } // 查看栈顶的元素，访问数组最后一个元素 this.peek = function () { return items[items.length - 1] } // 检查栈是否为空 this.isEmpty = function () { return items.length == 0 } // 返回栈的长度，栈的长度就是数组的长度 this.size = function () { return items.length } // 清空栈 this.clear = function () { items = [] } // 打印栈元素 this.print = function () { console.log(items.toString()) }}栈的使用现在我们来看如何使用栈：let stack = new Stack()stack.push(1)stack.push(2)stack.push(3)console.log(stack.peek()) // 3console.log(stack.isEmpty()) // falseconsole.log(stack.size()) // 3先向栈中加入三个元素1，2，3，接下来用一张图来看一下入栈的过程：入栈过程都是在栈顶依次入栈，接着调用peek方法返回栈顶元素3，isEmpty返回false，size返回栈的长度3，然后在继续调用pop来看看出栈的过程：stack.pop()stack.print() // 1,2出栈也是和入栈相同，都是从栈顶开始出栈，保证栈的后入先出原则es6声明Stack类上面创建了一个Stack函数来充当类，并且在里面声明了一个私有变量，但是在es6里面是有类的语法的，可以直接用es6新语法来声明，代码大概是这样事的：class Stack { constructor () { this.items = [] } push (element) { this.items.push(element) } pop () { return this.items.pop() } peek () { return this.items[items.length - 1] } isEmpty () { return this.items.length == 0 } size () { return this.items.length } clear () { this.items = [] } print () { console.log(this.items.toString()) }}let stack = new Stack()stack.push(1)console.log(stack.isEmpty())stack.print()看起来似乎不错，比之前要简单，关键是看起来更加合理，使用的是类的语法，调用也没有什么问题，但是如果这么执行呢？console.log(stack.items)会发现一个问题，在stack类外面可以直接访问类里面的属性，按照设计items应该是Stack类的私有属性才对，就像之前Stack函数里面的私有变量，是不能在外部访问的，如何才能将items变成私有属性呢？应该会有和我一样想法的人，使用闭包，在闭包里面里面定义私有属性，然后再将stack类返回回来，代码实现大概是这样的：let Stack = (function () { let items = new WeakMap() class Stack { constructor () { items.set(this, []) } push (element) { let s = items.get(this) s.push(element) } pop () { let s = items.get(this) return s.pop() } peek () { let s = items.get(this) return s[s.length - 1] } isEmpty () { let s = items.get(this) return s.length == 0 } size () { let s = items.get(this) return s.length } clear () { let s = items.get(this) s = [] } print () { let s = items.get(this) console.log(s.toString()) } } return Stack})()可能有人会问为什么这里要把items定义成一个WeakMap对象，先简单介绍一下WeakMap对象的用法，WeakMap对象是一对键/值对的集合，其键必须是对象，值可以是任意的，定义成WeakMap就是为了将items属性变成私有属性，在外部调用Stack对象的时候无法访问到items属性。栈的应用前面介绍了那么多栈相关的知识，最后也是介绍栈的应用场景的时候了，栈的实际应用非常广泛，例如用来存储访问过的任务或路径、撤销的操作。为了有一个更直观的应用了解，下面会介绍如何用来解决计算机中的进制转换问题，将10进制转换为其他进制数，可能不少人已经忘了如何进行进制转换了，下面先来看一个简单的10进制转2进制的过程:上面的图中展示将一个10进制8转化为2进制数的过程，接下来看看用栈是如何实现的：function conver(num, radix) { let stack = new Stack() let binaryString = ’’ let digits = ‘0123456789ABCDEF’ while (num > 0) { stack.push(num % radix) num = parseInt(num / radix) } while (!stack.isEmpty()) { binaryString += digits[stack.pop()] } console.log(binaryString)}conver(8, 2) // 1000总结这篇文章主要对栈做了简单介绍，动手实践了栈的实现，以及用栈实现了一个简单进制转换的功能。如果有错误或不严谨的地方，欢迎批评指正，如果喜欢，欢迎点赞。 ...

Python数据结构——另一个角度看Python(概述)Python 中绝大部分数据结构可以最终分解为三种类型: 标量(Scaler), 序列(Sequence), 映射(Mapping)。这表明了数据存储时所需要的基本单位, 其重要性如同欧式几何公理之于欧式空间。标量是指Python中数字的基本数据类型其可分为整数, 浮点数和布尔值。创建变量时, Python 不需要声明数据类型, x=3的数据类型是整数, 而x=3.3的数据类型是浮点数, 布尔值只有True和False两种值, 支持and, not, or三种运算。整数运算的结果永远是精确的, 而浮点数运算结果不一定是精确的。计算机的内存是有限的, 无法存储无限位的小数。Python的浮点数实际上是双精度浮点数, 即C语言的double类型。序列是Python中最为基础的内建类型其分为七种类型: 列表, 字符串, 元组, Unicode字符串, 字节数组, 缓冲区和xrange对象。常用的有: 列表(list), 字符串(string), 元组(tuple)。映射在Python的实现是数据结构字典(Dictionary)其作为第三种基本单位, 映射的灵活性使得它在多种场合都有广泛的应用和良好的可拓展性。集合(set)是独立于标量、序列和映射之外的特殊数据结构其支持数学理论的各种集合运算, 其存在使得用程序代码实现数学理论变得方便。

栈是一种限定仅在表尾进行插入和删除操作的线性表。栈的应用有很多，比如常见的递归，计算机表达式求值等。下面我们用栈来实现简易的四则运算计算器。列一下本文的思路:实现链栈的数据结构及其操作中缀表达式转后缀表达式后缀表达式求值1、首先, 先实现一个链栈。//定义栈的数据结构class Node{ public $symbol; public $next; public function __construct( $symbol, $next ) { $this->symbol = $symbol; $this->next = $next; }}//初始化栈,生成头结点function initStack( &$node ){ $node = new Node( ‘’, null );}//入栈function push( Node &$node, $symbol ){ $p = new Node( $symbol, null ); $p->next = $node->next; $node->next = $p;}//出栈function pop( Node &$node, &$symbol ){ if ( null == $node->next ) { echo “栈空\n”; return; } $q = $node->next; $symbol = $q->symbol; $node->next = $node->next->next; unset( $q );}2、其次, 利用第一步实现的链栈，将中缀表达式转为后缀表达式。//获取运算符的优先级function get_priority( $symbol ){ switch ( $symbol ) { case ‘(’: $priority = 3; break; case ‘’: case ‘/’: $priority = 2; break; case ‘+’: case ‘-’: $priority = 1; break; case ‘)’: $priority = 0; break; default: $priority = 0; break; } return $priority;}//栈顶依次出栈,如果遇到’(‘则停止function clear_stack( &$list ){ $res = ‘’; while ( null != $list->next ) { if ( ‘(’ != $list->next->symbol ) { pop( $list, $item ); $res .= $item; } else { pop( $list, $item ); return $res; } } return $res;}//中缀表达式转后缀表达式function middle_to_back( $middle_expression ){ initStack( $list ); $back_expression = ‘’; $length = strlen( $middle_expression ); for ( $i = 0; $i < $length; $i ++ ) { $symbol = $middle_expression[ $i ]; if ( ’ ’ != $symbol ) { if ( is_numeric( $symbol ) ) { //数字直接输出 $back_expression .= $symbol; } else {//非数字则比较优先级 $stack_top_priority = get_priority( null == $list->next ? ’’ : $list->next->symbol ); $current_symbol_priority = get_priority( $symbol ); if ( $current_symbol_priority > $stack_top_priority ) {//优先级比栈顶高则进栈 push( $list, $symbol ); } else { $output = clear_stack( $list ); $back_expression .= $output; if ( ‘)’ != $symbol ) { push( $list, $symbol ); } } } } } while ( null != $list->next ) {//将栈清空 pop( $list, $item ); $back_expression .= $item; } return $back_expression;}3、接下来, 我们利用第一步实现的链栈，和第二步得到的后缀表达式，计算最后的值。//是否是四则运算符号function is_arithmetic_symbol( $symbol ){ $arithmetic_symbols = array( ‘+’, ‘-’, ‘’, ‘/’ ); if ( in_array( $symbol, $arithmetic_symbols ) ) { return true; } else { return false; }}//计算后缀表达式的值function calculate( $expression ){ $stack = new Node( ‘’, null ); $length = strlen( $expression ); for ( $i = 0; $i < $length; $i ++ ) { if ( ’ ’ != $expression[ $i ] ) {//为空则跳过 if ( is_numeric( $expression[ $i ] ) ) { push( $stack, $expression[ $i ] ); } else if ( is_arithmetic_symbol( $expression[ $i ] ) ) { pop( $stack, $n1 ); pop( $stack, $n2 ); $res = get_result( $n2, $n1, $expression[ $i ] ); push( $stack, $res ); } else { echo “wrong symbol, exit”; exit(); } } } $value = $stack->next->symbol; return $value;}最后，我们测试一下所实现的计算器。function main(){ $back_expression = middle_to_back( ‘((1+2)*3-4) * 5’ ); $result = calculate( $back_expression ); echo “后缀表达式的值为: " . $back_expression, PHP_EOL; echo “result : " . $result, PHP_EOL;}main();得到的结果如下: 简易的计算器就实现啦！~~~（代码中有一些细节未做判断，希望读者理解。欢迎大家提出批评修改意见，感谢~） ...

本文由云+社区发表随着内容时代的来临，多媒体信息，特别是视频信息的分析和理解需求，如图像分类、图像打标签、视频处理等等，变得越发迫切。目前图像分类已经发展了多年，在一定条件下已经取得了很好的效果。本文因实际产品需求，主要探讨一下视频打标签的问题。查阅了部分资料，笔者拙见，打标签问题无论是文本、图像和视频，涉及到较多对内容的“理解”，目前没有解决得很好。主要原因有以下一些方面，标签具有多样性，有背景内容标签，细节内容标签，内容属性标签，风格标签等等；一些标签的样本的实际表现方式多种多样，样本的规律不明显则不利于模型学习；标签问题没有唯一的标准答案，也存在一定的主观性，不好评估的问题则更不利于模型学习。依然笔者拙见，视频打标签问题目前还没有很好的解决办法，也处于探索阶段。方法上主要有以下一些思路：可以从视频角度出发，可以从图像角度出发；可以利用caption生成的思路，可以转化为多分类问题。直接从视频角度出发，即从视频整体的角度出发，提取图像帧，甚至字幕或者语音信息，进一步处理得出视频标签的结果。Deep Learning YouTube Video Tags，这篇文章提出一个hybrid CNN-RNN结构，将视频的图像特征，以及利用LSTM模型对标签考虑标签相关性和依赖性的word embeddings，联合起来，网络结构如下图。Large-scale Video Classification with Convolutional Neural Networks提出了几种应用于视频分类的卷积神经网络结构，在网络中体现时空信息。single frame：就是把一帧帧的图像分别输入到CNN中去，和普通的处理图像的CNN没有区别；late fution：把相聚L的两帧图像分别输入到两个CNN中去，然后在最后一层连接到同一个full connect的softmax层上去；early fution：把连续L帧的图像叠在一起输入到一个CNN中去；slow fution：通过在时间和空间维度增加卷积层，从而提供更多的时空全局信息。如下图所示：另一方面，为了提高训练速度，这篇文章还提出Multiresolution CNNs，分别将截取中间部分的图像和缩放的图像作为网络的输入，如下图所示：这篇文章主要研究了卷积神经网络在大规模视频分类中的应用和表现。通过实验，文章总结网络细节对于卷积神经网络的效果并不非常敏感。但总的来说，slow fusion网络结构的效果更好。从图像角度出发，即从视频中提取一些帧，通过对帧图像的分析，进一步得出视频标签的结果。对图像的分析，也可以转化为图像打标签或者图像描述问题。Visual-Tex: Video Tagging using Frame Captions，先从视频中提取固定数量的帧，用训练好的image to caption模型对图像生成描述。然后将文本描述组合起来，提取文本特征并用分类方法进行分类，得到tag结果。这篇文章对生成的描述，对比了多种不同的特征和多种不同的分类方法。可见，图像打标签对视频打标签有较大的借鉴意义。另一种思路，CNN-RNN: A Unified Framework for Multi-label Image Classification可以看作将图像打标签问题转化为多分类问题。将卷积神经网络应用到多标签分类问题中的一个常用方法是转化为多个单标签的分类问题，利用ranking loss或者cross-entropy loss进行训练。但这种方法往往忽略了标签之间的联系或者标签之间语义重复的问题。这篇文章设计了CNN-RNN的网络结构里，并利用attention机制，更好地体现标签间的相关性、标签间的冗余信息、图像中的物体细节等。网络结构主要如下图所示，主要包括两个部分：CNN部分提取图像的语义表达，RNN部分主要获取图像和标签之间的关系和标签之间的依赖信息。针对空间部分短视频数据，笔者设计了一个简单的视频打标签的方案，并进行了实验。由于预处理和算法细节的很多进一步改进和完善工作还没有进行，在此只是提出一种思路和把实验结果简单地做个分享。方法介绍：整体思路：图片打标签 => 视频打标签也就是说，对视频提取帧，得到视频中的图片；然后对图片进行打标签；最后将视频中帧图片的标签进行整合，得到视频标签。1、从图片描述说起：图片描述典型框架：利用deep convolutional neural network来encode 输入图像，然后利用Long Short Term Memory(LSTM) RNN decoder来生成输出文本描述。2、在打标签任务中，我们把标签或类别组合，构造成“描述”:一级类别+二级类别+标签（重复的词语进行去重）3、利用预训练和强化学习，对训练样本图片和标签构造模型映射。《Self-critical Sequence Training for Image Captioning》网络模型有三种：fc model；topdown model；att2in model；模型细节见论文。一般地，给定输入图像和输出文本target，,模型训练的过程为最小化cross entropy loss（maximum-likelihood training objective）:利用self-critical policy gradient training algorithm：其中，是reward funtion通过根据每一个decoding time step的概率分布进行采样获得，是baseline output，通过最大化每一个decoding time step的概率分布输出获得，也就是a greedy search。论文里提到，利用CIDEr metric作为reward function，效果最好。 4、根据视频帧图片的标签，对视频打标签。具体有两种思路：记录视频提取的所有帧图片中每一个出现的标签，以及标签出现的次数（有多少帧图片被打上了这个标签）。按照出现次数排序。1.将帧图片的最多前n个标签，输出为视频标签。2.将帧图片中，出现次数大于阈值c的标签，，输出为视频标签。数据示例：其中1class表示一级类别，2class表示二级类别。实验结果示例：截取一些实验结果展示如下，其中output指模型输出的结果，reference指人工标定的参考结果。总的来说，游戏类视频的数据量最大，效果较好；但具体不同英雄的视频数据如果不平衡，也会影响算法结果。其他类型视频数据不算太稀疏的效果也不错，长尾视频的效果不行。总结：数据预处理、模型结构、损失函数、优化方法等各方面，都还有很多值得根据视频打标签应用的实际情况进行调整的地方。后续再不断优化。方法和实验都还粗糙，希望大家多批评指导。此文已由作者授权腾讯云+社区在各渠道发布获取更多新鲜技术干货，可以关注我们腾讯云技术社区-云加社区官方号及知乎机构号 ...

介绍Android提供了SparseArray，这也是一种KV形式的数据结构，提供了类似于Map的功能。但是实现方法却和HashMap不一样。它与Map相比，可以说是各有千秋。优点占用内存空间小，没有额外的Entry对象没有Auto-Boxing缺点不支持任意类型的Key，只支持数字类型（int，long）数据条数特别多的时候，效率会低于HashMap，因为它是基于二分查找去找数据的相关参考 SparseArray vs HashMap总的来说，SparseArray适用于数据量不是很大，同时Key又是数字类型的场景。比如，存储某月中每天的某种数据，最多也只有31个，同时它的key也是数字（可以使用1-31，也可以使用时间戳）。再比如，你想要存储userid与用户数据的映射，就可以使用这个来存储。接下来，我将讲解它的特性与实现细节。直观的认知它使用的是两个数组来存储数据，一个数组存储key，另一个数组来存储value。随着我们不断的增加删除数据，它在内存中是怎么样的呢？我们需要有一个直观的认识，能帮助我们更好的理解和体会它。初始化的状态内部有两个数组变量来存储对应的数据，mKeys用来存储key，mValues用来存储泛型数据，注意，这里使用了Object[]来存储泛型数据，而不是T[]。为什么呢？这个后面在讲。插入数据如下图所示，插入数据，总是“紧贴”数组的左侧，换句话说，总是从最左边的一个空位开始使用。我一开始没详细探究的时候，都以为它是类似HashMap那样稀疏的存储。另一个值得注意的事情是，key总是有序的，不管经过多少次插入，key数组中，key总是从小到大排列。扩容当一直插入数据，快满的时候，就会自动的扩容，创建一个更大的数组出来，将现有的数据全部复制过去，再插入新的数据。这是基于数组实现的数据结构共同的特性。删除删除是使用标记删除的方法，直接将目标位置的有效元素设置为一个DELETED标记对象。查询数据怎么查数据呢？比如我们查5这个数据get(5)，那么它是在mKeys中去查找是否存在5，如果存在，返回index，然后用这个index在对应的mValues取出对应的值就好了。实现接下来我们按照自己的理解，来实现这样的一个数据结构，从而学习它的一些细节和思想，加深对它的理解，有利于在生产中，能更有效的，正确的使用它。确定接口（API）首先，确定一下，我们需要暴露什么样的功能给别人使用。当然了，答案是显而易见的，当然是插入，查询，删除等功能了。public class SparseArray<E> { public SparseArray() { } public SparseArray(int initCap) { } public void put(int key, E value) { } public E get(int key) { } public void delete(int key) { } public int size() { } }上面列举了我们需要的功能，无参构造函数，有参数构造函数（期望能主动设置初始容量），put数据，get数据，删除数据，以及获取当前数据有多少。实现put方法put数据是最核心的方法，一般我们开发一个东西，也是先开发创建数据的功能，这样才能接着开发展示数据的功能。所以我们先来实现put方法。按照之前的理解，我们需要一些成员变量来存储数据。private int[] mKeys;private Object[] mValues;private int mSize = 0;需要先找到put到什么位置这里会有两种情况：我要put的key不存在，应该put到什么地方？我要put的key已经存在，直接覆盖因此第一步，需要先找一下，当前key，是否存在。我们使用二分查找来处理。public void put(int key, E value) { int i = BinarySearch.search(mKeys, mSize, key); if (i >= 0) { // 找到了有两种情况 // 1.是对应的mValues有一个有效的数据对象，直接覆盖 // 2.对应的mValues里面是一个DELETED对象，同样的，直接覆盖 mValues[i] = value; } else { }}如果在数组中找到了，那么操作就很简单，直接覆盖就完事了。如果没找到呢，我们需要将数据插入到正确的位置上，这个所谓正确的位置，指的是，插入之后，依然保证数组有序的情况。打个比方：1, 4, 5, 8，请问3应该插入哪里，当然是放到index=1的地方，结果就是1, 3, 4, 5, 8了。那如果key不存在，怎么知道应该放到哪里呢？我们来看一下这个二分查找，它帮我们解决了这个小问题。public static int search(int[] arr, int size, int target) { int lo = 0; int hi = size - 1; while (lo <= hi) { final int mid = (lo + hi) >>> 1; final int value = arr[mid]; if (value == target) { return mid; } else if (value > target) { hi = mid - 1; } else { lo = mid + 1; } } return lo;}按照传统的思想，查找类的API，如果找不到，一般都会返回-1，但是这个二分查找，返回了lo的取反。这会达到什么效果呢。情况1：数组是空的，那么查找任何东西，都找不到，那会怎么样？根据代码可以知道，循环都进不去，那么直接返回了0，也就是最大的负数。我们只需要知道它是一个负数。情况2：数组不是空的，比如1, 3, 5，我们找2，这里简单的单步执行一下：lo = 0, size = 3, hi = 2, 好，进入循环mid = (0 + 2) / 2 = 1, value = 3value > 2, 所以 hi = 1 - 1 = 0, 再次循环mid = (0 + 0) / 2 = 0, value = 1value < 2, so, lo = 0 + 1; 退出循环返回~1如果你在尝试去验算其他情况，你会发现，返回值刚好是它应该放置的位置的取反。换句话说，返回值再取反后，就可以得到，这个key应该插入的位置。这应该是二分查找的一个小技巧。非常的实用！接下来，想一想，0取反是负数，任何正数取反，也都是负数，也就是说，只要是负数，就代表没找到，再将这个数取反，就得到了，应该put的位置！所以，代码继续实现为：public void put(int key, E value) { int i = BinarySearch.search(mKeys, mSize, key); if (i >= 0) { // 找到了有两种情况 // 1.是对应的mValues有一个有效的数据对象，直接覆盖 // 2.对应的mValues里面是一个DELETED对象，同样的，直接覆盖 mValues[i] = value; } else { i = ~i; mKeys = GrowingArrayUtil.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtil.insert(mValues, mSize, i, value); mSize++; }}实现get方法接下来，我们实现get方法。get方法实现就比较简单了，只需要通过二分查找找到对应的index，再从value数组中取出对象即可。public E get(int key) { // 首先查找这个key存不存在 int i = BinarySearch.search(mKeys, mSize, key); if (i < 0) { return null; } else { return (E)mValues[i]; }}实现delete方法delete方法，就是删除某个key，对应的细节是，找到这个key是否存在，如果存在的话，将value数组中对应位置的数据设置为一个常量DELETED。这样做的好处就是比较快捷，而不需要真正的去删除元素。当然由于这个DELETED对象存在value数组中，对put和get以及size方法都会带来一些影响。下面的代码，定义一个静态的final变量DELETED用来作为标记已经删除的变量。另一个成员变量标记，当前value数组中是否有删除元素这个状态信息。private static final Object DELETED = new Object();/** * 标记是否有DELETED元素标记 * /private boolean mHasDELETED = false;public void delete(int key) { // 删除的时候为标记删除，先要找到是否有这个key，如果没有，就没必要删除了； // 找到了key看一下对应的value是否已经是DELETED，如果是的话，也没必要再删除了 int i = BinarySearch.search(mKeys, mSize, key); if (i >= 0 && mValues[i] != DELETED) { mValues[i] = DELETED; mHasDELETED = true; }}实现size方法size方法返回在这个容器中，数据对象有多少个。由于DELETED对象的存在，key数组和value数组，以及成员变量mSize都没法靠谱得直接得到有效数据的count。因此这里需要一个内部的工具方法gc()，它的作用就是，如果有DELETED对象存在，那么就重新整理一下数组，将DELETED对象都移除，数组中只保留有效数据即可。先来看gc的实现private void gc() { int placeHere = 0; for (int i = 0; i < mSize; i++) { Object obj = mValues[i]; if (obj != DELETED) { if (i != placeHere) { mKeys[placeHere] = mKeys[i]; mValues[placeHere] = obj; mValues[i] = null; } placeHere++; } } mHasDELETED = false; mSize = placeHere;}它的内部逻辑很简单，就是从头到尾遍历value数组，把每一个不是DELETED的对象都重新放置一遍，覆盖掉前面的DELETED对象。然后，我们再看一下size的实现public int size() { if (mHasDELETED) { gc(); } return mSize;}完善get方法假设有这样的一个场景，put(1, a), put(2, b), delete(2), get(2)。按照现在的get实现，就会返回DELETED对象出去，所以，由于DELETED的存在，我们需要完善一下get方法的逻辑。public E get(int key) { // 首先查找这个key存不存在 int i = BinarySearch.search(mKeys, mSize, key); // 这里有两种情况 // 如果key小于0，说明在mKeys中，没有目标key，没找到 // 如果key大于0，还要看一下，对应的mValues中，是否那个元素是DELETED，因为删除的时候是标记删除的 // 以上两种情况都是没有找到 if (i < 0 || mValues[i] == DELETED) { return null; } else { return (E)mValues[i]; }}完善put方法补充的代码上面我都写了注释，讲解了这两坨额外的代码是用来处理什么情况的。public void put(int key, E value) { int i = BinarySearch.search(mKeys, mSize, key); if (i >= 0) { // 找到了有两种情况 // 1.是对应的mValues有一个有效的数据对象，直接覆盖 // 2.对应的mValues里面是一个DELETED对象，同样的，直接覆盖 mValues[i] = value; } else { i = ~i; // 这一段代码是处理这一的场景的 // 1 2 3 5, delete 5, put 4 if (i < mSize && mValues[i] == DELETED) { mKeys[i] = key; mValues[i] = value; return; } // 另一种情况 // 如果有删除的元素，并且数组装满了，这个时候需要先GC，再重新搜一下key的位置 if (mHasDELETED && mSize >= mKeys.length) { gc(); i = ~BinarySearch.search(mKeys, mSize, key); } mKeys = GrowingArrayUtil.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtil.insert(mValues, mSize, i, value); mSize++; }}最后，GrowingArrayUtil.insert是做了什么？其实说起来很简单，用一个过程来概括一下一般情况。[1, 2, 3, 4, 5, 0, 0, 0, 0, 0]insert(index=2, value=99)1.复制index=2以前的元素 [1, 2, 3, 4, 5, 0, 0, 0, 0, 0]2.复制index=2以后的元素，往后挪一位 [1, 2, 3, 3, 4, 5, 0, 0, 0, 0]3.将index=2的位置，放入99 [1, 2, 99, 3, 4, 5, 0, 0, 0, 0]当然，这里要处理，如果刚好数据满了，插入新数据，就需要创建一个新的，更大的数组来复制以前的数据了。/* * @param rawArr 原始数组 * @param size 有效数据的长度，与数组长度不一样，如果数组长度大于有效数据的长度，那么往里面插入数据是OK的 * 如果有效数据的长度等于数组的长度，那么要插入数据，就要创建更大的数组 * @param insertIndex 插入index * @param insertValue 插入到index的数值 * */public static int[] insert(int[] rawArr, int size, int insertIndex, int insertValue) { if (size < rawArr.length) { System.arraycopy(rawArr, insertIndex, rawArr, insertIndex + 1, size - insertIndex); rawArr[insertIndex] = insertValue; return rawArr; } int[] newArr = new int[rawArr.length * 2]; System.arraycopy(rawArr, 0, newArr, 0, insertIndex); newArr[insertIndex] = insertValue; System.arraycopy(rawArr, insertIndex, newArr, insertIndex + 1, size - insertIndex); return newArr;}public static <T> Object[] insert(Object[] rawArr, int size, int insertIndex, T insertValue) { if (size < rawArr.length) { System.arraycopy(rawArr, insertIndex, rawArr, insertIndex + 1, size - insertIndex); rawArr[insertIndex] = insertValue; return rawArr; } Object[] newArr = new Object[rawArr.length * 2]; System.arraycopy(rawArr, 0, newArr, 0, insertIndex); newArr[insertIndex] = insertValue; System.arraycopy(rawArr, insertIndex, newArr, insertIndex + 1, size - insertIndex); return newArr;}好了，关于SparseArray的讲解就到这里结束了。完整的源码可以查看我写的，也可以查看官方的。之前提到的一些疑问点为什么用Object[]，而不是T[]我的理解是，如果使用泛型数组T[]，你就必须构造出一个泛型数组，那么构造泛型数组，你需要能创建泛型对象，也就是说，必须调用T的构造函数才能创建泛型对象，但是由于是泛型，构造函数是不确定的，只能通过反射的形式来调用，这样显然就效率和稳定性上有一些问题。因此大多数泛型的实现，都是通过Object对象来存储泛型数据。如果你觉得这篇内容对你有帮助的话，不妨打赏一下，哪怕是小小的一份支持与鼓励，也会给我带来巨大的动力，谢谢:) ...

【算法日积月累】1-选择排序[TOC]“算法”的入门，从“排序算法”开始，希望通过“排序算法”这一部分的学习，能够让我们认识到“算法”的威力，“算法”不仅仅只存在与我们的面试中（那时只是因为我不知道“算法”而已），“算法”无处不在，“算法”很有用。下面是一些说明：1、会直接使用“空间复杂度”和“时间复杂度”的概念，不妨先有个印象，实在纠结的话，可以去翻翻书，“空间复杂度”和“时间复杂度”最多的应用就在于比较不同算法的优劣；2、“排序算法”这一章节为了方便说明，使用的例子都是以“整数数组”为例，并且是“升序排序”，学习过 Java 语言的朋友就知道，待排序的也可以是对象，只要实现了相关的接口，实现了相应的比较规则，就可以进行排序。我们选择“选择排序”作为算法入门的开篇。理由如下：1、“选择排序”算法的思想十分简单，非常接近我们的思维方式：先找最小的数、再找第 2 小的数，依次类推，最后剩下的就是数组中最大的元素；2、“选择排序”的实现也很简单。通过具体例子理解“选择排序”的思想思想：不断地选择剩余元素之中的最小者。“选择排序”算法的特点1、每一轮交换都能排定一个元素，交换的总次数是固定的；说明：“交换的总次数”等于“元素的总数 - 1”，因此算法的时间复杂度取决于比较的次数；2、运行时间和输入无关，即：一个“已经有序”的数组、一个所有的元素都相等的数组、一个元素随机排列的数组所用的排序时间是一样的；说明：后续我们会编写一些测试用例，比较不同的算法在不同的测试用例上的运行时间。这些测试用例中，就有以下 $3$ 种。（1）一个“已经有序”的数组：例如：[4, 5, 6, 8, 9, 10]，以后我们学习的排序算法中，就有一种算法名叫“插入排序”就能检测出数组是不是有序的，极端情况下，“插入排序”算法看一遍数组中的元素，就知道数组已经有序了，后续就什么都不用做了。而“选择排序”得一遍又一遍看数组的元素好几遍，“几乎是”有多少个数，就会看数组多少遍，每一遍选出当前没有排定元素中的最小者；（2）一个所有的元素都相等的数组，例如：[6, 6, 6, 6, 6, 6]；（3）一个元素随机排列的数组，就是我们一般意义下，杂乱无序的数组，例如：[8, 18, 10, 6, 5, 4, 20]。3、数据移动是最少的。这点应该说是“选择排序”的优点了，如果我们的排序任务对交换操作非常敏感，不妨考虑“选择排序”。例如：我们待排序的是码头上的集装箱，交换集装箱的成本是很高的，此时“选择排序”就是最好的选择。小贴士：这一部分内容不需要记住，等到后面接触了“插入排序”、“归并排序”、“快速排序”等其它排序算法以后，再与“选择排序”进行比较，就不难理解了。“选择排序”算法实现Python 实现1：def swap(nums, idx1, idx2): if idx1 == idx2: return temp = nums[idx1] nums[idx1] = nums[idx2] nums[idx2] = tempdef select_sort(nums): """ 选择排序，记录最小元素的索引，最后才交换位置 :param nums: :return: """ l = len(nums) for i in range(l): min_index = i for j in range(i + 1, l): if nums[j] < nums[min_index]: min_index = j swap(nums, i, min_index)说明：交换两个数组中的元素，在 Python 中有更简单的写法，这是 Python 的语法糖，其它语言中是没有的。Python 实现2：主体部分和“Python 实现1”是一样的。def select_sort(nums): """ 选择排序，记录最小元素的索引，最后才交换位置 :param nums: :return: """ l = len(nums) for i in range(l): min_index = i for j in range(i + 1, l): if nums[j] < nums[min_index]: min_index = j nums[i], nums[min_index] = nums[min_index], nums[i]这就是“选择排序”算法。如果你看到自己编写的程序不正确，可以在程序中增加打印输出，帮助你调试程序：时间复杂度与空间复杂度时间复杂度：$O(n^2)$分析：第 1 轮要看 $n$ 个元素；第 2 轮要看 $n-1$ 个元素；第 3 轮要看 $n-2$ 个元素；……第 $n$ 轮要看 $1$ 个元素；对它们求和，用等差数列的通项公式。不过其实你也不用计算它，“时间复杂度”的计算我们只看次数最高的，所以“选择排序”是平方时间复杂度。空间复杂度：$O(1)$分析：我们在交换两个数组元素位置的时候，使用了 $1$ 个辅助的空间。热身练习是不是觉得很简单，后面难度会一点一点加上来。此时，我们不妨做一些热身的练习，我们后面会用到。这些练习只是减轻一点我们后面编写测试用例的工作量，自己设计函数参数就好。练习1：编写三个函数，分别生成上文中提到的 $3$ 种类型的数组，要求能够自定义生成数组的大小，这样我们以后编写测试用例的时候，就可以使用这些函数了。练习2：编写一个函数，判断一个数组是否是升序排序。这个函数用于判断我们的算法是否正确。补充知识以下补充的知识是针对零基础的朋友们的，因为我也是零基础过来的，觉得这些东西可以说一下。1、交换两个变量的值交换两个变量的值，在排序中是常见的操作，并且也是程式化的，特别好记。先给出 Java 的写法，再给出 Python 的写法，最后给出“不是人的写法”。Java 写法：int temp = a;a = b;b = temp;说明：这段代码其实很好理解，要交换两个变量的值，给要让变量 a 把位置让出来，即 int temp = a，然后把另一个变量 b 的值复制给 a，即 a = b，最后把之前 a 放在 temp 里的值赋给 b。这么说比较拗口，但其实我每次写这段代码的时候，都不用想这个过程的。因为这段代码有规律可循：首先引入一个辅助变量 temp，这是必要的，然后就开始“首尾相接”了，你们看一下，是不是这个特点，最后接回 temp，记住这个规律就可以了。在 Python 中是这样写的：Python 写法1：temp = aa = bb = temp不过，Python 是一门神奇的编程语言，它提供了语法糖。使用 Python 语法糖交换两个变量的值a, b = b, a就可以交换两个变量的值，不妨动手验证一下：是不是很酷，Python 的写法有的时候更像伪代码，更符合人的思维，但我没有说 Python 更好的意思。其实 Python 解释器在后台也是引入了辅助变量完成两个变量的交换。其实，交换两个变量的值，有更高效的做法，下面给出两个交换变量的代码，这两种方法都不用引入辅助变量，相信聪明的你一定不难理解。基于加减法交换两个变量的值基于异或运算交换两个变量的值这里利用到了异或运算的特点：异或运算可以理解成不进位的加法。那么一个数两次异或同一个数，就和原来的数相等。上面基于异或运算交换两个变量的值就利用这个性质。如果你还不熟悉异或运算，不妨查阅一些资料。2、Java 和 Python 语言中比较器的实现前面我们说到了，我们为了突出排序算法的思想，将所有的例子仅限在数组排序中。事实上 Java 和 Python 这些面向对象的编程语言都支持对象的排序，只要给它们定义相应的比较规则即可。有两种方式，Python 和 Java 都是支持的：（1）为对象添加用于比较的函数在 Python 中，有一个魔法函数，实现它即可：def cmp(self, other): pass定义这个魔法函数，就可以使用对象集合进行排序了。在 Java 中，实现 Comparable 接口中的 compareTo 方法。如果你觉得给对象添加用于比较的函数，这种做法的侵入性比较强（因为修改了类），那么你可以在排序的方法中，传入比较规则。（2）在排序的方法中，传入比较规则在 Python 中，比较规则可以通过 lambda 表达式传入：在 Java 中，可以传入一个实现了 Comparator 接口的对象。 ...

写在前面原计划是把《你不知道的Javascript》三部全部看完的，偶然间朋友推荐了数据结构与算法的一套入门视频，学之。发现数据结构并没有想象中那么遥不可及，反而发觉挺有意思的。手头上恰好有《学习Javascript数据结构与算法》的书籍，便转而先把数据结构与算法学习。一、认识数据结构什么是数据结构？下面是维基百科的解释数据结构是计算机存储、组织数据的方式数据结构意味着接口或封装：一个数据结构可被视为两个函数之间的接口，或者是由数据类型联合组成的存储内容的访问方法封装我们每天的编码中都会用到数据结构，因为数组是最简单的内存数据结构，下面是常见的数据结构数组（Array）栈（Stack）队列（Queue）链表（Linked List）树（Tree）图（Graph）堆（Heap）散列表（Hash）下面来学习学习栈和队列..二、栈2.1 栈数据结构栈是一种遵循后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都接近栈顶，旧元素都接近栈底。类比生活中的物件：一摞书????或者推放在一起的盘子2.2 栈的实现普通的栈常用的有以下几个方法：push 添加一个（或几个）新元素到栈顶pop 溢出栈顶元素，同时返回被移除的元素peek 返回栈顶元素，不对栈做修改isEmpty 栈内无元素返回true，否则返回falsesize 返回栈内元素个数clear 清空栈class Stack { constructor() { this._items = []; // 储存数据 } // 向栈内压入一个元素 push(item) { this._items.push(item); } // 把栈顶元素弹出 pop() { return this._items.pop(); } // 返回栈顶元素 peek() { return this._items[this._items.length - 1]; } // 判断栈是否为空 isEmpty() { return !this._items.length; } // 栈元素个数 size() { return this._items.length; } // 清空栈 clear() { this.items = []; }}现在再回头想想数据结构里面的栈是什么。突然发现并没有那么神奇，仅仅只是对原有数据进行了一次封装而已。而封装的结果是：并不去关心其内部的元素是什么，只是去操作栈顶元素，这样的话，在编码中会更可控一些。2.3 栈的应用（1）十进制转任意进制要求: 给定一个函数，输入目标数值和进制基数，输出对应的进制数（最大为16进制）baseConverter(10, 2) ==> 1010baseConverter(30, 16) ==> 1E分析: 进制转换的本质：将目标值一次一次除以进制基数，得到的取整值为新目标值，记录下余数，直到目标值小于0，最后将余数逆序组合即可。利用栈，记录余数入栈，组合时出栈// 进制转换function baseConverter(delNumber, base) { const stack = new Stack(); let rem = null; let ret = []; // 十六进制中需要依次对应AF const digits = ‘0123456789ABCDEF’; while (delNumber > 0) { rem = Math.floor(delNumber % base); stack.push(rem); delNumber = Math.floor(delNumber / base); } while (!stack.isEmpty()) { ret.push(digits[stack.pop()]); } return ret.join(’’);}console.log(baseConverter(100345, 2)); //输出11000011111111001console.log(baseConverter(100345, 8)); //输出303771console.log(baseConverter(100345, 16)); //输出187F9（2）逆波兰表达式计算要求: 逆波兰表达式，也叫后缀表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式，例如(a+b)(c+d)转换为a b + c d + [“4”, “13”, “5”, “/”, “+”] ==> (4 + (13 / 5)) = 6[“10”, “6”, “9”, “3”, “+”, “-11”, “”, “/”, “”, “17”, “+”, “5”, “+”]==> ((10 * (6 / ((9 + 3) * -11))) + 17) + 5分析: 以符号为触发节点，一旦遇到符号，就将符号前两个元素按照该符号运算，并将新的结果入栈，直到栈内仅一个元素function isOperator(str) { return [’+’, ‘-’, ‘*’, ‘/’].includes(str);}// 逆波兰表达式计算function clacExp(exp) { const stack = new Stack(); for (let i = 0; i < exp.length; i++) { const one = exp[i]; if (isOperator(one)) { const operatNum1 = stack.pop(); const operatNum2 = stack.pop(); const expStr = ${operatNum2}${one}${operatNum1}; const res = eval(expStr); stack.push(res); } else { stack.push(one); } } return stack.peek();}console.log(clacExp([“4”, “13”, “5”, “/”, “+”])); // 6.6（3）利用普通栈实现一个有min方法的栈思路: 使用两个栈来存储数据，其中一个命名为dataStack，专门用来存储数据，另一个命名为minStack，专门用来存储栈里最小的数据。始终保持两个栈中的元素个数相同，压栈时判别压入的元素与minStack栈顶元素比较大小，如果比栈顶元素小，则直接入栈，否则复制栈顶元素入栈；弹出栈顶时，两者均弹出即可。这样minStack的栈顶元素始终为最小值。class MinStack { constructor() { this._dataStack = new Stack(); this._minStack = new Stack(); } push(item) { this._dataStack.push(item); // 为空或入栈元素小于栈顶元素，直接压入该元素 if (this._minStack.isEmpty() || this._minStack.peek() > item) { this._minStack.push(item); } else { this._minStack.push(this._minStack.peek()); } } pop() { this._dataStack.pop(); return this._minStack.pop(); } min() { return this._minStack.peek(); }}const minstack = new MinStack();minstack.push(3);minstack.push(4);minstack.push(8);console.log(minstack.min()); // 3minstack.push(2);console.log(minstack.min()); // 2三、队列3.1 队列数据结构队列是遵循先进先出（FIFO，也称为先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾类比：日常生活中的购物排队3.2 队列的实现普通的队列常用的有以下几个方法：enqueue 向队列尾部添加一个(或多个)新的项dequeue 移除队列的第一(即排在队列最前面的)项，并返回被移除的元素head 返回队列第一个元素，队列不做任何变动tail 返回队列最后一个元素，队列不做任何变动isEmpty 队列内无元素返回true，否则返回falsesize 返回队列内元素个数clear 清空队列class Queue { constructor() { this._items = []; } enqueue(item) { this._items.push(item); } dequeue() { return this._items.shift(); } head() { return this._items[0]; } tail() { return this._items[this._items.length - 1]; } isEmpty() { return !this._items.length; } size() { return this._items.length; } clear() { this._items = []; }}与栈类比，栈仅能操作其头部，队列则首尾均能操作，但仅能在头部出尾部进。当然，也印证了上面的话：栈和队列并不关心其内部元素细节，也无法直接操作非首尾元素。3.3 队列的应用（1）约瑟夫环（普通模式）要求: 有一个数组a[100]存放099；要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数。分析: 按数组创建队列，依次判断元素是否满足为指定位置的数，如果不是则enqueue到尾部，否则忽略，当仅有一个元素时便输出// 创建一个长度为100的数组const arr_100 = Array.from({ length: 100 }, (, i) => i*i);function delRing(list) { const queue = new Queue(); list.forEach(e => { queue.enqueue(e); }); let index = 0; while (queue.size() !== 1) { const item = queue.dequeue(); index += 1; if (index % 3 !== 0) { queue.enqueue(item); } } return queue.tail();}console.log(delRing(arr_100)); // 8100 此时index=297（2）菲波那切数列（普通模式）要求: 使用队列计算斐波那契数列的第n项分析: 斐波那契数列的前两项固定为1，后面的项为前两项之和，依次向后，这便是斐波那契数列。function fibonacci(n) { const queue = new Queue(); queue.enqueue(1); queue.enqueue(1); let index = 0; while(index < n - 2) { index += 1; // 出队列一个元素 const delItem = queue.dequeue(); // 获取头部值 const headItem = queue.head(); const nextItem = delItem + headItem; queue.enqueue(nextItem); } return queue.tail();}console.log(fibonacci(9)); // 34（3）用队列实现一个栈要求: 用两个队列实现一个栈分析: 使用队列实现栈最主要的是在队列中找到栈顶元素并对其操作。具体的思路如下：两个队列，一个备份队列emptyQueue，一个是数据队列dataQueue；在确认栈顶时，依次dequeue至备份队列，置换备份队列和数据队列的引用即可class QueueStack { constructor() { this.queue_1 = new Queue(); this.queue_2 = new Queue(); this._dataQueue = null; // 放数据的队列 this._emptyQueue = null; // 空队列,备份使用 } // 确认哪个队列放数据,哪个队列做备份空队列 _initQueue() { if (this.queue_1.isEmpty() && this.queue_2.isEmpty()) { this._dataQueue = this.queue_1; this._emptyQueue = this.queue_2; } else if (this.queue_1.isEmpty()) { this._dataQueue = this.queue_2; this._emptyQueue = this.queue_1; } else { this._dataQueue = this.queue_1; this._emptyQueue = this.queue_2; } }; push(item) { this.init_queue(); this._dataQueue.enqueue(item); }; peek() { this.init_queue(); return this._dataQueue.tail(); } pop() { this.init_queue(); while (this._dataQueue.size() > 1) { this._emptyQueue.enqueue(this._dataQueue.dequeue()); } return this._dataQueue.dequeue(); };};学习了栈和队列这类简单的数据结构，我们会发现。数据结构并没有之前想象中那么神秘，它们只是规定了这类数据结构的操作方式：栈只能对栈顶进行操作，队列只能在尾部添加在头部弹出；且它们不关心内部的元素状态。个人认为，学习数据结构是为了提高我们通过代码建模的能力，这也是任何一门编程语言都通用的知识体系，优秀编码者必学之。 ...

题目用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。基本思路栈1:用于入队列存储栈2:出队列时将栈1的数据依次出栈，并入栈到栈2中栈2出栈即栈1的底部数据即队列要出的数据。注意:栈2为空才能补充栈1的数据，否则会打乱当前的顺序。代码const stack1 = [];const stack2 = [];function push(node){ stack1.push(node);}function pop(){ if(stack2.length === 0){ while(stack1.length>0){ stack2.push(stack1.pop()); } } return stack2.pop() || null;}

二叉树简介基本结构：function TreeNode(x) { this.val = x; this.left = null; this.right = null;}二叉树的前序、中序、后序遍历的定义：前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。题目1 二叉树的镜像1.1 题目描述操作给定的二叉树，将其变换为源二叉树的镜像。输入描述:二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 51.2 解题思路递归交换二叉树两棵字树的位置。1.3 代码function Mirror(root){ if(root){ const temp = root.right; root.right = root.left; root.left = temp; Mirror(root.right); Mirror(root.left); }}题目2 从上往下打印二叉树2.1 题目描述从上往下打印出二叉树的每个节点，同层节点从左至右打印。2.2 解题思路1.借助队列先进先出的数据结构2.让二叉树每层依次进入队列3.依次打印队列中的值2.3 代码 function PrintFromTopToBottom(root) { const queue = []; const print = []; if(root != null){ queue.push(root); } while (queue.length > 0) { const current = queue.shift(); print.push(current.val); if (current.left) { queue.push(current.left); } if (current.right) { queue.push(current.right); } } return print; } ...

具体讲解之前，有一点，再次强调下：B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是一种树。而事实上是，B-tree就是指的B树。特此说明。1、B-树(B树)的基本概念B-树中所有结点中孩子结点个数的最大值成为B-树的阶，通常用m表示，从查找效率考虑，一般要求m>=3。一棵m阶B-树或者是一棵空树，或者是满足以下条件的m叉树。1）每个结点最多有m个分支（子树）；而最少分支数要看是否为根结点，如果是根结点且不是叶子结点，则至少要有两个分支，非根非叶结点至少有ceil(m/2)个分支，这里ceil代表向上取整。2）如果一个结点有n-1个关键字，那么该结点有n个分支。这n-1个关键字按照递增顺序排列。3）每个结点的结构为：其中，n为该结点中关键字的个数；ki为该结点的关键字且满足ki<ki+1；pi为该结点的孩子结点指针且满足pi所指结点上的关键字大于ki且小于ki+1，p0所指结点上的关键字小于k1，pn所指结点上的关键字大于kn。4）结点内各关键字互不相等且按从小到大排列。5）叶子结点处于同一层；可以用空指针表示，是查找失败到达的位置。注：平衡m叉查找树是指每个关键字的左侧子树与右侧子树的高度差的绝对值不超过1的查找树，其结点结构与上面提到的B-树结点结构相同，由此可见，B-树是平衡m叉查找树，但限制更强，要求所有叶结点都在同一层。光看上面的解释可能大家对B-树理解的还不是那么透彻，下面我们用一个实例来进行讲解。上面的图片显示了一棵B-树，最底层的叶子结点没有显示。我们对上面提到的5条特点进行逐条解释：1）结点的分支数等于关键字数+1，最大的分支数就是B-树的阶数，因此m阶的B-树中结点最多有m个分支，所以可以看到，上面的一棵树是一个5-阶B-树。2）因为上面是一棵5阶B-树，所以非根非叶结点至少要有ceil(5/2)=3个分支。根结点可以不满足这个条件，图中的根结点有两个分支。3）如果根结点中没有关键字就没有分支，此时B-树是空树，如果根结点有关键字，则其分支数比大于或等于2，因为分支数等于关键字数+1.4）上图中除根结点外，结点中的关键字个数至少为2，因为分支数至少为3，分支数比关键字数多1，还可以看出结点内关键字都是有序的，并且在同一层中，左边结点内所有关键字均小于右边结点内的关键字，例如，第二层上的两个结点，左边结点内的关键字为15，26，他们均小于右边结点内的关键字39和45.B-树一个很重要的特征是，下层结点内的关键字取值总是落在由上层结点关键字所划分的区间内，具体落在哪个区间内可以由指向它的指针看出。例如，第二层最左边的结点内的关键字划分了三个区间，小于15，15到26，大于26，可以看出其下层中最左边结点内的关键字都小于15，中间结点的关键字在15和26之间，右边结点的关键字大于26.5）上图中叶子结点都在第四层上，代表查找不成功的位置。2、B-树的查找操作B-树的查找很简单，是二叉排序树的扩展，二叉排序树是二路查找，B-树是多路查找，因为B-树结点内的关键字是有序的，在结点内进行查找时除了顺序查找外，还可以用折半查找来提升效率。B-树的具体查找步骤如下（假设查找的关键字为key）：1）先让key与根结点中的关键字比较，如果key等于k[i]（k[]为结点内的关键字数组），则查找成功2）若key<k[1]，则到p[0]所指示的子树中进行继续查找（p[]为结点内的指针数组），这里要注意B-树中每个结点的内部结构。3）若key>k[n]，则道p[n]所指示的子树中继续查找。4）若k[i]<key<k[i+1]，则沿着指针p[I]所指示的子树继续查找。5）如果最后遇到空指针，则证明查找不成功。拿上面的二叉树进行举例，比如我们想要查找关键字42，下图加粗的部分显示了查找的路径：3、B-树的插入与二叉排序树一样，B-树的创建过程也是将关键字逐个插入到树中的过程。在进行插入之前，要确定一下每个结点中关键字个数的范围，如果B-树的阶数为m，则结点中关键字个数的范围为ceil(m/2)-1 ~ m-1个。对于关键字的插入，需要找到插入位置。在B-树的查找过程中，当遇到空指针时，则证明查找不成功，同时也找到了插入位置，即根据空指针可以确定在最底层非叶结点中的插入位置，为了方便，我们称最底层的非叶结点为终端结点，由此可见，B-树结点的插入总是落在终端结点上。在插入过程中有可能破坏B-树的特征，如新关键字的插入使得结点中关键字的个数超过规定个数，这是要进行结点的拆分。接下来，我们以关键字序列{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}创建一棵5阶B-树，我们将详细体会B-树的插入过程。（1）确定结点中关键字个数范围由于题目要求建立5阶B-树，因此关键字的个数范围为2～4（2）根结点最多可以容纳4个关键字，依次插入关键字1、2、6、7后的B-树如下图所示：3）当插入关键字11的时候，发现此时结点中关键字的个数变为5，超出范围，需要拆分，去关键字数组中的中间位置，也就是k[3]=6，作为一个独立的结点，即新的根结点，将关键字6左、右关键字分别做成两个结点，作为新根结点的两个分支（4）新关键字总是插在叶子结点上，插入关键字4、8、13之后树为：（5）关键字10需要插入在关键字8和11之间，此时又会出现关键字个数超出范围的情况，因此需要拆分。拆分时需要将关键字10纳入根结点中，并将10左右的关键字做成两个新的结点连在根结点上。插入关键字10并经过拆分操作后的B-树如下图：（6）插入关键字5、17、9、16之后的B-树如图所示：（7）关键字20插入在关键字17以后，此时会造成结点关键字个数超出范围，需要拆分，方法同上，树为：（8）按照上述步骤依次插入关键字3、12、14、18、19之后B-树如下图所示：（9）插入最后一个关键字15，15应该插入在14之后，此时会出现关键字个数超出范围的情况，则需要进行拆分，将13并入根结点，13并入根结点之后，又使得根结点的关键字个数超出范围，需要再次进行拆分，将10作为新的根结点，并将10左、右关键字做成两个新结点连接到新根结点的指针上，这种插入一个关键字之后出现多次拆分的情况称为连锁反应，最终形成的B-树如下图所示：4、B-树的删除对于B-树关键字的删除，需要找到待删除的关键字，在结点中删除关键字的过程也有可能破坏B-树的特性，如旧关键字的删除可能使得结点中关键字的个数少于规定个数，这是可能需要向其兄弟结点借关键字或者和其孩子结点进行关键字的交换，也可能需要进行结点的合并，其中，和当前结点的孩子进行关键字交换的操作可以保证删除操作总是发生在终端结点上。我们用刚刚生成的B-树作为例子，一次删除8、16、15、4这4个关键字。（1）删除关键字8、16。关键字8在终端结点上，并且删除后其所在结点中关键字的个数不会少于2，因此可以直接删除。关键字16不在终端结点上，但是可以用17来覆盖16，然后将原来的17删除掉，这就是上面提到的和孩子结点进行关键字交换的操作。这里不能用15和16进行关键字交换，因为这样会导致15所在结点中关键字的个数小于2。因此，删除8和16之后B-树如下图所示：（2）删除关键字15，15虽然也在终端结点上，但是不能直接删除，因为删除后当前结点中关键字的个数小于2。这是需要向其兄弟结点借关键字，显然应该向其右兄弟来借关键字，因为左兄弟的关键字个数已经是下限2.借关键字不能直接将18移到15所在的结点上，因为这样会使得15所在的结点上出现比17大的关键字，所以正确的借法应该是先用17覆盖15，在用18覆盖原来的17，最后删除原来的18，删除关键字15后的B-树如下图所示：（3）删除关键字4，4在终端结点上，但是此时4所在的结点的关键字个数已经到下限，需要借关键字，不过可以看到其左右兄弟结点已经没有多余的关键字可借。所以就需要进行关键字的合并。可以先将关键字4删除，然后将关键字5、6、7、9进行合并作为一个结点链接在关键字3右边的指针上，也可以将关键字1、2、3、5合并作为一个结点链接在关键字6左边的指针上，如下图所示：显然上述两种情况下都不满足B-树的规定，即出现了非根的双分支结点，需要继续进行合并，合并后的B-树如下图所示有时候删除的结点不在终端结点上，我们首先需要将其转化到终端结点上，然后再按上面的各种情况进行删除。在讲述这种情况下的删除方法之前，要引入一个相邻关键字的概念，对于不在终端结点的关键字a，它的相邻关键字为其左子树中值最大的关键字或者其右子树中值最小的关键字。找a的相邻关键字的方法为：沿着a的左指针来到其子树根结点，然后沿着根结点中最右端的关键字的右指针往下走，用同样的方法一直走到叶结点上，叶结点上的最右端的关键字即为a的相邻关键字（这里找的是a左边的相邻关键字，我们可以用同样的思路找到a右边的相邻关键字）。可以看到下图中a的相邻关键字是d和e，要删除关键字a，可以用d来取代a，然后按照上面的情况删除叶子结点上的d即可。6、B-树的应用为了将大型数据库文件存储在硬盘上，以减少访问硬盘次数为目的，在此提出了一种平衡多路查找树——B-树结构。由其性能分析可知它的检索效率是相当高的 为了提高 B-树性能’还有很多种B-树的变型，力图对B-树进行改进，比如B+树。

二叉树简介基本结构：function TreeNode(x) { this.val = x; this.left = null; this.right = null;}二叉树的前序、中序、后序遍历的定义：前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。题目1 二叉树遍历1.1 题目描述给定一棵二叉树的前序遍历和中序遍历，求其后序遍历输入描述:两个字符串，其长度n均小于等于26。第一行为前序遍历，第二行为中序遍历。二叉树中的结点名称以大写字母表示：A，B，C….最多26个结点。输出描述:输入样例可能有多组，对于每组测试样例，输出一行，为后序遍历的字符串。样例：输入ABCBACFDXEAGXDEFAG输出BCAXEDGAF1.2 解题思路前序遍历：跟节点 + 左子树前序遍历 + 右子树前序遍历中序遍历：左子树中序遍历 + 跟节点 + 右字数中序遍历后序遍历：左子树后序遍历 + 右子树后序遍历 + 跟节点1.前序遍历的头部为跟节点2.中序遍历以跟节点分割，左侧为左子中序遍历，右侧为右子树中序遍历3.根据中序遍历得到的左子树右子树的长度，得到左子树的前序遍历和右子树的前序遍历1.3 代码let pre;let vin; while((pre = readline())!=null){ vin = readline(); print(getHRD(pre,vin));} function getHRD(pre, vin) { if (!pre) { return ‘’; } if (pre.length === 1) { return pre; } const head = pre[0]; const splitIndex = vin.indexOf(head); const vinLeft = vin.substring(0, splitIndex); const vinRight = vin.substring(splitIndex + 1); const preLeft = pre.substring(1, splitIndex + 1); const preRight = pre.substring(splitIndex + 1); return getHRD(preLeft, vinLeft) + getHRD(preRight, vinRight) + head;题目2 二叉树重建2.1 题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。2.2 解题思路思路和题目1相似。根据前序遍历和中序遍历的结果可以拿到：左子中序遍历和右侧为右子树中序遍历左子树的前序遍历和右子树的前序遍历然后递归左子树和右子树的完成重建。2.3 代码 function reConstructBinaryTree(pre, vin) { if(pre.length === 0){ return null; } if(pre.length === 1){ return new TreeNode(pre[0]); } const value = pre[0]; const index = vin.indexOf(value); const vinLeft = vin.slice(0,index); const vinRight = vin.slice(index+1); const preLeft = pre.slice(1,index+1); const preRight = pre.slice(index+1); const node = new TreeNode(value); node.left = reConstructBinaryTree(preLeft, vinLeft); node.right = reConstructBinaryTree(preRight, vinRight); return node; } ...

什么是队列队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。允许插入的端是队尾，允许删除的端是队头。 队列是一个先进先出的线性表 。队列结构概念：入队、出队、队列头、队列尾js实现栈结构依靠数组 方法名 操作enqueue 入队dequeue 出队front 查看队列头isEmpty 检查队列是否为空size 获取队列大小clear 移除全部元素代码实现class Queue { constructor() { // 私有属性 this._items = []; } // 入队 enqueue(el) { this._items.push(el); } // 出队 dequeue(el) { this._items.shift(el); } // 查看队列头 front() { return this._items[this._items.length - 1]; } // 检查队列是否为空 isEmpty() { return this._items.length === 0; } // 查看队列的大小 size() { return this._items.length; } // 清除队列 clear() { this._items = []; }}下面来个例子炒股游戏：玩家猜涨跌，猜错了就出局，游戏最终结果为玩家全部输了为什么是炒股游戏：找不到图你让我怎么办，没办法只能随便编了下面开始码了// 玩家列表let arr = [‘a’, ‘b’, ‘c’, ’d’, ’e’, ‘f’, ‘g’, ‘h’, ‘i’, ‘j’];// 游戏规则function regulation() { return Math.random() > 0.5}function stocks() { let queue = new Queue() // 入队 arr.forEach(item => { queue.enqueue(item) }) // 当队列为空，说明全部出队，游戏结束 while (!queue.isEmpty()) { for (let i = 0; i < arr.length; i++) { // 为true说明玩家猜对了 if (regulation()) { // 循环队列 queue.enqueue(queue.dequeue()) console.log(玩家${arr[i]}赢了) } else { // 出队 queue.dequeue() console.log(玩家${arr[i]}输了) } } } console.log(‘全部玩家输了’)}此章完结，下一章链表欢迎关注，以便第一时间获取最新的文章 ...

题目描述输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。分析要了解链表的数据结构：val属性存储当前的值，next属性存储下一个节点的引用。要遍历链表就是不断找到当前节点的next节点，当next节点是null时，说明是最后一个节点，停止遍历。最后别忘了，从尾到头遍历链表，不要忘了将你的结果进行翻转。代码/function ListNode(x){ this.val = x; this.next = null;}/function printListFromTailToHead(head){ const result = []; let temp = head; while(temp){ result.push(temp.val); temp = temp.next; } return result.reverse();}拓展链表定义：用一组任意存储的单元来存储线性表的数据元素。一个对象存储着本身的值和下一个元素的地址。需要遍历才能查询到元素，查询慢。插入元素只需断开连接重新赋值，插入快。 function LinkList(){ function node(element){ this.value = element; this.next = null; } let length = 0; let head = null; } LinkList.prototype = { // 追加 append:function(element){ var node = new node(element); var temp = this.head; if(this.head){ //遍历找到链表的终点 while(temp.next){ temp = temp.next; } temp.next = node; }else{ this.head = node; } this.length++; }, // 插入 insert:function(element,index){ if(index <= this.length && index>0){ var node = new node(element); var currentIndex = 0; var currentNode = this.head; var preNode = null; if (currentIndex === 0) { node.next = currentNode; this.head = node; return; } while(currentIndex<index){ preNode = currentNode; currentNode = currentNode.next; currentIndex++; } preNode.next = node; node.next = currentNode; this.length++; } } }链表翻转把初始链表头当做基准点移动下一个元素到头部直到下一个元素为空 /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } / /* * @param {ListNode} head * @return {ListNode} */ var reverseList = function (head) { let currentNode = null; let headNode = head; while (head && head.next) { // 将当前节点从链表中取出 currentNode = head.next; head.next = currentNode.next; // 将取出的节点移动到头部 currentNode.next = headNode; headNode = currentNode; } return headNode; }; ...

前言可能有一部分人没有读过我上一篇写的二叉堆，所以这里把二叉树的基本概念复制过来了，如果读过的人可以忽略前面针对二叉树基本概念的介绍，另外如果对链表数据结构不清楚的最好先看一下本人之前写的js数据结构-链表二叉树二叉树(Binary Tree)是一种树形结构，它的特点是每个节点最多只有两个分支节点，一棵二叉树通常由根节点，分支节点，叶子节点组成。而每个分支节点也常常被称作为一棵子树。根节点：二叉树最顶层的节点分支节点：除了根节点以外且拥有叶子节点叶子节点：除了自身，没有其他子节点常用术语在二叉树中，我们常常还会用父节点和子节点来描述，比如图中2为6和3的父节点，反之6和3是2子节点二叉树的三个性质在二叉树的第i层上，至多有2^i-1个节点i=1时，只有一个根节点，2^(i-1) = 2^0 = 1深度为k的二叉树至多有2^k-1个节点i=2时，2^k-1 = 2^2 - 1 = 3个节点对任何一棵二叉树T，如果总结点数为n0，度为2(子树数目为2)的节点数为n2,则n0=n2+1树和二叉树的三个主要差别树的节点个数至少为1，而二叉树的节点个数可以为0树中节点的最大度数(节点数量)没有限制,而二叉树的节点的最大度数为2树的节点没有左右之分，而二叉树的节点有左右之分二叉树分类二叉树分为完全二叉树(complete binary tree)和满二叉树(full binary tree)满二叉树：一棵深度为k且有2^k - 1个节点的二叉树称为满二叉树完全二叉树：完全二叉树是指最后一层左边是满的，右边可能满也可能不满，然后其余层都是满的二叉树称为完全二叉树(满二叉树也是一种完全二叉树)二叉搜索树二叉搜索树满足以下的几个性质：若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；任意节点的左、右子树也需要满足左边小右边大的性质我们来举个例子来深入理解以下一组数据：12,4,18,1,8,16,20由下图可以看出，左边的图满足了二叉树的性质，它的每个左子节点都小于父节点，右子节点大于其父节点，同时左子树的节点都小于根节点，右子树的节点都大于根节点二叉搜索树主要的几个操作：查找（search）插入（insert）遍历（transverse）二叉树搜索树的链式存储结构通过下图，可以知道二叉搜索树的节点通常包含4个域，数据元素，分别指向其左，右节点的指针和一个指向父节点的指针所构成，一般把这种存储结构称为三叉链表。用代码初始化一个二叉搜索树的结点：一个指向父亲节点的指针 parent一个指向左节点的指针 left一个指向右节点的指针 right一个数据元素，里面可以是一个key和value class BinaryTreeNode { constructor(key, value){ this.parent = null; this.left = null; this.right = null; this.key = key; this.value = value; } }接着我们再用代码去初始化一个二叉搜索树在二叉搜索树中我们会维护一个root指针，这个就相当于链表中的head指针，在没有任何节点插入的时候它指向空，在有节点插入以后它指向根节点。 class BinarySearchTree { constructor() { this.root = null; } }创建节点 static createNode(key, value) { return new BinarySearchTree(key, value); }插入操作看下面这张图，13是我们要插入的节点，它插入的具体步骤：跟根节点12做比较，比12大，所以我们确定了，这个节点是往右子树插入的而根节点的右边已经有节点，那么跟这个节点18做比较，结果小于18所以往18的左节点找位置而18的左节点也已经有节点了，所以继续跟这个节点做比较，结果小于16刚好16的左节点是空的(left=null)，所以13这个节点就插入到了16的左节点通过上面的描述，我们来看看代码是怎么写的定义两个指针，分别是p和tail，最初都指向root，p是用来指向要插入的位置的父节点的指针，而tail是用来查找插入位置的，所以最后它会指向null，用上图举个例子，p最后指向了6这个节点，而tail最后指向了null（tail为null则说明已经找到了要插入的位置）循环，tail根据我们上面分析的一步一步往下找位置插入，如果比当前节点小就往左找，大则往右找，一直到tail找到一个空位置也就是null如果当前的root为null，则说明当前结构中并没有节点，所以插入的第一个节点直接为跟节点，即this.root = node将插入后的节点的parent指针指向父节点 insert(node){ let p = this.root; let tail = this.root; // 循环遍历，去找到对应的位置 while(tail) { p = tail; // 要插入的节点key比当前节点小 if (node.key < tail.key){ tail.left = tail.left; } // 要插入的节点key比当前节点大 else { tail.right = tail.right; } } // 没有根节点，则直接作为根节点插入 if(!p) { this.root = node; return; } // p是最后一个节点，也就是我们要插入的位置的父节点 // 比父节点大则往右边插入 if(p.key < node.key){ p.right = node; } // 比父节点小则往左边插入 else { p.left = node; } // 指向父节点 node.parent = p; }查找查找就很简单了，其实和插入差多，都是去别叫左右节点的大小，然后往下找如果root = null, 则二叉树中没有任何节点，直接return，或者报个错什么的。循环查找 search(key) { let p = this.root; if(!p) { return; } while(p && p.key !== key){ if(p.key<key){ p = p.right; }else{ p = p.left; } } return p; }遍历中序遍历(inorder)：先遍历左节点，再遍历自己，最后遍历右节点，输出的刚好是有序的列表前序遍历(preorder)：先自己，再遍历左节点，最后遍历右节点后序遍历(postorder)：先左节点，再右节点，最后自己最常用的一般是中序遍历，因为中序遍历可以得到一个已经排好序的列表，这也是为什么会用二叉搜索树排序的原因根据上面对中序遍历的解释，那么代码就变的很简单，就是一个递归的过程，递归停止的条件就是节点为null先遍历左节点–>yield* this._transverse(node.left)遍历自己 –> yield* node遍历左节点 –> yield* this._transverse(node.right) transverse() { return this._transverse(this.root); } _transverse(node){ if(!node){ return; } yield this._transverse(node.left); yield node; yield* this._transverse(node.right) }看上面这张图，我们简化的来看一下，先访问左节点4，再自己12，然后右节点18，这样输出的就刚好是一个12，4，8补充：这个地方用了generater，所以返回的一个迭代器。可以通过下面这种方式得到一个有序的数组，这里的前提就当是已经有插入的节点了 const tree = new BinaryTree(); //…中间省略插入过程 // 这样就返回了一个有序的数组 var arr = […tree.transverse()].map(item=>item.key);完整代码class BinaryTreeNode { constructor(key, value) { // 指向父节点 this.p = null; // 左节点 this.left = null; // 右节点 this.right = null; // 键 this.key = key; // 值 this.value = value; }}class BinaryTree { constructor() { this.root = null; } static createNode(key, value) { return new BinaryTreeNode(key, value); } search(key) { let p = this.root; if (!p) { return; } while (p && p.key !== key) { if (p.key < key) { p = p.right; } else { p = p.left; } } return p; } insert(node) { // 尾指针的父节点指针 let p = this.root; // 尾指针 let tail = this.root; while (tail) { p = tail; if (node.key < tail.key) { tail = tail.left; } else { tail = tail.right; } } if (!p) { this.root = node; return; } // 插入 if (p.key < node.key) { p.right = node; } else { p.left = node; } node.p = p; } transverse() { return this.__transverse(this.root); } __transverse(node) { if (!node) { return; } yield this.__transverse(node.left); yield node; yield* this.__transverse(node.right); }}总结二叉查找树就讲完了哈，其实这个和链表很像的，还是操作那么几个指针，既然叫查找树了，它主要还是用来左一些搜索，还有就是排序了，另外补充一下，二叉查找树里找最大值和最小值也很方便是不是，如果你大致读懂了的话。这篇文章我写的感觉有点乱诶，因为总感觉哪里介绍的不到位，让一些基础差的人会看不懂，如果有不懂或者文章哪里写错了，欢迎评论留言哈后续后续写什么呢，这个问题我也在想，排序算法，react第三方的一些模拟实现？，做个小程序组件库？还是别的，容我再想几个小时，因为可以，有建议的朋友们也可以留言说一下哈。最后最后，最重要的请给个赞，请粉一个呢，谢谢啦 ...

什么是链式队列队列是一种“先进先出”的存储结构,是一种特殊的线性表，于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。通常队列可以分为顺序队列和链式队列两种实现，顺序队列顾名思义就是采用顺序存储，如以数组方式来实现，链式队列采用链式存储，如以上篇说到的单向链表来实现，链式队列是以链式数据结构实现的队列队列有两个基本的操作，入队列和出队列代码实现链式队列实现方式多种多样，可以以单链表，双向链表，循环链表等各种方式来实现，这里以上篇提到的单链表的方式来实现。<?phprequire ‘SingleLinkList.php’;/** * Class Queue * 队列是一种“先进先出”的存储结构,它只允许在队头进行删除操作，而在队尾进行插入操作 * 通常队列可以分为顺序队列和链式队列两种实现 * 顺序队列顾名思义就是采用顺序存储，如以数组方式来实现 * 链式队列采用链式存储，如以上篇说到的单向链表来实现 * * 队列有两个基本的操作，入队列和出队列 /class QueueImplementedBySingleLinkList extends SingleLinkList{ /* * Queue constructor. * 构造函数，初始化队列 / public function __construct() { parent::__construct(); } /* * 入队 * @param $data / public function enQueue($data) { $node = new Node($data); parent::addNode($node); } /* * 出队 * @return mixed * @throws Exception / public function deQueue() { if ($this->isEmpty()) { throw new Exception(‘队列为空’); } $node = parent::searchNodeByIndex(1); parent::deleteNodeByIndex(1); return $node->data; } /* * 队列是否为空 * @return bool */ public function isEmpty() { return $this->header->next == null; }}示例$queue = new QueueImplementedBySingleLinkList();$queue->enQueue(‘1’);$queue->enQueue(‘2’);$queue->enQueue(‘3’);$queue->enQueue(‘4’);var_dump($queue);echo ‘———–’, PHP_EOL;$queue->deQueue();$queue->deQueue();var_dump($queue); ...

什么是单向链表链表是以链式存储数据的结构，其不需要连续的存储空间，链表中的数据以节点来表示，每个节点由元素和指针组成。单向链表（也叫单链表）是链表中最简单的一种形式，每个节点只包含一个元素和一个指针。它有一个表头，并且除了最后一个节点外，所有节点都有其后继节点。它的存储结构如下图所示代码实现定义节点class Node{ public $data; /** * @var null | Node / public $next; public function __construct($data) { $this->data = $data; $this->next = null; }}单链表实现/* * Class SingleLinkList * 单链接的实现示例，实现简单的填加，插入，删除, 查询，长度，遍历这几个简单操作 /class SingleLinkList{ /* * 链表头结点，头节点必须存在， * @var Node / public $header; private $size = 0; /* * 构造函数，默认填加一个哨兵节点，该节点元素为空 * SingleLinkList constructor. / public function __construct() { $this->header = new Node(null); } /* * 添加节点 * @param Node $node * @return int / public function addNode(Node $node) { $current = $this->header; while ($current->next != null) { $current = $current->next; } $current->next = $node; return ++$this->size; } /* * 在指定位置查入节点 * @param int $index 节点位置，从1开始计数 * @param Node $node * @return int * @throws Exception / public function insertNodeByIndex($index, Node $node) { if ($index < 1 || $index > ($this->size + 1)) { throw new Exception(sprintf(‘你要插入的位置，超过了链表的长度 %d’, $this->size)); } $current = $this->header; $tempIndex = 1; do { if ($index == $tempIndex++) { $node->next = $current->next; $current->next = $node; break; } } while ($current->next != null && ($current = $current->next)); return ++$this->size; } /* * 删除节点 * @param int $index 节点位置，从1开始计数 * @return int * @throws Exception / public function deleteNodeByIndex($index) { if ($index < 1 || $index > ($this->size + 1)) { throw new Exception(‘你删除的节点不存在’); } $current = $this->header; $tempIndex = 1; do { if ($index == $tempIndex++) { $current->next = $current->next->next; break; } } while ($current->next != null && ($current = $current->next)); return –$this->size; } /* * 查询节点 * @param int $index 节点位置，从1开始计数 * @return Node|null * @throws Exception / public function searchNodeByIndex($index) { if ($index < 1 || $index > ($this->size + 1)) { throw new Exception(‘你查询的节点不存在’); } $current = $this->header; $tempIndex = 1; do { if ($index == $tempIndex++) { return $current->next; } } while ($current->next != null && ($current = $current->next)); } /* * 获取节点长度 * @return int / public function getLength() { return $this->size; } /* * 遍历列表 */ public function showNode() { $current = $this->header; $index = 1; while ($current->next != null) { $current = $current->next; echo ‘index — ’ . $index++ . ’ — ‘; echo var_export($current->data); echo PHP_EOL; } }}示例$link = new SingleLinkList();$link->addNode(new Node(1));$link->addNode(new Node(2));$link->insertNodeByIndex(3, new Node(3));$link->addNode(new Node(4));$link->addNode(new Node(5));echo $link->getLength(), PHP_EOL;$link->showNode();echo ‘———–’, PHP_EOL;var_dump($link->searchNodeByIndex(3));echo ‘———–’, PHP_EOL;$link->deleteNodeByIndex(3);$link->showNode(); ...

二叉树二叉树(Binary Tree)是一种树形结构，它的特点是每个节点最多只有两个分支节点，一棵二叉树通常由根节点，分支节点，叶子节点组成。而每个分支节点也常常被称作为一棵子树。根节点：二叉树最顶层的节点分支节点：除了根节点以外且拥有叶子节点叶子节点：除了自身，没有其他子节点常用术语在二叉树中，我们常常还会用父节点和子节点来描述，比如图中2为6和3的父节点，反之6和3是2子节点二叉树的三个性质在二叉树的第i层上，至多有2^i-1个节点i=1时，只有一个根节点，2^(i-1) = 2^0 = 1深度为k的二叉树至多有2^k-1个节点i=2时，2^k-1 = 2^2 - 1 = 3个节点对任何一棵二叉树T，如果总结点数为n0，度为2(子树数目为2)的节点数为n2,则n0=n2+1树和二叉树的三个主要差别树的节点个数至少为1，而二叉树的节点个数可以为0树中节点的最大度数(节点数量)没有限制,而二叉树的节点的最大度数为2树的节点没有左右之分，而二叉树的节点有左右之分二叉树分类二叉树分为完全二叉树(complete binary tree)和满二叉树(full binary tree)满二叉树：一棵深度为k且有2^k - 1个节点的二叉树称为满二叉树完全二叉树：完全二叉树是指最后一层左边是满的，右边可能满也可能不满，然后其余层都是满的二叉树称为完全二叉树(满二叉树也是一种完全二叉树)二叉树的数组表示用一个数组来表示二叉树的结构，将一组数组从根节点开始从上到下，从左到右依次填入到一棵完全二叉树中，如下图所示通过上图我们可以分析得到数组表示的完全二叉树拥有以下几个性质：left = index * 2 + 1，例如：根节点的下标为0，则左节点的值为下标array[0＊2+1]=1right = index * 2 + 2，例如：根节点的下标为0，则右节点的值为下标array[0＊2+2]=2序数 >= floor(N/2)都是叶子节点，例如：floor(9/2) = 4，则从下标4开始的值都为叶子节点二叉堆二叉堆由一棵完全二叉树来表示其结构，用一个数组来表示，但一个二叉堆需要满足如下性质：二叉堆的父节点的键值总是大于或等于(小于或等于)任何一个子节点的键值当父节点的键值大于或等于(小于或等于)它的每一个子节点的键值时，称为最大堆（最小堆）从上图可以看出：左图：父节点总是大于或等于其子节点，所以满足了二叉堆的性质，右图：分支节点7作为2和12的父节点并没有满足其性质(大于或等于子节点)。二叉堆的主要操作insert：插入节点delete：删除节点max-hepify：调整分支节点堆性质rebuildHeap：重新构建整个二叉堆sort：排序初始化一个二叉堆从上面简单的介绍，我们可以知道，一个二叉堆的初始化非常的简单，它就是一个数组初始化一个数组结构保存数组长度 class Heap{ constructor(arr){ this.data = […arr]; this.size = this.data.length; } }max-heapify最大堆操作max-heapify是把每一个不满足最大堆性质的分支节点进行调整的一个操作。 如上图：调整分支节点2（分支节点2不满足最大堆的性质）默认该分支节点为最大值将2与左右分支比较，从2，12，5中找出最大值，然后和2交换位置根据上面所将的二叉堆性质，分别得到分支节点2的左节点和右节点比较三个节点，得到最大值的下标max如果该节点本身就是最大值，则停止操作将max节点与父节点进行交换重复step2的操作，从2，4，7中找出最大值与2做交换递归 maxHeapify(i) { let max = i; if(i >= this.size){ return; } // 当前序号的左节点 const l = i * 2 + 1; // 当前需要的右节点 const r = i * 2 + 2; // 求当前节点与其左右节点三者中的最大值 if(l < this.size && this.data[l] > this.data[max]){ max = l; } if(r < this.size && this.data[r] > this.data[max]){ max = r; } // 最终max节点是其本身,则已经满足最大堆性质，停止操作 if(max === i) { return; } // 父节点与最大值节点做交换 const t = this.data[i]; this.data[i] = this.data[max]; this.data[max] = t; // 递归向下继续执行 return this.maxHeapify(max); }重构堆我们可以看到，刚初始化的堆由数组表示，这个时候它可能并不满足一个最大堆或最小堆的性质，这个时候我们可能需要去将整个堆构建成我们想要的。上面我们做了max-heapify操作，而max-heapify只是将某一个分支节点进行调整，而要将整个堆构建成最大堆，则需要将所有的分支节点都进行一次max-heapify操作，如下图，我们需要依次对12，3，2，15这4个分支节点进行max-hepify操作具体步骤：找到所有分支节点：上面堆的性质提到过叶子节点的序号>=Math.floor(n/2)，因此小于Math.floor(n/2)序号的都是我们需要调整的节点。例如途中所示数组为[15,2,3,12,5,2,8,4,7] => Math.floor(9/2)=4 => index小于4的分别是15，2，3，12(需要调整的节点)，而5，2，8，4，7为叶子节点。将找到的节点都进行maxHeapify操作 rebuildHeap(){ // 叶子节点 const L = Math.floor(this.size / 2); for(let i = L - 1; i>=0; i–){ this,maxHeapify(i); } }最大堆排序最大堆的排序，如上图所示：交换首尾位置将最后个元素从堆中拿出，相当于堆的size-1然后在堆根节点进行一次max-heapify操作重复以上三个步骤，知道size=0 (这个边界条件我们在max-heapify函数里已经做了) sort() { for(let i = this.size - 1; i > 0; i–){ swap(this.data, 0, i); this.size–; this.maxHeapify(0); } }插入和删除这个的插入和删除就相对比较简单了，就是对一个数组进行插入和删除的操作往末尾插入堆长度+1判断插入后是否还是一个最大堆不是则进行重构堆 insert(key) { this.data[this.size] = key; this.size++ if (this.isHeap()) { return; } this.rebuildHeap(); }删除数组中的某个元素堆长度-1判断是否是一个堆不是则重构堆 delete(index) { if (index >= this.size) { return; } this.data.splice(index, 1); this.size–; if (this.isHeap()) { return; } this.rebuildHeap(); }完整代码/** * 最大堆 /function left(i) { return i * 2 + 1;}function right(i) { return i * 2 + 2;}function swap(A, i, j) { const t = A[i]; A[i] = A[j]; A[j] = t;}class Heap { constructor(arr) { this.data = […arr]; this.size = this.data.length; } /* * 重构堆 / rebuildHeap() { const L = Math.floor(this.size / 2); for (let i = L - 1; i >= 0; i–) { this.maxHeapify(i); } } isHeap() { const L = Math.floor(this.size / 2); for (let i = L - 1; i >= 0; i++) { const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER; const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER; const max = Math.max(this.data[i], l, r); if (max !== this.data[i]) { return false; } return true; } } sort() { for (let i = this.size - 1; i > 0; i–) { swap(this.data, 0, i); this.size–; this.maxHeapify(0); } } insert(key) { this.data[this.size++] = key; if (this.isHeap()) { return; } this.rebuildHeap(); } delete(index) { if (index >= this.size) { return; } this.data.splice(index, 1); this.size–; if (this.isHeap()) { return; } this.rebuildHeap(); } /* * 堆的其他地方都满足性质 * 唯独跟节点，重构堆性质 * @param {*} i */ maxHeapify(i) { let max = i; if (i >= this.size) { return; } // 求左右节点中较大的序号 const l = left(i); const r = right(i); if (l < this.size && this.data[l] > this.data[max]) { max = l; } if (r < this.size && this.data[r] > this.data[max]) { max = r; } // 如果当前节点最大，已经是最大堆 if (max === i) { return; } swap(this.data, i, max); // 递归向下继续执行 return this.maxHeapify(max); }}module.exports = Heap;总结堆讲到这里就结束了，堆在二叉树里相对会比较简单，常常被用来做排序和优先级队列等。堆中比较核心的还是max-heapify这个操作，以及堆的三个性质。后续下一篇应该会介绍二叉搜索树。欢迎大家指出文章的错误，如果有什么写作建议也可以提出。我会持续的去写关于前端的一些技术文章，如果大家喜欢的话可以关注一和点个赞，你的赞是我写作的动力。顺便再提一下，我在等第一个粉丝哈哈 ...

散列表散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。我们从上图开始分析有一个集合U，里面分别是1000，10，152，9733，1555，997，1168右侧是一个10个插槽的列表（散列表），我们需要把集合U中的整数存放到这个列表中怎么存放，分别存在哪个槽里？这个问题就是需要通过一个散列函数来解决了。我的存放方式是取10的余数，我们对应这图来看1000%10=0，10%10=0 那么1000和10这两个整数就会被存储到编号为0的这个槽中152%10=2那么就存放到2的槽中9733%10=3 存放在编号为3的槽中通过上面简单的例子，应该会有一下几点一个大致的理解集合U，就是可能会出现在散列表中的键散列函数，就是你自己设计的一种如何将集合U中的键值通过某种计算存放到散列表中，如例子中的取余数散列表，存放着通过计算后的键那么我们在接着看一般我们会怎么去取值呢？比如我们存储一个key为1000，value为’张三’ —> {key:1000,value:‘张三’}从我们上述的解释，它是不是应该存放在1000%10的这个插槽里。当我们通过key想要找到value张三，是不是到key%10这个插槽里找就可以了呢？到了这里你可以停下来思考一下。散列的一些术语（可以简单的看一下）散列表中所有可能出现的键称作全集U用M表示槽的数量给定一个键，由散列函数计算它应该出现在哪个槽中，上面例子的散列函数h=k%M,散列函数h就是键k到槽的一个映射。1000和10都被存到了编号0的这个槽中，这种情况称之为碰撞。看到这里不知道你是否大致理解了散列函数是什么了没。通过例子，再通过你的思考，你可以回头在读一遍文章头部关于散列表的定义。如果你能读懂了，那么我估计你应该是懂了。常用的散列函数处理整数 h=>k%M （也就是我们上面所举的例子）处理字符串： function h_str(str,M){ return […str].reduce((hash,c)=>{ hash = (31*hash + c.charCodeAt(0)) % M },0) }hash算法不是这里的重点，我也没有很深入的去研究，这里主要还是去理解散列表是个怎样的数据结构，它有哪些优点，它具体做了怎样一件事。而hash函数它只是通过某种算法把key映射到列表中。构建散列表通过上面的解释，我们这里做一个简单的散列表散列表的组成M个槽有个hash函数有一个add方法去把键值添加到散列表中有一个delete方法去做删除有一个search方法，根据key去找到对应的值初始化- 初始化散列表有多少个槽- 用一个数组来创建M个槽 class HashTable { constructor(num=1000){ this.M = num; this.slots = new Array(num); } }散列函数处理字符串的散列函数，这里使用字符串是因为，数值也可以传换成字符串比较通用一些先将传递过来的key值转为字符串，为了能够严谨一些将字符串转换为数组, 例如’abc’ => […‘abc’] => [‘a’,‘b’,‘c’]分别对每个字符的charCodeAt进行计算，取M余数是为了刚好对应插槽的数量，你总共就10个槽,你的数值%10 肯定会落到 0-9的槽里 h(str){ str = str + ‘’; return […str].reduce((hash,c)=>{ hash = (331 * hash + c.charCodeAt()) % this.M; return hash; },0) }添加调用hash函数得到对应的存储地址(就是我们之间类比的槽)因为一个槽中可能会存多个值，所以需要用一个二维数组去表示，比如我们计算得来的槽的编号是0，也就是slot[0]，那么我们应该往slot[0] [0]里存，后面进来的同样是编号为0的槽的话就接着往slot[0] [1]里存 add(key,value) { const h = this.h(key); // 判断这个槽是否是一个二维数组, 不是则创建二维数组 if(!this.slots[h]){ this.slots[h] = []; } // 将值添加到对应的槽中 this.slots[h].push(value); } 删除通过hash算法,找到所在的槽通过过滤来删除 delete(key){ const h = this.h(key); this.slots[h] = this.slots[h].filter(item=>item.key!==key); }查找通过hash算法找到对应的槽用find函数去找同一个key的值返回对应的值 search(key){ const h = this.h(key); const list = this.slots[h]; const data = list.find(x=> x.key === key); return data ? data.value : null; }总结讲到这里，散列表的数据结构已经讲完了，其实我们每学一种数据结构或算法的时候，不是去照搬实现的代码，我们要学到的是思想，比如说散列表它究竟做了什么，它是一种存储方式，可以快速的通过键去查找到对应的值。那么我们会思考，如果我们设计的槽少了，在同一个槽里存放了大量的数据，那么这个散列表它的搜索速度肯定是会大打折扣的，这种情况又应该用什么方式去解决，又或者是否用其他的数据结构的代替它。补充一个小知识点v8引擎中的数组 arr = [1,2,3,4,5] 或 new Array(100) 我们都知道它是开辟了一块连续的空间去存储，而arr = [] , arr[100000] = 10 这样的操作它是使用的散列，因为这种操作如果连续开辟100万个空间去存储一个值，那么显然是在浪费空间。后续后续可能会去介绍一下二叉树，另外对于文章有什么写错或者写的不好的地方大家都可以提出来。我会持续的去写关于前端的一些技术文章，如果大家喜欢的话可以关注一下，点个赞哦谢谢 ...

链表和数组大家都用过js中的数组，数组其实是一种线性表的顺序存储结构，它的特点是用一组地址连续的存储单元依次存储数据元素。而它的缺点也正是其特点而造成，比如对数组做删除或者插入的时候，可能需要移动大量的元素。这里大致模拟一下数组的插入操作： insert(arr, index, data){ for(let i = index + 1; i < arr.length; i++){ arr[i] = arr[i - 1]; } arr[index] = data; }从上面的代码可以看出数组的插入以及删除都有可能会是一个O(n)的操作。从而就引出了链表这种数据结构，链表不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的缺点，当然它也失去了数组在一块连续空间内随机存取的优点。单向链表单向链表的特点：用一组任意的内存空间去存储数据元素（这里的内存空间可以是连续的，也可以是不连续的）每个节点(node)都由数据本身和一个指向后续节点的指针组成整个链表的存取必须从头指针开始，头指针指向第一个节点最后一个节点的指针指向空（NULL）链表中的几个主要操作创建节点插入节点搜索/遍历节点删除节点合并初始化节点指针指向空存储数据 class Node { constructor(key) { this.next = null; this.key = key; } }初始化单向链表每个链表都有一个头指针，指向第一个节点，没节点则指向NULL class List { constructor() { this.head = null; } }创建节点 static createNode(key) { return new createNode(key); }这里说明一下，这一块我是向外暴露了一个静态方法来创建节点，而并非直接把它封装进插入操作里去，因为我感觉这样的逻辑会更加正确一些。 从创建一个链表 -> 创建一个节点 -> 将节点插入进链表中。可能你会遇到一些文章介绍的方式是直接将一个数据作为参数去调用insert操作，在insert内部做了一个创建节点。插入节点（插入到头节点之后）插入操作只需要去调整节点的指针即可,两种情况：head没有指向任何节点，说明当前插入的节点是第一个head指向新节点新节点的指针指向NULLhead有指向的节点head指向新的节点新节点的指针指向原本head所指向的节点 insert(node) { // 如果head有指向的节点 if(this.head){ node.next = this.head; }else { node.next = null; } this.head = node; }搜索节点从head开始查找找到节点中的key等于想要查找的key的时候，返回该节点 find(key) { let node = this.head; while(node !== null && node.key !== key){ node = node.next; } return node; }删除节点这里分三种情况：所要删除的节点刚好是第一个，也就是head指向的节点将head指向所要删除节点的下一个节点(node.next)要删除的节点为最后一个节点寻找到所要删除节点的上一个节点(prevNode)将prevNode中的指针指向NULL在列表中间删除某个节点寻找到所要删除节点的上一个节点(prevNode)将prevNode中的指针指向当前要删除的这个节点的下一个节点 delete(node) { // 第一种情况 if(node === this.head){ this.head = node.next; return; } // 查找所要删除节点的上一个节点 let prevNode = this.head; while (prevNode.next !== node) { prevNode = prevNode.next; } // 第二种情况 if(node.next === null) { prevNode.next = null; } // 第三种情况 if(node.next) { prevNode.next = node.next; } }单向链表整体的代码class ListNode { constructor(key) { this.next = null; this.key = key; }}class List { constructor() { this.head = null; this.length = 0; } static createNode(key) { return new ListNode(key); } // 往头部插入数据 insert(node) { // 如果head后面有指向的节点 if (this.head) { node.next = this.head; } else { node.next = null; } this.head = node; this.length++; } find(key) { let node = this.head; while (node !== null && node.key !== key) { node = node.next; } return node; } delete(node) { if (this.length === 0) { throw ’node is undefined’; } if (node === this.head) { this.head = node.next; this.length–; return; } let prevNode = this.head; while (prevNode.next !== node) { prevNode = prevNode.next; } if (node.next === null) { prevNode.next = null; } if (node.next) { prevNode.next = node.next; } this.length–; }}双向链表如果你把上面介绍的单向列表都看明白了，那么这里介绍的双向列表其实差不多。从上面的图可以很清楚的看到双向链表和单向链表的区别。双向链表多了一个指向上一个节点的指针。初始化节点指向前一个节点的指针指向后一个节点的指针节点数据 class ListNode { this.prev = null; this.next = null; this.key = key; }初始化双向链表头指针指向NULL class List { constructor(){ this.head = null; } }创建节点 static createNode(key){ return new ListNode(key); }插入节点（（插入到头节点之后）看上图中head后面的第一个节点可以知道，该节点的prev指向NULL节点的next指针指向后一个节点, 也就是当前头指针所指向的那个节点如果head后有节点，那么原本head后的节点的prev指向新插入的这个节点(因为是双向的嘛)最后将head指向新的节点 insert(node) { node.prev = null; node.next = this.head; if(this.head){ this.head.prev = node; } this.head = node; }搜索节点这里和单向节点一样，就直接贴代码了 search(key) { let node = this.head; while (node !== null && node.key !== key) { node = node.next; } return node; }删除节点和之前单向链表一样，分三种情况去看：删除的是第一个节点head指向所要删除节点的下一个节点下一个节点的prev指针指向所要删除节点的上一个节点删除的是中间的某个节点所要删除的前一个节点的next指向所要删除的下一个节点所要删除的下一个节点的prev指向所要删除的前一个节点删除的是最后一个节点要删除的节点的上一个节点的next指向null（也就是指向删除节点的next所指的地址） delete(node) { const {prev,next} = node; delete node.prev; delete node.next; if(node === this.head){ this.head = next; } if(next){ next.prev = prev; } if(prev){ prev.next = next; } }双向链表整体代码 class ListNode { constructor(key) { // 指向前一个节点 this.prev = null; // 指向后一个节点 this.next = null; // 节点的数据(或者用于查找的键) this.key = key; }}/** * 双向链表 */class List { constructor() { this.head = null; } static createNode(key) { return new ListNode(key); } insert(node) { node.prev = null; node.next = this.head; if (this.head) { this.head.prev = node; } this.head = node; } search(key) { let node = this.head; while (node !== null && node.key !== key) { node = node.next; } return node; } delete(node) { const { prev, next } = node; delete node.prev; delete node.next; if (node === this.head) { this.head = next; } if (prev) { prev.next = next; } if (next) { next.prev = prev; } }}总结这里做一个小总结吧，可能有一部分人读到这里还不是特别的明白，我的建议是先好好看懂上面的单向链表。 其实只要你明白了链表的基础概念，就是有一个head，然后在有好多的节点(Node)，然后用一个指针把他们串起来就好了，至于里面的插入操作也好，删除也好，其实都是在调整节点中指针的指向。后续后续可能还会是数据结构，可能是讲二叉堆，也可能回过头来讲一些队列和栈的思想在程序中的应用。欢迎大家指出文章的错误，如果有什么写作建议也可以提出。我会持续的去写关于前端的一些技术文章，如果大家喜欢的话可以关注一下哈 ...

队列上一篇数据结构讲到了栈，队列和栈非常类似。队列也是一种特殊的列表，它与栈的区别在于，栈是先入后出，而队列则是遵循FIFO先入先出的原则，换言之队列只能在队尾插入元素，而在队列的头部去删除元素。举个简单的例子，队列就相当于在生活中排队购物，后来的人需要排在队尾，而队伍最前面的人会一次结账后出列。队列的应用非常广泛，常用于实现缓冲区，广度优先搜索，优先级队列等等。队列最主要的两个操作分别是enqueue(入列)和dequeue(出列)队列的实现逻辑通过上面这张图我们可以看到队列的几个特点初始化有一块连续的空间用来去存储队列有一个头部指向第一个数据的地址有一个尾部指向数据后一个空位的地址空间的大小队列内部数据的长度 class Queue { constructor(max=1000){ // 定义一块连续的存储空间用来存储数据 this.data = new Array(1000); // 开辟的空间大小 this.max = max; // 头部位置 this.head = 0; // 尾部位置 this.tail = 0; // 数据长度 this.size = 0; } }enqueue 入列当数据长度超出了开辟的空间大小会报overflow的错误向尾部添加新数据尾部指针向后挪动一位，如果尾部没有空间，则指向0（见上图的两个enqueue操作） enqueue(x) { // 溢出 if(this.size === this.max){ throw ‘overflow’ } // 添加新数据到尾部 this.data[this.tail] = x; // 数据长度+1 this.size++; // 尾部指针向后挪动一位，如果后面没有空间，则指向0 if(this.tail === this.max-1){ this.tail = 0; }else{ this.tail++ } }dequeue出列如果当前数据长度为0，则抛出underflow的错误取出头部位置的数据头部指针向后挪动一位数据长度-1返回该数据 dequeue(){ if(this.size === 0){ throw ‘underflow’; } const x = this.data[this.head]; this.head++; this.size–; return x; }整个代码 class Queue { constructor(max = 1000) { this.data = new Array(max); this.max = max; this.head = 0; this.tail = 0; this.size = 0; } // 入列 enqueue(x) { if (this.size === this.max) { throw ‘overflow’; } this.data[this.tail] = x; this.size++; if (this.tail === this.max - 1) { this.tail = 0; } else { this.tail++; } } // 出列 dequeue() { if (this.size === 0) { throw ‘underflow’; } const x = this.data[this.head]; this.head++; this.size–; return x; } get length() { return this.size; } } module.exports = Queue;扩展–栈实现队列队列也可以通过两个栈来实现，不了解栈的同学可以看上一篇关于栈文章，接下来会引入之前写好的栈，具体代码见下面。 // 上一节中，栈的实现代码 const Stack = require(’./stack’); class Queue { constructor(max=1000){ // 实例化两个栈，分别是s1和s2, s1栈用来做入列,s2栈用来出列使用 this.s1 = new Stack(max); this.s2 = new Stack(max); this.max = max; } // 入列 enqueue(x) { if(this.s1.length === this.max){ throw ‘overflow’ } // s1作为入列 this.s1.push(x); } // 出列 dequeue(){ if(this.s2.length>0){ return this.s2.pop; } while(this.s1.length){ this.s2.push(this.s1.pop()); } return this.s2.pop(); } }在这里大致简单的说明一下以上用两个栈来实现队列的逻辑吧。栈s1 入栈后假设数据为 1,2,3,4,5，队列遵循先入先出，所以dequeue的时候的顺序应该是1,2,3,4,5,那么下面我们看如何利用栈s2出栈。首先栈s1 pop()出栈后的数据则为 5,4,3,2,1 正好倒过来, 我们利用循环将栈s1出栈的数据push到栈s2，则栈s2中的数据就会是5,4,3,2,1。下面我们再执行s2.pop()的时候，是不是就能刚好能依次拿到1,2,3,4,5这几个数据了后续下一张的数据结构会为大家介绍链表 ...

最近发现一个有趣的排序算法，通过位图来完成排序。位图排序其实就是基数排序，只不过位图排序的下标是比特位。问题描述输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=10^7。如果在输入文件中有任何正数重复出现就是致命错误。没有其他数据与该正数相关联。输出：按升序排列的输入正数的列表。约束：最多有1MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化。一种解决方法是把整个文件分成 40 份，每份 250000 个整数，一个整形占 4 字节，刚好可以在 1MB 的空间里操作。在第一趟遍历中，将大小为 0 至 249999 之间的任何整数都读入内存中，并对这 250000 个整数进行排序，写到输出文件中。第二趟遍历排序 250000 至 499999 之间的整数，依此类推，到第 40 趟结束，我们已经完成了排序。这种排序的代价是要读取输入文件 40 次。而另一种解决方法就是使用位图排序。位图排序一般编程语言的 int 类型所占空间大于等于 4 字节，共 32 位。我们可以用这 32 位来表示 0 到 31 的的数字。假设有一个集合为 {0, 3, 5}，在位图里表示就是 0000101001 ，这里省去了前面 22 个 0 。一个 32 位的 int 数可以表示 32 个数字。假设总共有 100 个数，我们只需 (100/32)+1=4 个 int 整数就可以表示这 100 个数，031 储存在第 1 个 int 数，3263 储存在第 2 个 int 数。这样，存储所有数值需要的 int 个数为 10^7 / 32 = 312500, 需要总内存为312500 * 4 / 1024 / 1024 = 1.25M, 1M内存限制跑两趟就可以完成排序。位图排序实现我们可以用 3 个函数来实现位图。函数1：将所有的位都置为0，从而将集合初始化为空。函数2：通过读入文件中的每个整数来建立集合，将每个对应的位置都置为 1。函数3：检验每一位，如果该为为1，就输出对应的整数。位图操作类class BitMap: # maxval 最大值 # bitsperword 一个int数的位数 # shift 能表示 bitsperword 需要的位数, 5 位可以表示 32 这个数 # mask 能表示 bitsperword 需要的位数，用二进制表示 def init(self, maxval, bitsperword=32, shift=5, mask=0b11111): self.bitsperword = bitsperword self.shift = shift self.mask = mask # 初始化位图，相当于函数1 self.x = [0 for i in range(1 + int(maxval / bitsperword))] def set(self, i): # i>>self.shift 操作等同于 i 除于 2^self.shift # i & self.mask 操作等同于 i 对 2^self.shift 求余 # 1 << n 等同于 1 * 2^n self.x[i >> self.shift] |= (1 << (i & self.mask)) # 如果某位上有数，就返回 true def test(self, i): return self.x[i >> self.shift] & (1 << (i & self.mask))设置>>> bit = BitMap(500)>>> bit.x[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]>>> bit.x[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]# self.x[0] 的二进制为 10>>> bit.set(4)>>> bit.x[18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]# self.x[0] 的二进制为 10010输出位对应的值>>> print (bit.test(1))2排序实现def bitSort(lists, maxval): sortLists = [] bit = BitMap(maxval) for val in lists: bit.set(val) for i in range(maxval): if bit.test(i): sortLists.append(i) return sortLists排序测试>>> lists = [5, 2, 6, 8, 10, 22, 25, 44, 29, 36, 40, 3, 4, 1, 20, 27, 37]>>> print (bitSort(lists, max(lists)))[1, 2, 3, 4, 5, 6, 8, 10, 20, 22, 25, 27, 29, 36, 37, 40]位图操作的优点非常明显，内存占用非常低，非常适合在内存有限时使用。完整代码#!/bin/python# -- coding:utf-8 --class BitMap: # maxval 最大值 # bitsperword 一个int数的位数 # shift 能表示 bitsperword 需要的位数, 5 位可以表示 32 这个数 # mask 能表示 bitsperword 需要的位数，用二进制表示 def init(self, maxval, bitsperword=32, shift=5, mask=0b11111): self.bitsperword = bitsperword self.shift = shift self.mask = mask # 初始化位图，相当于函数1 self.x = [0 for i in range(1 + int(maxval / bitsperword))] def set(self, i): # i>>self.shift 操作等同于 i 除于 2^self.shift # i & self.mask 操作等同于 i 对 2^self.shift 求余 # 1 << n 等同于 1 * 2^n self.x[i >> self.shift] |= (1 << (i & self.mask)) # 如果某位上有数，就返回 true def test(self, i): return self.x[i >> self.shift] & (1 << (i & self.mask))def bitSort(lists, maxval): sortLists = [] bit = BitMap(maxval) for val in lists: bit.set(val) for i in range(maxval): if bit.test(i): sortLists.append(i) return sortListsif name == ‘main’: lists = [5, 2, 6, 8, 10, 22, 25, 44, 29, 36, 40, 3, 4, 1, 20, 27, 37] print (bitSort(lists, max(lists)))参考: 编程珠玑 ...

一. 谈谈对redis的理解，它的应用场景。Redis是一个key-value存储系统，它支持存储的value类型包括string字符串、list链表、set集合、sorted Set有序集合和hash哈希等数据类型。这些数据类型都支持push/pop、add/remove及取交集并集和差集及更丰富的操作，而且这些操作都是原子性的，支持各种不同方式的排序。为了保证效率，Redis将数据都缓存在内存中，并周期性的把更新的数据写入磁盘或者把修改操作写入追加的记录文件，在此基础上实现master-slave(主从)同步。Redis的应用场景 数据类型应用场景StringString是最常用的一种数据类型，普通的key/value存储都可以归为此类。List关注列表、粉丝列表、消息队列等。SetSet提供一个与 List类似的列表功能，特殊之处在于Set会自动排序、去重，当需要存储一个列表数据，又不希望有重复数据时，Set是一个很好的选择，并且set提供了判断某个成员是否在一个set集合内的重要接口，这个也是list所不能提供的。1.使用Set存储一些集合性的数据，比如在微博应用中，可以将一个用户所有的关注人存在一个集合中，将其所有粉丝存在一个集合；2.可以对集合取交集、并集、差集，应用到好友推荐、共同关注等。3.还可以利用唯一性，统计访问网站的所有独立IP。SortedSetSortedSet与Set的使用场景类似，是不允许重复项的String集合。1.SortedSet可以通过提供一个优先级(score)的参数为成员排序，并且是插入有序的，即自动排序，可以应用于积分排行榜等。2.如果需要一个有序且不重复的集合列表，可以选择sorted set数据结构，比如twitter 的public timeline可以以发表时间作为score来存储，这样获取时就是自动按时间排好序的。3.用SortedSet做带权重的队列，比如普通消息的score为1，重要消息的score为2，然后工作线程可以选择按score的倒序来获取工作任务，让重要的任务优先执行。Hash 存储一个学生信息对象数据，字段包括：id、姓名、班级、年龄等，通过id可以获取/修改任意的字段。二. 既然一般的语言也能支持string、list、hash等数据结构，为什么还要用redis呢？这里要先提一下内存和缓存的区别：内存是物理上的，是一种物理存储介质。缓存是逻辑上的概念，是一种数据结构，可以是PHP语言里面的一种数据结构，也可以是Redis里面的一种数据结构。比如：用PHP数组存一些数据，每次有需求就直接从数组中读取；用PHP语言设计了一个缓存，用一个数组做队列，设计了一个基于先进先出策略的缓存；调用Redis的一些数据结构来存储数据。内存叫做RAM，随机可读存储器，硬盘一般叫做ROM，随机只读存储器。缓存包括cpu的一二级缓存、纯内存结构的缓存、半内存缓存、磁盘缓存，它们的速度是一层比一层慢。当CPU要读取一个数据时，首先从一级缓存中查找，如果没有找到再从二级缓存中查找，如果还是没有就从三级缓存或内存中查找，程序里面的各种数据结构、变量等等，都是运行在内存里面，而不是在硬盘上。假设有一个场景，比如历史用户日志访问数据，就是access_log，让你去统计都有哪些用户登录了这个网站，当然现在还有用户在持续登录着。这个时候你是不是要先去从access_log里面读取日志，然后提取出日志里面的userId，存到数组里面再去重。当新用户来的时候，你只需要和你数组里面的用户进行比较即可，就不需要再读取access_log文件了。这样就不用每次读取文件，只需要读取数组即可，速度回更快。 同理用Redis，也是因为当我们需要读取数据时，先从Redis查找，如果有就直接返回，不用再从mysql查找，速度会很快。从原理上讲，PHP里面的数据结构用的是纯内存，而Redis是需要走网络的；从速度上讲，纯内存的速度肯定是比先走网络、再从内存中读取的速度快。虽然Redis作为半内存缓存，没有直接内存结构的数据结构速度快，但Redis除了数据结构丰富外，还适合高并发场景，对高并发处理效率极高，此外可以做到集群式、可持久化。三. 具体讲一下Redis的数据结构，尽可能的举出他们的应用场景。Redis支持String、List、Set、Sorted Set、Hash等。String类型是二进制安全的，可以用来缓存一些静态文件，如图片、视频、css文件等。支持incr操作，可以用作计数器，比如统计网站访问次数等。微博中“关注、粉丝”、论坛中所有回帖的ID用的就是list列表，还有消息队列，也是列表。Set可以快速查找元素是否存在，用于记录一些不能重复的数据。例如： 在网站注册账号时，用户名不能重复，使用Set记录注册用户，如果注册的用户名已经存在于Set中，就拒绝该用户注册。或者用于记录做过某些事情。例如： 在某些投票系统中，每个用户一天只能投票一次，就可以用Set来记录某个用户的投票情况。Set能做的事Sorted Set也能做，Sorted Set还能完成一些Set不能做的事情。例如：使用Sorted Set构建一个具有优先级的队列。Hash适用于存储对象，比如把用户的信息存到hash里，以用户id为key，用户的详细信息为value。

这篇文章主要是介绍KMP模式匹配算法，在正式介绍KMP之前我们先看一下普通模式匹配，由普通模式匹配在进一步的推导KMP模式会更容易理解。字符串的普通模式匹配普通模式匹配的原理不进行说明了，简单来说就是两个字符串的每个字符依次进行匹配。public int match(String S,String T){ int i = 0; int j = 0; while(i < S.length() && j < T.length()){ if(S.charAt(i) == T.charAt(j)){ i++; j++; }else{ i = i - j + 1; j = 0; } } if(j >= T.length()){ return i - T.length(); }else{ return 0; }}普通模式匹配的时间复杂度最坏的情况（即T在S的末尾）为O（(m-n+1)*n）。这种算法的优点是实现简单，缺点也显而易见那就是效率较低。jdk String类内的静态方法indexOf底层使用的就是类似该种算法。KMP模式匹配算法推导回溯推导为了方便理解KMP模式，我们先看一下普通模式模式的流程：栗子1：主串：S = “abcdefgab"子串：T = “abcdex"观察下普通模式匹配算法，对于要匹配的子串T = “abcdex”来说首字母"a"与后面的串"bcdex"中的任意一个字符都不相等;串"bcde"与主串S的第2-5位相等，那么首字母"a"就不可能与主串S的第2-5位相等。所以，第2 3 4 5 的判断都是不需要的，这是个理解KMP模式的关键。那么问题来了，如果T串后面还含有首字母"a"的字符会怎么样呢？我们在看一个例子：粟子2：主串：S = “abcabcabc"子串：T = “abcabx”对于要比配的子串T = “abcabx"来说，T的首字母"a"与T的第2个字符"b”、第3个字符"c"均不等，且T的第1-3位字符与主串S的第1-3相等，所以，步骤2和步骤3可以省略；T的前2位串"ab"与T的第4-5串"ab"相等，且T的第4-5串"ab"与主串S的第4-5串"ab"相等，得出T的前2位串与S的第4-5也相等，可以省略。最后，第6步的前两次比较也是不需要的，直接比较 主串S的第6位的"a"和子串T的第3位"c"即可，如下图：对比这两个例子，可以发现普通模式主串S的游标每次都是回溯到i++的位置。而经过上面的分析后发现，这种回溯方式其实是不需要的，KMP模式就是解决了这些没有必要的回溯。既然要避免i的回溯，那么我们就要在子串T的游标j上下工夫了。通过观察也可发现，如果T的首字母与自身后面的字符有相等的情况，那j值的变化就会不相同。例子1内j的变化，由于首字母"a"与后面的字符都不相等，则j由6变回了1。例子2内j的变化，由于前缀"ab"与后面的"ab"相等，因此j从6变回了3。有没有看出什么规律？提示一下：例子1内与前缀相同的字符个数为0，j变成了1。例子2内与前缀相同的字符个数为2，j变成了3。j的变化取决也当前字符之前的串的前后缀的相似度。回溯公式根据上一节的推导，我们可以将T串各个位置的j的变化定义为一个数组next，next的长度就是T串的长度，我们可以得到下面的函数定义（为了后面读程序方便理解，所以该函数是遵循数组下标从0开始的规范）：我们来手工验证一下该函数。T = “abcdex"j123456模式串Tabcdexnext[j]000000if j = 0, next[0] = 0;if j = 1, ‘p0 … pk’ = ‘pj-k … pj’ –> ‘a’ <> ‘b’ ,next[1] = 0;if j = 2, 子串"abc”，也没有重复的字符子串，next[2] = 0;以后同理，所以最终T串的ntxt[j]为000000。例子就列举到这里，现在放下KMP的Java实现，其它实例大家可以使用程序进行验证。KMP模式匹配算法实现public void getNext(String T,Integer[] next){ next[0] = 0; //当j = 0时，next[0] = 0 int i = 1; int j = 0; int k = 0; while (i < T.length() && j < i){ if(T.substring(0,j).equals(T.substring(i-j,i))){ k = j; //若有相同子串，则记录下对应在T串内的位置，最终得出最长匹配成功的位置 } j++; if(j >= i){ next[i] = k; //若一直未匹配成功，将k = 0赋值给next[i] j = 1; k = 0; i++; } }}我们来测试 几个字符串：input: abcdexoutput:000000input: abcabxoutput:000012input: aaaaaaaaboutput:001234567下面是完整的KMP模式匹配算法的代码：package string;public class KMPMatch { public void getNext(String T,Integer[] next){ next[0] = 0; //当j = 0时，next[0] = 0 int i = 1; int j = 0; int k = 0; while (i < T.length() && j < i){ if(T.substring(0,j).equals(T.substring(i-j,i))){ k = j; //若有相同子串，则记录下对应在T串内的位置，最终得出最长匹配成功的位置 } j++; if(j >= i){ next[i] = k; //若一直未匹配成功，将k = 0赋值给next[i] j = 1; k = 0; i++; } } } public int match(String S,String T){ int i = 0; int j = 0; Integer[] next = new Integer[T.length()]; getNext(T,next); while(i < S.length() && j < T.length()){ if(j == 0 || S.charAt(i) == T.charAt(j)){ i++; j++; }else{ j = next[j]; } } if(j >= T.length()){ return i - T.length(); }else{ return 0; } } public static void main(String[] args) { String S = “aaaabcde”; String T = “abcd”; System.out.println(new KMPMatch().match(S,T)); }}对于方法getNext来说，若T的长度为m，因只涉及简单的单循环，其时间复杂度为O(m)，由于i不进行回溯，while循环的时间复杂度为O(n)。因此，整个算法的时间复杂度为O(m+n)。对于KMP模式来说，仅当子串与主串之前存在许多“部分匹配”的时候才体现出它的优势，否则两者差异并不明显。KMP模式匹配算法的优化看下面这个例子：S = “aaaabcde"T = “aaaaax"T的next分别为001234，两个串的匹配流程如下：从流程中可发现，当中的步骤2 3 4 5都是多余的判断。由于T串的第2 3 4 5位置的字符都与首字符相等，那么就可以用首位next[0]值去取代与它相等的字符的next[j]，下面就是对getNext方法进行的改良，代码如下：public void getNextVal(String T,Integer[] nextVal){ nextVal[0] = 0; //当j = 0时，next[0] = 0 int i = 1; int j = 0; int k = 0; while (i < T.length() && j < i){ if(T.substring(0,j).equals(T.substring(i-j,i))){ k = j; //若有相同子串，则记录下对应在T串内的位置，最终得出最长匹配成功的位置 } j++; if(j >= i){ //当前字符与前缀字符相同中，则当前字符j为nextVal[i] if(T.charAt(i) == T.charAt(k)){ nextVal[i] = nextVal[k]; }else { nextVal[i] = k; } j = 1; k = 0; i++; } }}学习是一个过程，对学习到的知识进行理解、吸收、整理，并将其按自己的理解进行输出。参考材料：《大话数据结构》 ...

（一）数据结构绪论数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。1.1 基本概念和术语数据 是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据元素 是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。数据项 一个数据元素可以由若干个数据组成。是数据不可分割的最小单位。数据对象 是性质相同的数据元素的集合，是数据的子集。图解 PS:数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。1.2 逻辑结构和物理结构逻辑结构 是指数据对象中数据元素之间的相互关系。1 集合结构 集合结构中的数据元素除了同属于同一个集合外，它们之间没有其他关系。2 线性结构 线性结构中的数据元素之间是一对一的关系。3 树形结构 树形结构中的数据元素之间存在一种一对多的层次关系。4 图形结构 图形结构中的数据元素是多对多的关系。物理结构 是指数据的逻辑结构在计算机中的存储形式。（也叫存储结构）1 顺序存储结构 是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。2 链式存储结构 是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。PS：1 数据元素的存储关系并不能反映其逻辑关系。2 逻辑结构是面向问题的，而逻辑结构就是面向计算机的，其基本的目标就是讲数据及其逻辑关系存储到计算机的内存中。1.3 数据类型数据类型 是指一组性质相同的值得集合及定义在此集合上的一些操作的总称。原子类型 是不可以再分解的基本类型，包括整型、实型、字符型等。结构类型 是由若干个类型组合而成，是可以再分解的。如，整型数组是由若干整型数据组成的。抽象数据类型 是指一个数学模型及定义在该模型上的一组操作。（面向对象）

本文介绍了深入理解ES6之数据解构的用法，写的十分的全面细致，具有一定的参考价值，对此有需要的朋友可以参考学习下。如有不足之处，欢迎批评指正。一 对象解构对象解构语法在赋值语句的左侧使用了对象字面量let node = { type: true, name: false} //既声明又赋值let { type, name} = node; //或者先声明再赋值let type, name({type,name} = node);console.log(type);//trueconsole.log(name);//falsetype与name标识符既声明了本地变量，也读取了对象的相应属性值。解构赋值表达式的值为表达式右侧的值。当解构表达式的右侧的计算结果为null或者undefined时，会抛出错误。默认值当你使用解构赋值语句时，如果所指定的本地变量在对象中没有找到同名属性，那么该变量会被赋值为undefinedlet node = { type: true, name: false}, type, name, value;({type,value,name} = node); console.log(type);//trueconsole.log(name);//falseconsole.log(value);//undefined//欢迎加入前端全栈开发交流圈一起吹水聊天学习交流：864305860你可以选择性地定义一个默认值，以便在指定属性不存在时使用该值。let node = { type: true, name: false }, type, name, value;({ type, value = true, name} = node); console.log(type);//trueconsole.log(name);//falseconsole.log(value);//true//欢迎加入前端全栈开发交流圈一起吹水聊天学习交流：864305860赋值给不同的本地变量名let node = { type: true, name: false, value: “dd”}let { type: localType, name: localName, value: localValue = “cc”} = node;console.log(localType);console.log(localName);console.log(localValue);type:localType这种语法表示要读取名为type的属性，并把它的值存储在变量localType上。该语法与传统对象字面量的语法相反嵌套的对象结构let node = {type: “Identifier”,name: “foo”,loc: { start: { line: 1, column: 1 }, end: { line: 1, column: 4 }//欢迎加入前端全栈开发交流圈一起吹水聊天学习交流：864305860}} let {loc: localL,loc: { start: localS, end: localE}} = node; console.log(localL);// start: {line: 1,column: 1},end: {line: 1,column: 4}console.log(localS);//{line: 1,column: 1}console.log(localE);//{line: 1,column: 4}//欢迎加入前端全栈开发交流圈一起吹水聊天学习交流：864305860当冒号右侧存在花括号时，表示目标被嵌套在对象的更深一层中（loc: {start: localS,end: localE}）二 数据解构数组解构的语法看起来跟对象解构非常相似，只是将对象字面量换成了数组字面量。let colors = [“red”, “blue”, “green”];let [firstC, secondC, thirdC, thursC = “yellow”] = colors;console.log(firstC//redconsole.log(secondC);//blueconsole.log(thirdC);//greenconsole.log(thursC);//yellow//欢迎加入前端全栈开发交流圈一起吹水聊天学习交流：864305860你也可以在解构模式中忽略一些项，并只给感兴趣的项提供变量名。let colors = [“red”,“green”,“blue”]; let [,,thirdC] = colors;console.log(thirdC);//blue//欢迎加入前端全栈开发交流圈一起吹水聊天学习交流：864305860thirdC之前的逗号是为数组前面的项提供的占位符。使用这种方法，你就可以轻易从数组任意位置取出值，而无需给其他项提供名称。解构赋值let colors = [“red”,“green”,“blue”], firstColor = “black”, secondColor = “purple”;[firstColor,secondColor] = colors;console.log(firstColor);//redconsole.log(secondColor);//green//欢迎加入前端全栈开发交流圈一起吹水聊天学习交流：864305860数组解构有一个非常独特的用例，能轻易的互换两个变量的值let a =1,b =2;[a,b] = [b,a];console.log(a);//2console.log(b);//1//欢迎加入前端全栈开发交流圈一起吹水聊天学习交流：864305860嵌套的解构let colors = [“red”, [“green”, “blue”], “yellow”];let [firstC, [, ssc]] = colors;console.log(ssc);//blue剩余项let colors = [“red”, “green”, “blue”];let [firstC, …restC] = colors;console.log(firstC);console.log(…restC);console.log(restC[0]);//greenconsole.log(restC[1]);//blue使用剩余项可以进行数组克隆let colors = [“red”, “green”, “blue”];let […restC] = colors;console.log(restC);//[“red”, “green”,“blue”]三 混合解构let node = {type: “Identifier”,name: ‘foo’,loc: { start: { line: 1, column: 1 }, end: { line: 1, column: 4 }//欢迎加入前端全栈开发交流圈一起吹水聊天学习交流：864305860},range: [0, 3]} let {type,name: localName,loc: { start: { line: ll }, end: { column: col }},range: [, second]} = node; console.log(type);//Identifierconsole.log(localName);//fooconsole.log(ll);//1console.log(col);//4console.log(second);//3结语感谢您的观看，如有不足之处，欢迎批评指正。 ...

题目操作给定的二叉树，将其变换为源二叉树的镜像。二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5题解首先先理解题意,镜像通过以下几个步骤可以实现：可以看到首先对根节点的左右进行翻转。再递归的对左子树，以及右子树进行翻转。之前讲过，链表的题目分为四个步骤：连过来、指针走、断后路、调状态。二涉及到树的题目，基本都是递归。一旦涉及到递归，就要搞清楚两个东西：递归的过程。在这里就是，先翻转根节点，再翻转左子树，再翻转右子树。递归结束的条件。 这里就是当树为Null的时候不翻转。public class Solution { public void Mirror(TreeNode root) { // 递归结束条件 if (root == null) return; // 交换左右 TreeNode temp = root.left; root.left = root.right; root.right = temp; // 递归 Mirror(root.left); Mirror(root.right); }}同时一般，我们会有一些边界case去检查一下代码的鲁棒性。比如左右有一个是null 8 / \ 10 Null / \ null null 代码执行到交换没啥问题： 8 / \ Null 10 / \ null null执行到递归，左子树就结束掉了。右子树的话还要递归的执行左右子树，也可以执行正确，但是其实没必要。public class Solution { public void Mirror(TreeNode root) { // 递归结束条件 if (root == null) return; if (roo.left == null && root.left == null) return; // 交换左右 TreeNode temp = root.left; root.left = root.right; root.right = temp; // 递归 Mirror(root.left); Mirror(root.right); }}热门阅读【Leetcode】175. 组合两个表jvm类加载机制学习资料推荐 ...

前言区块链太复杂，那我们就讲点简单的。用JS来构建你自己的区块链系统，寥寥几行代码就可以说明区块链的底层数据结构，POW挖矿思想和交易过程等。当然了，真实的场景远远远比这复杂。本文的目的仅限于让大家初步了解，初步认识区块链。文章内容主要参考视频：使用Javascript建立区块链（https://www.youtube.com/playlist?list=PLzvRQMJ9HDiTqZmbtFisdXFxul5k0F-Q4）感谢原作者，本文在原视频基础上做了修改补充，并加入了个人理解。认识区块链区块链顾名思义是由区块连接而成的链，因此最基本的数据结构是块。每个块都含有时间戳，数据，散列，previousHash等信息。其中数据用来存储数据，previousHash是前一个区块的哈希值示意如下：哈希是对区块信息的摘要存储，哈希的好处是任意长度的信息经过哈希都可以映射成固定长度的字符串，如可用SHA256：calculateHash() { return SHA256(this.previousHash + this.timestamp + JSON.stringify(this.data)).toString();}块的数据结构块的最基本数据结构如下：class Block { constructor(timestamp, data, previousHash = ‘’) { this.timestamp = timestamp; this.data = data; this.previousHash = previousHash; //对hash的计算必须放在最后，保证所有数据赋值正确后再计算 this.hash = this.calculateHash(); } calculateHash() { return SHA256(this.previousHash + this.timestamp + JSON.stringify(this.data)).toString(); }}BlockChain的数据结构多个区块链接而成BlockChain，显然可用用数组或链表来表示，如：class BlockChain { constructor() { this.chain = []; }}创世区块正所谓万物始于一，区块链的第一个区块总是需要人为来手动创建，这个区块的previousHash为空，如：createGenesisBlock() { return new Block(“2018-11-11 00:00:00”, “Genesis block of simple chain”, “”);}区块链的构造方法也应改为：class BlockChain { constructor() { this.chain = [this.createGenesisBlock()]; }}添加区块每新加一个区块，必须保证与原有区块链连接起来，即：class BlockChain { getLatestBlock() { return this.chain[this.chain.length - 1]; } addBlock(newBlock) { //新区块的前一个hash值是现有区块链的最后一个区块的hash值； newBlock.previousHash = this.getLatestBlock().hash; //重新计算新区块的hash值（因为指定了previousHash)； newBlock.hash = newBlock.calculateHash(); //把新区块加入到链中； this.chain.push(newBlock); } …}校验区块链区块链数据结构的核心是保证前后链接，无法篡改，但是如果有人真的篡改了某个区块，我们该如何校验发现呢？最笨也是最自然是想法就是遍历所有情况，逐一校验，如：isChainValid() { //遍历所有区块 for (let i = 1; i < this.chain.length; i++) { const currentBlock = this.chain[i]; const previousBlock = this.chain[i - 1]; //重新计算当前区块的hash值，若发现hash值对不上，说明该区块有数据被篡改，hash值未重新计算 if (currentBlock.hash !== currentBlock.calculateHash()) { console.error(“hash not equal: " + JSON.stringify(currentBlock)); return false; } //判断当前区块的previousHash是否真的等于前一个区块的hash，若不等，说明前一个区块被篡改，虽然hash值被重新计算正确，但是后续区块的hash值并未重新计算，导致整个链断裂 if (currentBlock.previousHash !== previousBlock.calculateHash) { console.error(“previous hash not right: " + JSON.stringify(currentBlock)); return false; } } return true;}跑吧跑起来看看，即：let simpleChain = new BlockChain();simpleChain.addBlock(new Block(“2018-11-11 00:00:01”, {amount: 10}));simpleChain.addBlock(new Block(“2018-11-11 00:00:02”, {amount: 20}));console.log(JSON.stringify(simpleChain, null, 4));console.log(“is the chain valid? " + simpleChain.isChainValid());结果如下：ali-186590cc4a7f:simple-chain shanyao$ node main_1.js { “chain”: [ { “timestamp”: “2018-11-11 00:00:00”, “data”: “Genesis block of simple chain”, “previousHash”: “”, “hash”: “fd56967ff621a4090ff71ce88fdd456547d1c92d2e93766b7e8791f7a5f91f89” }, { “timestamp”: “2018-11-11 00:00:01”, “data”: { “amount”: 10 }, “previousHash”: “fd56967ff621a4090ff71ce88fdd456547d1c92d2e93766b7e8791f7a5f91f89”, “hash”: “150b196268a0152e9f0e719ac131a722472a809f49bd507965029a78c7400529” }, { “timestamp”: “2018-11-11 00:00:02”, “data”: { “amount”: 20 }, “previousHash”: “150b196268a0152e9f0e719ac131a722472a809f49bd507965029a78c7400529”, “hash”: “274a7a13ed20118e8cb745654934a7e24a4d59333ba17dfbf5d4cfe0fa8a6e34” } ]}is the chain valid? true注意看其中的previousHash与哈希，确实是当前区块的previousHash指向前一个区块的哈希值。篡改下试试都说区块链不可篡改，是真的吗让我们篡改第2个区块试试，如？let simpleChain = new BlockChain();simpleChain.addBlock(new Block(“2018-11-11 00:00:01”, {amount: 10}));simpleChain.addBlock(new Block(“2018-11-11 00:00:02”, {amount: 20}));console.log(“is the chain valid? " + simpleChain.isChainValid());//将第2个区块的数据，由10改为15simpleChain.chain[1].data = {amount: 15};console.log(“is the chain still valid? " + simpleChain.isChainValid());console.log(JSON.stringify(simpleChain, null, 4));结果如下：ali-186590cc4a7f:simple-chain shanyao$ node main_1.js is the chain valid? truehash not equal: {“timestamp”:“2018-11-11 00:00:01”,“data”:{“amount”:15},“previousHash”:“fd56967ff621a4090ff71ce88fdd456547d1c92d2e93766b7e8791f7a5f91f89”,“hash”:“150b196268a0152e9f0e719ac131a722472a809f49bd507965029a78c7400529”}is the chain still valid? false{ “chain”: [ { “timestamp”: “2018-11-11 00:00:00”, “data”: “Genesis block of simple chain”, “previousHash”: “”, “hash”: “fd56967ff621a4090ff71ce88fdd456547d1c92d2e93766b7e8791f7a5f91f89” }, { “timestamp”: “2018-11-11 00:00:01”, “data”: { “amount”: 15 }, “previousHash”: “fd56967ff621a4090ff71ce88fdd456547d1c92d2e93766b7e8791f7a5f91f89”, “hash”: “150b196268a0152e9f0e719ac131a722472a809f49bd507965029a78c7400529” }, { “timestamp”: “2018-11-11 00:00:02”, “data”: { “amount”: 20 }, “previousHash”: “150b196268a0152e9f0e719ac131a722472a809f49bd507965029a78c7400529”, “hash”: “274a7a13ed20118e8cb745654934a7e24a4d59333ba17dfbf5d4cfe0fa8a6e34” } ]}显然，篡改了数据之后，哈希值并未重新计算，导致该区块的哈希值对不上。再篡改下试试那么，如果我们聪明点，篡改后把哈希值也重新计算会如何？let simpleChain = new BlockChain();simpleChain.addBlock(new Block(“2018-11-11 00:00:01”, {amount: 10}));simpleChain.addBlock(new Block(“2018-11-11 00:00:02”, {amount: 20}));console.log(“is the chain valid? " + simpleChain.isChainValid());//篡改后重新计算hash值simpleChain.chain[1].data = {amount: 15};simpleChain.chain[1].hash = simpleChain.chain[1].calculateHash();console.log(“is the chain still valid? " + simpleChain.isChainValid());console.log(JSON.stringify(simpleChain, null, 4));结果如下：ali-186590cc4a7f:simple-chain shanyao$ node main_1.js is the chain valid? trueprevious hash not right: {“timestamp”:“2018-11-11 00:00:02”,“data”:{“amount”:20},“previousHash”:“150b196268a0152e9f0e719ac131a722472a809f49bd507965029a78c7400529”,“hash”:“274a7a13ed20118e8cb745654934a7e24a4d59333ba17dfbf5d4cfe0fa8a6e34”}is the chain still valid? false{ “chain”: [ { “timestamp”: “2018-11-11 00:00:00”, “data”: “Genesis block of simple chain”, “previousHash”: “”, “hash”: “fd56967ff621a4090ff71ce88fdd456547d1c92d2e93766b7e8791f7a5f91f89” }, { “timestamp”: “2018-11-11 00:00:01”, “data”: { “amount”: 15 }, “previousHash”: “fd56967ff621a4090ff71ce88fdd456547d1c92d2e93766b7e8791f7a5f91f89”, “hash”: “74d139274fb692495b7c805dd5822faa0c5b5e6058b6beef96e87e18ab83a6b1” }, { “timestamp”: “2018-11-11 00:00:02”, “data”: { “amount”: 20 }, “previousHash”: “150b196268a0152e9f0e719ac131a722472a809f49bd507965029a78c7400529”, “hash”: “274a7a13ed20118e8cb745654934a7e24a4d59333ba17dfbf5d4cfe0fa8a6e34” } ]}显然，第3个区块的previousHash并未指向第2个区块的哈希值。是真的无法篡改吗其实并不是，如果我们再聪明一点，把后续区块的哈希值也重新计算一下，不就OK了吗？确实如此，如：let simpleChain = new BlockChain();simpleChain.addBlock(new Block(“2018-11-11 00:00:01”, {amount: 10}));simpleChain.addBlock(new Block(“2018-11-11 00:00:02”, {amount: 20}));console.log(“is the chain valid? " + simpleChain.isChainValid());//篡改第2个区块simpleChain.chain[1].data = {amount: 15};simpleChain.chain[1].hash = simpleChain.chain[1].calculateHash();//并把第3个区块也重新计算simpleChain.chain[2].previousHash = simpleChain.chain[1].hash;simpleChain.chain[2].hash = simpleChain.chain[2].calculateHash();console.log(“is the chain still valid? " + simpleChain.isChainValid());console.log(JSON.stringify(simpleChain, null, 4本文作者：扁鹊他大哥阅读原文本文为云栖社区原创内容，未经允许不得转载。 ...

题目假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。示例 1:输入: nums = [2,5,6,0,0,1,2], target = 0输出: true示例 2:输入: nums = [2,5,6,0,0,1,2], target = 3输出: false进阶:这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？题解这道题与之前Search in Rotated Sorted Array类似，问题只在于存在dupilcate。那么和之前那道题的解法区别就是，不能通过比较A[mid]和边缘值来确定哪边是有序的，会出现A[mid]与边缘值相等的状态。当中间值与边缘值相等时，让指向边缘值的指针分别往前移动，忽略掉这个相同点，再用之前的方法判断即可。而如果解决掉重复之后，利用一个性质，旋转后两部分一定有一部分有序(自己找两个例子画画看)，那么通过判断左边还是右边有序分为两种情况。然后再判断向左走还是向右走。这一改变增加了时间复杂度，试想一个数组有同一数字组成{1，1，1，1，1}，target=2, 那么这个算法就会将整个数组遍历，时间复杂度由O(logn)升到O(n)。javaclass Solution { public boolean search(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) return true; if (nums[mid] == nums[left]) left++; //重复了，跳过 else if (nums[mid] > nums[left]) { //左边有序 if (nums[mid] > target && nums[left] <= target) right = mid - 1; else left = mid + 1; } else { //右边有序 if (nums[mid] < target && nums[right] >= target) left = mid + 1; else right = mid - 1; } } return false; }}pythonclass Solution: def search(self, nums, target): """ :type nums: List[int] :type target: int :rtype: bool """ left = 0 right = len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return True # 重复了，跳过 if nums[mid] == nums[left]: left += 1 elif nums[mid] > nums[left]: if nums[mid] > target >= nums[left]: right = mid - 1 else: left = mid + 1 else: if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1 return False相关阅读【设计模式】单例模式布隆过滤器 ...

HTTP【HTTP】分布式session的管理【HTTP】Cookie和Session【HTTP】当我在谈论RestFul架构时我在谈啥？【HTTP】HTTP状态码详解【HTTP】无状态协议和Cookie【HTTP】HTTP请求支持哪些方法？【HTTP】分层协议栈Redis【redis】Redis有哪些数据结构Java【java】CyclicBarrier【java】CountDownLatch运用场景（1）说说你常用的linux命令?【java】为什么要有包装类【java】面向对象的特征是啥？spring【Spring】IOC是啥有什么好处系统设计【工程】在线诊断系统设计与实现mysqlMySQL索引背后的数据结构及算法原理软技能时间管理，这篇文章就够了！程序员实习（初入职场）怎么最大限度提高自己？看了很多技术书，为啥仍然写不出项目？机器学习相关就业会达到饱和吗？Leetcode题解【Leetcode】79.单词搜索【Leetcode】78. 子集【Leetcode】77. 组合【Leetcode】76. 最小覆盖子串【Leetcode】75.颜色分类【Leetcode】74. 搜索二维矩阵【Leetcode】73.矩阵置零【Leetcode】72.编辑距离【Leetcode】71. 简化路径【Leetcode】70. 爬楼梯【Leetcode】69. x 的平方根【Leetcode】67. 二进制求和【Leetcode】66. 加一【Leetcode】65. 有效数字【Leetcode】64. 最小路径和【Leetcode】63. 不同路径 II【Leetcode】62. 不同路径【Leetcode】61.旋转链表【Leetcode】60. 第k个排列【Leetcode】59. 螺旋矩阵 II【Leetcode】58. 最后一个单词的长度【Leetcode】57. 插入区间【Leetcode】56. 合并区间【Leetcode】55. 跳跃游戏【Leetcode】54. 螺旋矩阵【Leetcode】53. 最大子序和【Leetcode】52. N皇后 II【Leetcode】51. N皇后【Leetcode】50.求x的n次方【Leetcode】49. 字母异位词分组【LeetCode】48. 旋转图像【Leetcode】47. 全排列 II【Leetcode】46.全排列【Leetcode】45. 跳跃游戏 II【Leetcode】44. 通配符匹配【Leetcode】43. 字符串相乘【Leetcode】42. 接雨水【Leetcode】41. 缺失的第一个正数【Leetcode】40.组合总和 II【Leetcode】39. 组合总和【Leetcode】38. 报数【Leetcode】37. 解数独【Leetcode】36. 有效的数独【Leetcode】35. 搜索插入位置【Leetcode】34. 在排序数组中查找元素的第一个和最后一个位置【Leetcode】33. 搜索旋转排序数组【Leetcode】32. 最长有效括号【Leetcode】31. 下一个排列【Leetcode】30.与所有单词相关联的字串【Leetcode】29. 两数相除【Leetcode】28. 实现strStr()【Leetcode】27.移除元素【Leetcode】26. 删除排序数组中的重复项【Leetcode】25. k个一组翻转链表【Leetcode】24. 两两交换链表中的节点【Leetcode】23. 合并K个排序链表【Leetcode】22. 括号生成【Leetcode】21. 合并两个有序链表【Leetcode】20. 有效的括号【Leetcode】19. 删除链表的倒数第N个节点【Leetcode】18. 四数之和【Leetcode】17. 电话号码的字母组合【Leetcode】16. 最接近的三数之和【Leetcode】15. 三数之和【Leetcode】14. 最长公共前缀【Leetcode】13. 罗马数字转整数【Leetcode】12. 整数转罗马数字【Leetcode】11. 盛最多水的容器【Leetcode】10. 正则表达式匹配【Leetcode】9. 回文数【Leetcode】8. 字符串转整数 (atoi)【Leetcode】7. Reverse Integer【Leetcode】6. Z字形变换【Leetcode】5. Longest Palindromic Substring【Leetcode】4. 两个排序数组的中位数【Leetcode】3. Longest Substring Without Repeating Characters【Leetcode】2. Add Two Numbers【Leetcode】1. Two Sum ...