数据结构基础day2

题目：75. 颜色分类

我的解法：双重循环交换

交换操作可以用swap，时间复杂度为O(n^2)

class Solution {
public:void sortColors(vector<int>& nums) {int n = nums.size();for(int i=0; i<n; ++i){for(int j=i+1; j<n; ++j){if(nums[j]<nums[i]){int temp = nums[j];nums[j] = nums[i];nums[i] = temp;}}}}
};

其他解法1：单指针，两次循环

时间复杂度O(n)

class Solution {
public:void sortColors(vector<int>& nums) {int n = nums.size();int ptr = 0;for(int i=0; i<n; ++i){	//调整0到前面去if(nums[i]==0){swap(nums[i], nums[ptr]);++ptr;}}for(int i=ptr; i<n; ++i){	//调整1到前面去if(nums[i]==1){swap(nums[i], nums[ptr]);++ptr;}}}
};

其他解法2：双指针，一次遍历

class Solution {
public:void sortColors(vector<int>& nums) {int n = nums.size();int p0 = 0, p2 = n-1;	//一个从头遍历，一个从尾遍历for(int i=0; i<n; ++i){while(i<=p2 && nums[i]==2){	//将2移到后面去swap(nums[i], nums[p2]);--p2;}if(nums[i]==0){	//如果交换过来的数是0，和p0做交换swap(nums[i], nums[p0]);++p0;}}}
};

题目：56. 合并区间

解法：排序加比较

对intervals进行排序，比较区间边界值

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> merged;	//存储已经合并好的数组sort(intervals.begin(), intervals.end());	//对intervals进行排序for(int i=0; i<intervals.size(); ++i){	//遍历intervalsint L = intervals[i][0], R = intervals[i][1];	//取待合并的区间边界值if(!merged.size()||merged.back()[1]<L){	//如果merged中还没有数组，或者，最后一个数组的右边界小于待合并的区间的左边界值，将该待合并区间直接插入merged中merged.push_back(intervals[i]);}else{	//否则merged的最后一个区间和待合并区间有重合，调整边界值merged.back()[1] = max(merged.back()[1], R);}}return merged;}
};

题目：705. 设计哈希集合

1. 设计哈希函数
2. 冲突处理：（1）链表地址法（2）开放地址法（h h+1 h+2……）（3）再哈希法（换哈希函数）
3. 扩容，当元素过多要扩容哈希集合

解法：

class MyHashSet {
private:vector<vector<int>> data;	//存储hash表static const int base = 769;	//设置映射质数static const int hash(int key){	//哈希函数，h(key)=key mod basereturn key%base;}
public:MyHashSet() : data(base){}	//初始化，注意这个形式void add(int key) {int h = hash(key);	//找到对应映射哈希值for(auto it = data[h].begin(); it!=data[h].end(); ++it){	//链地址法if((*it) == key) return;	//如果已经存在键值返回}data[h].push_back(key);	//对应hash值的hash表中无key，存储key}void remove(int key) {int h = hash(key);	//找到对应映射哈希值for(auto it = data[h].begin(); it!=data[h].end(); ++it){if((*it) == key){data[h].erase(it);	//找到对应key，删掉return;}}}bool contains(int key) {int h = hash(key);for(auto it = data[h].begin(); it!=data[h].end(); ++it){if((*it) == key){	//存在对应key，返回truereturn true;}}return false;}
};/*** Your MyHashSet object will be instantiated and called as such:* MyHashSet* obj = new MyHashSet();* obj->add(key);* obj->remove(key);* bool param_3 = obj->contains(key);*/

题目：706. 设计哈希映射

解法：同705

这里要求存储【key，value】，所以hashmap的初始化是list

class MyHashMap {
private:vector<list<pair<int, int>>> hashmap;	//初始化为list类型的数组static const int base = 769;static int hash(int key){return key%base;}
public:MyHashMap() : hashmap(base){}void put(int key, int value) {int h = hash(key);for(auto it = hashmap[h].begin(); it!=hashmap[h].end(); ++it){if((*it).first==key){	//找到键值为key的表的位置(*it).second=value;	//设置对应valuereturn;}}hashmap[h].push_back(make_pair(key, value));	//如果不存在key，成pair存入}int get(int key) {int h = hash(key);for(auto it = hashmap[h].begin(); it!=hashmap[h].end(); ++it){if((*it).first==key){	//找到对应key，返回valuereturn (*it).second;}}return -1;	//没有返回-1}void remove(int key) {int h = hash(key);for(auto it = hashmap[h].begin(); it!=hashmap[h].end(); ++it){if((*it).first==key){	//找到对应key的键值对hashmap[h].erase(it);	//清空return;}}}
};/*** Your MyHashMap object will be instantiated and called as such:* MyHashMap* obj = new MyHashMap();* obj->put(key,value);* int param_2 = obj->get(key);* obj->remove(key);*/