diff options
author | Jack Sangdahl <[email protected]> | 2025-01-06 10:43:01 +0100 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-06 10:43:01 +0100 |
commit | 2e10f9743041778aff34b4e6c84710db2098502a (patch) | |
tree | e575679e27726ecb02a0db5a3e95aa685a9acfa6 | |
parent | b218fc8b0fcd51654a4b9c92fdf57169f00d6ab3 (diff) | |
download | leetcode-2e10f9743041778aff34b4e6c84710db2098502a.tar.gz leetcode-2e10f9743041778aff34b4e6c84710db2098502a.zip |
1769. minimum number of operations to move all balls to each box
-rw-r--r-- | min_num_ops_ball_box.c | 38 | ||||
-rw-r--r-- | min_num_ops_ball_box.py | 38 |
2 files changed, 64 insertions, 12 deletions
diff --git a/min_num_ops_ball_box.c b/min_num_ops_ball_box.c index a6cba59..1492a6e 100644 --- a/min_num_ops_ball_box.c +++ b/min_num_ops_ball_box.c @@ -1,25 +1,39 @@ // 1769. Minimum Number of Operations to Move All Balls to Each Box -#include <stdio.h> -#include <stdlib.h> -#include <string.h> +#include "leetcode.h" + +/* + * you have 'n' boxes. you are given a binary string 'boxes' of length 'n' where + * 'boxes[i]' is '0' if the i'th box is empty, and '1' if it contains one ball. + * in one operation, you can move one ball from a box to an adjacent box. box + * 'i' is adjacent to box 'j' if 'abs(i - j) == 1'. note that after doing so, + * there may be more than one ball in some boxes. return an array 'answer' of + * size 'n' where 'answer[i]' is the minimum number of operations needed to move + * all the balls to i'th box. + */ int *minOperations(char *boxes, int *returnSize) { - int len = strlen(boxes), steps; - int *ans = malloc(len * sizeof(int)); - for (int i = 0; i < len; i++) { + int n = strlen(boxes), steps; + int *ans = (int *)malloc(n * sizeof(int)); + for (int i = 0; i < n; i++) { steps = 0; - for (int j = 0; j < len; j++) + for (int j = 0; j < n; j++) if (boxes[j] == '1') steps += abs(i - j); ans[i] = steps; } - *returnSize = len; + *returnSize = n; return ans; } int main() { - char boxes1[] = {"110"}, boxes2[] = {"001011"}; - int rs1[] = {3}, rs2[] = {6}; - printf("%c\n", *minOperations(boxes1, rs1)); // expect: 1,1,3 - printf("%c\n", *minOperations(boxes2, rs2)); // expect: 11,8,5,4,3,4 + char *b1 = "110", *b2 = "001011"; + int rs1, *mo1 = minOperations(b1, &rs1); + int rs2, *mo2 = minOperations(b2, &rs2); + for (int i = 0; i < rs1; i++) + printf("%d ", mo1[i]); // expect: 1 1 3 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", mo2[i]); // expect: 11 8 5 4 3 4 + printf("\n"); + free(mo1), free(mo2); } diff --git a/min_num_ops_ball_box.py b/min_num_ops_ball_box.py new file mode 100644 index 0000000..59d5233 --- /dev/null +++ b/min_num_ops_ball_box.py @@ -0,0 +1,38 @@ +# 1769. Minimum Number of Operations to Move All Balls to Each Box + +""" +you have 'n' boxes. you are given a binary string 'boxes' of length 'n' where +'boxes[i]' is '0' if the i'th box is empty, and '1' if it contains one ball. +in one operation, you can move one ball from a box to an adjacent box. box +'i' is adjacent to box 'j' if 'abs(i - j) == 1'. note that after doing so, +there may be more than one ball in some boxes. return an array 'answer' of +size 'n' where 'answer[i]' is the minimum number of operations needed to move +all the balls to i'th box. +""" + + +class Solution(object): + def minOperations(self, boxes): + """ + :type boxes: str + :rtype: List[int] + """ + l_cnt, l_cost, r_cnt, r_cost, n = 0, 0, 0, 0, len(boxes) + ans = [0] * n + for i in range(n): + if boxes[i - 1] == "1": + l_cnt += 1 + l_cost += l_cnt + ans[i] = l_cost + for i in range(n - 2, -1, -1): + if boxes[i + 1] == "1": + r_cnt += 1 + r_cost += r_cnt + ans[i] += r_cost + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.minOperations(boxes="110")) + print(obj.minOperations(boxes="001011")) |