[LintCode] Order Problem

maybe_009 發布于2019-08-16 12:34 / 1208人閱讀

Problem

There is now an order with demand for n items, and the demand for the i-th item is order[i]. The factory has m production modes. Each production mode is shaped like [p[1],p[2],...p[n]], that is, produce p[1] first items, p[2] second items... You can use multiple production modes. Please tell me how many items do not meet the demand at least in the case of not exceeding the demand of any kind of items?

Example

Given order=[2,3,1], pattern=[[2,2,0],[0,1,1],[1,1,0]] , return 0.

Explanation:
Use [0,1,1] once, [1,1,0] twice, remaining [0,0,0].
Given order=[2,3,1], pattern=[[2,2,0]] , return 2.

Explanation:
Use [2,2,0] once, remaining [0,1,1].

Solution

public class Solution {
    private int minCount;
    /**
     * @param order: The order
     * @param pattern: The pattern
     * @return: Return the number of items do not meet the demand at least
     */
    public int getMinRemaining(int[] order, int[][] pattern) {
        for (int count: order) {
            minCount += count;
        }
        
        if (order == null || order.length == 0) {
            return 0;
        }
        
        if (pattern == null || pattern.length == 0) {
            return minCount;
        }

        int[] record = new int[order.length];
        DFS(order, pattern, record, 0);
        return minCount;
    }

    private void DFS(int[] order, int[][] pattern, int[] record, int curIndex) {
        if (!isValid(order, record) || curIndex == pattern.length) {
            return;
        }
        // path_1: 
        DFS(order, pattern, record, curIndex + 1);
        
        int max = getMaxUsage(order, pattern[curIndex]);
        if (max < 0) {
            return;
        }
        for (int i = 0; i < max; i++) {
            for (int j = 0; j < order.length; j++) {
                record[j] += pattern[curIndex][j];
            }
            // path_2
            DFS(order, pattern, record, curIndex + 1);
        }
        
        for (int j = 0; j < order.length; j++) {
            record[j] -= (max * pattern[curIndex][j]);
        }
    }

    // get the max times the pattern can be used, if any item exceeds the limit, return -1
    private int getMaxUsage(int[] order, int[] pattern) {
        int max = -1;
        for (int i = 0; i < order.length; i++) {
            if (order[i] < pattern[i]) {
                return -1;
            } else if (pattern[i] > 0) {
                int cur = order[i] / pattern[i];
                if (cur < max || max < 0) {
                    max = cur;
                }
            } else {
                continue;
            }
        }
        return max;
    }

    //check if the record is valid, update minCount if true
    private boolean isValid(int[] order, int[] record) {
        int curCount = 0;
        for (int i = 0; i < order.length; i++) {
            int diff = order[i] - record[i];
            if (diff < 0) {
                return false;
            }
            curCount += diff;
        }
        minCount = Math.min(minCount, curCount);
        return true;
    }
}

云服務器 GPU云服務器 problem LintCode LintCode134_LRU ORDER

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/71339.html

[LintCode] Nuts & Bolts Problem

Problem Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Comparison of a nut to another nut or a bolt to another bolt is not ...

tuomao 2019-08-14 15:15 評論0 收藏0
[LintCode/LeetCode] Subsets & Subsets II

Subsets Problem Given a set of distinct integers, return all possible subsets. Notice Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets. Example ...

tracy 2019-08-14 14:26 評論0 收藏0
[LintCode/LeetCode] Binary Tree Level Order Traver

Problem Given a binary tree, return the level order traversal of its nodes values. (ie, from left to right, level by level). For example:Given binary tree {3,9,20,#,#,15,7}, 3 / 9 20 / ...

makeFoxPlay 2019-08-14 15:48 評論0 收藏0
[LintCode] Spiral Matrix I & Spiral Matrix II

摘要：如果不在前兩個循環之后的話，那么那多余的一行或一列就會被加入數組兩次，造成錯誤的結果。解法和一樣，只是簡化了，甚至可以用一樣的方法去做，只要把也換成。使用，以及最后討論是否為奇數以判斷中間是否有一個未循環的點，是這道題的兩個有趣的地方。 Spiral Matrix I Problem Given a matrix of m x n elements (m rows, n columns...

tuantuan 2019-08-14 15:19 評論0 收藏0
[LintCode/LeetCode] Combination Sum I & II

摘要：和唯一的不同是組合中不能存在重復的元素，因此，在遞歸時將初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...

ThreeWords 2019-08-14 15:23 評論0 收藏0