vector在OJ中的使用
1.只出现一次的数字
class Solution {
public:
int singleNumber(vector<int>& nums) {
int value = 0;
for(auto e : v) {value ^= e; }
return value;
}
};
2.杨辉三角
class Solution {
public:
vector<vector<int>> generate(int numRows)
{
vector<vector<int>> vv;
vv.resize(numRows);
for (size_t i = 0; i < vv.size(); i++)
{
vv[i].resize(i + 1, 0);
vv[i][i] = vv[i][0] = 1;
}
for (size_t i = 0; i < vv.size(); i++)
{
for (size_t j = 0; j < vv[i].size(); j++)
{
if (vv[i][j] == 0)
{
vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
}
}
}
return vv;
}
};
class Solution {
public:
int removeDuplicates(vector<int>& nums)
{
int p=0,q=1;
while(q<nums.size())
{
if(nums[p]==nums[q])
{
q++;
}
else
{
nums[++p]=nums[q];
q++;
}
}
return p+1;
}
};
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int>& numbers)
{
sort(numbers.begin(),numbers.end());
int count=0;
int middle=numbers[numbers.size()/2];
for(int i=0;i<numbers.size();i++)
{
if(numbers[i]==middle)
{
count++;
}
}
return (count>numbers.size()/2)?middle:0;
// write code here
}
};
5.
class Solution
{
string strA[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
public:
void Combine(string digits, int level, string combineStr, vector<string>& v)
{
if (level == digits.size())
{
v.push_back(combineStr);
return;
}
int num = digits[level] - '0';
string str = strA[num];
for (size_t i = 0; i < str.size(); i++)
{
Combine(digits, level + 1, combineStr + str[i], v);
}
}
vector<string> letterCombinations(string digits)
{
vector<string> v;
if (digits.empty())
{
return v;
}
Combine(digits, 0,"", v);
return v;
}
};
使用memcpy拷贝问题
int main()
{
mm::vector<mm::string> v;
v.push_back("1111");
v.push_back("2222");
v.push_back("3333");
return 0;
}
假设模拟实现的vector中的reserve接口中，使用memcpy进行的拷贝,则：
1.memcpy是内存的二进制格式拷贝，将一段内存空间中的内容原封不动的拷贝到另一端内存中。
2.如果拷贝的是内置类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。
结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是
浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。
注意：vector是深拷贝。但vector空间上存的对象是string的数组，使用memcpy导致string对象的浅拷贝。
for(size_t i=0;i<v.size();i++)
{
_start[i]=v._start[i];
}
解决方案： T是string这样深拷贝的类，调用的是string赋值重载，实现string对象的深拷贝。
vector的模拟实现
#pragma once
#include <assert.h>
#include <iostream>
#include <algorithm>
namespace Q
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
// vector<int> v(10, 1);
// vector<int> v(10u, 1);
// vector<string> v1(10, "1111");
//选择问题
vector(size_t n, const T& val = T())
{
resize(n, val);
}
vector(int n, const T& val = T())
{
resize(n, val);
}
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
vector(const vector<T>& v)
{
_start = new T[v.capacity()];
//memcpy(_start,v._start,sizeof(T)*v.size());
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v._start[i];
}
/*_finish = v._finish;
_endofstorage = v._endofstorage;*/
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}
/*vector(const vector<T>& v)
{
reserve(v.capacity());
for (auto e : v)
{
push_back(e);
}
}*/
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_endofstorage = n;
}
}
void resize(size_t n, const T& val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish != _start + n)
{
*_finish = val;
_finish++;
}
}
}
void push_back(const T& x)
{
/*if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
_finish++;*/
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
size_t capacity() const
{
return _endofstorage - _start;
}
size_t size() const
{
return _finish - _start;
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <=_finish);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
_finish++;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
it++;
}
_finish--;
return pos;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
void print()
{
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
}