算法
前言 “讲一下你对限流的了解” 面试遇到限流的问题，很多人会千篇一律的回答“令牌桶”、“漏桶”算法，但是真正研究过限流的人可不会对你这种回答满意。今天薛师兄就带你飞，教你如何在回答“限流”问题上脱颖而出！ 限流算法分析 漏桶算法 漏桶算法思路很简单，水（请求）先进入到漏桶里，漏桶…
题目一 给定一个 没有重复 数字的序列，返回其所有可能的全排列。 示例: 解法一：插入法 解题思路： · 待排列数字为 [1, 2, 3]，先排列数字 1 ，结果是 [1]。 · 再排列数字 2 ，插入到上一个排列中，插到 1 前面得到[2,1]，插到 1 后面得到 [1,2]。…
题目 输入 n 个整数，找出其中最小的 k 个数。例如输入4、5、1、6、2、7、3、8 这8个数字，则最小的4个数字是1、2、3、4。 初窥 这道题最简单的思路莫过于把输入的 n 个整数排序，排序之后位于最前面的 k 个数就是最小的 k 个数。这种思路的时间复杂度是 O(nlo…
题目描述 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 解题思路 将旋转数组对半分可以得到一个包含最小元素的新旋转数组，以及一个非递减排序的数组。新的旋转数组的数组元素是原数组的一半，从而将问题规模…
本文是继《一文了解有趣的位运算》的第二篇文章. 我们知道，计算机最基本的操作单元是字节(byte)，一个字节由8个位(bit)组成，一个位只能存储一个0或1，其实也就是高低电平。无论多么复杂的逻辑、庞大的数据、酷炫的界面，最终体现在计算机最底层都只是对0101的存储和运算。因此，…
题目 输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。 举例 输入：2, -3, 4, 5, -9 输出：9 和最大的连续子数组是 {4, 5}，结果就是9。 贪心算法 我们先假设和最大连续子数…
概述 背包问题（Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。 定义 我们有 n 种物品，…
算法概述 快速排序（Quicksort），又称划分交换排序，简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序n个项目要O(n log n)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。 事实上，快速排序O(n log n)通常明显比其他算法更快…
算法概述 二分搜索，也称折半搜索、对数搜索，是一种在有序数组中查找某一特定元素的搜索算法。 搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比…
一、位运算概述 从现代计算机中所有的数据二进制的形式存储在设备中。即0、1两种状态，计算机对二进制数据进行的运算(+、-、\、/)都是叫位运算，即将符号位共同参与运算的运算。 口说无凭，举一个简单的例子来看下CPU是如何进行计算的，比如这行代码： 计算两个数的和，因为在计算机中都…
0、算法概述 0.1 算法分类 十种常见排序算法可以分为两大类： · 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。 · 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线…
一致性Hash算法背景 一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得DHT可以在P2P环境中真…
题目要求： 现在我们拥有全国的省、市、县、镇的行政信息，比如 浙江省 -> 杭州市 -> 西湖区 --> xx街道，请将这些信息构建成一棵树，根节点为全国，叶子节点为镇。 我的误解： 刚开始我并没有明白题意，走了弯路，只是简单的构建了一个多叉树。代码如下： 当面试官看到代码后，提…
这道题是我亲身经历的一道大厂面试题，非常值得分享！ 这道题可以分为两个步骤进行编码解答，第一步是基于数组实现一个队列，第二步是实现线程阻塞。 如果是基于数组实现栈的数据结构，那么我们只需要一个指针进行来回移动即可。 想象一下，脑海中有一个竖立起来的栈，指针上移代表元素进栈，指针下…
什么是负载均衡 负载均衡，英文 名称为Load Balance，指由多台服务器以对称的方式组成一个服务器集合，每台服务器都具有等价的地位，都可以单独对外提供服务而无须其他服务器的辅助。通过某种 负载分担技术，将外部发送来的请求均匀分配到对称结构中的某一台服务器上，而接收到请求的服…
倒排索引是目前搜索引擎公司对搜索引擎最常用的存储方式，也是搜索引擎的核心内容，在搜索引擎的实际应用中，有时需要按照关键字的某些值查找记录，所以是按照关键字建立索引，这个索引就被称为倒排索引。 首先你要明确，索引这东西，一般是用于提高查询效率的。举个最简单的例子，已知有5个文本文件…
斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........ 这个数列从第3项开始，每一…
