算法初学(第四天)4-1

1. 猫狗队列:实现一种狗猫队列的结构, 要求如下:

  •     用户可以调用add方法将cat类或dog类的实例放入队列中;
  •     用户可以调用pollAll方法, 将队列中所有的实例按照进队列的先后顺序依次弹出;
  •     用户可以调用pollDog方法, 将队列中dog类的实例按照进队列的先后顺序依次弹出;
  •     用户可以调用pollCat方法, 将队列中cat类的实例按照进队列的先后顺序依次弹出;
  •     用户可以调用isEmpty方法, 检查队列中是否还有dog或cat的实例;
  •     用户可以调用isDogEmpty方法, 检查队列中是否有dog类的实例;
  •     用户可以调用isCatEmpty方法, 检查队列中是否有cat类的实例。

   1.1  首先构造一个PetEnterQueue类,包括属性Pet和数字Count,count用来记录进入队列的先后顺序

   1.2  add方法,判断输入的什么类型的宠物,然后dog队列或者cat队列的方法,把PetEnterQueue(pet和时间)加入到队列。

   1.3  pollAll,判断dog队列或者cat队列的count属性,谁小谁先poll

   1.4  pollDog/pollCat , 直接poll。

   1.5 isEmpty,直接判断队列是否为空

2. 给定一个整数数组,将按照转圈的方式打印它。额外空间复杂度为O(1)。

   2.1 给定两个点(a,b),(c,d),四个信息,就能把整个边框界定出来;

   2.2 判断左上和右上是不是相等,如果相等,就从左上打印到左下,不相等再

         判断左上和左下是不是相等,如果相等,就从左上到右上,不相等再

         然后四圈打印,左上到右上,右上到右下,右下到左下,左下到左上。

  2.3 上述的过程是一个子步骤的过程,表示打印完一圈,然后再缩小圈。

3. 给定一个数组,将其顺时针选择90度。(选择技巧,先在纸上写好,然后再填写,(x,y)和数组中相反)

    3.1 先完成一个子旋转,先将第一个数保存起来,然后用应该填补他的数去填补,一个转圈,然后再把第一个数存到下一个数中,先拿走,再填补。

    public static void rotateEdge(int[][] m, int a, int b, int c, int d) {
         int times = c-a;
         int temp =0;
         for(int i=0;i<times;i++){
             temp = m[b][a+i] ;
             m[b][a+i]  = m[d-i][a];
             m[d-i][a] = m[d][c-i];
             m[d][c-i] = m[b+i][c];
             m[b+i][c] = temp;

         }
    }

     3.2   让边界满足条件

        while (a <= c && b <= d) {
            rotateEdge(matrix, a++, b++, c--, d--);
        }

4. Z字形打印数组(z字形打印其实是打印对角线上元素

算法初学(第四天)4-1

    4.1 设置两个点A,B,A只能往右走,走到底之后才能向下走,B只能往下走,走到底之后才能向右走;

    4.2  A,B就能表示成对角线上边界元素;

    4.3 设置一个Boolean类型的变量,用来控制对角线的打印方向;

    4.4 代码:

        int a1 = 0;
        int a2 = 0;
        int b1 = 0;
        int b2 = 0;
        int c = matrix.length - 1;
        int d = matrix[0].length - 1;
        boolean flag =true;
        while (a2!=d+1) {
            printLevel(matrix, a1, a2, b1,b2,flag);
            a2 = a1==c? a2+1:a2;
            a1 = a1==c? a1:a1+1;
            b1 = b2==d? b1+1:b1;
            b2 = b2==d? b2:b2+1;
            flag = !flag;

        }

5. 在行列都排好序的矩阵中找数

    给定一个有N*M的整数矩阵和一个整数K,矩阵的每行每列都是排好序的。实现一个函数,判断K是否在矩阵中。

    要求:时间复杂度为O(N+M),额外空间复杂度为O(1)

    5.1 从矩阵的右上角或者左下角找起

    5.2 右上角,如果比这个数大,那么向下寻找;

                        如果比这个数小,那么向左寻找;

    5.3 直到到达左上角或者右下角为止。

6. 打印两个有序链表的公共部分 (链表从大到小)

    6.1 两个链表的头结点进行比较,相等则打印,两个头结点走向下一个结点

         不等的话,让大的走向下一个结点,再对比。

    6.2 直到走向一个链表为空。

    

算法初学(第四天)4-1算法初学(第四天)4-1 ych_ych918 发布了13 篇原创文章 · 获赞 13 · 访问量 2万+ 私信 关注
上一篇:python 转换进制(2-62进制)


下一篇:Excel查找匹配函数的16种方法