Python
Java
PHP
IOS
Android
Nodejs
JavaScript
Html5
Windows
Ubuntu
Linux
数组双指针法汇总
指针移动方向 相向夹逼 同向移动 维护的是一个区间还是只是关心指针指向的两个元素 同向移动的 维护一个区间的双指针法即滑动窗口法 2Sum 排序后两头往中间夹逼的双指针法 指针为什么可以不回退 即为什么可以i只 j只 当A i A j
算法
线性表数组
双指针
同类问题汇总
递归、加法原理,如何分解问题(独立且完备的划分)
加法原理适用于做一件事有n种独立不相交且完备的方向 每个方向上有ai种方案 则总的方案数就是 a1 a2 an 例题 把n个数分为k个非空子集 有多少种分法 分解问题 第一个集合里放多少个数把原问题的解分成了独立且完备的若干方向 分别解每个
同类问题汇总
算法
DFS
DP
有限自动机总结
有限自动机A用来识别字符串 它由5部分组成 1 alphabet 字符集 2 states 状态集合 3 init 初始状态 4 trans s ch 状态转移函数 5 end 可接受state 集合 A str true的意思是 A可以接
同类问题汇总
再谈缓存
凡是涉及管理数据的系统 都可以用图书馆来考虑 都要面临图书的位置查找和实际摆放两个问题 对应的两大组件就是就是index store 所有的数据管理系统都包含这两部分 缓存从过期又什么触发的角度分为容量触发和时间触发 容量触发 就是缓存满了
系统分析设计
OoD
同类问题汇总
打表法经典2题:小于n的质数和第k个丑数
1 求小于n的所有质数 1 开一个大小为n的bool数组A 下标代表整数 值true代表被mark过 有因子 非素数 2 i 从 2开始到n 1 如果A i 没被mark A i 就是质数 然后mark有A i 因子的数 2 A i 3 A
线性表数组
同类问题汇总
算法
数学
大数据问题汇总
1最基本的 一个数据流 文件 求top k biggest solution 维护大小为K的最小堆 和堆顶比 大于堆顶的加入堆 堆顶相当于准入门槛 如果size 超过K 移除堆顶 vector
系统分析设计
同类问题汇总
双向BFS搜索和A*算法
双向BFS适合给出起点和终点 求最短路径的问题 分别从起点和终点扩展 找交点 每次选择待扩展节点少的那个方向进行扩展 一次扩展一层 扩展一个节点的时候 如果节点也在另一个方向的待扩展队列里 找到交点 int doubleBFS vector
图论 隐式图
同类问题汇总
路径搜索问题
之前碰到的很多问题都可以归结为路径搜索问题 就是求两点之间的路经 1 是否存在路径 2 求任意一条路径 3 求所有路径 求是否有路径和任意一条路径的时候 和正常遍历一样 一个点被mark之后不再访问 因为如果这个结点到终点有路径 之前就应该
同类问题汇总
DFS
算法
图论 隐式图
再谈type ahead 问题
问题 给定一个词典 包括一些词和其出现的频率 实现type ahead功能 要求用户每键入一个字符 下拉框显示以当前输入为前缀的前10个最热门的词 解法1 用不带data的Trie data仅仅是词频 实时查询法 需要实时的去build h
同类问题汇总
算法
系统分析设计
一个完整的语法分析、词法分析例子——Universal Pasrser
需求 用户用formal notation指定语法 词法 然后可以匹配相应的文本 用法类似正则表达式 只需给出formal notation 不需要为每一种格式的文本单独写匹配器 formal notation主要是3个部分 1 BNF 列
parser
算法
同类问题汇总
系统分析设计
最少砝码问题(用一部分数的和/差表示区间上所有的整数)
问题1 需要表示 1 N 的所有重量 最少需要多少砝码 答案 需要 1 2 4 ceiling logN 每个砝码代表二进制数的一位 N有ceiling logN 个二进制位 问题2 需要表示 1 N 的所有重量 手头已有一些砝码 问 怎样
数学
同类问题汇总
算法
算法的三种练习
除了具体写代码 做这些练习 1 循环不变式 用循环不变式去解释算法 2 递归 动归的 递推式 3 搜索问题的隐式图构造 隐式树还是图 一个前驱 多个前驱 点是什么 边是什么 怎么扩展
同类问题汇总
算法
最大公约数,最小公倍数,素数等问题
1 两个数的 最小公倍数 等于两个数的乘积除以最大公约数 scm a b a b gcd a b 所以主要是最大公约数问题 gcd 问题 辗转相除法 依据就是欧几里得定理 gcd a b gcd b a b def gcd a b whil
数学
同类问题汇总
算法
merge sort 一些变种、应用
1 逆序对数目 分治公式 总的逆序对个数 前半部分逆序对个数 后半部分逆序对个数 merge时候每取一次后半部分的数 累加一次前半部分剩余的数的个数 int countInvertion vector
线性表数组
算法
同类问题汇总
排序
二叉树 level order 遍历问题汇总
一 如何确定层结束 1 维护一个levelEnd 如果当前结点等于level end 更新levelEnd 为queue back 注意先判断queue是否empty 最后一层结束后 queue就空了 2 维护一个curLevelNum 和
同类问题汇总
二叉树
还是搜索、索引的问题
搜索要弄清2个基本问题 1 要搜索出什么类型的entity 2 entity的哪个方面 维度和关键词发生关联的 一般来说可以有多个角度link到entity 一个entity支持多个索引 可以从不同的column检索 对于 web sear
架构
系统分析设计
同类问题汇总
背包问题,硬币问题
至少有4种背包问题 1 01背包 2 部分背包 3 完全背包 4 多重背包 只有部分背包是个贪心问题 其他的都是以01背包为基础的动归问题 部分背包问题 把物品按价值密度从大到小排序 W i V i 然后从第一种物品开始 尽可能多拿当前物品
DP
背包问题
同类问题汇总
中缀表达式求值问题
1 有无括号 2 一种优先级运算符 只有 或 还是2种 和 都有 3 求逆波兰序列 求值 求表达式树 两种思路 1 分治 求值 和求表达式树都可以用 nlogn 1 先去掉冗余括号 两边最外面的 如 1 1 2 如果有的话 找到优先级最小的
算法
stack
同类问题汇总
自己动手写一个key value store
一涉及到persistent 哪怕只是最基本的需求 很多人都会依赖数据库 或是其他现成的库或工具 确实 对于文件 大部分人很少直接打交道 或者只是诸如整体反序列化 序列化 按行读取 append new line等有限的操作 一个persi
算法
文件操作
系统分析设计
同类问题汇总
架构
爬虫中网页分析的几种技术
一般来说我们只抓取网页中的特定数据 比如抓取某人所有的blog 我们就只关心list 页面中文章列表那部分的链接和title 有几种技术可以用来分析网页 1 正则匹配 2 一般字符串匹配content substring pattern s
parser
同类问题汇总
系统分析设计
1
2
»