这是四则或许对你有些许帮助的信息:
1、👉 最近我发现了一个每日都会推送最新校招资讯的《校招日程》文档,其中包括往届补录、应届实习校招信息,比如各种大厂、国企、银行、事业编等信息都会定期更新,帮忙扩散一下。
2、😍 免费分享阿秀个人学习计算机以来收集到的免费学习资源,点此白嫖;也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏。
3、🚀如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人踩过的坑和留下的经验,事实上你现在遇到的大多数问题你的学长学姐师兄师姐基本都已经遇到过了。
4、🔥 欢迎准备计算机校招的小伙伴加入我的学习圈子,一个人踽踽独行不如一群人报团取暖,圈子里沉淀了很多过去21/22/23届学长学姐的经验和总结,好好跟着走下去的,最后基本都可以拿到不错的offer!此外,每周都会进行精华总结和分享!如果你需要《阿秀的学习笔记》网站中📚︎校招八股文相关知识点的PDF版本的话,可以点此下载 。
# 75. 颜色分类
力扣原题链接(点我直达) (opens new window)
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
1
2
2
进阶:
- 一个直观的解决方案是使用计数排序的两趟扫描算法。 首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
- 你能想出一个仅使用常数空间的一趟扫描算法吗?
# 第一版,直接解出来
执行用时 :4 ms, 在所有 cpp 提交中击败了90.02%的用户
内存消耗 :8.5 MB, 在所有 cpp 提交中击败了51.89%的用户
void sortColors(vector<int>& nums) {
int zeroCut=0, oneCut=0, twoCut=0;
for (auto& n : nums) {
if (n == 0) zeroCut++;
else if (n == 1) oneCut++;
else twoCut++;
}
for (size_t i = 0; i < nums.size(); ++i) {
if (i < zeroCut) nums[i] = 0;
else if (i >= zeroCut && i < zeroCut + oneCut) nums[i] = 1;
else
nums[i] = 2;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 第二版,进阶,双路快排的思想,感觉时间不太对
执行用时 :0 ms, 在所有 cpp 提交中击败了100.00%的用户
内存消耗 :8.5 MB, 在所有 cpp 提交中击败了50.30%的用户
void sortColors(vector<int>& nums) {
int low = 0, high = nums.size() - 1,index=-1;
while (low<=high)
{
if (nums[low] == 0) swap(nums[++index], nums[low++]);
else if (nums[low] == 2) swap(nums[high--], nums[low]);
else
low++;
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11