周赛遇到的LC.2915
https://leetcode.cn/problems/length-of-the-longest-subsequence-that-sums-to-target/description/
相当于01背包模型加上了一个背包恰好装满时取得的最大值
算法竞赛进阶指南0x01
直线交点数计算
灵犀互娱笔试第五题,出自HDU
http://acm.hdu.edu.cn/showproblem.php?pid=1466
假设平面上有n条直线,且不存在三条或以上直线共点的情况,求这n条直线可能存在多少种不同交点数.
例n=2,则可能的交点数量为0(平行)或者1(不平行)。
CF1555D Say No to Palindromes
CF1555D
https://codeforces.com/problemset/problem/1555/D
阿里巴巴控股集团笔试第三题改了下修改区间在线查询,原题是个比较简单的贪心,想清楚只有六种情况就可以了。
Let’s call the string beautiful if it does not contain a substring of length at least 2, which is a palindrome. Recall that a palindrome is a string that reads the same way from the first character to the last and from the last character to the first. For example, the strings a, bab, acca, bcabcbacb are palindromes, but the strings ab, abbbaa, cccb are not.
怎么不析构就置vector的capacity为0
vector的内存占用空间不会随着clear()和erase()方法的调用而减少,元素虽然去除但是内存空间只有在vector析构的时候才能被系统回收。像resize()方法如果缩小大小,虽然后续的元素无法被访问了,但内存空间也没有被释放。
其实如果需要空间动态缩小,可以用deque。
那么在不调用析构函数的情况下怎么释放vector的内存呢。
swap方法可以交换两容器的内容。
1 | arr1.swap(arr2); |
这可以用来收缩内存空间,
1 | vector<int>(v).swap(v); |
首先vector(v)利用拷贝构造函数创建了一个匿名对象,拥有全部的数据但没有空闲的空间。之后通过调用swap交换了v与匿名类的内容。
该语句执行完毕后匿名对象被析构,空间自动释放,达到了我们想要的效果。
智能指针底层浅析
linux三剑客
sort函数源码浅析
基本用法
首先肯定是用法,由于在排序过程中涉及到元素交换等操作,所以sort函数仅支持可随机访问的容器,如数组, string、vector、deque等。函数原型如下
1 | template<typename _RandomAccessIterator> void sort(_RandomAccessIterator __first, _RandomAccessIterator __last) |
不传入第三个参数的话,默认是升序排列,直接传入两个迭代器即可。
降序需要传入比较函数。
push和emplace的区别
emplace是C++11标准中新增的,与push的效果相同。
但在底层实现机制上有所不同:
- push会先创建元素,然后将元素拷贝或移动到容器当中,若是拷贝还需要在结束后销毁之前创建的元素
- emplace直接在容器尾部创建元素,省去了拷贝或者移动元素的过程。
push在底层调用的时候首先调用拷贝函数,然后调用移动构造函数,如无移动构造函数则调用拷贝构造函数。
emplace直接传入构造对象需要的元素,然后调用其构造函数。
相比之下emplace更节省内存,更节省时间。
但其实C++11后,push_back在条件允许的情况下会直接调用emplace。
emplace_back(type) 对应 push_back(type)
emplace(i, type) 对应 insert(type, i)
emplace_front(type) 对应 push_front()
判断点在多边形内部
中望的内推人说笔试可能会出判断点在多边形内部。
如果从点P作水平向左的射线的话,假设P在多边形内部,那么这条射线与多边形的交点必为奇数,如果P在多边形外部,则交点个数必为偶数(0也在内)。
所以,我们可以遍历多边形的每条边,求出交点的总个数。
比较特殊的情况是如果射线正好穿过两条边之间,那么这个交点会被算作2次,处理办法是可以规定线段的两个端点中每个端点只属于其中一条线。