微软面试题解析：栈的push、pop序列（栈）

2017年02月05日 35 阅读

微软面试题解析：栈的push、pop序列（栈）2014-12-25题目：输入两个整数序列。其中一个序列表示栈的push顺序，判断另一个序列有没有可能是对应的pop顺序。为了简单起见，我们假设push序列的任意两个整数都是不相等的。比如：输入的push序列是1，2，3，4，5 ，那么4，5，3，2，1就有可能是一个pop序列。因为可以有如下的push和pop序列：push 1, push 2, push 3, push 4, pop, push 5, pop...

微软面试题解析：整数的二进制表示中1的个数

2017年02月05日 36 阅读

微软面试题解析：整数的二进制表示中1的个数2014-12-25题目：输入一个整数，求该整数的二进制表达中有多少个1。例如输入10，由于其二进制表示为1010，有两个1，因此输出2。分析：使用移位操作，来实现。具体实现如下：#include<iostream>using namespace std;int binary1num（int d）{int cnt = 0;while（d/2 ！= 0）{if（d%2 == 1） cnt ++;d = d...

全排列的递归与非递归实现浅析

2017年02月05日 35 阅读

全排列的递归与非递归实现浅析2014-12-25全排列问题在公司笔试的时候很常见，这里介绍其递归与非递归实现。递归算法1、算法简述简单地说：就是第一个数分别以后面的数进行交换E.g：E = （a , b , c），则 prem（E）= a.perm（b,c）+ b.perm（a,c）+ c.perm（a,b）然后a.perm（b,c）= ab.perm（c）+ ac.perm（b）= abc + acb.依次递归进行。void swap（string &a...

质数与合数及其应用

2017年02月05日 35 阅读

质数与合数及其应用2014-12-25质数与合数摘自维基百科：质数，又称素数，指在大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数（也可定义为只有1和本身两个因数的数）。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着非常重要的地位。质因数分解 即 分解质因数 。每个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数，叫做这个合数的分解质因数。 分解质因数只针对合数。分解质因数的算式的叫短除法。更多知识请...

1+2+3+...+n不能用while、for、if else等实现

2017年02月05日 35 阅读

1+2+3+...+n不能用while、for、if else等实现2014-12-25问题描述求 1+2+ … +n ，要求不能使用乘除法、 for 、 while 、 if 、 else 、 switch 、 case 等关键字以及条件判断语句。实际意义不大，题目涉及的知识还是不错的！方法1用构造函数求解。#include <iostream>using namespace std; class Plus {public: P...

图的深度优先遍历：邻接表实现

2017年02月05日 38 阅读

图的深度优先遍历：邻接表实现2014-12-25这里用邻接表实现图的深度优先遍历，采用递归实现。#include<iostream>using namespace std;#define VERTEXNUM 5//结点数structedgenode{int to;int weight; // 边的权值edgenode *next;};struct vnode{int from;edgenode *first;};void createGraph...

梯度下降算法：Gradient Descent

2017年02月05日 33 阅读

梯度下降算法：Gradient Descent2014-12-25最近在搞论文，需要用梯度下降算法求解，所以重新整理分享在这里。主要包括梯度介绍、公式求导、学习速率选择、代码实现。梯度下降的性质：1.求得的解和选取的初始点有关2.可以保证找到局部最优解，因为梯度最终会减小为0，则步长与梯度的乘积会自动越来越小。梯度简介一个多元函数的在某点的梯度方向是函数值在该点增长最快的方向，即方向导数取最大值的方向。问题描述公式求导学习率选择假设要学习这么一个函数：那么...

一致性哈希算法 Consistent Hashing 探讨以及相应的新问题出现解决

2017年02月05日 35 阅读

一致性哈希算法 Consistent Hashing 探讨以及相应的新问题出现解决2014-12-25一、业务场景假如我们现在有12台Redis服务器（其它的什么东西也行），有很多User（用户）的数据数据从前端过来，然后往12台redis服务器上存储，在存储中就会出现一个问题，12台服务器，有可能其中几台Redis服务器上（简称集群A）存了很多的数据，然后另外几台Redis服务器（简称集群B）上存的数据很少，这样的话那 A 上的读写压力就会很大（当然，这...

大话数据结构一：线性表的顺序存储结构

2017年02月05日 35 阅读

大话数据结构一：线性表的顺序存储结构2014-12-281. 线性表的顺序存储结构：指的是用一段地址连续的存储单元依次存储线性表的数据元素。2. Java实现线性表的顺序存储结构：// 顺序存储结构public class SequenceList {private static final int DEFAULT_SIZE = 10; // 默认初始化数组大小private int size; // 当前数组大小private static Object...

大话数据结构二：线性表的链式存储结构（单链表）

2017年02月05日 36 阅读

大话数据结构二：线性表的链式存储结构（单链表）2014-12-281. 线性表的链式存储结构：指的是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这就意味着这些数据元素可以存在内存未被占用的任意位置。2. 结点：结点由存放数据元素的数据域和存放后继结点地址的指针域组成。1.）顺序存储结构中，每个数据元素只需要存数据元素的信息就可以了。2.）链式存储结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址。3....

大话数据结构三：线性表的链式存储结构（静态链表）

2017年02月05日 38 阅读

