Data structure advanced training course notes and algorithm exercises

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

题目1

我们把只包含因子2,3,5的数称为丑数。求从小到大的第1500个丑数。
  -例如：6,8都是丑数，但14不是丑数，因为它包含因子7.习惯上我们把1当做丑数。
  -编写尽可能高效的算法。提示：（可以用空间换时间）

1.1 算法设计思想

准备一个数组，初始化第1个丑数的下标0，值1；
然后1X2得到2，就是第2个丑数；
然后1X3得到3，就是第3个丑数；
不能直接1X5就是第4个丑数，因为还有一个丑数2X2=4；
所以难点就是判断中间丑数，然后存储在数组中；往下循环；
然后1X5得到5，就是第5个丑数

1.2 源代码

int min_num(int n1,int n2,int n3){
  int min=(n1<n2)?n1:n2;
  min=(min<n3)?min:n3;
  return min;
}

void solution(long int array[]){
  int i;
  int t2=0;//记录M2的下标
  int t3=0;
  int t5=0;

  for(i=1; i<1500; i++){
    while(array[t2]*2<=array[i-1])//查找到新的M2，即乘以2后第一个大于M的数
        t2++;
    while(array[t3]*3<=array[i-1])
        t3++;
    while(array[t5]*5<=array[i-1])
        t5++;
    int min=min_num(array[t2]*2, array[t3]*3, array[t5]*5);
    array[i]=min;
  }
}

1.3 运行情况截图

题目2

顺时针打印矩阵

2.1 算法设计思想

针对一般矩阵，先顺时针打印最外部一圈，
那么这个矩阵去掉外部一圈，内部也是一个小矩阵；
按照这样的规律，依次打印最外部一圈就可以了

2.2 源代码

void PrintMatrix(int (*num)[4], int col, int row, int layer){
  int i;
  int new_col = col - layer;
  int new_row = row - layer;
  for(i=layer; i<new_col; i++){		// 从左至右打印第一行
    printf("%d ", num[layer][i]);
  }
  if(new_row>layer){
    for(i=layer+1; i<new_row; i++){		// 从上至下打印最右一列
      printf("%d ", num[i][new_row-1]);
    }
  }
  if(new_col-1>layer && new_row-1>layer){
    for(i=new_col-2; i>=layer; i--){		// 从右至左打印最后一行
      printf("%d ", num[new_col-1][i]);
    }
  }
  if(new_col-1>layer && new_row-1>layer+1){
    for(i=new_row-2; i>layer; i--){		// 从下至上打印最左一列
      printf("%d ", num[i][layer]);
    }
  }
}

2.3 运行情况截图

题目3

设二维数组B[0..m-1][0..n-1]的数据在行、列方向上都按从小到大的顺序有序，
且x在B中存在。试设计一个算法，找出x在B数组中的位置i,j。
要求比较的次数不超过m+n

3.1 算法设计思想

第一个循环（最多4次）：

将要定位的元素与每一行的最后一个元素比较，如果小于等于最后一个元素就结束循环，此时的i值就是元素的行坐标；

第二次循环（最多5次）：

将要定位的元素与每一列的所有元素比较，如果小于等于这个值，就结束循环，此时的j值就是元素的列坐标

3.2 源代码

int matrix[4][5] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}, i, j;
for(i=0; i<4; i++){   // 定位行坐标i
  if(obj <= matrix[i][4])
    break;
}
for(j=0; j<5; j++){   // 定位列坐标j
  if(obj <= matrix[i][j])
    break;
}

3.3 运行情况截图