头像

yzm0211




离线:3天前



yzm0211
2019-09-01 02:39
class UnionFind{
public:
    vector<int>father;
    UnionFind(int num){//num表示元素的个数
        for(int i = 0; i < num; i++){
            father.push_back(i);//箭头指向自己
        }
    }
    int Find(int n){
        //递归
        if(father[n] == n)
            return n;
        father[n] = Find(father[n]);//路径压缩版本
        return father[n];
    }
    bool Union(int a, int b){//返回a和b是否本身在一个集合里
        int fa = Find(a);
        int fb = Find(b);
        bool res = fa==fb;
        father[fb] = fa;
        return res;
    }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int N = edges.size();
        UnionFind UF(N+1);
        vector<int>res(2, 0);
        for(int i = 0; i < edges.size(); i++){
            int u = edges[i][0];
            int v = edges[i][1];
            if(UF.Union(u, v)){//冗余
                res[0] = u;
                res[1] = v;
            }
        }
        return res;
    }
};



活动打卡代码 AcWing 547. Friend Circles

yzm0211
2019-09-01 02:37
class UnionFind{
public:
    vector<int>father;
    UnionFind(int num){//num表示元素的个数
        for(int i = 0; i < num; i++){
            father.push_back(i);//箭头指向自己
        }
    }
    int Find(int n){
        //递归
        if(father[n] == n)
            return n;
        father[n] = Find(father[n]);//路径压缩版本
        return father[n];
    }
    void Union(int a, int b){
        int fa = Find(a);
        int fb = Find(b);
        father[fb] = fa;
    }
};
class Solution {
public:  
    int findCircleNum(vector<vector<int>>& M) {
        int N = M.size();
        UnionFind UF(N);
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(M[i][j]){
                    UF.Union(i, j);//两个人是朋友则合并朋友圈
                }
            }
        }
        int res = 0;
        for(int i = 0; i < N; i++){
            if(UF.Find(i) == i)//计算朋友圈的个数
                res++;
        }
        return res;
    }
};




yzm0211
2019-09-01 02:34
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        int tot = 0, ans = 0;
        hash[0] = 1;
        for (auto x : nums) {
            tot += x;
            ans += hash[tot - k];
            hash[tot]++;
        }
        return ans;
    }
};




yzm0211
2019-09-01 02:32
class Solution {
public:
    string dfs(TreeNode *r, unordered_map<string, int> &hash, vector<TreeNode*> &ans) {
        if (r == NULL)
            return "";
        string cur = "";
        cur += to_string(r -> val) + ",";
        cur += dfs(r -> left, hash, ans) + ",";
        cur += dfs(r -> right, hash, ans);
        hash[cur]++;
        if (hash[cur] == 2)
            ans.push_back(r);
        return cur;
    }
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        unordered_map<string, int> hash;
        vector<TreeNode*> ans;
        dfs(root, hash, ans);
        return ans;
    }
};


活动打卡代码 AcWing 706. Design HashMap

yzm0211
2019-09-01 02:22
class MyHashMap {
public:
    /** Initialize your data structure here. */
    const static int N = 20011;

    vector<list<pair<int,int>>> hash;

    MyHashMap() {
        hash = vector<list<pair<int,int>>>(N);
    }

    list<pair<int,int>>::iterator find(int key)
    {
        int t = key % N;
        auto it = hash[t].begin();
        for (; it != hash[t].end(); it ++ )
            if (it->first == key)
                break;
        return it;
    }

    /** value will always be non-negative. */
    void put(int key, int value) {
        int t = key % N;
        auto it = find(key);
        if (it == hash[t].end())
            hash[t].push_back(make_pair(key, value));
        else
            it->second = value;
    }

    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        auto it = find(key);
        if (it == hash[key % N].end())
            return -1;
        return it->second;
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        int t = key % N;
        auto it = find(key);
        if (it != hash[t].end())
            hash[t].erase(it);
    }
};



yzm0211
2019-09-01 02:19
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> res;
        unordered_map<string, int> S;
        for (int i = 0; i + 10 <= s.size(); i ++ )
        {
            string str = s.substr(i, 10);
            if (S[str] == 1) res.push_back(str);
            S[str] ++ ;
        }
        sort(res.begin(), res.end());
        return res;
    }
};


活动打卡代码 AcWing 1. Two Sum

yzm0211
2019-09-01 02:19
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        vector<int> res;
        unordered_map<int,int> hash;
        for (int i = 0; i < nums.size(); i ++ )
        {
            int another = target - nums[i];
            if (hash.count(another))
            {
                res = vector<int>({hash[another], i});
                break;
            }
            hash[nums[i]] = i;
        }
        return res;
    }
};



yzm0211
2019-08-11 16:14
class Solution {
    deque<int> q;
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        for(int i = 0; i < nums.size(); i++){
            while (q.size() && i - q.front() >= k) q.pop_front();//维护队列头部是否需要出列
            while (q.size() && nums[q.back()] < nums[i]) q.pop_back();//维护单调队列只让nums[q.back()] >= nums[i]入队
            q.push_back(i);// nums[q.back()] > nums[i];
             if(i >= k -1) res.push_back(nums[q.front()]);//在窗口等于k时才取值
        }
        return res;

    }
};


活动打卡代码 AcWing 42. Trapping Rain Water

yzm0211
2019-08-11 15:55
class Solution{
public:
    int trap(vector<int>& height){
        int left = 0,right = height.size() - 1,water = 0,minHeight = 0;
        while(left < right){
            while(left < right && height[left] <= minHeight)
                water += minHeight - height[left++];
            while(left < right && height[right] <= minHeight)
                water += minHeight - height[right--];
            minHeight = min(height[left],height[right]);
        }
        return water;
    }
};


活动打卡代码 AcWing 155. Min Stack

yzm0211
2019-08-11 15:36
#include<stack>
using namespace std;
class MinStack {
    stack<int>stk1;
    stack<int>stk2;
public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        stk1.push(x);
        if(stk2.empty() || x <= stk2.top()){//这里一定要小于等于
            stk2.push(x);
        }

    }

    void pop() {
        if(stk1.empty()) return ;
        if(stk1.top() == stk2.top()){
            stk2.pop();
        }
        stk1.pop();
    }

    int top() {
       // if(stk1.empty()) return 0;
        return stk1.top();

    }

    int getMin() {
        return stk2.top();
    }
};