头像

gcc7




离线:1小时前


最近来访(74)
用户头像
七月不远
用户头像
枫夕
用户头像
予希
用户头像
zwling
用户头像
guobaocan
用户头像
StarLi9ht
用户头像
呼叫1118号小行星
用户头像
A_Better_Man
用户头像
奥来
用户头像
就爱摆烂_3
用户头像
acwing_4167
用户头像
alxy
用户头像
星光璀璨
用户头像
狂野的小黄花
用户头像
cloudsRise
用户头像
逆天小英才
用户头像
GuiYufeng
用户头像
Nowsastra
用户头像
纯纯代码人
用户头像
小魏


gcc7
1小时前

参考文献

ref
优先队列,归并排序

C++ 代码

class Twitter {
public:
    int timestamp{0};
    unordered_map<int, unordered_set<int>> follow_;
    // userId - posters, one post [timestamp, tweetId, userId, idx]
    // userId 是在多路归并排序的时候,找到队列;idx表示在当前序列的下标
    typedef vector<vector<int>> VVI;
    typedef vector<int> VI;
    unordered_map<int, VVI> posters_;

    Twitter() {

    }

    void postTweet(int userId, int tweetId) {
        int idx = posters_[userId].size();
        // 尾部最新
        posters_[userId].push_back({timestamp++, tweetId, userId, idx});
    }

    vector<int> getNewsFeed(int userId) {
        // 多路归并
        vector<int> res;
        priority_queue<VI, vector<VI>, less<VI>> heap;
        // 找到关注列表
        follow_[userId].insert(userId);
        for(int user : follow_[userId]){
            if(posters_[user].size())heap.push(posters_[user].back());
        }
        while(res.size()<10 && heap.size()){
            auto t = heap.top();
            heap.pop();
            res.push_back(t[1]);
            int userId = t[2], idx = t[3];
            if(idx-1 >= 0){
                heap.push(posters_[userId][idx-1]);
            }
        }
        return res;
    }

    void follow(int followerId, int followeeId) {
        follow_[followerId].insert(followeeId);
    }

    void unfollow(int followerId, int followeeId) {
        follow_[followerId].erase(followeeId);
    }
};

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter* obj = new Twitter();
 * obj->postTweet(userId,tweetId);
 * vector<int> param_2 = obj->getNewsFeed(userId);
 * obj->follow(followerId,followeeId);
 * obj->unfollow(followerId,followeeId);
 */



gcc7
3小时前

参考文献

lt ref
ref

C++ 代码

class Solution {
public:
    // w和h都比前一个大的最长上升序列,先排序就修改成了 LIS 问题
    // O(n^2)的解法会超时,还是修改是O(nlgn)
    // f[i]表示长度为i+1的tail最小值
    // 对于宽度 w 相同的数对,要对其高度 h 进行降序排序。因为两个宽度相同的信封不能相互包含的,逆序排序保证在 w 相同的数对中最多只选取一个。
    int maxEnvelopes(vector<vector<int>>& en) {
        // w不同,直接考虑h递增;w相同,只能取一个,所以h递减,保证不会选到2个,因为我们选递增序列
        auto cmp = [](vector<int>& e1, vector<int>& e2){
            return e1[0]<e2[0] || (e1[0]==e2[0] && e1[1]>e2[1]);
        };
        sort(en.begin(), en.end(), cmp);
        int n = en.size();
        // 考虑第二维的 LIS 问题
        vector<int> f;
        for(int i=0; i<n; ++i){
            auto& now = en[i];
            if(f.empty() || f.back() < now[1])f.push_back(now[1]);
            else {
                int l=0, r=f.size()-1;
                while(l<r){
                    int mid = l+r>>1;
                    if(f[mid]>=now[1])r=mid;
                    else l=mid+1;
                }
                f[l]=now[1];
            }
        }
        return f.size();
    }
};



gcc7
2天前

参考文献

ref
区间合并的分情况讨论,通过set中平衡树logn查找

C++ 代码

class SummaryRanges {
public:
    set<vector<int>> inters_;
    SummaryRanges() {
        inters_.insert({INT_MIN, INT_MIN});
        inters_.insert({INT_MAX, INT_MAX});
    }

    void addNum(int val) {
        auto iter = inters_.upper_bound({val, INT_MAX});
        auto right = iter;
        auto left = --iter;
        if((*left)[1] >= val)return;
        if((*left)[1]+1 == val && val+1 == (*right)[0]){
            inters_.insert({(*left)[0],(*right)[1]});
            inters_.erase(left);
            inters_.erase(right);
        } else if(val+1 == (*right)[0]){
            inters_.insert({val, (*right)[1]});
            inters_.erase(right);
        } else if((*left)[1]+1 == val){
            inters_.insert({(*left)[0], val});
            inters_.erase(left);
        } else {
            inters_.insert({val, val});
        }
    }

