整个面试分为三个部分： 1、自我介绍、项目介绍 自我介绍随便说说就行，主要还是项目介绍，我的三个项目都讲了。 2、专业知识提问 2.1 虚函数与纯虚函数的区别。 2.2 ping的原理 2.3 TCP的三次握手和四次告别。 2.4 STL的底层实现，和为什么要这么实现。 2.5 HDFS的原理 2.6 MapReduce的原理 2.7 是否了解关系型数据库和非关系型数据库 2.8 Hash的原理 3、算法题 判断两个字符串是否同构。 考察方式：在网页的白板上打代码，主要是看思路。

杨辉三角的数字和二项式展开的系数有对应关系，如下图： 通过二项式定理：,我们可以用杨辉三角形的性质来求组合数。时间复杂度O（n^2） int n; ll c[maxn][maxn]; void init(){ for(int i = 0;i <= n;i++){ c[i][0] = 1; for(int j = 1;j <= i;j++){ c[i][j] = (c[i-1][j-1]+c[i-1][j])%mod; } } } 还有一个O（n）的算法，运用性质：，可以算出指定...

ps：学习AC自动机的时候必须先点亮KMP和字典树的技能点。 步骤： 1.将所有模式串建立一个字典树。 2.对字典树建立失配边。 3.用目标串与字典树进行匹配。 写法： 现在通用的AC自动机写法有两类：1.数组。2.指针。（也有把这两种结合到一起的写法） 指针比较直观，但是做有的题时不好操作；数组相对抽象些，但是适用范围广。我用的是数组的写法，借鉴的是kuangbin大神的板子。 例子： 举个例子，有模式串：she  he  say  shr  her 目标串：yasherhs 现在我们要用这5个模式串建立字典树，并构建失...

单调栈就是一个栈里面要么全放升序的值，要么全是降序的值。 可以做下这道题加深理解：HDU 1506 https://vjudge.net/problem/HDU-1506 题解可以看“李二娃的博客”，里面有详细的debug过程，很直观。 https://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html   HDU 1506 AC代码： #include <iostream> #include <stack> #include <cmath> usi...

RMQ用于求区间最值问题。需要O(nlogn)的预处理时间，查询时间为O(1)，用于解决大量查询的时间复杂度优化，是一个很简单的算法，思路很好想，代码也不长，很好写。   在讲解之前需要注意的点： 1.数组下标从0开始。 2. i 代表的是长度下标， j 代表的是2的幂数，2^j 代表下标。   附下图（我临摹地可能不好额emmmm） d[i][j]表示从i开始的，长度为2^j的一段元素中的最值。 递推公式：d[i][j] = min(d[i][j-1] , d[i+2^(j-1)][j-1]) 由于 2^j <= n，所以j <= logn，可以推出d数组的...

看了一天终于把”懵逼武士“入门了，那些大佬们都太强了。 学习moblus必须耐心看数学公式和推算证明，如果不能做到这点最好先放一放，提高一下数学思维再来学习。 需要明确的是莫比乌斯反演是一种类似“逆”的东西，正着做题不好解，但是逆向思考就很简单了。 对于莫比乌斯反演的学习网上有很多博客，但是有的讲得不是很好，我把我认为讲得很好的链接放在下面，可以方便读者更快地学习。（我的推荐有两个链接，第一个是博客，第二个是ppt，博客中有关于反演证明的详细解释，很赞。） https://blog.bluefissure.com/2016/08/19/e8-8e-ab-e6-af-94-e4-b9-8...

ps：学习AC自动机的时候必须先点亮KMP和字典树的技能点。 步骤： 1.将所有模式串建立一个字典树。 2.对字典树建立失配边。 3.用目标串与字典树进行匹配。 写法： 现在通用的AC自动机写法有两类：1.数组。2.指针。（也有把这两种结合到一起的写法） 指针比较直观，但是做有的题时不好操作；数组相对抽象些，但是适用范围广。我用的是数组的写法，借鉴的是kuangbin大神的板子。 例子： 举个例子，有模式串：she  he  say  shr  her 目标串：yasherhs 现在我们要用这5个模式串建立字典树，并构建失配边。如下图： 代码：（对AC自动机的解释都...

码片是一个8bit的码片。 #include <iostream> #include <vector> using namespace std; //正交码结构体 struct Chips{ int my_chip[8];//原始码片 int chips[256][8];//正交码片 }cp; int t = 0;//正交码片个数 bool judge(int *chip1, int *chip2){//判断是否正交 int sum = 0; for(int i = 0; i < 8; i++){ sum += chip1[i]+c...

首先我们来安装python 1、首先进入网站下载：点击打开链接（或自己输入网址https://www.python.org/downloads/），进入之后如下图，选择图中蓝色圈中区域进行下载。     2、下载完成后如下图所示       3、双击exe文件进行安装，如下图，并按照圈中区域进行设置，切记要勾选打钩的框，然后再点击Customize installation进入到下一步： 4、对于上图中，可以通过Browse进行自定义安装路径，也可以直接点击Install进行安装，点击install后便可以完成安装了。 5、为了检查我们的python是否...

一.目的： 1.搭建hadoop集群，集群中有3台机器，让它们在一个环回网络中，分别是： 192.168.1.2 master 192.168.1.3 slave1 192.168.1.4 slave2 2.其中master是主机，slave1和slave2是活动节点，实现免密码互通。 3.在master中安装eclipse，在eclips中配置hadoop。 二.搭建步骤： 1.安装VM，这个网上有许多教程，就不在这里浪费时间了。 2.下载centos7的镜像，在官网上下载就行了。 3.安装centos7，注意在选择SOFTWARE（软件）时选择带图形化界面的推荐选择KD...

声明    ： 仅一张图片转载于http://www.cnblogs.com/shuaiwhu/archive/2012/04/22/2464583.html，自己画太麻烦了。。。那个博客的讲解也很好，只是他用了指针的方式来定义线段树，而我用了结构体，并且他讲了线段树的更高级的操作，若对线段树的初级操作不理解，请继续阅读 线段树作为一种十分常用的数据结构，在NOIP、NOI中广泛的出现，所以在这里对线段树进行简单的讲解。     线段树支持对一个数列的求和、单点修改、求最值（最大、最小）、区间修改（需要lazy标记，暂不讲解）。这几种操作，时间复杂度是（logn）级别的，是一种十分优秀的...

#include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; int n,m;//节点数和边数 int dis[105];//记录每个点到源点的距离 int mapi[105][105];//记录边 int vis[105];//记录这个点是否被选中过 void dijkstra(int s){//s是源点 memset(dis,INF,sizeof(dis)); memset(vis,0,sizeof(vis)); int start = s; vis[start] = 1...

  史上题面最短的题但是题目标题很长并且这题可能很简单也可能很难 描述   输入   多组输入，每组输入一个整数k(0<=k<=3000) 输出   每组输出一个数：2^k 输入样例 1 2 输出样例 1 4 import java.math.*; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); while(cin.hasNext(...

第一种多组输入模板格式： while True:     try:         caption = list(map(int, input().split()))         ans = 0         for i in caption:             ans += i         print(ans)     except EOFError:         break 第一种模板适合那些没有告诉有多少组数据，只是让你不断地输入，典型的题型如A+B问题。 第二种有限输入模板格式： T = int(input()) for case in range(T): ...