算法

前言 在开发高并发系统时，有三把利器用来保护系统：缓存、降级和限流。那么何为限流呢？顾名思义，限流就是限制流量，就像你宽带包了1个G的流量，用完了就没了。通过限流，我们可以很好地控制系统的qps，从而达到保护系统的目的。本篇文章将会介绍一下常用的限流算法以及他们各自的特点。 几种常见的限流方法计数器固定窗口算法计数器算法是限流算法里最简单也是最容易实现的一种算法。 比如我们规定，对于A接口来说，我们1分钟的访问次数不能超过100个。那么我们可以这么做：在一开 始的时候，我们可以设置一个计数器counter，每当一个请求过来的时候，counter就加1，如果counter的值大于100并且该请求与第一个 请求的间隔时间还在1分钟之内，那么说明请求数过多；如果该请求与第一个请求的间隔时间大于1分钟，且counter的值还在限流范围内，那么就重置 counter，具体算法的示意图如下： 伪代码12345678910111213141516171819202122232425public class CounterTest { public long timeSta...

1 - 两数之和 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 解题方法暴力法 遍历数组，依次判断arr[0]+arr[1]，arr[0]+arr[2] ... ，arr[1]+arr[2]，arr[1]+arr[3] ... ，arr[2]+arr[3]，arr[1]+arr[3] ... 因为需要遍历Nb*Nb次循环，所以时间复杂度为O(N^2) 123456789101112131415161718192021class Solution { // Brute Force // @爱学习的饲养员 // N is the size of nums // Time Complexity: O(N^2) // Space COmplexity: O(1) public int[] twoSum(int[] nums, i...

摘自：https://zhuanlan.zhihu.com/p/50479555 算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。 那么我们应该如何去衡量不同算法之间的优劣呢？ 主要还是从算法所占用的「时间」和「空间」两个维度去考量。 时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。 空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。 因此，评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而，有的时候时间和空间却又是「鱼和熊掌」，不可兼得的，那么我们就需要从中去取一个平衡点。 下面我来分别介绍一下「时间复杂度」和「空间复杂度」的计算方式。 时间复杂度我们想要知道一个算法的「时间复杂度」，很多人首先想到的的方法就是把这个算法程序运行一遍，那么它所消耗的时间就自然而然知道了。 这种方式可以吗？当然可以，不过它也有很多弊端。这种方式非常容易受运行环境的影响，在性能高的机器上跑出来的结果与在性...