ARTS-1

发表于 | 分类于 | |

前言

ARTS 是「左耳朵耗子」发起的活动，每周至少做一个 leetcode 的算法题，阅读并点评至少一篇英文技术文章，学习至少一个技术技巧，至少分享一篇有观点和思考的技术文章。坚持至少一年！（也就是：Algorithm、Review、Technique、Share 简称 ARTS）

Algorithm

two sum

经典第一题：

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

首先是一个极其stright-forward的遍历解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); ++i) {
            int find = target - nums[i];
            for (int j = nums.size() - 1; j > i; --j) {
                if (find == nums[j]) {
                    vector<int> res = {i, j};
                    return res;
                }
            }
        }
        vector<int> res {-1, -1};
        return res;
    }
};

这个方法由于两个循环遍历，时间复杂度是O(N^2)

改进办法想了很久，陷入了各种排序和二分查找方法之中。主要是因为不了解hash_map的原理，陷入认为hash_map是一个查找复杂度为O(log(N))的数据结构，其实既然是用了hash做key，应该是直接同数组一样是O(1)的查找时间复杂度。

所以解法应该为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int, int> indexT;
        for (int i = 0; i < nums.size(); ++i) {
            int need = target - nums[i];
            auto it = indexT.find(need);
            if(it != indexT.end()) {
            vector<int> res = {it->second, i};
            return res;
            } else {
            indexT[nums[i]] = i;
            }
        }
        std::cout << "can't find" << std::endl;
        return {-1, -1};
    }
};

这个只是做了一次遍历，时间复杂度为O(N)，空间复杂度为O(N)

Reading

因为最近公司的工作中用到了Kafka，这周阅读的是Kafka发明者写的《Kafka: a Distributed Messaging System for Log Processing》。文章作者是LinkedIn的三位工程师，其中详细介绍了Kafka之前消息系统的问题，他们对这些问题的改进设计，Kafka在LinkedIn业务中的实际应用和测试数据。

思维导图

参考

Kafka: a Distributed Messaging System for Log Processing
Kafka设计解析

Tips

基于fork和merge request机制的代码管理方式
Git团队合作开发流程

Share

输入优质信息很重要，国内渐渐优质社区少了。在某沙龙活动上问了下几位KOL他们是如何能吸收到大量优质信息的。他们的回答是直接看外网消息，硬着头皮获取第一手消息源；同时尽量看长文、看经过思考过写出来的文字。结合耗子叔的观点，目前光是搬运外网优质信息咀嚼过一遍到中文网络就能做成产业。感觉知识垄断已经越来越严重了。