我使用一維陣列解決了一個問題（Longest Even Length Substring ）。但我不知道我的代碼有什么問題。它失敗了。您能否分析我的代碼并通過適當的示例解釋我的方法失敗的原因。
#include<iostream>
using namespace std;
int main()
{
int t;
string number;
cin>>t;
while(t--) {
cin>>number;
int current=0,prev=0;
int length = number.length();
int sum[length],n1,n2;
sum[0] = number[0]-'0';
for(int i=1; i<length; i ) {
sum[i] = sum[i-1] (number[i]-'0');
}
for(int i=0; i<length; i ) {
for(int j=i 1;j<length;j=j 2) {
int value;
if(i==0) value = sum[j]; else value = sum[j]-sum[i-1];
if(value%2 == 0) {
int index = (i j)/2;
if(index == 0) {
n1 = sum[0];
n2 = sum[j];
}
else {
int data;
if(i==0) data = 0; else data = sum[i-1];
n1 = sum[index]-data;
n2 = sum[j]-sum[index];
}
if(n1==n2 ){
if( (j-1 1) > prev) {
prev=current=j-i 1;
}
}
}
}
}
cout<<current<<"\n";
}
return 0;
}
uj5u.com熱心網友回復：
我試著解決這個問題。這是一種簡單的蠻力方法。讓我解釋一下我的代碼，以便您可以理解基本邏輯并可以自己用c 實作。
偽代碼：
從輸入數字 (n) 創建一個數字串列 (lst)。這里我使用 map 將字串轉換為整數，然后將其轉換為串列。
創建一個包含串列 (lst) 的所有子字串的串列 (substr)。
從長度為奇數的串列 (substr) 中洗掉所有子字串。如果長度是奇數，那么我們無法將子字串分成相等的磁區（請參閱問題）。
然后簡單地從串列（substr）中迭代子字串并分成兩個磁區（k1和k2）并檢查總和是否相等。
如果它們相等，則將以下子字串的長度附加到串列 (fi) 中。
然后列印存盤在串列 (fi) 中的最大長度。
for i in range(int(input())): n = input() lst = list(map(int, n)) substr = [lst[i: j] for i in range(len(lst)) for j in range(i 1, len(lst) 1)] for i in substr: if (len(i) % 2 != 0): substr.remove(i) fi = [] for lst1 in substr: mid = int(len(lst1)/2) k1 = lst1[0:mid] k2 = lst1[mid:len(lst1)] if(sum(k1) == sum(k2)): fi.append(len(lst1)) if(len(fi) == 0): print("0") else: print(max(fi))
uj5u.com熱心網友回復：
這個給你：
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
int main() {
int t;
std::cin >> t;
int i;
std::string str;
std::vector<std::vector<int>> px(t);
for (i = 0; i != t; i) {
std::cin >> str;
px[i].reserve(str.size() 1);
px[i].emplace_back(0);
for (auto const& ch : str) {
px[i].emplace_back(px[i].back() ch - '0');
}
}
std::vector<int> ans;
ans.reserve(t);
int k, k_max, pp, pp_lim, lhs, rhs, tmp, max;
for (auto const& v : px) {
max = 0;
for (k = 1, k_max = (v.size() - 1) >> 1; k <= k_max; k) {
for (pp = k, pp_lim = v.size() - k; pp != pp_lim; pp) {
lhs = v[pp] - v[pp - k];
rhs = v[pp k] - v[pp];
if (lhs == rhs) {
tmp = k << 1;
if (tmp > max) {
max = tmp;
}
}
}
}
ans.emplace_back(max);
}
std::copy(ans.cbegin(), ans.cend(), std::ostream_iterator<int>(std::cout, "\n"));
return 0;
}
您正在嘗試實作前綴和演算法，但不幸的是您做錯了。讓我們看一下第二個str，即“1234123”。它的前綴總和看起來像這樣：
0 1 3 6 10 11 13 16
k 在這種情況下屬于范圍 [1; (8 - 1)/2 或 (8 - 1) >> 1]，其中 (8 - 1) 是“1234123”的 .size()，8 是 v 的 .size()，它是保持“1234123”的前綴總和。讓我們看一下我們可以得到的總和：
k = 1
1 = 2 -> v[1] - v[1 - k] = v[1 k] - v[1]
2 = 3 -> v[2] - v[2 - k] = v[2 k] - v[2]
3 = 4 -> v[3] - v[3 - k] = v[3 k] - v[3]
4 = 1 -> v[4] - v[4 - k] = v[4 k] - v[4]
1 = 2 -> v[5] - v[5 - k] = v[5 k] - v[5]
2 = 3 -> v[6] - v[6 - k] = v[6 k] - v[6]
k = 2
1 2 = 3 4 -> v[2] - v[2 - k] = v[2 k] - v[2]
2 3 = 4 1 -> v[3] - v[3 - k] = v[3 k] - v[3]
3 4 = 1 2 -> v[4] - v[4 - k] = v[4 k] - v[4]
4 1 = 2 3 -> v[5] - v[5 - k] = v[5 k] - v[5]
k = 3
1 2 3 = 4 1 2 -> v[3] - v[3 - k] = v[3 k] - v[3]
2 3 4 = 1 2 3 -> v[4] - v[4 - k] = v[4 k] - v[4]
你有一個支點 pp 屬于范圍 [k; v.size() - k)。您的 lhs 公式是 str 的子字串的字符之和，索引 pp 左側有 k 個字符，包括 pp 是 v[pp] - v[pp - k] 和 rhs 的字符之和不包括 pp 的索引 pp 右側有 k 個字符的 str 的子字串是 v[pp k] - v[pp]。您正在處理的子字串的長度 tmp 始終為 k * 2 或 k << 1。您必須將 tmp 與 max 進行比較，這是您迄今為止在 v 中處理的最長子字串的長度，并在需要時將 tmp 分配給 max。我將每個 v 的最大值存盤在一個名為 ans 的向量中，然后使用 std::copy 輸出其內容。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/419570.html
標籤：