网盘XZ：极客时间李煜东算法训练营2021版二期

为什么要学习数据结构和算法

学习算法最重要的是什么？ 在学习算法的过程中，一能解决问题，二对自己有用，是最大的推动力。 而那些抽象的，与程序员日常工作关系不大的竞赛题，很难提起大多数人的学习兴趣。 最好能通过工作中应用的一些案例来切入，利用碎片化时间入门算法，提升技术竞争力。

想要通关大厂面试，千万别让数据结构和算法拖了后腿
很多大公司，比如 BAT、Google、Facebook，面试的时候都喜欢考算法、让人现场写代码。有些人虽然技术不错，但每次去面试都会“跪”在算法上，很是可惜。那你有没有想过，为什么这些大公司都喜欢考算法呢？

业务开发工程师，你真的愿意做一辈子 CRUD boy 吗？
如果你是一名业务开发工程师，你可能要说，我整天就是做数据库 CRUD（增删改查），哪里用得到数据结构和算法啊？

是的，对于大部分业务开发来说，我们平时可能更多的是利用已经封装好的现成的接口、类库来堆砌、翻译业务逻辑，很少需要自己实现数据结构和算法。但是，不需要自己实现，并不代表什么都不需要了解。

基础架构研发工程师，写出达到开源水平的框架才是你的目标！
现在互联网上的技术文章、架构分享、开源项目满天飞，照猫画虎做一套基础框架并不难。我就拿 RPC 框架举例。

不同的公司、不同的人做出的 RPC 框架，架构设计思路都差不多，最后实现的功能也都差不多。但是有的人做出来的框架，Bug 很多、性能一般、扩展性也不好，只能在自己公司仅有的几个项目里面用一下。而有的人做的框架可以开源到 GitHub 上给很多人用，甚至被 Apache 收录。为什么会有这么大的差距呢？

掌握了数据结构与算法，你看待问题的深度，解决问题的角度就会完全不一样。因为这样的你，就像是站在巨人的肩膀上，拿着生存利器行走世界。数据结构与算法，会为你的编程之路，甚至人生之路打开一扇通往新世界的大门。

算法训练营2021版二期算法面试题

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]
示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]
说明:

输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
解答
方法1
将数组nums1的元素放入一个set中，然后遍历nums2的元素nums2[i]，判断它是否在set中，如果在set中，则说明这个元素是交集的部分，将它加入结果中。

设nums1的大小为m，数组nums2的大小为n

时间复杂度：O(m + n)
空间复杂度：O(m)
C++代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.empty() || nums2.empty())
            return vector<int>();
        
        unordered_set<int> st;
        for(auto a : nums1)
            st.insert(a);
        
        vector<int> res;
        for(int a : nums2)
        {
            if(st.count(a) > 0)
            {
                res.push_back(a);
                st.erase(a);
            }
        }
        
        return res;
    }
};

Python代码

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        s = set()
        res = []
        for a in nums1:
            s.add(a)
        for a in nums2:
            if a in s:
                res.append(a)
                s.remove(a)
        return res

给定一个字符串，逐个翻转字符串中的每个单词。

示例:

输入: "the sky is blue",
输出: "blue is sky the".
说明:

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
进阶: 请选用C语言的用户尝试使用 O(1) 空间复杂度的原地解法。

解答
首先清除字符串s头和尾的所有空格，然后反转整个字符串，最后反转字符串中的每个单词，这样得到的单词序列满足要求。但是由于字符串单词之间只能保留一个空格，因此反转之后需要把字符串s拷贝到另一个字符串s1，然后s清空，之后每反转一次单词，将反转的单词加到s1尾部，同时加上一个空格，直到最后一个反转的单词，就不需要加空格了。

注意：边界条件很多

单词间的空格要减到一个，因此需要另一块内存来存放消除掉空格的字符串
s首尾都有可能有空格，所以刚开始需要过滤掉收尾的空格
s可能全都是空格，这种情况输出空字符串
时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
public:
    void reverseWords(string &s) {
        if(s.empty()) return;
        while(!s.empty() && s.back() == ' ')
            s.pop_back();
        
        if(s.empty()) return;
        
        reverse(s.begin(),s.end());
        
        while(!s.empty() && s.back() == ' ')
            s.pop_back();
        
        string s1(s);
        s.clear();
        
        int len = s1.size();
        int l = 0,r = 0;
        
        while(r < len)
        {
            if(s1[r] == ' ')
            {
                reverse(s1.begin() + l,s1.begin() + r);
                copy(s1.begin() + l,s1.begin() + r + 1,back_inserter(s));
                while(s1[r] == ' ' && r < len) r++;
                l = r;
            }
            
            r++;
        }
        
        reverse(s1.begin() + l,s1.begin() + r);
        copy(s1.begin() + l,s1.begin() + r,back_inserter(s));
    }
};

。。。