成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LintCode] Order Problem

maybe_009 / 1222人閱讀

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;
    }
}

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://systransis.cn/yun/71339.html

相關(guān)文章

  • [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 評(píng)論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 評(píng)論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 評(píng)論0 收藏0
  • [LintCode] Spiral Matrix I & Spiral Matrix II

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

    tuantuan 評(píng)論0 收藏0
  • [LintCode/LeetCode] Combination Sum I & II

    摘要:和唯一的不同是組合中不能存在重復(fù)的元素,因此,在遞歸時(shí)將初始位即可。 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 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<