3.3.6、数组的力扣练习题——搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

 输入: nums = [1,3,5,6], target = 5
 输出: 2

思路分析：

• 如果数组中的值大于或者等于target，直接return

• 如果全部遍历完证明target是最大的数，直接插入末尾

  代码实现：

  ```JAVA
  /**

• description
• 数组的力扣练习题——搜索插入位置
• 如果数组中的值大于或者等于target，直接return
• 如果全部遍历完证明target是最大的数，直接插入末尾
  *
• @author

• @since 2022/11/26 23:30
  */
  public class Answer {
  public static void main(String[] args) {

   int target = 2;
   int[] arr = {1, 3, 5, 6};
   int i = searchInsert(arr, target);
   System.out.println(i);
  

  }

  /**

  • 搜索插入的位置的方法
    *
  • @param nums 需要操作的数组
  • @param target 需要插入的数字
  • @return
    */
    public static int searchInsert(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {

     //数组中的值大于或者等于target，直接return
     if (nums[i] >= target) {
         return i;
     }
    

    }
    //全部遍历完证明target是最大的数，直接插入数组末尾
    return nums.length;
    }
    }
    ```

3.4、二维数组

3.4.1、二维数组简介

二维数组是一种结构较为特殊的数组，只是将数组中的每个元素变成了一维数组。

所以二维数组的本质上仍然是一个一维数组，内部的一维数组仍然从索引 0 开始，我们可以将它看作一个矩阵，并处理矩阵的相关问题。

• 示例
  类似一维数组，对于一个二维数组 A = [[1, 2, 3, 4],[2, 4, 5, 6],[1, 4, 6, 8]]，计算机同样会在内存中申请一段 连续 的空间，并记录第一行数组的索引位置，即 A[0][0] 的内存地址，它的索引与内存地址的关系如下图所示。

注意，实际数组中的元素由于类型的不同会占用不同的字节数，因此每个方格地址之间的差值可能不为 1。

实际题目中，往往使用二维数组处理矩阵类相关问题，包括矩阵旋转、对角线遍历，以及对子矩阵的操作等

3.4.2、二维数组的力扣练习题——合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]

思路分析：合并 2 个区间

• 对二维数组进行排序，按照第一列升序列排列
• 借用临时空间，判断是否需要合并集合当前值，当前集合是否放入结果集触发点

代码实现：

/**
 * description
 * 二维数组的练习题——合并区间的解法
 *
 * @author
 * @since 2022/11/27 10:14
 */
public class practice {
    public static void main(String[] args) {
        int [][] arr = new int[3][3];
        int[][] merge = merge(arr);
        System.out.println(Arrays.toString(merge));
    }
    /**
     * 合并所有重叠的区间的方法
     *
     * @param intervals 若干个区间的集合
     * @return 一个不重叠的区间数组
     */
    public static int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return intervals;
        }
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));//按每行的第0列升序排序
        Vector<int[]> integerVector;//由于我们事先不知道数组大小，所以用Vector类实现动态数组。
        integerVector = new Vector<>();
        int[] ints = intervals[0];//定义一个Int类型数组用于作比较，默认值为第一组二维数组的值。
        for (int i = 1; i < intervals.length; i++) {//循环这个二维数组
            if (ints[1] >= intervals[i][0]) {//如果第一个数组的右端点大于等于下一个数组的左端点，做说明两个数组有所交集。
                ints[1] = Math.max(ints[1], intervals[i][1]);//int类型数组的右端点等于两个数组中右端点大的那个值。
            } else {
                integerVector.add(ints);//把int类型一维数组ints添加到我们创建的vector类里面。
                ints = intervals[i];//给一维数组重新赋值。
            }
        }
        integerVector.add(ints);//把最后一个区间添加到Vector里面
        return integerVector.toArray(new int[integerVector.size()][2]);//把vector转换成二维数组返回。
    }
}

3.4.3、二维数组的力扣练习题——旋转矩阵

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

例 1:

给定 matrix = 
[
[1,2,3],
[4,5,6],
[7,8,9]
],

原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

思路分析：

• 如下图，先由对角线 [1, 5, 9] 为轴进行翻转：

翻转后的数组变成了

[1,4,7]
[2,5,8]
[3,6,9]

再对每一行以中点进行翻转，就得到了

[7,4,1]
[8,5,2]
[9,6,3]

代码实现如下：

/**
 * description
 * 二维数组的力扣练习题——旋转矩阵
 *
 * @author
 * @since 2022/11/27 12:54
 */
public class Matrix {
    public static void main(String[] args) {
        int[][] arr = {
   
   {1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        //矩阵旋转前
        System.out.println("矩阵旋转前的数组");
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();    //换行
        }
        rotate(arr);
        System.out.println("矩阵旋转后的数组");
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();    //换行
        }
    }

