Optimal Division (Leetcode 553)

A家的一道面试题 （A家的题真是出的越来越犀利了...）. 直接的方法就是memorization search. 对于每一个数，递归找左边的最大值，以及右边的最小值。然后联合string result一起做成一个struct返回。这里用hashmap来记录，避免重复计算.

class Solution {
public:
    struct Pair{
        float max_value, min_value;
        string max_record, min_record;
        Pair(float mx, float mn, string s1, string s2) : max_value(mx), min_value(mn), max_record(s1), min_record(s2){}
    };
    
    Pair *find_util(vector<int>& nums, int start, int end, vector<vector<bool>> &visited, unordered_map<string, Pair*> &record){
        if(start == end){
            Pair *P = new Pair(INT_MIN, INT_MAX, "", "");
            P->max_value = nums[start];
            P->min_value = nums[start];
            P->max_record = to_string(nums[start]);
            P->min_record = to_string(nums[start]);
            return P;
        }else if(visited[start][end]){
            string cur = to_string(start) + "->" + to_string(end);
            return record[cur];
        }
         Pair *P = new Pair(INT_MIN, INT_MAX, "", "");
        for(int i=start; i<end; i++){
            Pair *left = find_util(nums, start, i, visited, record);
            Pair *right = find_util(nums, i+1, end, visited, record);
            if (P->min_value > left->min_value / right->max_value) {
                P->min_value = left->min_value / right->max_value;
                P->min_record = left->min_record + "/" + (i + 1 != end ? "(" : "") + right->max_record + (i + 1 != end ? ")" : "");
            }
            if (P->max_value < left->max_value / right->min_value) {
                P->max_value = left->max_value / right->min_value;
                P->max_record = left->max_record + "/" + (i + 1 != end ? "(" : "") + right->min_record + (i + 1 != end ? ")" : "");
            }
        }
        visited[start][end] = true;
        string cur = to_string(start) + "->" + to_string(end);
        record[cur] = P;
        return P;
    }

    string optimalDivision(vector<int>& nums) {
        if(nums.empty()) return "";
        else if(nums.size() == 1) return to_string(nums[0]);
        int size = nums.size();
        vector<vector<bool>> visited(size, vector<bool>(size, 0));
        unordered_map<string, Pair*> record;
        Pair *P = find_util(nums, 0, size-1, visited, record);
        return P->max_record;
    }
    
};

参考discussion后，这道题最优解其实可以只有一种解法。那就是 a/(b/c/d) = a * c * d / b; 其实直接loop input array，并生成这样的string即可.

class Solution {
public:
    string optimalDivision(vector<int>& nums) {
        if(nums.empty()) return "";
        else if(nums.size() == 1) return to_string(nums[0]);
        else if(nums.size() == 2) return to_string(nums[0]) + '/' + to_string(nums[1]);
        string ret = to_string(nums[0]) + "/(" + to_string(nums[1]);
        for(int i=2; i<nums.size(); i++){
            ret += '/';
            ret += to_string(nums[i]);
        }
        ret += ')';
        return ret;
    }
};