Weekly Contest 98

1. 888. 公平的糖果交换

分析：用flag标记一下B数组，然后从A中找到一个数，使得A[i]-(sum(A)-sum(B)/2)正好被flag标记

const int MAXB = 1e5 + 5;

class Solution {
public:
    
    int get_sum(vector<int> X) {
        int sum = 0;
        for(int i = 0; i < X.size(); i++) sum += X[i];
        return sum;
    }
    
    vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
        vector<int> ans(2);
        int delta = (get_sum(A) - get_sum(B))/2; //差必为偶(包含负数)
        /*
        //数据略水，下面的O(N*M)(N,M分别为A、B的长度)算法也ac啦
        for(int i = 0; i < A.size(); i++) {
            for(int j = 0; j < B.size(); j++) {
                if(A[i] - B[j] == delta) {
                    ans[0] = A[i], ans[1] = B[j];
                    return ans;
                }
            }
        }
        */
        vector<bool> f(MAXB, false); 
        for(int i = 0; i < B.size(); i++) f[B[i]] = true;
        for(int i = 0; i < A.size(); i++) { 
            //疑:当i>MAXB,不能确保f[i]=0, 所以此处要加个上界判断.用bitset或int则没这个问题
            if(A[i]-delta>0 && A[i]-delta<=100000 && f[A[i]-delta]) {
                ans[0] = A[i], ans[1] = A[i]-delta;
                break;
            }
        }
        return ans;
    }
};

2. 890. 查找和替换模式

分析：用两个哈希表和标记数组处理一下即可

class Solution {
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        vector<string> ans;
        for(int i = 0; i < words.size(); i++) {
            char h[26] = {'\0'}, h1[26] = {'\0'};
            bool flag[26] = {false}, flag1[26] = {false};
            int j;
            for(j = 0; j < pattern.length(); j++) {
                int offset = pattern[j]-'a';
                int offset1 = words[i][j]-'a';
                if(!flag[offset]) {
                    if(flag1[offset1] && h1[offset1] != pattern[j]) break; //
                    h[offset] = words[i][j];
                    h1[offset1] = pattern[j];
                    flag[offset] = flag1[offset1] = true;
                    continue;
                } 
                if(h[offset] != words[i][j]) break;
            }
            if(j == pattern.length()) ans.push_back(words[i]);
        }
        return ans;
    }
};
// ccc abb

3. 889. 根据前序和后序遍历构造二叉树

分析：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
//T: o(N^2), S: o(N)
class Solution {
public:
    int findPos(vector<int> post, int s, int e, int pattern) {
        int pos = -1;
        for(int i = s; i <= e; i++) {
            if(post[i] == pattern) {
                pos = i;
                break;
            }
        }
        return pos;
    }
    
    void createTree(TreeNode* &root, vector<int> pre, int s1, int e1, vector<int> post, int s2, int e2) {
        if(s1 > e1) return; //
        //root = new TreeNode;  error: no matching function for call to 'TreeNode::TreeNode()', 因为结点定义是带参构造函数
        root = new TreeNode(pre[s1]);
        if(s1 == e1) return;
        int p = findPos(post, s2, --e2, pre[++s1]); // post.indexOf(pre[s1])
        createTree(root->left, pre, s1, s1+p-s2, post, s2, p);
        createTree(root->right, pre, s1+p-s2+1, e1, post, p+1, e2);
    }
    
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        TreeNode* root = NULL;
        createTree(root, pre, 0, pre.size()-1, post, 0, post.size()-1);
        return root;
    }
};

4. 891. 子序列宽度之和

分析：

const int P = 1e9 + 7;
class Solution {
public:
    int sumSubseqWidths(vector<int>& A) {
        long long ans = 0;
        vector<int> pow2(A.size()); //如果不定义大小,后面只能用push_back
        pow2[0] = 1;
        for(int i = 1; i < A.size(); i++) pow2[i] = 2*pow2[i-1] % P;         
        sort(A.begin(), A.end()); //
        /*
        //way 1
        for(int i = 1; i < A.size(); i++) (ans += 1LL*(pow2[i]-1)*A[i]) %= P;
        for(int i = 0; i < A.size()-1; i++) {
            ans -= 1LL*(pow2[A.size()-i-1]-1)*A[i];
            ans %= P;
            if(ans < 0) ans += P;
        }
        */
        //way 2
        for(int i = 0; i < A.size(); i++) {
            (ans += 1LL*(pow2[i]-1)*A[i]) %= P;
            ans -= 1LL*(pow2[A.size()-i-1]-1)*A[i] % P;
            ans = (ans + P)%P;
        }
        return (int)ans;
    }
};

参照：

【1】： https://leetcode.com/problems/sum-of-subsequence-widths/solution/#

【2】：https://leetcode.com/problems/sum-of-subsequence-widths/solution/#