CSDN編程挑戰裡的題目
例如有一個字符串"iinbinbing"，截取不同位置的字符‘b’、‘i’、‘n’、‘g’組合成單詞"bing"。
若從1開始計數的話，則‘b’ ‘i’ ‘n’ ‘g’這4個字母出現的位置分別為(4,5,6,10) (4,5,9,10),
(4,8,9,10)和(7,8,9,10)，故總共可以組合成4個單詞”bing“。
問題是：現給定任意字符串，只包含小寫‘b’ ‘i’ ‘n’ ‘g’這4種字母，請問一共能組合成多少個單詞bing?
字符串長度不超過10000，由於結果可能比較大，請輸出對10^9 + 7取余數之後的結果。
這個問題寫個四重循環就可以.只是效率方面還有待優化.
第一版代碼:
#include <stdio.h>
#include <iostream>
#include <>
#include <cstring>
#include <cstdio>
BING_MAX 1000000007
Bing( * (!szBing || !szBing[
len = ( * listPosB = (*)malloc(len*( * listPosI = (*)malloc(len*( * listPosN = (*)malloc(len*( * listPosG = (*)malloc(len*( memset(listPosB, , len*( memset(listPosI, , len*( memset(listPosN, , len*( memset(listPosG, , len*( numB = numI = numN = numG =
( i = ; i < len; i++ listPosB[numB] = numB++ listPosI[numI] = numI++ listPosN[numN] = numN++ listPosG[numG] = numG++
count =
( b = ; b < numB; b++ startB =
( i = ; i < numI; i++ startI = (startI <
( n = ; n < numN; n++ startN = (startN <
( g = ; g < numG; g++ startG = (startG <
count++ (count > count -=
}
優化後的代碼:
#include <cstring>
#include <cstdio>
BING_MAX 1000000007
Bing( * (!szBing || !szBing[
len = ( U2* listPosB = (U2*)malloc(len* U2* listPosI = (U2*)malloc(len* U2* listPosN = (U2*)malloc(len* U2* listPosG = (U2*)malloc(len* memset(listPosB, , len*( memset(listPosI, , len*( memset(listPosN, , len*( memset(listPosG, , len*( numB = numI = numN = numG =
( i = ; i < len; i++ listPosB[numB].pos = ( numB++ listPosI[numI].pos = ( numI++ listPosN[numN].pos = ( numN++ listPosG[numG].pos = ( numG++
( i = ; i < numB; i++ ( j = ; j < numI; j++ (listPosB[i].pos < listPosB[i].next =
( i = ; i < numI; i++ ( j = ; j < numN; j++ (listPosI[i].pos < listPosI[i].next =
( i = ; i < numN; i++ ( j = ; j < numG; j++ (listPosN[i].pos < listPosN[i].next =
count = ( b = ; b < numB; b++ ( i = listPosB[b].next; i < numI; i++ ( n = listPosI[i].next; n < numN; n++ ( g = listPosN[n].next; g < numG; g++ count++ (count > count -=
}
第三版優化,還是運行時間超過3s,我是真沒轍了.
#include <cstring>
#include <cstdio>
#include <assert.h>
BING_MAX 1000000007
Bing( * szBing, (!szBing || !szBing[
U2* listPosB = (U2*)malloc(len* U2* listPosI = (U2*)malloc(len* U2* listPosN = (U2*)malloc(len* U2* listPosG = (U2*)malloc(len* memset(listPosB, , len*( memset(listPosI, , len*( memset(listPosN, , len*( memset(listPosG, , len*( numB = numI = numN = numG =
( i = ; i < len; i++ (szBing[i] == listPosB[numB].pos = ( numB++ (szBing[i] == listPosI[numI].pos = ( numI++ (szBing[i] == listPosN[numN].pos = ( numN++
listPosG[numG].pos = ( numG++
t = ( i = ; i < numB; i++ ( j = t; j < numI; j++ (listPosB[i].pos < listPosB[i].next = t =
t = ( i = ; i < numI; i++ ( j = t; j < numN; j++ (listPosI[i].pos < listPosI[i].next = t =
t = ( i = ; i < numN; i++ ( j = t; j < numG; j++ (listPosN[i].pos < listPosN[i].next = t =
count = ( b = ; b < numB; b++ ( i = listPosB[b].next; i < numI; i++ ( n = listPosI[i].next; n < numN; n++ count += numG -
(count > count -=
}
第四版代碼:
#include <cstring>
#include <cstdio>
BING_MAX 1000000007
Bing( * szBing, (!szBing || !szBing[
U2* listPosB = (U2*)malloc(len* U2* listPosI = (U2*)malloc(len* U2* listPosN = (U2*)malloc(len* U2* listPosG = (U2*)malloc(len* memset(listPosB, , len*( memset(listPosI, , len*( memset(listPosN, , len*( memset(listPosG, , len*( numB = numI = numN = numG =
( i = ; i < len; i++ (szBing[i] == listPosB[numB].pos = numB++ (szBing[i] == listPosI[numI].pos = numI++ (szBing[i] == listPosN[numN].pos = numN++ (szBing[i] == listPosG[numG].pos = numG++
b = i = n = g =
(n = ; n < numN; n++ (listPosG[g].pos < listPosN[n].pos && g < g++ listPosN[n].count = numG -
n = (i = ; i < numI; i++ (listPosN[n].pos < listPosI[i].pos && n < n++ listPosI[i].count = (t = n; t < numN; t++ listPosI[i].count +=
i = count = ( b = ; b < numB; b++ (listPosI[i].pos < listPosB[b].pos && i < i++ listPosB[b].count = (t = i; t < numI; t++ listPosB[b].count +=
count += (count > count -=
}
終於想到正確答案了,原來我一開始就誤入歧途了,最早的代碼算法復雜度是O(n^4),我將其優化到O(n^2),然後又優化到O(n*log(n)),而最終代碼的復雜度是O(n).
BING_MAX 1000000007
Bing( * numB = numI = numN = numG = pos = (szBing[pos] == numB++ (szBing[pos] == numI += (szBing[pos] == numN += (szBing[pos] == numG += (numG > numG -= pos++
}
