[LeetCode] Weekly Contest 127

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        int N = A.size();
        sort(A.begin(), A.end());

        int idx = 0;
        while(K--) {
            A[idx] = -A[idx];

            // next?
            if(K == 0)  break; // done
            if(idx+1 == N || A[idx+1] > 0) { // all positive
                sort(A.begin(), A.end());
                idx = 0;
            }
            else if(A[idx] > 0) {
                if(A[idx+1] == 0) break; // found zero
                if(A[idx+1] < 0) idx++; // go to the next
            }
        }

        int totalSum = 0;
        for(int i = 0; i < N; i++) {
            totalSum += A[i];
        }

        return totalSum;
    }
};

class Solution {
public:
    int clumsy(int N) {

        int nums = N/4;
        int sig = (nums == 0)? 1:-1;
        int ans = 0;

        for(int i = 0; i < nums; i++) {
            if(i == 0)  ans += (1)*(N*(N-1)/(N-2))+(N-3);
            else        ans += (-1)*N*(N-1)/(N-2)+(N-3);
            N -= 4;
        }

        int rest = N%4;
        if(rest == 3)       ans += (sig)*N*(N-1)/(N-2);
        else if(rest == 2)  ans += (sig)*N*(N-1);
        else if(rest == 1)  ans += (sig)*N;

        return ans;
    }
};

class Solution {
public:
    int minDominoRotations(vector<int>& A, vector<int>& B) {
        int N = A.size();
        int ans[4] = {0,};
        bool fail[4] = {0, };

        int baseNum[4];
        baseNum[0] = A[0];
        baseNum[1] = A[N-1];
        baseNum[2] = B[0];
        baseNum[3] = B[N-1];

        int answer = INT_MAX;

        for(int i = 0; i < A.size()-1; i++) {
            for(int j = 0; j < 4; j++) {
                if(!fail[j]) {
                    int firstTarget, secondTarget;
                    if(j == 0)      { firstTarget = A[i+1];         secondTarget = B[i+1];      }
                    else if(j == 1) { firstTarget = A[N-1-(i+1)];   secondTarget = B[N-1-(i+1)];}
                    else if(j == 2) { firstTarget = B[i+1];         secondTarget = A[i+1];      }
                    else if(j == 3) { firstTarget = B[N-1-(i+1)];   secondTarget = A[N-1-(i+1)];}

                    if(baseNum[j] == firstTarget) {
                        ;
                    }
                    else if(baseNum[j] == secondTarget) {
                        ans[j]++;
                    }
                    else {
                        fail[j] = true;
                        ans[j] = INT_MAX;
                    }
                }
            }

            if(fail[0] && fail[1] && fail[2] && fail[3]) {
                return -1;
            }

        }

        return min(min(ans[0], ans[1]), min(ans[2], ans[3]));

    }
};

class Solution {
public:
    int i = 0;
    TreeNode* bstFromPreorder(vector<int>& A, int bound = 100) {
        if (i == A.size() || A[i] > bound) return NULL;
        TreeNode* root = new TreeNode(A[i++]);
        root->left = bstFromPreorder(A, root->val);
        root->right = bstFromPreorder(A, bound);
        return root;
    }
};