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 + "不存在");
}
}
- 进行测试删除的操作
- 结果如图所示
