執行加減命令後打印修改後的數組  


難度級別 中烘焙
經常問 ByteDance 思科 思傑 免費收費 HackerRank 長郎 Opera 瀏灠器 Teradata數據
排列

您將得到一個大小為n的數組,最初該數組中的所有值均為0,然後執行查詢。 每個查詢包含四個值,查詢的類型T,範圍的左點,範圍的右點和數字k,您必須執行以下操作。

如果T = 0,則將值k加到給定數組中給定範圍(開始,結束)內的所有整數,

如果T = 1,則從給定數組中給定範圍(開始,結束)內的所有整數中減去k,

例  

arr[]={0, 0, 0, 0, 0}
Query: {(0, 2, 4, 1), (1, 3, 5, 2), (0, 1, 4, 3)}
3 4 2 2 -2

解釋

(0、2、4、1)將1加到該範圍內的所有整數,因為它是類型0查詢。

(1、3、5、2)從範圍內的所有整數中減去2,因為它是類型1查詢。

(0、1、4、3)將3加到該範圍內的所有整數,因為它是類型0查詢。

執行加減命令後打印修改後的數組  

 

多次查詢後打印修改後的數組的算法  

  1. 初始化 排列 與0。
  2. 對於每個查詢,
  3. 如果類型查詢要添加值,則在左1位置通過添加值k來更新值,在右位置減去值k。
  4. 如果類型查詢要減去值,則通過減去值k在左1位置更新值,在右邊的位置加k值。
  5. 遍歷數組並將每個先前的值添加到數組的當前值。
  6. 打印最終數組。
也可以看看
以相反的順序打印斐波那契數

解釋

給我們一個數組,最初,數組中的所有值均為0。我們還提供了一個 q 查詢的數量,查詢將分為兩種類型,每個查詢包含其類型,範圍和數字k。 如果查詢的類型為0,我們會將值k加到該範圍內的所有整數中。 如果給定查詢類型為1,我們將從範圍內的所有整數中減去k。 執行完所有查詢後,我們將打印該結果數組。

用於執行這些操作。 首先,我們需要檢查提供給我們的查詢類型。 如果查詢是第一種類型,則將值k添加到數組中範圍的起點。 同樣,從數組範圍的終點減去值k。

我們將與前面提到的技術相反。 如果允許使用類型1查詢,則必須減去範圍內整數數組的所有值。 然後,我們將從數組的起始範圍值中減去k。 之後,在範圍的端點索引處添加值k。

對於給定的每個查詢。 我們必須執行上述技術。 然後,我們將構建一個數組,在其中將先前的值添加到數組的當前值。 並將總和存儲為當前值。 或者可以說我們更新了數組的當前值。 構建陣列後,我們將打印陣列。 這將是修改後的數組的理想結果。

也可以看看
朋友配對問題

推薦碼  

執行加法和減法命令後打印修改後的數組的C ++代碼

#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;

void solveQuery(int arr[], int n, int T, int left, int right, int k)
{
    if (T == 0)
    {
        arr[left -1] += k;
        arr[right] += -k;
    }
    else
    {
        arr[left -1] += -k;
        arr[right] += k;
    }
    return;
}

void build(int arr[], int n)
{
    for (int i = 1; i < n; ++i)
        arr[i] += arr[i-1];

    return;
}

int main()
{
    int n = 5;
    int arr[n+1];

    memset(arr, 0, sizeof(arr));


    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 0, 2, 4, 1);

    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 1, 3, 5, 2);

    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 0, 1, 4, 3);

    build(arr, n);

    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    return 0;
}
3 4 2 2 -2

Java代碼在執行加減命令後打印修改後的數組

import java.util.Arrays;

class AdditionSubtractionQuery
{
    static void solveQuery(int arr[], int n, int T, int left, int right, int k)
    {
        if (T == 0)
        {
            arr[left -1] += k;
            arr[right] += -k;
        }
        else
        {
            arr[left -1] += -k;
            arr[right] += k;
        }
        return;
    }
    
    static void build(int arr[], int n)
    {
        for (int i = 1; i < n; ++i)
            arr[i] += arr[i-1];
    }
    
    public static void main(String arg[])
    {
        int n = 5;
        int arr[] = new int[n+1];
        Arrays.fill(arr, 0);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 0, 2, 4, 1);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 1, 3, 5, 2);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 0, 1, 4, 3);

        build(arr, n);

        for (int i = 0; i < n; ++i)
            System.out.print(arr[i]+" ");
    }
}
3 4 2 2 -2

複雜度分析  

時間複雜度

O(q + n) 哪裡 “Q” 是查詢數,並且 “ n” 是數組中元素的數量。 因為首先我們執行耗時O(1)的Q查詢,然後構建數組則需要O(N)的時間。

也可以看看
查找字符串中嵌套括號的最大深度

空間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。 由於我們創建了一個數組來執行操作。 空間複雜度是線性的。