LeetCode 1769 - Minimum Number of Operations to Move All Balls to Each Box


https://chowdera.com/2021/03/20210326160903226c.html

Give you a length of n Binary string of boxes , among boxes[i] The value of is '0' It means the first one i A box is empty Of , and boxes[i] The value of is '1' There is... In the box One Pellet .

In one step , You can take One The ball moves from a box to an adjacent box . The first i A box and j Two adjacent boxes need to satisfy abs(i - j) == 1 . Be careful , After operation , There may be more than one ball in some boxes .

Returns a length of n Array of answer , among answer[i] It's moving all the balls to the second i What a box needs Minimum Operands .

Every answer[i] It all depends on the box The initial state Calculate .

有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ,其中 boxes[i] 的值为 '0' 表示第 i 个盒子是 空 的,而 boxes[i] 的值为 '1' 表示盒子里有 一个 小球。

在一步操作中,你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == 1 。注意,操作执行后,某些盒子中可能会存在不止一个小球。

返回一个长度为 n 的数组 answer ,其中 answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数。

每个 answer[i] 都需要根据盒子的 初始状态 进行计算。

输入:boxes = "110"
输出:[1,1,3]
解释:每个盒子对应的最小操作数如下:
1) 第 1 个盒子:将一个小球从第 2 个盒子移动到第 1 个盒子,需要 1 步操作。
2) 第 2 个盒子:将一个小球从第 1 个盒子移动到第 2 个盒子,需要 1 步操作。
3) 第 3 个盒子:将一个小球从第 1 个盒子移动到第 3 个盒子,需要 2 步操作。将一个小球从第 2 个盒子移动到第 3 个盒子,需要 1 步操作。共计 3 步操作。
示例 2:

输入:boxes = "001011"
输出:[11,8,5,4,3,4]

X. O(n) - left sum and right sum
    public int[] minOperations(String boxes) {
        int n = boxes.length();

        int[] left = new int[n];
        int[] right = new int[n];
        int[] ans = new int[n];

        int count = boxes.charAt(0) - '0';
        for(int i = 1 ; i < n ; i++){
            left[i] = left[i - 1] + count;
            count += boxes.charAt(i) - '0';
        }

        count = boxes.charAt(n - 1) - '0';
        for(int i = n - 2 ; i >=0 ; i--){
            right[i] = right[i + 1] + count;
            count += boxes.charAt(i) - '0';
        }
		
        for(int i = 0 ; i < n ; i++) {
            ans[i] = left[i] + right[i];
        }

        return ans;
    }
You can just get rid of the temp arrays. As problem asks us to return a new answer array, we won't consider that space in complexity analysis and hence space complexity is constant.
  public int[] minOperations(String boxes) {        
        int[] ans = new int[boxes.length()];
		int cnt = boxes.charAt(0) - '0';
		for(int i=1;i<boxes.length(); i++) {
			ans[i] = ans[i-1] + cnt;
			cnt += boxes.charAt(i) - '0';
		}
		
		int runner = 0; 
		cnt = boxes.charAt(boxes.length()-1) - '0';
		for(int i=boxes.length()-2;i>=0; i--) {
			runner += cnt; 
			ans[i] += runner;
			cnt += boxes.charAt(i) - '0'; 
		}
        return ans;  
  }
public int[] minOperations(String boxes) {
    int left = 0, right = 0, lsum = 0, rsum = 0, len = boxes.length();
	for (int i = 0; i < len; i++) {
		if (boxes.charAt(i) == '1') {
			right++;
			rsum += i;
		}
	}

	int[] ans = new int[len];

	for (int i = 0; i < len; i++) {
		ans[i] = lsum + rsum;
		if (boxes.charAt(i) == '1') {
			left++;
			right--;
		}
		lsum = lsum + left;
		rsum = rsum - right;
	}

	return ans;
}

We first "move" balls from left to right, and track how many ops it takes for each box.

For that, we count how many balls we got so far in cnt, and accumulate it in ops.

Then, we do the same from right to left.

