算法与数据结构---查找和哈希

下面的题都是来自于牛客网的面试宝典

1.手写二分查找

二分查找:在查找的时候，每次都是从数据的中间开始，按照一定规则向左或者向右继续查找。也因此，二分查找的数据被要求具有一定的规则。一般是有序性。

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr,int target) {int l = 0;int r = arr.size()-1;int ans=-1;while(l<=r){int mid = l + (r-l)/2;if(target==arr[mid]){ans=mid;break;}else if(target>arr[mid]){l=mid+1;}//向右else if(target<arr[mid]){r=mid-1;}//向左}return ans;}
};

2.算法题，单调函数求零点(简单的二分法)

#include double f(double x)
{return 2 * x * x * x - 4 * x * x + 3 * x - 6;
}double findZero(double a, double b,double err)
{double m = 0.0;if (fabs(f(a)) < err)return a;if (fabs(f(b)) < err)return b;while (fabs(a - b) > err){m = (a + b) / 2;if (f(a) * f(m) < 0){b = m;}else{a = m;}if(fabs(f(m))<err){return m;}}return m;
}int main()
{std::cout << findZero(-10, 10, 0.001) << std::endl;
}

3.Hash表处理冲突的方法

hash算法能保证对于不同的参数，返回的数值不能保证不重复。这就是冲突

4.一致性hash算法

一致性哈希算法在1997年由麻省理工学院提出，设计目标是为了解决因特网中的热点(Hot pot)问题，初衷和CARP（缓冲阵列路由协议，Cache Array Routing Protocol）十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得DHT（Distributed Hash Table，分布式哈希）可以在P2P环境中真正得到应用。
标准：一致性哈希提出了在动态变化的Cache环境中，哈希算法应该满足的4个适应条件：

1）、平衡性(Balance)

平衡性也就是说负载均衡，是指客户端hash后的请求应该能够分散到不同的服务器上去。一致性hash可以做到每个服务器都进行处理请求，但是不能保证每个服务器处理的请求的数量大致相同。
2）、单调性(Monotonicity)

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应该能够保证已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

3）、分散性(Spread)

分布式环境中，客户端请求时候可能不知道所有服务器的存在，可能只知道其中一部分服务器，在客户端看来他看到的部分服务器会形成一个完整的hash环。如果多个客户端都把部分服务器作为一个完整hash环，那么可能会导致，同一个用户的请求被路由到不同的服务器进行处理。这种情况显然是应该避免的，因为它不能保证同一个用户的请求落到同一个服务器。所谓分散性是指上述情况发生的严重程度。

4）、负载(Load)

负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

5.KM算法

匈牙利算法：求最大匹配
当我们需要每一个在左边的点都尽量找到右边的一个点和它匹配。我们依次枚举左边的点x指向右边的点y。若y之前没有被匹配，那么（x,y）就是一对合法的匹配，我们将匹配数加一，否则我们试图给原来匹配y的x’重新找一个匹配。如果x’匹配成功，那么(x,y)就可以新增为一对合法的匹配。给x’寻找匹配的过程可以递归解决.

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！