資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學透過遞減相鄰對來建立零陣列
問題陳述包括透過遞減相鄰對來建立一個零陣列。
輸入將給出陣列，我們可以在陣列上執行操作，即**從第 i 個和第 (i+1) 個索引減去 1，其中 0<=i<(陣列大小−1)**。我們可以根據需要執行給定的操作，以使陣列的元素變為零。陣列將只包含正整數。
在這個問題中，我們將得到一個輸入陣列，我們需要檢查是否可以透過執行任意次數上述操作將陣列的所有元素轉換為零。如果可以透過執行任意次數的操作將陣列的所有元素轉換為零，則需要列印“Yes”，否則需要列印“No”。
讓我們透過以下示例來了解這個問題。
輸入
a[]={1,2,5,4}
輸出
Yes
**解釋** − 對陣列應用操作後，它變為
{1,2,5,4}={0,1,5,4}={0,0,4,4}
對 a[2] 和 a[3] 應用 4 次操作，我們得到 {0,0,0,0}。
由於可以透過多次應用指定的操作將陣列轉換為零陣列，因此輸出為 yes。
輸入
a[]={3, 2, 2, 6}
輸出
No
**解釋** − 對陣列應用操作後，
{3,2,2,6}={2,1,2,6}={1,0,2,6}={1,0,1,5}={1,0,0,4}
由於我們只能從 a[i] 和 a[i+1] 減去 1，並且無法將陣列轉換為零陣列，因此無法進一步執行操作。因此，輸出為 No。
有各種方法可以解決這個問題，以檢查是否可以透過多次應用指定的操作將陣列轉換為零陣列。讓我們看看並理解解決這個問題的有效方法。
方法一
如果陣列中奇數位置元素的和等於陣列中偶數位置元素的和，則該陣列可以轉換為零陣列。由於我們只能從 i 和 (i+1) 位置減去 1，因此要透過從奇數位置和偶數位置減去 1 來使陣列成為零陣列，只有當奇數位置元素的和等於偶數位置元素的和時才有可能。
例如，**{1,2,5,4}** 可以轉換為零陣列。
奇數位置元素的和，即 a[1]+a[3]=2+4=6
偶數位置元素的和，即 a[0]+a[2]=1+5=6
因此，它可以轉換為零陣列。
我們在方法中使用此邏輯來檢查是否可以透過遞減相鄰對將陣列轉換為零陣列。
在 C++ 中實現該方法的步驟
我們將建立一個函式來檢查陣列是否可以透過計算偶數位置和奇數位置的和來轉換為零陣列。
初始化兩個變數來儲存偶數位置和奇數位置的數字之和。
從 i=0 到 i<陣列大小迭代 for 迴圈。
在 for 迴圈中迭代時，我們將檢查 i 是否為偶數，如果為偶數，我們將把第 i 個位置對應的元素新增到我們將用來儲存偶數位置數字之和的變數中，否則，如果 i 不是偶數，我們將把第 i 個位置對應的數字新增到另一個變數中，以儲存奇數位置的和。
在整個陣列迭代之後，我們將透過比較變數中儲存的值來檢查偶數位置的和是否等於奇數位置的和。
如果兩者相等則返回 true，否則返回 false。
如果函式返回 true，則在輸出中列印“Yes”，否則列印“No”。
示例
//C++ code to check if the array can be converted to zero array by decrementing adjacent pairs by 1
#include<bits/stdc++.h>
using namespace std;
//function to check if the array can be converted to a zero array
bool check(int a[],int N){
int even_sum=0; //to store sum of elements at even position
int odd_sum=0; //to store sum of elements at odd positions
//to find the sum of even and odd positions
for(int i=0;i<N;i++){
//if i is even
if(i%2==0){
even_sum += a[i];
}
else{
odd_sum += a[i];
}
}
if(even_sum==odd_sum){ //return true if sum of even positions is equal to odd positions
return true;
} else{
return false;
}
}
int main()
{
int a[]={2,8,3,12,5,9,17,8,8,11};
int N; //to store size of the array
N=sizeof(a)/sizeof(a[0]);
//calling the function
if(check(a,N)==true){
cout<<"Yes"<<endl;
} else{
cout<<"No"<<endl;
}
return 0;
}
輸出
No
**時間複雜度** − O(N)，因為我們迭代陣列以儲存偶數位置和奇數位置的數字之和。
**空間複雜度** − O(1)，因為該方法沒有佔用額外的空間。
方法二
在這種方法中，我們將檢查由給定陣列形成的數字。如果由陣列形成的數字是 11 的倍數，則可以透過多次從 a[i] 和 a[i+1] 減去 1 將陣列轉換為零陣列。如果由給定陣列形成的數字不是 11 的倍數，則該陣列無法轉換為零陣列。
例如，陣列為 **{3,2,2,6}**。
由陣列形成的數字將是 3226。由於這個數字不是 11 的倍數，因此該陣列無法轉換為零陣列。
如果給定陣列為 **{1,2,5,4}**。
由陣列形成的數字將是 1254。這個數字是 11 的倍數，因為 11*114 等於 1254。因此，可以透過執行操作將陣列轉換為零陣列。
在 C++ 中實現該方法的步驟
我們將建立一個函式來檢查由給定陣列形成的數字是否是 11 的倍數。
初始化一個變數來儲存由陣列形成的數字。
我們將從 i=0 到 i<陣列大小迭代 for 迴圈，並透過將其乘以 10 並新增第 i 個數字來不斷更新數字。
一旦我們得到由陣列形成的數字，我們將檢查它是否能被 11 整除。如果它能被 11 整除，我們將列印 Yes，因為形成的數字是 11 的倍數，否則我們將列印 No。
**注意：**此方法僅適用於大小小於或等於 18 的陣列，因為由陣列形成的數字可能會超過資料型別的範圍。
示例
// C++ code to check if the array can be converted to a zero array
// by decrementing the pairs of adjacent
#include <bits/stdc++.h>
using namespace std;
//function to check if the given array can be converted to a zero array
bool check(int a[], int N)
{
// to store the number formed by the given array
long long number = 0;
for (int i = 0; i < N; i++){
//update the number
number = number * 10 + a[i];
}
//if number is multiple of 11, it will be divisible by 11
if(number%11==0){
return true;
} else{
return false;
}
}
int main()
{
int a[] = {2,5,1,3,6,1 };
int N = sizeof(a) / sizeof(a[0]); //calculating size of the array
//calling the function
if (check(a, N)){
cout << "Yes"<<endl;
} else{
cout << "No"<<endl;
}
}
輸出
Yes
**時間複雜度** − O(N)，因為我們迭代給定陣列以獲得由陣列形成的數字
**空間複雜度** − O(1)，因為該方法沒有佔用額外的空間。
結論
本文討論了檢查給定陣列是否可以透過遞減相鄰對將給定陣列轉換為零陣列的問題。我們嘗試使用簡單的邏輯在 O(N) 執行時間和恆定空間內使用兩種不同的方法在 C++ 中解決這個問題。
我希望在閱讀本文後，您能理解這個問題以及解決這個問題的方法。
77 次瀏覽
