-
MST
最小生成树（min spanning tree）概念带权连通图中代价最小的生成树以上的基本原则是基于MST的如下性质：设G=(V，E)是一个带权连通图，U是顶点集V的一个非空子集。若u∈U ，v∈V-U，且(u, v)是U中顶点到V-U中顶点之间权值最小的边，则必存在一棵包含边(u, v)的最小生成树。证明： 用反证法证明。设图G的任何一棵最小生成树都不包含边(u,v)。设T是G的一棵生成树，则T是连通的，从u到v必有一条路径(u,…,v)，当将边(u,v)加入到T中时就构成了回路。则路径...…
-
线程
线程：基本用法 线程和进程的虚拟地址空间不同。 区别。线程的优点：切换 ，创造、资源更轻量， 进程中多个线程的共有数据 和 私有数据 pthread_detach 创建一个线程默认的状态是joinable, 如果一个线程结束运行但没有被join,则它的状态类似于进程中的Zombie Process,即还有一部分资源没有被回收（退出状态码），所以创建线程者应该调用pthread_join来等待线程运行结束，并可得到线程的退出代码，回收其资源（类似于wait,wai...…
-
protobuf
proto buff一篇讲的比较好的原文：https://blog.csdn.net/program_think/article/details/4229773作用用于数据存储， 协议传输等场合优点性能效率好： 时间效率高， 冗余文本少支持多种语言向前兼容， 向后兼容缺点二进制格式可读性差， 缺乏自描述…
-
java面试复习
java 语法1 java 类型Java中的基本数据类型只有8个：byte、short、int、long、float、double、char、boolean；除了基本类型（primitive type）和枚举类型（enumeration type），剩下的都是引用类型（reference type）int和Integer有什么区别？答：Java是一个近乎纯洁的面向对象编程语言，但是为了编程的方便还是引入了基本数据类型，但是为了能够将这些基本数据类型当成对象操作，Java为每一个基本数据类型...…
-
操作系统面试复习
1 死锁的四个条件： 互斥使用(Mutual exclusion) ：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。 不可抢占(No preemption)：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。 请求和保持(Hold and wait)：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占...…
-
动态规划
逆序对629 K Inverse Pairs ArrayGiven two integers n and k, find how many different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs.思路， 假设 dp[n,k] 代表1-n个数组成的k个逆序对的个数，那么 dp[n,k] = dp[n-1,k] +dp[n-1,k-1]…+ dp[n-1, k-(n...…
-
树
树 二叉查找树 树的遍历 平衡树树的高度111. Minimum Depth of Binary Tree求树的最短深度（叶子节点到根的最小距离） 注意此题子树深度为0时，并没有叶子节点，要特殊处理 另外一种做法是层序遍历，用队列的结构，根据size或者每层push一个特殊node来判断层数。直到遇到一个叶子节点。 层序遍历比深度优先的递归更效率些。因为它不用查到最后一层/** * Definition for a binary tree node. * struct TreeN...…
-
堆与优先队列
堆分为大顶堆和小顶堆：特点是一个完全二叉树，根节点总是比左右两个子节点大（小）。建立堆时 需要解决两个问题： 从无序的数中建立堆 当取出堆顶元素后如何调整堆先解决第二个问题， 如上图所示， 取出堆顶元素后， 将尾部元素插到顶部，调整即可。</p>对于第一个问题， 其实就是一个对多个元素调整的问题。我们需要先从最后一个非叶节点调整，依次调整至堆顶节点。优先队列就是基于堆的结构实现的。215. Kth Largest Element in an ArrayFind the k...…
-
位运算
二进制编码：原码、反码以及补码 原码：第一位符号位加真值。如：0000 0001 是1的原码， 1000 0001 是-1的原码 反码：正数的反码是其本身,负数的反码是在其原码的基础上, 符号位不变，其余各个位取反. 补码： 正数的补码就是其本身，负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)为何会出现三种编码形式？简化运算，让符号位也参与运算。比如减法也可用加上一个负数运算，在这种情况下，原码和补码的编码运算会出现错误：1 - 1...…
-
排列组合
排列567. Permutation in StringGiven two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.Example 1:Input:s1 = “ab” s...…
-
Hash表的原理及例题讲解
Hash数据结构： hash表可以提供快速的插入操作和查找操作。需要首先申请较大的空间，将元素根据特定规则求key,散列到不同的空间位置。哈希表散列方法： 直接定址法 数字分析法 平方取中法 折叠法 除留余数法 随机数法哈希表处理冲突方法： 开放定址法：当冲突时， 重新计算地址 H = (H(key) + di) MOD m di = 1, 2, 3…时，线性探测再散列, 能保证只要表未满，就能找到空位，但是会造成“二次聚集”： 如下一个地址为 i,i + ...…
-
二分查找
二分查找注意的问题： (low + high) / 2 容易越界， 所以用 low + (high - low) / 2 更好 二分查找， 用在有有序性质的结构中。 或者找某个范围中的值。（1） 483. Smallest Good BaseFor an integer n, we call k>=2 a good base of n, if all digits of n base k are 1.Now given a string representing n, you s...…
-
Linear_regression
…
-
自动摘要综述
自动摘要分类自动摘要分为：1） 抽取式（extrative） 和 2） 摘要式（abstractive）。<p>现在的自动摘要主要是抽取式，文章划分为句子，然后选取句子特征，训练模型，根据结果选取代表性句子组成摘要，缺点摘要的连贯性、一致性很难保证。另外，深度学习领域，seq2seq+attention 模型，可以应用到自动摘要，取得了一定效果。自动摘要评价自动文档摘要评价方法大致分为两类：（1）内部评价方法(Intrinsic Methods)：提供参考摘要，以参考摘要为基准...…
-
笔试面经笔记
2017微软转正实习生第一面没问算法，直接问项目，首先我解释了几个课程设计，后来按着机器学习一直问。。没怎么回答好。。后来讲了一下简历写的个小游戏。二面开始问我迷宫查找怎么实现的，就是深度优先和广度优先的搜索。问了俩算法，比较简单：一个是树的层序遍历，另一个求经过root的两个树节点之间的路径长度。手写代码，讲思路和测试用例。另外引申了一下求两个节点的不经过root的最短路径长度。我说要求最近公共祖先，但是代码还没想出来咋写呢，时间也差不多，就结束了二面。三面竟然问一些语言特性。。java...…
-
我的博客
正文： 博客正式开启喽~会把之前的一些笔记再整理一下。预写 机器学习笔记 数据结构算法整理笔记Markdown语法参考链接: 作业部落转载请注明原地址，beibei的博客：http://alwaysright.github.io 谢谢！…
