数据结构
网络
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 次查看
广告