[Leetcode] 2293. Min Max Game

2293. Min Max Game

You are given a 0-indexed integer array nums whose length is a power of 2.

Apply the following algorithm on nums:

Let n be the length of nums. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n / 2.

For every even index i where 0 <= i < n / 2, assign the value of newNums[i] as min(nums[2 * i], nums[2 * i + 1]).

For every odd index i where 0 <= i < n / 2, assign the value of newNums[i] as max(nums[2 * i], nums[2 * i + 1]).

Replace the array nums with newNums.

Repeat the entire process starting from step 1.

Return the last number that remains in nums after applying the algorithm.

Constraints:

1 <= nums.length <= 1024

1 <= nums[i] <= 10^9

nums.length is a power of 2.

Analysis

This question can be resolved by the classic Divide and Conquer algorithm.

The only extra thing is we need a flag to indicate whether it is the first half or the second half.

when flag == 0, we choose the min;

when flag == 1, we choose the max.

See the code below:

class Solution {
public:
    int minMaxGame(vector<int>& nums) {
        return f(nums, 0, nums.size(), 0);
    }
private:
    int f(vector<int>&ns, int left, int right, int flag) {
        if(left+1 == right) return ns[left];
        int mid = left + (right - left)/2;
        int x = f(ns, left, mid, 0), y = f(ns, mid, right, 1);
        return flag ? max(x, y) : min(x, y);
    }
};

Leetcode 679: 24 Game

https://leetcode.com/problems/24-game/description/

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Example 1:

Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24

Example 2:

Input: [1, 2, 1, 2]
Output: False

Note:

1. The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
2. Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
3. You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

Notes:

This question can be solved by DFS (brutal force version). But here I want to share another solution using Divide and Conquer.

In some sense, due to the using of (), this question is similar to Leetcode 241: Different Ways to Add Parentheses.

First step, we can get all the permutations of the four numbers.

Then for each permutation, we can run divide and conquer to get all the possible results. The key is how to divide them first and then merge them back.

See the code below:

class Solution {
public:
    bool judgePoint24(vector<int>& nums) {
        double epslon = 0.00001;
        vector<vector<int>> allPermu = findAllPermu(nums);
        for(auto &a : allPermu) {
            vector<double> res = findAll(a, 0, (int)nums.size()-1);
            for(auto &a : res) {
                if(abs(a-24)<epslon) return true;
            }
        }
        return false;
    }

private:
    vector<vector<int>> findAllPermu(vector<int>& nums) {
        set<vector<int>> res;
        int len = nums.size();
        vector<bool> visit(len, false);
        vector<int> temp;
        dfs(nums, visit, temp, res);
        return vector<vector<int>> (res.begin(), res.end());
    }

    void dfs(vector<int>& nums, vector<bool>& visit, vector<int>& ts, set<vector<int>>& res) {
        if(ts.size() == nums.size()) {
            res.insert(ts);
            return;
        }
        for(int i=0; i<nums.size(); ++i) {
            if(visit[i]) continue;
            visit[i] = true;
            ts.push_back(nums[i]);
            dfs(nums, visit, ts, res);
            ts.pop_back();
            visit[i] = false;
        }
    }

    vector<double> findAll(vector<int>& nums, int left, int right) {
        if(left > right) return {};
        if(left == right) return {(double)nums[left]};
        set<double> res;
        for(int i=left; i<right; ++i) {
            auto lvs = findAll(nums, left, i);
            auto rvs = findAll(nums, i+1, right);
            for(auto &a: lvs) {
                for(auto &b: rvs) {
                    res.insert(a+b);
                    res.insert(a-b);
                    res.insert(a*b);
                    if(b != 0.0) res.insert(a/b);
                }
            }
        }
        return vector<double> (res.begin(), res.end());
    }
};

Leetcode 241: Different Ways to Add Parentheses

https://leetcode.com/problems/different-ways-to-add-parentheses/description/

Notes:

This question could be a very good interview question. Of course, if you cannot come up with the divide-and-conquer idea, it could be overwhelming.

We can apply () any place we want, it means we can divide it any place. So it is a question designed for the very fundamental and very powerful divide-and-conquer concept.

After dividing, we has successfully convert the original problem to a same problem but with a smaller size, so it can be solved by recursion.

For each divided part, we will calculate all the possible results from the expression, just like the original question.

So the basic case it when we have 0 element, we simply return an empty vector, {};

When we have only 1 element, we simply return a vector with that element, {v[i]};

When we have more 1 element, we need to introduce the operators between the numbers.

After we obtain all the possible results for each divided part, we can again connect them back using the operator between them. The is like the merging back concept after dividing them.

See the code below:

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        int len = input.size();
        vector<int> nums;
        for(int i=0; i<len; ){//convert the input to array
            if(input[i] >='0' && input[i] <='9'){
                int num = 0;
                while(i<len && input[i] >='0' && input[i] <='9') {
                    num = num*10 + (input[i++] - '0');
                }
                nums.push_back(num);
            }
            if(i<len && input[i] == '+' || input[i] == '-' || input[i] == '*'){
                if(input[i] == '+') nums.push_back(-1);
                else if(input[i] == '-') nums.push_back(-2);
                else nums.push_back(-3);
                ++i;
            }
        }
        return dac(nums, 0, nums.size());
    }

private:
    vector<int> dac(vector<int> &ns, int left, int right) {
        if(left >= right) return {};
        if(left + 1 == right) return {ns[left]};
        vector<int> res;
        for(int i=left; i<right; ++i){
            if(ns[i] == -1 || ns[i] == -2 || ns[i] == -3){
                vector<int> v1 = dac(ns, left, i);//divide and conquer
                vector<int> v2 = dac(ns, i+1, right);
                for(int &a : v1) {//all possible results
                    for(int &b : v2) {
                        if(ns[i] == -1) res.push_back(a+b);
                        else if(ns[i] == -2) res.push_back(a-b);
                        else res.push_back(a*b);
                    }
                }
            }
        }
        return res;
    }
};

Follow up:

It is said it is one phone interview from Google: given a array with integers, add operators, +, -, *, /, or () any places legally. Return all the possible results after the operations.

So the core algorithm used is in the above dac() function. For, /, we need to deal with 0. or data type. And we can discuss with the interviewer for these considerations.

Leetcode 23: Merge K Sorted Lists

https://leetcode.com/problems/merge-k-sorted-lists/description/

Notes:

A very classic question!

The basic idea is divide and conquer. After dividing, the basic task becomes merging two sorted lists, which is very easy to implement.

The time complexity is O(N*M), where N is the number of list and M is the averaged number of notes for each list. Since each note is processed only one time. (see the update below)

 In comparison, if we a used naive brute-force way to do this by two-layer for loops, the time complexity is O(N*N*M). Since we will repeat to process the notes that have already been temporally processed before.

[update in 2019-12-03] the time complexity of the following code is O(N*logN*M), which is derived from the typical divide and conquer algorithm (similar to merge sort).

See the code below:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return div(lists, 0, lists.size());
    }

private:
    ListNode* div(vector<ListNode*> &ls, int left, int right) {
        if(left == right) return NULL;
        if(left + 1 == right) return ls[left];
        int mid = left + (right - left)/2;
        return mergeSorted(div(ls, left, mid), div(ls, mid, right));
    }

    ListNode* mergeSorted(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        if(!l2) return l1;
        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy, *p1 = l1, *p2 = l2;
        while(p1 && p2) {
            if(p1->val <= p2->val) {
                p->next = p1;
                p1 = p1->next;
            }
            else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        if(p1) p->next = p1;
        else p->next = p2;
        return dummy->next;
    }
};