A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast

Problem 1.

Let’s say we have n super washing machines in one row. Each machine may have a certain amount of clothes in it to start with, or it may be empty. In each operation, you can select any M (1≤ M ≤ N) M (1≤ M ≤ N) m (1≤ M ≤ N) washing machines, and at the same time send one item from each washing machine to the adjacent washing machine. Given an array of nonnegative integers representing the number of laundry items in each washing machine from left to right, give the minimum number of steps that would equal the number of laundry items left in all washing machines. If the number of clothes in each washing machine cannot be equal, return -1.

Example 1: Input: [1,0,5] Output: 3 Explanation: Step 1:1 0 <-- 5 => 1 1 4 Step 2:1 <-- 1 <-- 4 => 2 1 3 Step 3:2 1 <-- 3 => 2 2 Example 2: Input: [0,3,0] Output: 2 Explanation: Step 1:0 <-- 3 0 => 1 2 0 Step 2:1 2 --> 0 => 1 1 1 Example 3: Input: [0,2,0] Output: -1 Explanation: It is not possible for all three washing machines to have the same amount of laundry left at the same time.Copy the code

2.

If sum does not divisible into n, there is no solution. The final equal number is average = sum/n.

2, start with the simplest case, what should [3,2,1] choose? Of course, choose [3,2], 3 passes one to 2,2 passes one to 1, it only takes one operation to balance. We find that it is a process of water flowing downwards, and although our goal is to give one of the three to one, we are forced to choose the two that has been balanced in the middle. This means that once a washing machine is balanced, it must be selected if any clothes want to pass through it. Otherwise it will just take more steps to rebalance it.

3, want to understand the above point, we can further find that all the washing machine balance method only two cases: first, more or less clothes on both sides of the washing machine:

Second, the washing machine with less clothes is on the two sides, and the washing machine with the most clothes is in the middle

Let’s look at the first case. 4 will not change until 5 passes the two pieces to the right, which takes two steps. Then 4 passes a piece of clothing to the right, the total step is 3. So it’s equivalent to:

When we look at the second washing machine, we can combine 1 and 2 washing machines, and there are 3 pieces of clothes on the left (on average, each is 3 pieces, so it is 5+4-3*2=3). These 3 pieces should be passed to the right. Further, let’s draw a dotted line anywhere, assuming it has a leftleftleft item on the left and a rightrightright item on the right, and the left should be left’left ‘left ‘item, So there are left−left ‘left -left’left−left ‘clothes on the left, which need to flow to the right. When we go through all the dotted positions, the largest Max (left−left ‘) Max (left-left’) Max (left−left ‘) is the answer. The answer is obvious: only one piece of clothing can flow at a time, and the left side has more left−left ‘left -left’left−left ‘left−left ‘left−left ‘, so at least that many flow steps. So when these clothes flow to the right side, they can balance the right side. The diagram below:

And then if I have a YYY on the right that is greater than average, then it must not be right next to X on the left, because if I were right next to X, The left−left ‘left-left’left−left ‘left−left’ of the Y position must be greater than the left−left ‘left-left’left−left’ of the X position, So Max (left−left ‘) Max (left-left’) Max (left−left ‘) is YYY.

What if I have Z between X and Y that is less than average? We must first flow the garment from X to Z, and at the same time, to reduce the number of steps, we will flow the garment from Y to the further right. The point is, when Z is in equilibrium, Y must have been in equilibrium first, otherwise it would be Y right next to X, which is contradictory again. And when Y is balanced, it becomes the case where X is distributed to the right, and we can do that.

Once the first is clear, the second is easier to understand. Think of the washing machine with the most clothes as a true supermachine, with the left and right washing machines waiting to be handed out.

class Solution {
public:
    int findMinMoves(vector<int>& machines) {
        int i, size = machines.size(), sum = getSum(machines), average = sum / size;
        if(average * size ! = sum) {return - 1;
        }

        int left = machines[0], wantedLeft = average, right, wantedRight = average * (size - 2);
        int minMoves = max(abs(machines[0] - average), abs(machines[size - 1] - average));

        for (i = 1; i < size - 1; ++i) {
            int num = machines[i];
            right = sum - num - left;

            if (num >= average) {
                int moves = num - average;
                if (left > wantedLeft) {
                    moves += (left - wantedLeft);
                }
                if (right > wantedRight) {
                    moves += (right - wantedRight);
                }
                minMoves = max(minMoves, moves);

            }

            left += num;
            wantedLeft += average;
            wantedRight -= average;
        }

        return minMoves;
    }

    int getSum(vector<int>& machines) {
        int sum = 0;

        for (int num : machines) {
            sum += num;
        }

        returnsum; }};Copy the code

Complexity analysis

  • Time complexity: O(N).
  • Space complexity: O(1).

A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast