Question

在线等!!以下题目可以帮帮我吗?

以下题目可以帮帮我吗? 我在找不到答案啊!

1、设n为正整数，分析下列程序段中加下划线的语句的执行次数。
X=0; y=0;
For( int I =1 ; i<=n ; i++)
For (int j =1 ;j<=I ;j++)
For( int k = 1 ; k<=j ; k++)
X+=y ;
语句执行次数为？？？

2、设计一个算法，计算在二叉树中左子树比右子树高1的节点个数。

3、设计一个算法，统计在一段字符串中每个重复子串的个数。（比如字符串abcabc，那么重复子串为a：2个，b：2个，c：2个，ab：2个，abc：2个，bc：2个）并给出该算法的时间复杂度。

Answer 1

1. n=1时，f(1)=1次；
n+1时，f(n+1)=f(n)+(1+2+...+n+1)=f(n)+(n+1)(n+2)/2
所以，f(n)=∑i(i+1)/2 (i=1..n)
即f(n)=n(n+1)(n+2)/6

2.
int count = 0;
int countNode(Node* i) {
if (i==null) return 0;
Node* l = i->left;
Node* r = i->right;
int leftCount = countNode(l);
int rightCount = countNode(r);
if (leftCount - rightCount == 1) count++;
return max(leftCount, rightCount)+1;
}
void main(){
countNode(root);
printf("%d", count);
}

3.
int findStrInVec(vector<string>& strVec, string& tmpstr)
{
for (int i=0; i<strVec.size(); i++) {
if (strVec[i] == tmpstr)
return i;
}
return -1;
}

main() {
n = strlen(str);
vector<string> strVec;
vecotr<int> strCountVec;
for (int i=0; i<n; i++) {
for (int j=i; j<n; j++) {
tmpstr = substr(str, i, j);
pos = findStrInVec(strVec, tmpstr);
if (pos < 0) {
strVec.push_back(tmpstr);
strCountVec.push_back(1);
}else{
strCountVec(pos)++;
}
}
}
for (i=0; i<strCountVec.size(); i++) {
if (strCountVec[i] > 1) {
pirntf("%s, %d\n", strVec[i], strCountVec[i]);
}
}
}

时间复杂度貌似O(n^2*log(n))