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