    //旋转矩阵的方法
    public static void rotate(int[][] matrix) {
        int n = matrix.length;  //使用变量平替二维数组matrix
        for (int i = 0; i < n - 1; i++) {
            //先以对角线（左上-右下）为轴进行翻转
            for (int j = i + 1; j < n; j++) {
                int tmp = matrix[i][j];  //tmp就是轴
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        //再对每一行以中点进行翻转
        int mid = n >> 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < mid; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = tmp;
            }
        }
    }
}

四、链表

4.1 、链表(Linked List)介绍

链表是有序的列表，但是它在内存中是存储如下

小结上图:

• 1) 链表是以节点的方式来存储,是链式存储
• 2) 每个节点包含 data 域， next 域：指向下一个节点
• 3) 如图：发现链表的各个节点不一定是连续存储
• 4) 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
  • 单链表(带头结点) 逻辑结构示意图如下

4.2、 单链表的应用实例

使用带 head 头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作，注: 删除和修改,查找

• 1) 第一种方法在添加英雄时，直接添加到链表的尾部 思路分析示意图:

• 2) 第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示) 思路的分析示意图:

• 3) 修改节点功能 思路(1) 先找到该节点，通过遍历，(2) temp.name = newHeroNode.name ; temp.nickname= newHeroNode.nickname

• 4) 删除节点 思路分析的示意图:

• 5) 完成的代码演示:
  • 首先创建定义英雄的对象，定义英雄的属性，再生成构造器和toString方法

/**
 * description
 * 每个HeroNode对象就是一个节点
 * @author
 * @since 2022/10/20 15:06
 */
public class SingleLinkedListHeroNode {
    public int no;
    public String name;
    public String nickname;
    public SingleLinkedListHeroNode next;  //指向下一个节点

    public SingleLinkedListHeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "SingleLinkedListHeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

• 再定义一个链表来管理英雄的对象

/**
 * description
 * 定义SingleLinkedList来管理我们的英雄
 * @author
 * @since 2022/10/20 15:10
 */
public class SingleLinkedList {
    //先初始化一个头节点，头节点一般不动,表示数据中的头节点，并不存放具体数据
    private SingleLinkedListHeroNode head = new SingleLinkedListHeroNode(0,"","");

    /*定义一个添加的方法，用于添加节点到单向链表
    思路：当不考虑编号顺序时：1、找到当前链表的最后这个节点；2、将最后这个节点的next域指向新的节点
    */
    public void add(SingleLinkedListHeroNode heroNode){
        //因为head（即头节点）不能动，因此我们需要一个辅助变量temp
        SingleLinkedListHeroNode temp = head;
        //遍历链表找到最后节点
        while (true){
            //当变量temp找到最后一个节点为空时，就代表找到了最后节点的位置
            if (temp.next == null){
                break;
            }
                //如果没有找到最后，就让temp向后移动即可
                 temp = temp.next;
        }
        //当退出了这个循环后说明了temp已经指向了链表的最后，那么这个时候只需要将temp连上新的节点即可
        temp.next = heroNode;
    }

    //显示链表的方法（即遍历）
    public void list(){
        //首先判断链表是否为空，若为空就不用遍历了
        if (head.next == null){
            System.out.println("链表为空");
        }
        //因为头节点不能动，因此，需要通过一个辅助变量来遍历整个链表
        SingleLinkedListHeroNode temp = head.next;
        //链表不为空，开始循环
        while (true){
            //判断是否到达链表最后
            if (temp == null){
                break;
            }
            //若链表不为空就输出整个节点的信息
            System.out.println(temp);
            //将temp后移，不后移会导致链表死循环
            temp = temp.next;
        }
    }
}

• 定义好之后再进行测试

/**
 * description
 * 单链表的案例实现
 * @author
 * @since 2022/10/20 15:05
 */
public class SingleLinkedListDemo  {
    public static void main(String[] args) {
        //进行测试，先创建节点
        SingleLinkedListHeroNode heroNode1 = new SingleLinkedListHeroNode(1, "宋江", "及时雨");
        SingleLinkedListHeroNode heroNode2 = new SingleLinkedListHeroNode(2, "卢俊义", "玉麒麟");
        SingleLinkedListHeroNode heroNode3 = new SingleLinkedListHeroNode(3, "吴用", "智多星");
        SingleLinkedListHeroNode heroNode4 = new SingleLinkedListHeroNode(4, "林冲", "豹子头");

        //创建一个链表用于存放数据
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //将节点加入
        singleLinkedList.add(heroNode1);
        singleLinkedList.add(heroNode2);
        singleLinkedList.add(heroNode3);
        singleLinkedList.add(heroNode4);
        //显示链表，测试是否能正常显示
        singleLinkedList.list();
    }
}

• 经测试，输出结果如下

• 但同时我们发现了问题，即在新加入节点时输出结果会根据添加节点的顺序进行排序

