常见的排序算法有以下几种： 递归性排序 归并排序：归并排序的主要思想是分治，也就是先把数组分成两部分，当两部分都有序时，然后再将两部分进行二路归并。需要注意的是归并排序的时间复杂度分析方法，就是画出$T(n) = 2T(n/2) + cn$ 的递归树，并计算最终时间复杂度。但是要注意的是，归并排序在进行二路归并时，可能会产生额外的空间复杂度。 ：快速排序的思路也是分治，但分治之前需要选择一个主元作为基准，将主元放在应该在的位置，并且数组左边比主元小，右边比主元大。这样如果当左边有序和右边有序时，整个数组就有序了。假设主元位置为i，快速排序复杂度为$T(n) = T(i) + T(n - i ...

1. JDK和JRE、JVM的区别是什么JRE（Java运行时环境）： Java Runtime Environment JRE顾名思义是java运行时环境，包含了java虚拟机，java基础类库。是使用java语言编写的程序运行所需要的软件环境，是提供给想运行java程序的用户使用的。 JDK（Java 开发工具包）：Java Development Kit JDK顾名思义是java开发工具包，是程序员使用java语言编写java程序所需的开发工具包，是提供给程序员使用的。JDK包含了JRE，同时还包含了编译java源码的编译器javac，还包含了很多java程序调试和分析的工具：jcons ...

1. 背景 本文中研究的问题为位置感知的发布/订阅框架设计与实现。订阅者以订阅（subscription）的形式向发布/订阅系统注册，表达对特定事件的兴趣；发布者发布消息到发布/订阅系统；发布/订阅系统充当订阅者和发布者的中介，负责订阅的管理，并以通知的形式发送消息到感兴趣的订阅者。 与传统的基于文本的发布订阅问题不同，在我们所研究的问题中，发布者发布的消息和订阅者的订阅都是同时包含了空间位置和文本描述两种信息。 ​ 订阅者对于空间位置和文本描述的相似性有着不同的偏好，比如一些订阅者更希望得到与自己的订阅文本相似程度更高的消息，而另一些订阅者则更关注获得的消息与自己所在的空间位置的相近 ...

1. 监督学习 vs 无监督学习 有监督学习：输入数据有标签，比如分类回归 无监督学习：输入数据没有标签，比如聚类 半监督学习：输入数据部分有标签，部分没有，或者有标签的部分不确定是否正确，让学习器不依赖外界交互、自动地利用未标记样本来提升学习性能，就是半监督学习 2. 生成模型 vs 判别模型监督学习方法又可以分为生成方法(generative approach)和判别方法(discriminative approach)。所学到的模型分别为生成模型(generative model)和判别模型(discriminative model)。 2.1 生成方法和生成模型生成模型：无穷样本== ...

1. 应用场景AVL树：平衡二叉树之一，应用相对其他数据结构比较少，windows对进程地址空间的管理用到了AVL 红黑树：平衡二叉树，广泛应用在C++STL中，比如map和set，Java的TreeMap B和B+树：主要用在文件系统以及数据库中做索引等 Trie 树：用在统计和排序大量字符串中，一个典型应用是前缀匹配，比如下面这个很常见的场景，在我们输入时，搜索引擎会给予提示。还有比如IP选路，也是前缀匹配 R树：空间数据库索引 2. 二叉搜索树不必多说了，可以参考 【九章算法基础班】二叉树与分治法 时间复杂度最好情况是O(logn) ，最坏情况下时间复杂度O(n)，恰好选择了最小或者最大 ...

1. 过拟合与欠拟合​ 机器学习中一个重要的话题便是模型的泛化能力，泛化能力强的模型才是好模型. ​ 对于训练好的模型，若在训练集表现差，不必说在测试集表现同样会很差，这可能是欠拟合导致；若模型在训练集表现非常好，却在测试集上差强人意，则这便是过拟合导致的. ​ 过拟合与欠拟合也可以用 Bias 与 Variance （偏差和方差）的角度来解释，欠拟合会导致高 Bias ，过拟合会导致高 Variance ，所以模型需要在 Bias 与 Variance 之间做出一个权衡。 ​ 使用简单的模型去拟合复杂数据时，会导致模型很难拟合数据的真实分布，这时模型便欠拟合了，或者说 ...

本文主要回顾和总结2017编程之美决赛中校园聊天机器人后端搜索引擎的实现。 1. 项目简介校园聊天机器人，针对用户的问题进行回答，当然，问题都是跟校园相关的一些问题。 收集校主页和论坛上的信息，招聘信息、征友信息、失物招领等信息，根据用户的需求返回合适的答案。 2. 爬虫北邮人论坛格式相对工整，并不需要进行DFS爬取。论坛某个页面如下： 论坛格式基本如下： 1 [标题，最新回复时刻]2 [标题，最新回复时刻]...10 [标题，最新回复时刻] 第k页 因此只需要按页遍历即可。 2.1 数据库设计爬取的内容建立一张表放入MySQL。由于每个帖子都有自己的唯一性ID ...

outline滚动数组 house robber I/II Maximal Square 记忆化搜索 longest increasing subsequence coins in a line 动态规划四要素 状态 转移方程 初始化 答案 滚动数组优化f[i] = max(f[i-1],f[i-2]+A[i]); 转化为： f[i%2] = max(f[(i-1)%2],f[(i-2)%2]) 滚动数组优化不会对时间复杂度进行优化，而只是对空间进行优化 例题1. House Robber给定一个数组，代表抢劫商店可以获得的价值，不可以抢劫相邻的商店，计算能够获得的最大价值 思路： ...

1. 海量数据选取TOPKbaseline： 用堆，如果取最大的K个，就用最小堆，遍历数组，遇到比堆顶元素大的元素就入堆，同时堆中元素超过k个需要poll操作，保证堆中只有K个元素，最终的topk元素在堆中。 时间复杂度分析: O(n*logk)$$ ，元素入堆复杂度$$O(logk)O(n)算法： 先用quick select方法找到第K大的元素，复杂度O(n) 然后再遍历一遍，将大于K的元素取出，复杂度O(n) 总复杂度O(n) ！！！！！卧槽！神奇！！！！ follow up：海量数据选取第K大 Quick Select，详见【九章算法强化班】两指针 时间复杂度O(n) 2. 大数排序 ...

1. 项目简介无线短视频推荐项目，负责无线端用户的短视频推荐，也就是给手机端用户推荐短视频。主要用到了item-based协同过滤的思想，为用户提供候选短视频推荐集合，然后再利用预训练的LR模型返回候选推荐集合的最终排序，推给用户。 2. 推荐系统分类感谢@奔波的梦想 的总结。推荐算法大致可以分为三类：基于内容的推荐算法、协同过滤推荐算法和基于知识的推荐算法。​ 基于内容的推荐算法，原理是用户喜欢和自己关注过的Item在内容上类似的Item，比如你看了哈利波特I，基于内容的推荐算法发现哈利波特II-VI，与你以前观看的在内容上面（共有很多关键词）有很大关联性，就把后者推荐给你， ...