資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究透過選擇二進位制字串每個‘1’左側的陣列元素來最大化總和
在這個問題中，我們將找到透過從當前 1 的索引左側拾取未選擇的元素來獲得陣列元素的最大和。
我們可以使用向量列表和 sort() 方法來解決問題或優先順序佇列。優先順序佇列按排序順序插入元素。
問題陳述
我們給定一個二進位制字串 alpha 和相同長度的 arr[]。我們需要逐一選擇 alpha 的所有 '1'，並獲取在使用 0 到 p 個元素形成的 arr[] 的子陣列中未選擇的最大元素。這裡，P 是二進位制字串中選擇的 '1' 的索引。我們需要列印此類陣列元素的最大和。
示例
輸入
alpha = "01010"; arr[] = {30, 40, 3, 7, 20};
輸出
70
解釋
對於索引 1 處的 '1'，我們可以選擇 40。
對於索引 3 處的 '1'，我們可以選擇 30。
因此 40 和 30 的總和為 70。
輸入
alpha = "00000"; arr[] = {30, 40, 3, 7, 20};
輸出
0
解釋 - 二進位制字串包含所有 0。因此，它列印 0 和。
輸入
alpha = "00001"; arr[] = {100, 70, 80, 8, 20};
輸出
100
解釋 - 我們為 '1' 選擇 100，因為它位於 o 到 4 的子陣列內並且尚未被選中。
方法 1
在這種方法中，我們將繼續計算 1 的數量並將陣列元素推入列表。此外，我們保持列表排序，並且每當我們在二進位制字串中找到 '0' 時，我們將最後計數數量的元素新增到總和並將其從排序陣列中刪除。這裡，計數是在最後一個零和當前零之間出現的 1 的數量。
演算法
步驟 1 - 將 'count' 和 'array_sum' 初始化為零，以儲存兩個 0 之間的 1 的數量和最大和輸出。
步驟 2 - 此外，定義 'numbers' 列表以儲存陣列元素。
步驟 3 - 開始遍歷字串。如果二進位制字串中的當前字元為 '1'，則將 'count' 加 1。
步驟 4 - 否則，使用 hwile 迴圈進行迭代，直到 'count' 不等於 0。在迴圈中，將最後一個元素新增到 'array_sum'，將其從列表中刪除，並將 'count' 減 1。
步驟 5 - 將當前元素推入列表。
步驟 6 - 使用 sort() 方法對列表進行排序。
步驟 7 - 使用 while 迴圈進行迭代，直到 count 不等於零。在迴圈中，將陣列的最後一個元素新增到 array_sum，並從列表中刪除最後一個元素。
步驟 8 - 返回 array_sum 的值。
示例
#include <stdio.h>
#include <stdlib.h>
int getMaximumSum(int arr[], char alpha[], int len) {
int count = 0, array_sum = 0;
int numbers[len];
int numbers_size = 0;
// Iterate the string
for (int p = 0; p < len; p++) {
if (alpha[p] == '1') {
count++;
} else {
// Pop all count number of elements from the stack
while (count != 0) {
array_sum += numbers[--numbers_size];
count--;
}
}
// Push element to stack
numbers[numbers_size++] = arr[p];
// Sort the stack (use any sorting algorithm)
// Example: Bubble Sort
for (int i = 0; i < numbers_size - 1; i++) {
for (int j = 0; j < numbers_size - i - 1; j++) {
if (numbers[j] > numbers[j + 1]) {
// Swap numbers[j] and numbers[j+1]
int temp = numbers[j];
numbers[j] = numbers[j + 1];
numbers[j + 1] = temp;
}
}
}
}
// If the stack is not empty, then pop the elements and do its sum
while (count != 0) {
array_sum += numbers[--numbers_size];
count--;
}
// Return the answer
return array_sum;
}
int main() {
int len = 5;
char alpha[] = "01010";
int arr[] = {30, 40, 3, 7, 20};
printf("The maximum sum of array elements according to the given condition is %d\n", getMaximumSum(arr, alpha, len));
return 0;
}
輸出
The maximum sum of array elements according to the given condition is 70
#include <bits/stdc++.h>
using namespace std;
int getMaximumSum(int *arr, string alpha, int len) {
int count = 0, array_sum = 0;
vector<int> numbers;
// Iterate the string
for (int p = 0; p < len; p++) {
if (alpha[p] == '1') {
count++;
} else {
// Pop all count number of elements from the queue
while (count != 0) {
array_sum += numbers[numbers.size() - 1];
numbers.pop_back();
count--;
}
}
// Insert element to list
numbers.push_back(arr[p]);
// sort the list
sort(numbers.begin(), numbers.end());
}
// If the queue is not empty, then pop the elements and do its sum
while (count != 0) {
array_sum += numbers[numbers.size() - 1];
numbers.pop_back();
count--;
}
// return answer
return array_sum;
}
int main() {
int len = 5;
string alpha = "01010";
int arr[] = {30, 40, 3, 7, 20};
cout << "The maximum sum of array elements according to the given condition is " << getMaximumSum(arr, alpha, len) << endl;
return 0;
}
輸出
The maximum sum of array elements according to the given condition is 70
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Main {
public static int getMaximumSum(int[] arr, String alpha, int len) {
int count = 0;
int array_sum = 0;
List<Integer> numbers = new ArrayList<>();
// Iterate the string
for (int p = 0; p < len; p++) {
if (alpha.charAt(p) == '1') {
count++;
} else {
// Pop all count number of elements from the list
while (count != 0) {
array_sum += numbers.get(numbers.size() - 1);
numbers.remove(numbers.size() - 1);
count--;
}
}
// Append element to list
numbers.add(arr[p]);
// Sort the list
Collections.sort(numbers);
}
// If the list is not empty, then pop the elements and do its sum
while (count != 0) {
array_sum += numbers.get(numbers.size() - 1);
numbers.remove(numbers.size() - 1);
count--;
}
// Return the answer
return array_sum;
}
public static void main(String[] args) {
int len = 5;
String alpha = "01010";
int[] arr = {30, 40, 3, 7, 20};
System.out.println("The maximum sum of array elements according to the given condition is " + getMaximumSum(arr, alpha, len));
}
}
輸出
The maximum sum of array elements according to the given condition is 70
def getMaximumSum(arr, alpha, len):
count = 0
array_sum = 0
numbers = []
# Iterate the string
for p in range(len):
if alpha[p] == '1':
count += 1
else:
# Pop all count number of elements from the list
while count != 0:
array_sum += numbers.pop()
count -= 1
# Append element to list
numbers.append(arr[p])
# Sort the list
numbers.sort()
# If the list is not empty, then pop the elements and do its sum
while count != 0:
array_sum += numbers.pop()
count -= 1
# Return the answer
return array_sum
if __name__ == "__main__":
len = 5
alpha = "01010"
arr = [30, 40, 3, 7, 20]
print("The maximum sum of array elements according to the given condition is", getMaximumSum(arr, alpha, len))
輸出
The maximum sum of array elements according to the given condition is 70
時間複雜度 - O(N*NlogN)，其中 O(N) 用於遍歷字串，O(NlogN) 用於對陣列進行排序。
空間複雜度 - O(N) 用於在列表中儲存陣列元素。
方法 2
在這種方法中，我們將使用優先順序佇列來保持元素列表排序。它類似於堆資料結構，並且在堆中插入非常高效。
我們可以插入元素，它會設定元素在排序順序中的位置。當我們在二進位制字串中找到 '0' 時，我們可以從開頭彈出元素。
演算法
步驟 1 - 將 'count' 和 'array_sum' 初始化為 0。
步驟 2 - 開始遍歷二進位制字串。如果當前字元為 '1'，則將 'count' 加 1。
步驟 3 - 如果當前字元為 '0'，則使用迴圈從佇列中刪除 count 個元素並將其新增到 'array_sum' 變數。
步驟 4 - 將當前元素推入佇列。
步驟 5 - 如果 count 不為零，則從佇列中刪除 count 個元素。
步驟 6 - 返回 'array_sum' 值。
示例
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
void buildMaxHeap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
}
int getMaximumSum(int arr[], char alpha[], int len) {
int count = 0, array_sum = 0;
// Build a max heap
buildMaxHeap(arr, len);
// Iterate the string
for (int p = 0; p < len; p++) {
if (alpha[p] == '1') {
count++;
} else {
// Pop all count number of elements from the heap
for (int i = 0; i < count; i++) {
array_sum += arr[0];
arr[0] = arr[len - 1 - i];
heapify(arr, len - i, 0);
}
count = 0;
}
}
// If there are remaining elements in the heap, pop and sum them
for (int i = 0; i < count; i++) {
array_sum += arr[0];
arr[0] = arr[len - 1 - i];
heapify(arr, len - i, 0);
}
// Return the answer
return array_sum;
}
int main() {
int len = 5;
char alpha[] = "01010";
int arr[] = {30, 40, 3, 7, 20};
printf("The maximum sum of array elements according to the given condition is %d\n", getMaximumSum(arr, alpha, len));
return 0;
}
輸出
The maximum sum of array elements according to the given condition is 70
#include <bits/stdc++.h>
using namespace std;
int getMaximumSum(int *arr, string alpha, int len) {
int count = 0, array_sum = 0;
priority_queue<int> queue;
// Iterate the string
for (int p = 0; p < len; p++) {
if (alpha[p] == '1') {
count++;
} else {
// Pop all count number of elements from the queue
while (count != 0) {
array_sum += queue.top();
queue.pop();
count--;
}
}
// Insert element to queue
queue.push(arr[p]);
}
// If the queue is not empty, then pop the elements and do its sum
while (count != 0) {
array_sum += queue.top();
queue.pop();
count--;
}
// return answer
return array_sum;
}
int main() {
int len = 5;
string alpha = "01010";
int arr[] = {30, 40, 3, 7, 20};
cout << "The maximum sum of array elements according to the given condition is " << getMaximumSum(arr, alpha, len) << endl;
return 0;
}
輸出
The maximum sum of array elements according to the given condition is 70
import java.util.PriorityQueue;
public class Main {
public static int getMaximumSum(int[] arr, String alpha) {
int count = 0;
int array_sum = 0;
PriorityQueue<Integer> queue = new PriorityQueue<Integer>((a, b) -> b - a); // Max heap to simulate the queue
// Iterate the string
for (int p = 0; p < alpha.length(); p++) {
if (alpha.charAt(p) == '1') {
count++;
} else {
// Pop all count number of elements from the queue
while (count != 0) {
array_sum += queue.poll();
count--;
}
}
// Insert element into the queue
queue.offer(arr[p]);
}
// If the queue is not empty, then pop the elements and do its sum
while (count != 0) {
array_sum += queue.poll();
count--;
}
return array_sum;
}
public static void main(String[] args) {
int len = 5;
String alpha = "01010";
int[] arr = {30, 40, 3, 7, 20};
System.out.println("The maximum sum of array elements according to the given condition is " + getMaximumSum(arr, alpha));
}
}
輸出
The maximum sum of array elements according to the given condition is 70
def get_maximum_sum(arr, alpha):
count = 0
array_sum = 0
queue = [] # List to simulate the queue
# Iterate the string
for i in range(len(alpha)):
if alpha[i] == '1':
count += 1
else:
# Pop all count number of elements from the queue
while count != 0:
array_sum += queue.pop(0)
count -= 1
# Insert element into the queue
queue.append(arr[i])
# If the queue is not empty, then pop the elements and do its sum
while count != 0:
array_sum += queue.pop(0)
count -= 1
return array_sum
if __name__ == "__main__":
length = 5 # Changed the variable name from "len" to "length"
alpha = "01010"
arr = [30, 40, 3, 7, 20]
print("The maximum sum of array elements according to the given condition is", get_maximum_sum(arr, alpha))
輸出
The maximum sum of array elements according to the given condition is 70
時間複雜度 - O(N*logN)，其中 O(N) 用於遍歷字串，O(logN) 用於將元素插入佇列。
空間複雜度 - O(N)，用於在佇列中儲存元素。
在這裡，我們使用列表和佇列來解決問題。我們可以觀察到佇列是如何有效的。如果我們需要在每次迭代後對陣列進行排序，我們可以使用優先順序佇列。
更新於：2023-10-23
76 次檢視
廣告