  • 即当我们加入的顺序打乱，输出的结果就会根据添加的顺序排列

  

• 输出结果如下

• 所以要进行链表有序排列，需要再次进行优化

  • 思路分析

  

• 将原有的代码进行优化，新增另一种添加英雄的方式，即根据排名将英雄插入到指定位置

//新增第二种添加英雄的方式，根据排名将英雄插入到指定位置，若有此排名，则添加失败并返回错误信息
    public void addByOrder(SingleLinkedListHeroNode heroNode){
        /*因为头节点不能动，因此我们仍然通过一个辅助变量来帮助找到添加的位置
        又因为这是单链表，辅助变量temp是位于添加位置的前一个节点，否则插入不了*/
        SingleLinkedListHeroNode temp = head;
        //标识添加的变量是否存在，默认为false
        boolean flag = false;
        while (true){
            if (temp.next == null){ //说明temp已经到了链表的最后
                break;
            }
            if (temp.next.no > heroNode.no){ //位置找到，就在temp的后边插入
                break;
            }else if (temp.next.no == heroNode.no){ //说明希望添加的heroNode的编号已经存在
                flag = true; //说明编号存在
                break;
            }
            temp = temp.next;  //若是以上三个条件都不满足，就让temp后移，遍历当前链表
        }
        //判断flag的值
        if (flag){//若flag的值为true，说明不能添加，编号已经存在
            System.out.println("准备的插入的英雄编号" + heroNode.no + "已经存在了,无法重复添加");
        }else {
            //插入到链表种，即temp的后一位
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

• 打乱添加顺序，重新测试

singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode5);
        singleLinkedList.addByOrder(heroNode3);

• 输出结果如下：添加顺序混乱，但链表内的节点仍能自动排序

• 当加入一个重复添加的编号控制台会报错

• 至此代码优化完毕
  • 接下来是进行修改操作
  • 加入修改的方法

/*修改节点的信息，根据编号来修改，即编号不能进行修改
    说明：根据newHeroNode的no来修改即可
    */
    public void update(SingleLinkedListHeroNode newHeroNode){
        //首先判断链表是否为空
        if(head.next == null ){
            System.out.println("链表为空，无法修改");
        }
        //找到需要修改的节点,根据no编号来找，定义辅助节点方便查询
        SingleLinkedListHeroNode temp = head.next;
        boolean flag = false; //表示是否找到该节点
        while (true){
            if (temp == null){
                break;  //若temp为空表示链表已经遍历结束了
            }
            if (temp.no == newHeroNode.no){
                //temp找到当前需要修改的节点了
                flag = true;
                break;  //找到就结束循环，否则会一直往后
            }
            temp = temp.next;
        }
        //根据flag判断是否找到要修改的节点
        if(flag = true){
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        }else { //没有找到此节点
            System.out.println("没有找到编号为" + newHeroNode.no + "的节点");
        }
    }

• 测试修改功能是否正常

        //修改前的链表显示
        singleLinkedList.list();

        //测试修改节点的代码
        SingleLinkedListHeroNode newHeroNode = new SingleLinkedListHeroNode(2,"小卢","麒麟");
        singleLinkedList.update(newHeroNode);

        System.out.println("修改后的链表情况");
        //显示链表，测试是否能正常显示
        singleLinkedList.list();

• 修改效果如图
  • 经测试修改功能正常

• 接下来是删除功能

  • 思路如下

    

  • 代码实现

/*删除节点，思路：1、head节点不能动，因此我们需要temp辅助节点找到待删除节点的前一个节点
    2、我们在比较时，是temp.next.no 和需要删除的节点的no进行比较 */
    public void delete(int no){
        SingleLinkedListHeroNode temp = head;
        boolean flag = false; //标识是否找到待删除节点的前一个节点
        while (true){
            if (temp.next == null){ //说明已经到了链表的最后
                break;
            }
            if (temp.next.no == no){
                //说明找到了待删除节点的前一个节点temp
                flag = true;
                break;
            }
            temp = temp.next;  //temp后移实现链表遍历
        }
        //判断flag
        if (flag){ //找到节点
            //进行删除操作
            temp.next = temp.next.next;
        }else {
            System.out.println("要删除的节点" + no + "不存在");
        }
    }

• 进行测试删除的操作
  • 结果如图所示