极客时间李煜东算法训练营2021版二期【包完结】

网盘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));
    }
};


。。。

上一篇:javaScript力扣刷题——简单数组(三)


下一篇:两个数组的交集 II --java