给定字符串(ASCII码0-255)数组,请在不开辟额外空间的情况下删除开始和结尾处的空格,并将中间的多个连续的空格合并成一个。例如:” i am a little boy. “,变成”i am a little boy”,语言不限,但不要用伪代码作答,函数输入输出请参考如下的函数原型:
1
2
3
C++函数原型:
void FormatString(char str[],int len){
}
#include<stdio.h>#include <string.h>void FormatString(char str[],int len){if (str == NULL || len <= 0) {return;}int i = 0;int j = 0;if (str[i] == ' ') {while (str[i] == ' ') {++i;}}while (str[i] != '\0') {if (str[i] == ' ' && str[i + 1] == ' ' || str[i + 1] == '\0') {++i;continue;}str[j++] = str[i++];}str[j] = '\0';}int main() {char a[] = " i am alittle boy. ";int len = strlen(a);printf("%d\n",len);FormatString(a,len);printf("%d\n",strlen(a));printf("%s\n",a);return 0;}
给定一颗二叉树,以及其中的两个node(地址均非空),要求给出这两个node的一个公共父节点,使得这个父节点与两个节点的路径之和最小。描述你程序的最坏时间复杂度,并实现具体函数,函数输入输出请参考如下的函数原型:
C++函数原型:
1
2
3
4
5
6
7
strucy TreeNode{
TreeNode* left; //指向左子树
TreeNode* right; //指向右子树
TreeNode* father; //指向父亲节点
};
TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second){
}
int nodeHeight(TreeNode* node){int height = 0;while(node != NULL){height++;node = node->father;}}TreeNode* LowestCommonAncestor(TreeNode* first, TreeNode* second){int diff = nodeHeight(first) - nodeHeight(second);if(diff > 0){while(diff > 0){first = first->father;diff--;}}else{while(diff < 0){second = second->father;diff++;}}while(first != second){first = first->father;second = second->father;} return first;}