public int[] minOperations(String boxes) {
    int[] res = new int[boxes.length()];
    for (int i = 0, ops = 0, cnt = 0; i < boxes.length(); ++i) {
       res[i] += ops;
       cnt += boxes.charAt(i) == '1' ? 1 : 0;
       ops += cnt;
    }    
    for (int i = boxes.length() - 1, ops = 0, cnt = 0; i >= 0; --i) {
        res[i] += ops;
        cnt += boxes.charAt(i) == '1' ? 1 : 0;
        ops += cnt;
    }
    return res;
}

What needs to be considered is , How to move to by all x The number of operations answer[x] Find all move to x+1 The number of operations answer[x+1]. about x+1 The ball on the left , Each ball will be operated once more , about x The ball on the right , Each will operate less than once . So , You just have to figure out x+1 The number of balls on the left side left(x+1) and x The number of balls on the right right(x) that will do . That is to say answer[x+1]=answer[x]+left(x+1)-right(x).

At present, we don't have to ask for it every time left and right, Save the position of the ball in line , Compare the current position and x,x+1 The relationship between , It can be calculated directly left and right The change of , But this code is easier to understand . You can try to optimize it yourself .

vector<int> minOperations(string boxes) { vector<int> positions; int n = boxes.size(); vector<int> answer(n, 0); for (int i = 0; i < n; i++) { if (boxes[i] == '1') { positions.push_back(i); if (i) answer[0] += i; } } for (int i = 1; i < n; i++) { // answer[i]=answer[i-1]+left(i)-right(i-1) int left = lower_bound(positions.begin(), positions.end(), i) - positions.begin(); int right = positions.end() - upper_bound(positions.begin(), positions.end(), i - 1); answer[i] = answer[i - 1] + left - right; } return answer; }

https://www.taodudu.cc/news/show-2114813.html

这个思路是:我们先找到把所有的 1 移到下标为 0 的起始位置需要的最小操作数为 r e s [ 0 ] res[0] res[0]。然后其余把所有 1 移到 i i i 位置的操作数 = 把所有 1 移到 i − 1 i - 1 i1 位置的的操作数 -(右边的所有 1) + (左边的所有 1),即转移方程是:

r e s [ i ] = r e s [ i − 1 ] − ( o n e s − v i s i t e d ) + v i s i t e d res[i] = res[i - 1] - (ones - visited) + visited res[i]=res[i1](onesvisited)+visited

原理是什么呢?因为把所有位置移动到 r e s [ i ] res[i] res[i] 位置相对于 r e s [ i − 1 ] res[i - 1] res[i1] 位置来说,所有它右边位置的 1 少移动了一次,它左边位置的 1 多移动了一次。

时间复杂度: O ( N ) O(N) O(N),空间复杂度: O ( 1 ) O(1) O(1).

https://shareablecode.com/snippets/minimum-number-of-operations-to-move-all-balls-to-each-box-c-solution-leetcode-u8Vu-zhvF

    vector<int> minOperations(string boxes) {
        vector<int> result(size(boxes)); 
        for (int i = 0, accu = 0, cnt = 0; i < size(boxes); ++i) {
           result[i] += accu;
           cnt += (boxes[i] == '1') ? 1 : 0;
           accu += cnt;
        }
        for (int i = size(boxes) - 1, accu = 0, cnt = 0; i >= 0; --i) {
            result[i] += accu;
            cnt += (boxes[i] == '1') ? 1 : 0;
            accu += cnt;
        }
        return result;
    }

X.

https://www.taodudu.cc/news/show-2114813.html

本题的数据规模为 2000,用 O ( N 2 ) O(N^2) O(N2) 的解法竟然能过。这个方法比较简单,直接对每个位置向左右两边统计具体各个 1 的位置之和。

    def minOperations(self, boxes: str) -> List[int]:
        N = len(boxes)
        res = [0] * N
        for i in range(N):
            left = [i - j for j in range(i) if boxes[j] == "1"]
            right = [j - i for j in range(i + 1, N) if boxes[j] == "1"]
            res[i] = sum(left) + sum(right)
        return res

https://kickstart.best/1769-minimum-number-of-operations-to-move-all-balls-to-each-box/

vector<int> minOperations(string boxes) {
int n = boxes.size();
vector<int> ret(n, 0);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
if(boxes[j] == '1') {
ret[i] += abs(i - j);
}
}
}
return ret;
}


Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts