构造给定数组的后缀递增/递减操作计数-yiteyi-C++库

给定一个非负整数数组。我们需要从一个全零数组构造给定的数组。我们可以做以下操作。

null

选择say i的任何索引，并将1添加到所有元素，或从索引i的所有元素中减去1到最后一个索引。我们基本上把后缀增加/减少1。

例如：

Input : brr[] = {1, 2, 3, 4, 5}Output : 5Here, we can successively choose indices 1, 2, 3, 4, and 5, and add 1 to corresponding suffixes.Input : brr[] = {1, 2, 2, 1}Output : 3Here, we choose indices 1 and 2 and adds 1 to corresponding suffixes, then we choose index 4 and subtract 1.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

允许 brr[] 被赋予数组和 arr[] 是当前数组（最初为0）。方法很简单：

为了使第一个元素相等，我们必须进行|brr[1]|运算。完成后，arr[2]、arr[3]、arr[4]、…arr[n]=brr[1]。
为了使第二个元素相等，我们必须进行| brr[2]–brr[1]|运算。完成后，arr[3]、arr[4]、arr[5]、…arr[n]=brr[2]。

一般来说，要使arr[i]=brr[i]，我们需要进行| brr[i]-b[i-1]运算。所以总的来说，我们必须进行|b[1]|+|b[2]–b[1]|+| b[3]–b[2]|+…+| b[n]–b[n–1]|操作。下面是上述方法的CPP和Java实现：

C++

                         // CPP program to find minimum number of steps                       
                         // to make the array equal to the given array.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to calculate min_Steps                       
                         int                                     minSteps(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 int                                     min_Steps = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 if                                     (i > 0)                       
                                                 min_Steps +=                                     abs                                     (arr[i] - arr[i - 1]);                       
                                   
                                                 // first element of arr.                       
                                                 else                       
                                                 min_Steps +=                                     abs                                     (arr[i]);                       
                                                 }                       
                                                 return                                     min_Steps;                       
                         }                       
           
                         // driver function                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 1, 2, 2, 1 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 cout << minSteps(arr, n) << endl;                       
                         }                       

JAVA

                         // Java program to find minimum number of steps                       
                         // to make the array equal to the given array.                       
                         import                                     java.util.*;                       
                         import                                     java.lang.*;                       
           
                         public                                     class                                     GfG {                       
                                                 // function to calculate min_Steps                       
                                                 public                                     static                                     int                                     minSteps(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 int                                     min_Steps =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
                                                 if                                     (i >                                     0                                     )                       
                                                 min_Steps +=                       
                                                 Math.abs(arr[i] - arr[i -                                     1                                     ]);                       
                                   
                                                 // first element of arr.                       
                                                 else                       
                                                 min_Steps += Math.abs(arr[i]);                       
                                                 }                       
                                                 return                                     min_Steps;                       
                                                 }                       
           
                                                 // driver function                       
                                                 public                                     static                                     void                                     main(String argc[])                       
                                                 {                       
                                                 int                                     [] arr =                                     new                                     int                                     [] {                                     1                                     ,                                     2                                     ,                                     2                                     ,                                     1                                     };                       
                                                 int                                     n =                                     4                                     ;                       
                                                 System.out.println(minSteps(arr, n));                       
                                                 }                       
                         }                       

Python3

                         # Python 3 program to find minimum number                       
                         # of steps to make the array equal to the                       
                         # given array.                       
           
                         # function to calculate min_Steps                       
                         def                                     minSteps(arr, n):                       
                                                 min_Steps                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 if                                     (i >                                     0                                     ):                       
                                                 min_Steps                                     +                                     =                                     abs                                     (arr[i]                                     -                       
                                                 arr[i                                     -                                     1                                     ])                       
                                   
                                                 # first element of arr.                       
                                                 else                                     :                       
                                                 min_Steps                                     +                                     =                                     abs                                     (arr[i])                       
                                                 return                                     min_Steps                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 arr                                     =                                     [                                     1                                     ,                                     2                                     ,                                     2                                     ,                                     1                                     ]                       
                                                 n                                     =                                     len                                     (arr)                       
                                                 print                                     (minSteps(arr, n))                       
           
                         # This code is contributed                       
                         # by PrinciRaj19992                       

C#

                         // C# program to find minimum number of steps                       
                         // to make the array equal to the given array.                       
                         using                                     System;                       
           
                         public                                     class                                     GfG {                       
                                   
                                                 // function to calculate min_Steps                       
                                                 public                                     static                                     int                                     minSteps(                                     int                                     [] arr,                                     int                                     n)                       
                                                 {                       
                                                 int                                     min_Steps = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 if                                     (i > 0)                       
                                                 min_Steps += Math.Abs(arr[i] - arr[i - 1]);                       
           
                                                 // first element of arr.                       
                                                 else                       
                                                 min_Steps += Math.Abs(arr[i]);                       
                                                 }                       
                                                 return                                     min_Steps;                       
                                                 }                       
           
                                                 // driver function                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] arr =                                     new                                     int                                     [] { 1, 2, 2, 1 };                       
                                                 int                                     n = 4;                       
                                                 Console.WriteLine(minSteps(arr, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m                       

PHP

                         <?php                       
                         // PHP program to find minimum                       
                         // number of steps to make the                       
                         // array equal to the given array.                       
           
                         // function to calculate min_Steps                       
                         function                                     minSteps(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 $min_Steps                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $i                                     > 0)                       
                                                 $min_Steps                                     +=                                     abs                                     (                                     $arr                                     [                                     $i                                     ] -                       
                                                 $arr                                     [                                     $i                                     - 1]);                       
                                   
                                                 // first element of arr.                       
                                                 else                       
                                                 $min_Steps                                     +=                                     abs                                     (                                     $arr                                     [                                     $i                                     ]);                       
                                                 }                       
                                                 return                                     $min_Steps                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $arr                                     =                                     array                                     ( 1, 2, 2, 1 );                       
                         $n                                     = sizeof(                                     $arr                                     ) ;                       
           
                         echo                                     minSteps(                                     $arr                                     ,                                     $n                                     ),                                     ""                                     ;                       
           
                         // This code is contributed by ajit                       
                         ?>                       

Javascript

                         <script>                       
                                                 // Javascript program to find minimum number of steps                       
                                                 // to make the array equal to the given array.                       
                                   
                                                 // function to calculate min_Steps                       
                                                 function                                     minSteps(arr, n)                       
                                                 {                       
                                                 let min_Steps = 0;                       
                                                 for                                     (let i = 0; i < n; i++) {                       
                                                 if                                     (i > 0)                       
                                                 min_Steps += Math.abs(arr[i] - arr[i - 1]);                       
           
                                                 // first element of arr.                       
                                                 else                       
                                                 min_Steps += Math.abs(arr[i]);                       
                                                 }                       
                                                 return                                     min_Steps;                       
                                                 }                       
                                   
                                                 let arr = [ 1, 2, 2, 1 ];                       
                                                 let n = arr.length;                       
                                                 document.write(minSteps(arr, n));                       
                                   
                                                 // This code is contributed by divyeshrabadiya07.                       
                         </script>                       

输出：

时间复杂性 =O（n）。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章