75 Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

Link

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

56 Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Link

class Solution {
public:
    static bool comp(vector<int> a,vector<int> b){
        if(a[0]<b[0]) return true;
        else return false;
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        if(intervals.size() == 0) return vector<vector<int>>();
        sort(intervals.begin(),intervals.end(),comp);
        for(int i=0;i<intervals.size();i++){
            int left=intervals[i][0],right=intervals[i][1];
            if(ans.empty()||ans.back()[1]<left){
                ans.push_back({left,right});
            }else{
                ans.back()[1]=max(ans.back()[1],right);
            }
        }
        return ans;
    } 
};

706 Design HashMap

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

• MyHashMap() initializes the object with an empty map.
• void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
• int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
• void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Link

class MyHashMap {
    vector<list<pair<int,int>>> data;
    static const int base=769;
    static int hash(int key){
        return key%base;
    }
public:
    MyHashMap() :data(base){

    }
    
    void put(int key, int value) {
        int h= hash(key);
        for(auto it=data[h].begin();it!=data[h].end();it++){
            if((*it).first==key){
                (*it).second=value;
                return;
            }
        }
        data[h].push_back(make_pair(key,value));
    }
    
    int get(int key) {
        int h=hash(key);
        for(auto it=data[h].begin();it!=data[h].end();it++){
            if(it->first==key){
                return it->second;
            }
        }
        return -1;
    }
    
    void remove(int key) {
        int h=hash(key);
        for(auto it=data[h].begin();it!=data[h].end();it++){
            if(it->first==key){
                data[h].erase(it);
                return;
            }
        }
    }
};