0%

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.

Read more »

vector的内存占用空间不会随着clear()和erase()方法的调用而减少,元素虽然去除但是内存空间只有在vector析构的时候才能被系统回收。像resize()方法如果缩小大小,虽然后续的元素无法被访问了,但内存空间也没有被释放。
其实如果需要空间动态缩小,可以用deque。
那么在不调用析构函数的情况下怎么释放vector的内存呢。

swap方法可以交换两容器的内容。

1
arr1.swap(arr2);

这可以用来收缩内存空间,

1
vector<int>(v).swap(v);

首先vector(v)利用拷贝构造函数创建了一个匿名对象,拥有全部的数据但没有空闲的空间。之后通过调用swap交换了v与匿名类的内容。
该语句执行完毕后匿名对象被析构,空间自动释放,达到了我们想要的效果。

基本用法

首先肯定是用法,由于在排序过程中涉及到元素交换等操作,所以sort函数仅支持可随机访问的容器,如数组, string、vector、deque等。函数原型如下

1
2
template<typename _RandomAccessIterator> void sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
template<typename _RandomAccessIterator, typename _Compare> void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

不传入第三个参数的话,默认是升序排列,直接传入两个迭代器即可。
降序需要传入比较函数。

Read more »

emplace是C++11标准中新增的,与push的效果相同。
但在底层实现机制上有所不同:

  1. push会先创建元素,然后将元素拷贝或移动到容器当中,若是拷贝还需要在结束后销毁之前创建的元素
  2. 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次,处理办法是可以规定线段的两个端点中每个端点只属于其中一条线。

Read more »