資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中統計優質子陣列的數量
假設我們有一個整數陣列nums和一個整數k。如果一個子陣列中包含k個奇數，則稱該子陣列為優質子陣列。我們需要找到優質子陣列的數量。例如，如果陣列是[1,1,2,1,1]，k = 3，則輸出為2，因為子陣列是[1,1,2,1]和[1,2,1,1]
為了解決這個問題，我們將遵循以下步驟：
- ans := 0, n := nums陣列的大小
- left := 0, right := 0, count := 0
- 定義一個數組odd，用nums中所有奇數值填充它
- 如果odd陣列的長度>= k，則
- 對於i從0到k-1，j從k-1到odd陣列大小-1，i和j分別加1
- left := 如果i = 0，則odd[i] + 1，否則odd[i] – odd[i – 1]
- right := 如果odd陣列大小-1 = j，則odd[j]，否則odd[j + 1] – odd[j]
- ans := ans + left * right
- 對於i從0到k-1，j從k-1到odd陣列大小-1，i和j分別加1
- 返回ans
示例(C++)
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int ans = 0;
int n = nums.size();
int left = 0;
int right = 0;
int cnt = 0;
vector <int> odd;
for(int i = 0; i < n; i++){
if(nums[i] % 2 == 1)odd.push_back(i);
}
if(odd.size()>=k){
for(int i = 0, j = k-1; j < odd.size(); i++, j++){
int left = i==0?odd[i]+1: odd[i] - odd[i-1];
int right = j==odd.size()-1 ?n-odd[j] : odd[j+1] - odd[j];
ans += left * right;
}
}
return ans;
}
};
main(){
vector<int> v = {1,1,2,1,1};
Solution ob;
cout <<ob.numberOfSubarrays(v, 3);
}輸入
[1,1,2,1,1] 3
輸出
2
更新於：2020年4月30日
793 次瀏覽
廣告