[LintCode] Order Problem

maybe_009 发布于2019-08-16 12:34 / 1209人阅读

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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