发布于

又一个美女同事离职了

一个容貌绝美，身材高挑的美女同事离职了，今天得知她还是清华的博士，上帝其实还是不公平的，开了门也开了很多窗，就是有集万千宠爱与一身的人。我待得还挺久的，上班也没有盼头…

发布于

编译gRPC+protobuf需要注意的几点

1. 用grpc工程里的protobuf，不要用自己单独下的
2. check out protobuf 3.14.x的代码（或以上），否则grpc编不过
3. 编完protobuf再编grpc example

补充几点，否则可能会遇上链接错误
1，到third_party下生成protobuf工程，编译完成后要运行install ，用以获得protobuf的相关路径
2，将grpc生成的protoc.exe 和相关Lib替换protobuf/build/install 的相关文件
3，生成，编译example/helloworld工程，注意，默认grpc是release，helloworld也只能选release, 运行时库是MD

发布于

LeetCode[169]Majority Element 解法及代码(c++)

题目描述

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3
Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

这道题是难度为“简单”的题目，常规的解题思路就能解，但没什么意思。比如用一个map, 记录每个数出现的次数，当次数 == n/2时，这个数即是众数。
这个解法的算法复杂度是O(n), 空间复杂度是O(n)。下面介绍一种牛逼的算法–boyer-moore算法, 是一种字符串搜索算法，我们在这里杀鸡用牛刀。
思路：假设一个数是众数，我们有一个计数器count，当遇到这个数+1, 非这个数-1, 那么count最后>0。反过来想,遇到的具体一个数（候选数）时count += 1, 下一个还是这个数时count += 1, 不是这个数时count -= 1.
当 count == 0时，遇到的数为候选数，如此循环一遍，候选数即是众数，算法复杂度O(n), 空间O(1)

代码

int majorityElement(vector<int>& nums) {
  int candidate = 0;
  int count = 0;
  for (auto n : nums) {
    if (count == 0) {
      candidate = n;
    }
    count += n == candidate ? 1 : -1;
  }
  return candidate;
}