Your Site Title

Leetcode - 周赛

 
  • Jan 10, 2021

周赛

223th

5649. 解码异或后的数组

分类：数学

class Solution {
public:
    vector<int> decode(vector<int>& encoded, int first) {
        vector<int> res(encoded.size() + 1);
        res[0] = first;
        for(int i=0; i<res.size()-1; i++){
            res[i+1] = res[i]^encoded[i];
        }
        return res;
    }
};

5652. 交换链表中的节点

分类：链表

class Solution {
public:
    ListNode* swapNodes(ListNode* head, int k) {
        ListNode *faster = head, *slower = head;

        for(int i=1; i!=k; i++)
            { faster=faster->next; } //找到第k个

        ListNode* mark = faster;

        while(faster->next!=NULL) 
            { faster=faster->next; slower=slower->next; } //找到倒数第k个

        swap(mark->val, slower->val);
        
        return head;
    }
};

// 参考
class Solution {
public:
    ListNode* swapNodes(ListNode* head, int k) {
        ListNode* p = head;//遍历用
        ListNode* a = head;//指向第k
        ListNode* b = head;//指向倒数第k
        for(int i=1; p; i+=1){
            if(i<k) a = a->next;
            if(i>k) b = b->next;
            p = p->next;
        }
        swap(a->val, b->val);
        return head;
    }
};

5650. 执行交换操作后的最小汉明距离

分类：图、并查集

如果i和j可以交换，j和k可以交换，显然有i和k可以交换。用并查集维护这一关系

source中下标属于同一个连通分量的对应元素构成一个连同分量，target同理。

source和target对应连通分量的差集的和，即为最小汉明距离

class Solution {
public:
    int root(int *u, int i){
        while(i != u[i]) i = u[i];
        return i;
    }
    void connect(int *u, int i, int j){
        u[root(u, j)] = root(u, i);
    }
    bool isConnected(int* u, int i, int j){
        return root(u, i) == root(u, j);
    }
    int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
        int n = source.size(), *u = new int[n];
        map<int, multiset<int> > s, t;

        for(int i=0; i<n; i++) u[i]=i;
        for(int i=0; i<allowedSwaps.size(); i++)
            connect(u, allowedSwaps[i][0], allowedSwaps[i][1]);            
        
        for(int i=0; i<n; i++){
            int r = root(u, i);
            if(s.find(r) == s.end()){
                s[r] = multiset<int>();
                t[r] = multiset<int>();
            }
            s[r].insert(source[i]);
            t[r].insert(target[i]);
        }

        int res=0;
        for(auto it1=s.begin(), it2=t.begin(); it1!=s.end(); ++it1, ++it2){
            multiset<int> *s1 = &(*it1).second, *s2 = &(*it2).second;
            vector<int> vec_c(max(s1->size(), s2->size()));
	        auto iter = std::set_difference(s1->begin(), s1->end(), s2->begin(), s2->end(), vec_c.begin());
	        res += iter - vec_c.begin();
        }

        return res;
    }
};

我麻了，这就是周赛吗，光理解就花了好久

5639. 完成所有工作的最短时间

分类：动态规划

关于状态压缩

设有一个状态i∈[0, 2^N)代表完成这些工作需要的总时间tot[i],它的前一个状态，即某个1改成0，可记为i-2^x，故tot[i] = tot[i-2^x] + jobs[x]

设dp[j][i]为前j个工人，完成状态i需要花费的必要工作时间，再假设在这之前有j-1个工人完成了状态为i-s的工作，即第j个工人完成了状态为s的工作，那么dp[j][i] = max(dp[j-1][i-s], tot[s])

遍历所有的s，即可得到最短必要时间dp[j][i]=min(max{dp[j-1][i-s], tot[s]})

class Solution {
public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
		int n = jobs.size();
        vector<int> tot(1<<n, 0);
        vector<vector<int> > dp(k+1, vector<int>(1<<n, 0));
        
        //init tot[]
        for(int i=1; i<(1<<n); i++){ //i==0时显然为0
            for(int x=0; x<n; x++){
                if( (i & (1<<x)) == 0) continue; //说明没有交集
                int left = i - (1<<x);
	            tot[i] = tot[left] + jobs[x];
                break; //？
            }
        }
        
        //init dp[1] 前1个工人完成状态i需要时间tot[i]
        for(int i=0; i<(1<<n); i++){
            dp[1][i] = tot[i];
        }
        
        for(int j=2; j<k+1; j++){
            for(int i=0; i<(1<<n); i++){
                int _min = INT_MAX;
                for(int s=i; s; s = (s-1)&i){//遍历i的子集
                    
                    int t = max(dp[j-1][i-s], tot[s]);
                    _min = min(_min, t);
                }
                dp[j][i] = _min;
            }
        }
        return dp[k][(1<<n)-1];
        
    }
};

累了累了

2021/01/10

Search