• 【每日一题Day45】LC1769移动所有球到每个盒子所需要的最小操作数 | 模拟 贡献


    移动所有球到每个盒子所需要的最小操作数【LC1769】

    You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the ith 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 the ith box.

    Each answer[i] is calculated considering the initial state of the boxes.

    我承认我飘了

    暴力

    • 思路:暴力

      如果第 j j j个盒子里装有小球,那么移到到第 i i i个盒子,所需要的操作数为 a b s ( j − i ) abs(j-i) abs(ji),累加计算总和既可

    • 实现

      class Solution {
          public int[] minOperations(String boxes) {
              int n = boxes.length();
              int[] res = new int[n];
              for (int i = 0; i < n; i++){
                  for (int j = 0; j < n; j++){
                      if (boxes.charAt(j) == '1'){
                          res[i] += Math.abs(j - i);
                      }
                  }
              }
              return res;
          }
      }
      
      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 复杂度

        • 时间复杂度: O ( n 2 ) O(n^2) O(n2)
        • 空间复杂度: O ( 1 ) O(1) O(1)

    贡献

    • 思路:将所有球移入盒子 i i i所需要的操作数取决于其右侧盒子内的小球和左侧盒子内的小球至其的距离,最终操作数即为距离的累加和。因此盒子 i + 1 i+1 i+1所需要的操作数,可以由盒子 i i i所需要的操作数推出。

      • 假设所有球移入盒子 i i i所需要的操作数为 r e s i res_i resi,右侧盒子的小球个数为 r i g h t i right_i righti,左侧盒子的小球个数为 l e f t i left_i lefti(包括其自身),那么盒子 i + 1 i+1 i+1所需要的操作数为 r e s i + l e f t i − r i g h t i res_i+left_i-right_i resi+leftirighti
    • 实现

      class Solution {
          public int[] minOperations(String boxes) {
              int n = boxes.length();
              int[] res = new int[n];
              int left = boxes.charAt(0) - '0';
              int right = 0;
              for (int i = 1; i < n; i++){
                  if (boxes.charAt(i) == '1'){
                      right++;
                      res[0] += i;
                  }
              }
              for (int i = 1; i < n; i++){
                  res[i] = res[i-1] + left - right;
                  if (boxes.charAt(i) == '1'){
                      left++;
                      right--;
                  }
              }
              return res;
          }
      }
      
      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 复杂度

        • 时间复杂度: O ( n ) O(n) O(n)
        • 空间复杂度: O ( 1 ) O(1) O(1)
  • 相关阅读:
    一套SCDM脚本建模与二次开发攻略
    【Docker】Docker最近这么火,它到底是什么
    ABAP技术总结2022.8.30(ALV和smart forms)
    从零开始搭建 Hexo 个人博客
    动态拼接 merge 语句
    2022/07/29 入职健海JustFE团队,我学到了高效开发(年中总结)
    2023年武汉市职业院校技能大赛“网络安全”竞赛任务书
    泛型的理解和使用--定义后端统一返回结果
    推荐系统-召回-概述(一):内容为王
    git提交设置忽略指定文件,文件夹
  • 原文地址:https://blog.csdn.net/Tikitian/article/details/128145348