首页 > 代码库 > 笔试算法题（26）：顺时针打印矩阵 & 求数组中数对差的最大值

笔试算法题（26）：顺时针打印矩阵 & 求数组中数对差的最大值

2024-07-05 18:08:55   230人阅读

出题： 输入一个数字矩阵，要求从外向里顺时针打印每一个数字；

分析：

  • 从外向里打印矩阵有多重方法实现，但最重要的是构建合适的状态机，这样才能控制多重不同的操作；
  • 注意有四种打印模式（左右，上下，右左，下上），所以需要一个index变量控制每次循环时执行的打印模式；
  • 注意水平打印和垂直打印分别需要两个变量控制打印元素，并且两组变量中的两个端点都是相互靠近的（hs和he，vs和he），每执行一种打印模式之前，需要更新当前打印模式中打印方向的其实坐标，因为它已经在上一种打印模式中打印过；
  • 每一种打印模式执行之前需要检测hs>he或者vs>ve，如果成立则打印结束；
  • 其他方法：递归法：每次都打印矩阵第一行，然后将剩余的元素逆时针旋转90度创建一个矩阵；贪吃蛇法：创建一个bool矩阵表示元素是否被打印，然后创建一个类似index的控制打印模式的变量，遇到false的元素就转到下一个打印模式；

解题：

 1 /**
 2  * 设置四个变量，两两一组分别表示水平和垂直方向的打印的起始点
 3  * index表示四种打印方式中的一种（左右，上下，右左，下上）
 4  * 当两两一组的变量中hs>he或者vs>ve的时候结束打印
 5  * 注意每一种打印模式开始之前，需要更新起始点的坐标，因为
 6  * 它已经在上一个打印模式中打印过
 7  * */
 8 void clockwisePrintMatrix(int *array, int x, int y) {
 9         int hs=-1, he=x-1;
10         int vs=0, ve=y-1;
11         int index=4;
12 
13         while(true) {
14                 printf("hs=%d, he=%d, vs=%d, ve=%d\n",hs,he,vs,ve);
15                 index%=4;
16                 if(index==0) {
17                         /**
18                          * 左右打印模式：
19                          *
20                          * */
21                         hs++;
22                         if(hs>he) break;
23                         for(int i=hs;i<=he;i++)
24                                 printf("%d, ",array[vs*x + i]);
25                         printf("\n");
26                 } else if(index==1) {
27                         /**
28                          * 上下打印模式：
29                          *
30                          * */
31                         vs++;
32                         if(vs>ve) break;
33                         for(int i=vs;i<=ve;i++)
34                                 printf("%d, ",array[i*y + he]);
35                         printf("\n");
36                 } else if(index==2) {
37                         /**
38                          * 右左打印模式：
39                          *
40                          * */
41                         he--;
42                         if(hs>he) break;
43                         for(int i=he;i>=hs;i--)
44                                 printf("%d, ",array[ve*x + i]);
45                         printf("\n");
46                 } else if(index==3) {
47                         /**
48                          * 下上打印模式：
49                          *
50                          * */
51                         ve--;
52                         if(vs>ve) break;
53                         for(int i=ve;i>=vs;i--)
54                                 printf("%d, ",array[i*y + hs]);
55                         printf("\n");
56                 }
57                 index++;
58         }
59 }
60 
61 int main() {
62         int matrix[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25};
63         clockwisePrintMatrix(matrix, 5, 5);
64         return 0;
65 }

 

出题：一个数组中，某一个数字减去它右边数字得到一个数对差，求所有数对差中的最大值；

分析：

  • 数对差的解法可转换成求最大子数组和，或者转换成DP问题；
  • 解法1：构建子数组最大和值
    定义数 组:array[i]-array[i+1];array[i+1]-array[i+2];……;array[j-1]-array[j];所以 array[i]-array[j]的差就是前面所有相邻元素差的和，所以将原始数组转换成相邻元素的差组成的数组，而求原数组元素差的最大值转换成新数 组的子数组元素的最大和；
  • 解法2：动态规划解法：diff[i]存储array[i]与其左边数组最大元素的差值，得到diff[i]之后求diff[i+1]，则需要知道 array[i+1]左边数组的最大元素，而有两种可能，计算diff[i]的时候得到的最大值，或者就是array[i]。所以只需一遍扫描就可以；

解题：

 1 int MaxDif(int *array, int length) {
 2         /**
 3          * 定义局部stack数组存储相邻元素差值
 4          * 循环获取相邻元素差值
 5          * */
 6         int difarray[length-1];
 7         for(int i=0;i<length-1;i++) {
 8                 difarray[i]=array[i]-array[i+1];
 9                 printf("\n%d",difarray[i]);
10         }
11         /**
12          * sum记录最大和值
13          * tempsum记录当前元素的和值
14          * 如果元素为+++++++，则从开始相加到最后
15          * 如果元素为-------，则sum保持为0
16          * 如果元素为++++---，则sum保持为前半正数
17          * 如果元素为----+++，则sum保持为后半正数
18          * 还有其他满足条件的情况
19          * */
20         int tempsum=0, sum=0;
21         for(int i=0;i<length-1;i++) {
22                 tempsum+=difarray[i];
23                 if(tempsum<0)
24                         tempsum=0;
25                 else if(tempsum>sum)
26                         sum=tempsum;
27         }
28 
29         return sum;
30 }
31 
32 int MaxDifDP(int *array, int length) {
33         /**
34          * difarray[i]用于存储array[i]左边的最大元素
35          * 与array[i]的差值，
36          * difarray[i+1]同理，但根据DP原理，左边的最大
37          * 元素可能是array[i]找到的最大元素，可能是
38          * array[i]本身，所以一遍扫描，DP复用
39          * */
40         int difarray[length-1];
41         int max=array[0];
42         for(int i=0;i<length-1;i++) {
43                 if(array[i]>max)
44                         max=array[i];
45                 difarray[i]=max-array[i+1];
46         }
47         int difmax=difarray[0];
48         for(int i=1;i<length-1;i++) {
49                 if(difarray[i]>difmax)
50                         difmax=difarray[i];
51         }
52         return difmax;
53 }
54 
55 int main() {
56         int array[]={6,7,9,6,-4,0,7,9};
57         printf("\nthe max diff is: %d",MaxDif(array,8));
58         printf("\nthe max diff is: %d",MaxDifDP(array,8));
59         return 0;
60 }

 


联系
我们