大话数据结构三：线性表的链式存储结构（静态链表）2014-12-281. 静态链表：用数组描述的链表叫静态链表，通常为方便数据插入，我们会把数组建的大一些。2. 数组元素（node）：由两个数据域组成（data，cursor）。数据域data用来存放数据元素，也就是通常我们要处理的数据；而cursor相当于单链表中的指针，存放该元素的后继在数组中的下标。3. Java实现静态链表：// 静态链表class StaticLinkedList {private...

大话数据结构四：线性表的链式存储结构（单向循环链表）

2017年02月05日 37 阅读

大话数据结构四：线性表的链式存储结构（单向循环链表）2014-12-281. 单向循环链表：将单链表尾结点的指针端由空指针改为指向头结点，使整个单链表形成一个环，这种头尾相接的单链表称为单向循环链表。2. 单向循环链表和单链表实现的区别：1.）添加一个结点到单向循环链表末尾时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为null。2.）判断是否到达表尾时，单向循环链表可以判断该结点是否指向头结点，单链表只需要知道是否为null。3.Jav...

大话数据结构五：线性表的链式存储结构（双向链表）

2017年02月05日 35 阅读

大话数据结构五：线性表的链式存储结构（双向链表）2014-12-281. 双向链表：在单链表的每个结点中，再设置一个指向其前驱结点的指针域，那么在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。2. 单链表和双向链表比较：单链表：总是要从头到尾找结点，只能正遍历，不能反遍历。双向链表： 可以从头找到尾，也可以从尾找到头，即正反遍历都可以，可以有效提高算法的时间性能，但由于每个结点需要记录两份指针，所以在空间占用上略多一点，这就是通过空...

大话数据结构六：特殊的线性表（栈）

2017年02月05日 37 阅读

大话数据结构六：特殊的线性表（栈）2014-12-301. 什么是栈？栈（stack）是限定仅在表尾进行插入和删除操作的线性表。2. 栈的特点：1.） 栈又称为后进先出（Last In First out）的线性表，栈元素具有线性关系，即前驱后继关系。2.） 栈的特殊之处在于：它的栈底是固定的，只允许在栈顶进行插入和删除操作。3. 栈的顺序存储结构（Java数组实现）：// 栈的数组实现, 底层使用数组:public class ArrayStack<...

大话数据结构七：两栈共享存储空间（双向栈）

2017年02月05日 35 阅读

大话数据结构七：两栈共享存储空间（双向栈）2014-12-301. 为什么要使用双向栈？通过上一篇博客 - 特殊的线性表（栈），不难知道栈的顺序存储（数组实现）性能相对较好，因为它不存在插入和删除时移动元素的问题，但是它有一点缺陷：要事先确定数组存储容量的大小，万一不够，就需要扩充数组容量。这时双向栈就派上用场了，它可以最大限度的利用事先开辟的存储空间。2. 双向栈有什么特点？数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一...

大话数据结构八：队列的顺序存储结构（循环队列）

2017年02月05日 36 阅读

大话数据结构八：队列的顺序存储结构（循环队列）2014-12-301. 什么是队列？队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。2. 队列的特点:队列是一种先进先出（First In First out）的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。3. 队列顺序存储有什么不足？使用数组实现的顺序存储，当做出队列操作时，所有的元素都需要向前移动一位，性能很低。4. 什么是循环队列？队列头尾相接的顺序存储结构称为...

大话数据结构九：队列的链式存储结构（链队列）

2017年02月05日 35 阅读

大话数据结构九：队列的链式存储结构（链队列）2014-12-301. 链队列的特点：链队列其实就是单链表，只不过它是先进先出的单链表，为了实现方便，程序中设置了队头（front），队尾（rear）两个指针。2. Java使用链表实现队列://结点类，包含结点的数据和指向下一个节点的引用public class Node<E> {private E data; // 数据域private Node<E> next; // 指针域保存着...

大话数据结构十：字符串的模式匹配（BF算法）

2017年02月05日 37 阅读

大话数据结构十：字符串的模式匹配（BF算法）2014-12-301. BF算法简介：BF（Brute Force）算法是普通的模式匹配算法，又称为朴素匹配算法或蛮力算法，该算法最大缺点就是字符匹配失败指针就要回溯，所以性能很低。2. BF算法思想:BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和P的第一个字符，依次比较下去，直到得出最后的匹配结果。3...

大话数据结构十一：字符串的模式匹配（KMP算法）

2017年02月05日 38 阅读

大话数据结构十一：字符串的模式匹配（KMP算法）2014-12-301. KMP算法简介：kmp算法是一种改进的字符串匹配算法，相比朴素算法，KMP算法预先计算出了一个哈希表，用来指导在匹配过程中匹配失败后尝试下次匹配的起始位置，以此避免重复的读入和匹配过程。这个哈希表被称为"部分匹配值表"（Particial match table），这种设计是KMP算法最精妙之处。2. KMP算法分析：下面以阮一峰老师博客中的一篇文章来分析KMP算...

大话数据结构十二：字符串的模式匹配（BM算法）

2017年02月05日 38 阅读

大话数据结构十二：字符串的模式匹配（BM算法）2014-12-301. BM算法简介：KMP算法其实并不是效率最高的字符串匹配算法，实际应用的并不多，各种文本编辑器的“查找”功能大多采用的是BM算法（Boyer Moore）。BM算法效率更高，更容易理解。2. BM算法分析：（1） 假定字符串为"HERE IS A SIMPLE EXAMPLE"，搜索词为"EXAMPLE"。（2） 首先，&q...