最简单的二分 1.循环实现 template <typename T> int binary_search(const vector<T> &set, const T &value) { auto low = set.begin(); auto high = set.end(); auto high_dump = high; auto low_dump = low; auto mid = low + ((high - low) >> 1); /*1. mid=(low+high)/2,如果 low 和 high 太大就会产生溢出*/ while ((low <= high) && (mid != high_dump)) /*2. 一定是 <= */ { if (*mid == value) return mid - low_dump; /*3. 一定要+1,-1,不然当  继续阅读 >>


刘生玺 18/11/04 22:52:10
题目1 : 单词搜索 给定一个二维网格和一个单词,找出该单词是否存在于网格中。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例: board = [ [‘A’,’B’,’C’,’E’], [‘S’,’F’,’C’,’S’], [‘A’,’D’,’E’,’E’] ] 给定 word = “ABCCED”, 返回 true. 给定 word = “SEE”, 返回 true. 给定 word = “ABCB”, 返回 false. 解题思路:简单DFS,注意边界条件的判断和点的回溯(index和visted) #include <iostream> #include <vector> #include <string> using namespace std; class Solution { public: strin 继续阅读 >>


刘生玺 18/08/11 09:54:45
一、 对象已死嘛 引用计数法 给对象添加一个引用计数器,每当有一个地方引用它时,计数器值就加1;当引用失效时,计数器值就减1;任何时刻计数器为0的对象就是不可能再被利用的。 引用计数法的实现简单,判定效率也高,但是它很难解决对象间相互循环引用的问题。 比如对象A和B都有字段instance,赋值令A.instance = B且B.instance = A,除此之外,这两个对象再无任何引用。实际上这两个对象已经不可能再被访问,但是它们因为互相引用着对方,导致它们的引用计数都不为0,于是引用计数法无法通知GC收集器回收它们。 可达性分析算法 通过一系列称为“GC Roots”的对象作为起始点,从这些节点开始向下搜索,搜索所走过的路径称为引用链,当一个对象到GC Roots没有任何引用链相连时,则表明此对象是不可用的。 可作为GC Roots的对象包括下面几种: 虚拟机栈(栈帧中的本地变量表)中引用的对象 方法区中类静态属性、常量引用的对象 本地方法栈中JNI引用的对象 引用 继续阅读 >>


李猛 18/08/10 15:04:26
题意:原题链接 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性: 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 示例: 现有矩阵 matrix 如下: [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] 给定 target = 5,返回 true。 给定 target = 20,返回 false。 很显然,遍历该二位数组是最愚蠢的做法,如果这样做也是挺智障的。那有没有更好的想法呐?emmmmmmm,好吧,还是直说吧,就不废话了 。用我们刚刚讲过的二叉查找树的思路解决。 思路:从该二维数组右上角的数字开始,如果该数字和target相等,那么查找完毕;如果小于,往左走,如果大于往下走 。就像二叉查找树一样,就 继续阅读 >>


刘生玺 18/07/28 15:34:19
最长上升子序列(LIS)的定义:    一个数的序列bi,当b1 < b2 < … < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN),我们可以得到一些上升的子序列(ai1, ai2, …, aiK),这里1 <= i1 < i2 < … < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8). 三种求解方法: 1. O(n^2)的DP 2. O(nlogn)的二分+贪心法 3. O(nlogn)的树状数组优化的DP 题目:Longest Increasing Subsequence 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2, 继续阅读 >>


刘生玺 18/07/20 12:10:14
题目:不同路径 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。 问总共有多少条不同的路径? 例如,上图是一个7 x 3 的网格。有多少可能的路径? 说明:m 和 n 的值均不超过 100。 示例 1: 输入: m = 3, n = 2 输出: 3 解释: 从左上角开始,总共有 3 条路径可以到达右下角。 1. 向右 -> 向右 -> 向下 2. 向右 -> 向下 -> 向右 3. 向下 -> 向右 -> 向右 示例 2: 输入: m = 7, n = 3 输出: 28 原题链接:https://leetcode-cn.com/explore/interview/card/top-interview-questions-medium/51/dynamic-programming/105/ 继续阅读 >>


刘生玺 18/07/19 11:15:47
1. 感性认识“动态规划” 1. 基本概念    是求解决策过程(decision process)最优化的数学方法。把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,是一种解决这类过程优化问题的新方法。 2. 使用技巧:    动态规划算法通常用于求解具有某种最优性质的问题!!!特别的 ,动态规划(Dynamic Programming)对于子问题重叠的情况特别有效,因为它将子问题的解保存在表格中,当需要某个子问题的解时,直接取值即可,从而避免重复计算! 3. 基本思想与策略 我们通过一个问题来引出: 提问:动态规划与分治法有什么不同?    答:适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题 继续阅读 >>


刘生玺 18/07/18 19:02:57
全排列算法思想: 1. 全排列的定义和公式:    从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。由排列的定义,显然不同的顺序是一个不同的排列。从n个元素中取m个元素的所有排列的个数,称为排列数。从n个元素取出n个元素的一个排列,称为一个全排列。 公式:全排列数f(n) = n! (定义0!=1) 2. 时间复杂度:    n个数(字符、对象)的全排列一共有n!种,所以全排列算法至少时间O(n!)的。如果要对全排列进行输出,那么输出的时间要O(n∗n!),因为每一个排列都有n个数据。所以实际上,全排列算法对大型的数据是无法处理的,而一般情况下也不会要求我们去遍历一个大型数据的全排列。 3. 全排列的初始思想    为了解决一个算法问题,我们选择从基本的想法做起。先回顾一下我们自己是如何写一组数的全排列的:1,3,5,9 首先肯定是 : 1 ,[3, 5,9的全排列] 3 继续阅读 >>


刘生玺 18/07/17 11:08:08
结构化与非结构化网络 非结构化的P2P网络是指网络节点之间不存在组织关系,节点之间完全是对等的,比如第一代P2P网络Napster。 结构化的P2P网络与非结构化恰好相反,我们认为网络在逻辑上存在一个人为设计的结构,比如Chord假定网络是一个环,Kadelima则假定为一颗二叉树。有了这些逻辑结构,就给我们资源查找引入了更多的算法和思路。 引言 我们在 计算机网络–详解P2P对等网络(一)—BitTorrent协议 这一篇博客中讲述了BT下载的过程:在对等用户拿到种子文件的时候,首先会联系tracker服务器,然后加入用户集群,并在用户集群中寻找自己所需的内容,最后与拥有内容的对等用户进行联系。 从BT下载的过程中引出本节所要讨论的问题:如何高效的从用户集群中找出哪些对等用户拥有你正在寻求的具体内容? 在历史中有三种比较典型的模型来解决这个问题: Napster:使用一个中心服务器接收所有的查询,服务器告知去哪下载其所需要的数据。存在的问题是中心服务器单点失效导致整个网络瘫痪。 继续阅读 >>


董恒毅 18/06/28 21:24:59
注:本篇博客只是讲述了一致性哈希的思想,我们会在之后讲述分布式哈希表以及一致性哈希的一种实现(Chord算法)。 什么是一致性哈希算法? 引用自维基百科: 一致性哈希是一种特殊的哈希算法。在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对 K/n个关键字重新映射,其中K是关键字的数量,n是槽位数量。然而在传统的哈希表中,添加或删除一个槽位几乎需要对所有关键字进行重新映射。 总结:一致性哈希算法主要关注的是在分布式架构中,当节点数目发生变化的时候(增加/删除),怎样使再哈希的数据量最少。 一致性哈希的引出 在分布式系统中,节点的宕机、某个节点加入或者移出集群是常事。对于分布式存储而言,假设存储集群中有10台机器(node),如果采用传统Hash方式对数据分片(item)(即数据根据哈希函数映射到某台机器上存储),哈希函数应该是这样的:hash(item) % 10。根据上面的介绍,当node数发生变化(增加、移除)后,数据会被重新“打散”,导致大部分数据不能落到原 继续阅读 >>


董恒毅 18/06/26 21:06:58