資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在 C++ 中查詢具有恰好 k 個奇數的最長子陣列
假設我們有一個包含 n 個元素的陣列。問題是找到具有恰好 k 個奇數的最長子陣列。因此，如果 A = [2, 3, 4, 11, 4, 12, 7]，並且 k = 1，則輸出將為 4，子陣列為 [4, 11, 4, 12]
我們可以使用滑動視窗來解決這個問題。任務如下所示：
- 初始化 max := 0，count := 0，以及 start := 0
- 對於 i 從 0 到 n – 1 的範圍，執行以下操作
- 如果 arr[i] 模 2 不為 0，則將 count 加 1
- 當 count > k 且 start <= i 時，執行以下操作
- 如果 arr[start] 模 2 不為 0，則將 count 減 1
- 將 start 加 1
- 如果 count = k，則
- 如果 max < (i – start + 1)，則 max := (i – start + 1)
- 返回 max
示例
#include<iostream>
using namespace std;
int oddSubarrayMaxLength(int arr[], int n, int k) {
int max_len = 0, count = 0, start = 0;
for (int i = 0; i < n; i++) {
if (arr[i] % 2 != 0)
count++;
while (count > k && start <= i)
if (arr[start++] % 2 != 0)
count--;
if (count == k)
if (max_len < (i - start + 1))
max_len = i - start + 1;
}
return max_len;
}
int main() {
int arr[] = {2, 3, 4, 11, 4, 12, 7};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 1;
cout << "Maximum Length is: "<< oddSubarrayMaxLength(arr, n, k);
}輸出
Maximum Length is: 4
更新於: 2019-12-18
63 次瀏覽
廣告