Data structure advanced training course notes and algorithm exercises 数据结构进阶实训课程笔记和算法练习

Source Code: https://github.com/MysticalGuest/DataStructure/tree/master/AdvancedJuniorTraining

题目1

实现将一个字符串中的每个空格字符换成“%20”。
  - 例如：输入“We are happy.”, 则输出:
  - “We%20are%happy.”
要求在时间复杂度O（n）,空间复杂度O（1）下完成。假设存放字符串的数组空间足够大。

1.1 算法设计思想

前提假设存放字符串的数组空间足够大；

第一次，遍历，计算出字符串长度，和替换后字符串长度；

i从原字符串末尾出发，j从新字符串末尾出发，遇到空格就替换为“%20”。

1.2 源代码

char str[100] = "We are happy.";    // 假设空间足够大
int length=0, blank=0, i, j;
while(str[length]!='\0'){
  printf("%c", str[length]);
  if(str[length]==' '){
    blank++;
  }
  length++;
}
length += 2 * blank;

i=length-2*blank;
j=length;

while(i>=0 && j>i){
  if(str[i]==' '){
    str[j--]='0';
    str[j--]='2';
    str[j--]='%';
  }
  else{
    str[j--]=str[i];
  }
  i--;
}

1.3 运行情况截图

题目2

数组中出现次数超过一半的数字已知数组中有一个数字其出现的次数超过了数组长度的一半，请找出这个数组。
要求：
  - 高效
  - 分析时空效率

2.1 算法设计思想

一个数字出现的次数超过了数组的一半，那么将其排序后，称为有序数列，中间的元素即为所求。

2.2 源代码

void sort(int a[], int length){
  int i, j, min, temp;
  for(i=0; i<length; i++){
    min=i;
    for(j=i; j<length; j++){
      if(a[min]>a[j])
        min=j;
    }
    if(min!=i){
      temp=a[min];
      a[min]=a[i];
      a[i]=temp;
    }
  }
}

printf("%d\n", array[length/2]);

2.3 运行情况截图

题目3

已知数组中的n个正数，找出其中最小的k个数。
要求：
  - 高效
  - 分析时空效率

3.1 算法设计思想

先将数组从小到大排序；

即可顺序打印出前k个数，即为数组中最小的k个数。

时间复杂度为O(n)，空间复杂度为O(1)。

3.2 源代码

void sort(int a[], int length){
  int i, j, min, temp;
  for(i=0; i<length; i++){
    min=i;
    for(j=i; j<length; j++){
      if(a[min]>a[j])
        min=j;
    }
    if(min!=i){
      temp=a[min];
      a[min]=a[i];
      a[i]=temp;
    }
  }
}

printf("\nEnter the value k and output the smallest k number among them, k = ");
scanf("%d", &k);
printf("The smallest %d number in the array is: \n", k);
for(i=0; i<k; i++){
  printf("%d\t", array[i]);
}

3.3 运行情况截图