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 运行情况截图