    vector<vector<int>> getIntervals() {
        vector<vector<int>> res;
        for(auto iter : inters_){
            if(iter[0]!=INT_MIN && iter[1]!=INT_MAX){
                res.push_back(iter);
            }
        }
        return res;
    }
};

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges* obj = new SummaryRanges();
 * obj->addNum(val);
 * vector<vector<int>> param_2 = obj->getIntervals();
 */



gcc7
2天前

参考文献

ref
map, multimap, set, multiset, unordered_map, unordered_multimap, unordered_set, unordered_multiset

C++ 代码

unordered_multiset 方法

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_multiset<int> h1(nums1.begin(), nums1.end());
        vector<int> res;
        for(int num : nums2){
            if(h1.count(num)){
                res.push_back(num);
                h1.erase(h1.find(num));
            }
        }
        return res;
    }
};

已经排序的情况,双指针方法。可以解决nums1和nums2都很大的情况,先外部排序,再分步来做

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        vector<int> res;
        for(int i=0, j=0; i<nums1.size() && j<nums2.size();){
            if(nums1[i] < nums2[j])++i;
            else if(nums1[i] > nums2[j])++j;
            else {
                res.push_back(nums1[i]);
                ++i, ++j;
            }
        }
        return res;
    }
};



gcc7
2天前

参考文献

求两个数组交集,结果需要去重

C++ 代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> h1(nums1.begin(), nums1.end());
        unordered_set<int> h2(nums2.begin(), nums2.end());
        vector<int> res;
        for(int num : h2){
            if(h1.count(num))res.push_back(num);
        }
        return res;
    }
};



gcc7
2天前

参考文献

ref
计数排序

C++ 代码

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> dict;
        for(int num : nums)dict[num]++;
        int n = nums.size();
        // 计数排序, 用频率来排序
        vector<int> fre(n+1);
        for(auto iter : dict)fre[iter.second]++;
        // for(int i=0; i<=n; ++i)cout << fre[i] << ",,";

        int threshold = n;
        while(k -= fre[threshold], k>0)threshold--;
        // 用上述的频率来筛选结果
        vector<int> res;
        for(auto iter : dict){
            if(iter.second>=threshold)res.push_back(iter.first);
        }
        return res;
    }  
};



gcc7
2天前

参考文献

ref
有条件的双指针

C++ 代码

class Solution {
public:
    string reverseVowels(string s) {
        set<char> vowels{'a', 'e', 'i', 'o', 'u'};
        for(int i=0, j=s.size()-1; i<j;++i, --j){
            while(i<j && !vowels.count(tolower(s[i])))++i;
            while(i<j && !vowels.count(tolower(s[j])))--j;
            if(i<j)swap(s[i], s[j]);
        }
        return s;
    }
};



gcc7
2天前

参考文献

双指针翻转字符串(char数组)

C++ 代码

class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i=0, j=s.size()-1; i<j; ++i, --j)swap(s[i], s[j]);
    }
};



gcc7
2天前

参考文献

ref

C++ 代码

动态规划

class Solution {
public:
    // dp方便理解
    // f[i] 表示i拆分后的最大值;
    // f[i] = (i-j)*max(f[j], j); // 分别表示将j拆分与不拆分
    int integerBreak(int n) {
        vector<int> f(n+1);
        f[0] = 0, f[1] = 1;
        for(int i=2; i<=n; ++i){
            // 计算i,所以j可以从1取到i-1
            for(int j=1; j<i; ++j){
                f[i] = max(f[i], (i-j)*max(f[j], j));
            }
        }
        return f[n];
    }
};

数学

class Solution {
public:
    int integerBreak(int n) {
        vector<int> f(7);
        // 需要尽可能多的3,f[2]和f[3]是特例,所以f[6]后面的 值才可以表示成 3^p*f[n]
        f[2] = 1, f[3] = 2, f[4] = 4, f[5] = 6, f[6] = 9;
        int res = 1;
        while(n>6){
            n -= 3;
            res *= 3;
        }
        return res*f[n];
    } 
};



gcc7
2天前

参考文献

加法较多,比如
1. 循环解法
2. 先判断是2的幂(即二进制只有1个1),再判断这个1是在偶数位
3. 4^n = 2^(2*n) = (2^n)^2, 先开根号,再判断是2的幂

ref

C++ 代码

循环解法

class Solution {
public:
    bool isPowerOfFour(int n) {
        if(n<1)return false;
        while(n%4 == 0){
            n /= 4;
        }
        return n == 1;
    }
};

解法2

class Solution {
public:
    bool isPowerOfFour(int n) {
        if(n<1)return false;
        // 注意运算优先级
        bool a = ((n&-n) == n);
        bool b = (n & 0x55555555) != 0;
        // cout << a << "," << b << endl;
        return a&&b;
    }
};

解法3

class Solution {
public:
    bool isPowerOfFour(int n) {
        if(n<1)return false;
        int m = sqrt(n);
        return m*m==n && ((1<<30)%n == 0);
    }
};