一、数组扩容动态数组与普通数组不同动态数组的大小可在运行时调整ArrayList类是典型实例。数组扩容机制当数组元素数量达到容量极限时需创建更大数组并复制原元素。新数组长度常为原数组的1.5倍。数组复制扩容时原数组元素要复制到新数组逐个赋值实现package com.qcby.array; // 数组扩容 public class ArrayList { private int[] arr new int[10];// 初始容量为10的数组用于存储元素 private int size 0;// 记录数组中有效元素的个数 // 添加元素到数组末尾 public void add(int num) { // 检查是否需要扩容 if (size arr.length) { // 创建一个长度为原数组1.5倍的新数组 int[] brr new int[(int) (arr.length * 1.5)]; // 将原数组元素复制到新数组 for (int i 0; i arr.length; i) { brr[i] arr[i]; } // 将引用指向新数组 arr brr; } // 将新元素添加到数组末尾 arr[size] num; // 有效元素个数加1 size; } // 将数组转换为字符串表示 Override public String toString() { // 使用StringBuilder构建字符串提高效率 StringBuilder res new StringBuilder([); for (int i 0; i size; i) { res.append(arr[i]); // 如果不是最后一个元素添加逗号和空格 if (i ! size - 1) { res.append(, ); } } res.append(]); return res.toString(); } // 主方法用于测试 public static void main(String[] args) { ArrayList list new ArrayList(); // 添加多个元素到数组 list.add(10); list.add(1); list.add(20); list.add(8); list.add(9); list.add(5); list.add(2); list.add(11); list.add(13); list.add(18); list.add(21); list.add(22); list.add(3); list.add(5); list.add(7); // 打印数组内容 System.out.println(list); } // 在指定位置插入元素 public void add(int position, int num) { // 检查插入位置是否合法 if (position 0 || position size) { System.out.println(插入位置不合理); return; } // 检查是否需要扩容 if (size arr.length) { // 创建一个长度为原数组1.5倍的新数组 int[] brr new int[(int) (arr.length * 1.5)]; // 将原数组元素复制到新数组 for (int i 0; i arr.length; i) { brr[i] arr[i]; } // 将引用指向新数组 arr brr; } // 将插入位置及其之后的元素向后移动 for (int i size - 1; i position; i--) { arr[i 1] arr[i]; } // 将新元素插入到指定位置 arr[position] num; // 有效元素个数加1 size; } // 删除数组中的某个元素 public void delete(int num) { // 遍历数组从后向前查找要删除的元素 for (int i size - 1; i 0; i--) { if (arr[i] num) { // 将删除位置之后的元素向前移动 for (int j i 1; j size; j) { arr[j - 1] arr[j]; } // 有效元素个数减1 size--; } } } // 获取数组中有效元素的个数 public int size() { return size; } // 查找元素在数组中的位置 public int search(int num) { // 遍历数组查找指定元素 for (int i 0; i size; i) { if (arr[i] num) { return i; // 找到元素返回其索引 } } return -1; // 未找到元素返回-1 } }二、二分查找法二分查找法对有序数组适用。它重复将数组中点与目标值比对依大小关系缩小搜索区间直至找到目标或确定查找失败。时间复杂度为O(log n)适用场景适用于查找有序数组或列表中的元素可扩展到变体问题如查找第一个大于等于目标值的元素等。实现步骤初始化左右指针计算中间位置并与目标值比较调整搜索范围重复直至找到目标或搜索范围为空。package com.qcby.array; //二分查找法只适用于【有序数组】每次折半缩小查找范围效率远高于顺序遍历 public class BinarySearch { //程序入口主方法 public static void main(String[] args) { //定义一个升序排列的int数组二分查找必须有序 int[] arr {12, 37, 49, 71, 85, 88, 93, 100, 456}; //调用二分查找方法查找数字88打印返回的下标 System.out.println(binarysearch(88, arr)); } /** * 二分查找核心方法 * param num 需要查找的目标数字 * param arr 待查找的有序数组 * return 找到返回对应元素下标没找到返回-1 */ public static int binarysearch(int num, int[] arr) { //左边界初始指向数组第一个元素下标 int left 0; //右边界初始指向数组最后一个元素下标 int right arr.length - 1; //循环条件左边界不大于右边界说明区间内还有元素可以查找 while (left right) { //计算中间下标取左右边界的平均值分割数组 int mid (left right) / 2; //情况1中间元素正好等于目标值查找成功直接返回下标mid if (num arr[mid]) { return mid; } //情况2目标数字比中间值大 → 目标在右半边左边界移动到mid下一位 else if (num arr[mid]) { left mid 1; } //情况3目标数字比中间值小 → 目标在左半边右边界移动到mid前一位 else { right mid - 1; } } //循环结束仍未return说明数组中不存在目标数字返回-1标记查找失败 return -1; } }三、链表插入方法1.头插法头插法是在链表的头部插入一个新节点。过程创建一个新节点。如果链表为空新节点成为头节点。如果链表不为空新节点的 next 指针指向当前头节点然后将头指针更新为新节点。// 头插法 public void insertHead(int num) { Node node new Node(num); // 创建一个新节点 if (head null) { // 如果链表为空 head node; // 新节点成为头节点 return; } node.next head; // 新节点的 next 指向当前头节点 head node; // 更新头指针为新节点 }2.尾插法在链表的尾部插入一个新节点。过程创建一个新节点如果链表为空新节点成为头节点如果链表不为空找到当前链表的最后一个节点将该节点的 next 指针指向新节点// 尾插法 public void insert(int num) { Node node new Node(num); // 创建一个新节点 if (head null) { // 如果链表为空 head node; // 新节点成为头节点 return; } Node index head; // 从头节点开始遍历 while (index.next ! null) { // 找到最后一个节点 index index.next; } index.next node; // 将最后一个节点的 next 指向新节点 }3.获取链表长度和任意节点length 方法计算链表中有效节点的数量。实现初始化计数器 count 为 0然后遍历链表每访问一个节点就将计数器加 1直到遍历完整个链表。返回值返回计数器的值即链表的长度。search 方法在链表中查找具有特定值的节点。实现从头节点开始遍历链表检查每个节点的值是否等于目标值。如果找到匹配的节点则返回该节点如果遍历完整个链表都没有找到则返回 null 。返回值如果找到匹配的节点则返回该节点否则返回 null 。// 链表的长度 public int length() { int count 0; // 初始化计数器用于记录节点数量 Node index head; // 从头节点开始遍历 while (index ! null) { // 当前节点不为空时继续循环 count; // 计数器加一表示找到一个节点 index index.next; // 移动到下一个节点 } return count; // 返回计数器的值即链表长度 } // 查找 public Node search(int num) { Node index head; // 从头节点开始查找 while (index ! null) { // 当前节点不为空时继续循环 if (index.value num) { // 如果当前节点的值等于要查找的值 return index; // 返回当前节点 } index index.next; // 移动到下一个节点 } return null; // 如果遍历完整个链表仍未找到返回null }4.在任意位置插入// 任意位置插入 public void insertAtPosition(int num, int position) { // 检查插入位置是否合理即不小于0或大于链表长度 if (position 0 || position length()) { System.out.println(插入位置不合理); return; } // 如果位置为0即在链表头部插入 if (position 0) { insertHead(num); } else if (position length()) { // 如果位置等于链表长度即在链表尾部插入 insert(num); } else { // 在链表的中间位置插入新节点 Node node new Node(num); Node index head; Node pre null; int count 0; // 遍历链表找到插入位置的前一个节点 while (index ! null) { if (count position) { // 找到插入位置执行插入操作 pre.next node; node.next index; return; } pre index; index index.next; count; } // 如果遍历完成后仍未找到插入说明position超出链表长度将新节点添加到链表尾部 pre.next node; node.next index; } }5.删除增加一个哑节点任何情况下通用写法头结点也能删public void delete(int value) { Node dummy new Node(-1); // 1. 虚拟头统一头节点删除 dummy.next head; Node prev dummy, curr head; while (curr ! null) { if (curr.value value) { // 2. 找到要删的节点 prev.next curr.next; // 3. 跳过它 } else { prev curr; // 4. 正常前进 } curr curr.next; // 5. 继续扫描 } head dummy.next; // 6. 真实头可能改变 }四、总体node类初始化一个节点后续才有头插尾插
一、数组扩容动态数组与普通数组不同动态数组的大小可在运行时调整ArrayList类是典型实例。数组扩容机制当数组元素数量达到容量极限时需创建更大数组并复制原元素。新数组长度常为原数组的1.5倍。数组复制扩容时原数组元素要复制到新数组逐个赋值实现package com.qcby.array; // 数组扩容 public class ArrayList { private int[] arr new int[10];// 初始容量为10的数组用于存储元素 private int size 0;// 记录数组中有效元素的个数 // 添加元素到数组末尾 public void add(int num) { // 检查是否需要扩容 if (size arr.length) { // 创建一个长度为原数组1.5倍的新数组 int[] brr new int[(int) (arr.length * 1.5)]; // 将原数组元素复制到新数组 for (int i 0; i arr.length; i) { brr[i] arr[i]; } // 将引用指向新数组 arr brr; } // 将新元素添加到数组末尾 arr[size] num; // 有效元素个数加1 size; } // 将数组转换为字符串表示 Override public String toString() { // 使用StringBuilder构建字符串提高效率 StringBuilder res new StringBuilder([); for (int i 0; i size; i) { res.append(arr[i]); // 如果不是最后一个元素添加逗号和空格 if (i ! size - 1) { res.append(, ); } } res.append(]); return res.toString(); } // 主方法用于测试 public static void main(String[] args) { ArrayList list new ArrayList(); // 添加多个元素到数组 list.add(10); list.add(1); list.add(20); list.add(8); list.add(9); list.add(5); list.add(2); list.add(11); list.add(13); list.add(18); list.add(21); list.add(22); list.add(3); list.add(5); list.add(7); // 打印数组内容 System.out.println(list); } // 在指定位置插入元素 public void add(int position, int num) { // 检查插入位置是否合法 if (position 0 || position size) { System.out.println(插入位置不合理); return; } // 检查是否需要扩容 if (size arr.length) { // 创建一个长度为原数组1.5倍的新数组 int[] brr new int[(int) (arr.length * 1.5)]; // 将原数组元素复制到新数组 for (int i 0; i arr.length; i) { brr[i] arr[i]; } // 将引用指向新数组 arr brr; } // 将插入位置及其之后的元素向后移动 for (int i size - 1; i position; i--) { arr[i 1] arr[i]; } // 将新元素插入到指定位置 arr[position] num; // 有效元素个数加1 size; } // 删除数组中的某个元素 public void delete(int num) { // 遍历数组从后向前查找要删除的元素 for (int i size - 1; i 0; i--) { if (arr[i] num) { // 将删除位置之后的元素向前移动 for (int j i 1; j size; j) { arr[j - 1] arr[j]; } // 有效元素个数减1 size--; } } } // 获取数组中有效元素的个数 public int size() { return size; } // 查找元素在数组中的位置 public int search(int num) { // 遍历数组查找指定元素 for (int i 0; i size; i) { if (arr[i] num) { return i; // 找到元素返回其索引 } } return -1; // 未找到元素返回-1 } }二、二分查找法二分查找法对有序数组适用。它重复将数组中点与目标值比对依大小关系缩小搜索区间直至找到目标或确定查找失败。时间复杂度为O(log n)适用场景适用于查找有序数组或列表中的元素可扩展到变体问题如查找第一个大于等于目标值的元素等。实现步骤初始化左右指针计算中间位置并与目标值比较调整搜索范围重复直至找到目标或搜索范围为空。package com.qcby.array; //二分查找法只适用于【有序数组】每次折半缩小查找范围效率远高于顺序遍历 public class BinarySearch { //程序入口主方法 public static void main(String[] args) { //定义一个升序排列的int数组二分查找必须有序 int[] arr {12, 37, 49, 71, 85, 88, 93, 100, 456}; //调用二分查找方法查找数字88打印返回的下标 System.out.println(binarysearch(88, arr)); } /** * 二分查找核心方法 * param num 需要查找的目标数字 * param arr 待查找的有序数组 * return 找到返回对应元素下标没找到返回-1 */ public static int binarysearch(int num, int[] arr) { //左边界初始指向数组第一个元素下标 int left 0; //右边界初始指向数组最后一个元素下标 int right arr.length - 1; //循环条件左边界不大于右边界说明区间内还有元素可以查找 while (left right) { //计算中间下标取左右边界的平均值分割数组 int mid (left right) / 2; //情况1中间元素正好等于目标值查找成功直接返回下标mid if (num arr[mid]) { return mid; } //情况2目标数字比中间值大 → 目标在右半边左边界移动到mid下一位 else if (num arr[mid]) { left mid 1; } //情况3目标数字比中间值小 → 目标在左半边右边界移动到mid前一位 else { right mid - 1; } } //循环结束仍未return说明数组中不存在目标数字返回-1标记查找失败 return -1; } }三、链表插入方法1.头插法头插法是在链表的头部插入一个新节点。过程创建一个新节点。如果链表为空新节点成为头节点。如果链表不为空新节点的 next 指针指向当前头节点然后将头指针更新为新节点。// 头插法 public void insertHead(int num) { Node node new Node(num); // 创建一个新节点 if (head null) { // 如果链表为空 head node; // 新节点成为头节点 return; } node.next head; // 新节点的 next 指向当前头节点 head node; // 更新头指针为新节点 }2.尾插法在链表的尾部插入一个新节点。过程创建一个新节点如果链表为空新节点成为头节点如果链表不为空找到当前链表的最后一个节点将该节点的 next 指针指向新节点// 尾插法 public void insert(int num) { Node node new Node(num); // 创建一个新节点 if (head null) { // 如果链表为空 head node; // 新节点成为头节点 return; } Node index head; // 从头节点开始遍历 while (index.next ! null) { // 找到最后一个节点 index index.next; } index.next node; // 将最后一个节点的 next 指向新节点 }3.获取链表长度和任意节点length 方法计算链表中有效节点的数量。实现初始化计数器 count 为 0然后遍历链表每访问一个节点就将计数器加 1直到遍历完整个链表。返回值返回计数器的值即链表的长度。search 方法在链表中查找具有特定值的节点。实现从头节点开始遍历链表检查每个节点的值是否等于目标值。如果找到匹配的节点则返回该节点如果遍历完整个链表都没有找到则返回 null 。返回值如果找到匹配的节点则返回该节点否则返回 null 。// 链表的长度 public int length() { int count 0; // 初始化计数器用于记录节点数量 Node index head; // 从头节点开始遍历 while (index ! null) { // 当前节点不为空时继续循环 count; // 计数器加一表示找到一个节点 index index.next; // 移动到下一个节点 } return count; // 返回计数器的值即链表长度 } // 查找 public Node search(int num) { Node index head; // 从头节点开始查找 while (index ! null) { // 当前节点不为空时继续循环 if (index.value num) { // 如果当前节点的值等于要查找的值 return index; // 返回当前节点 } index index.next; // 移动到下一个节点 } return null; // 如果遍历完整个链表仍未找到返回null }4.在任意位置插入// 任意位置插入 public void insertAtPosition(int num, int position) { // 检查插入位置是否合理即不小于0或大于链表长度 if (position 0 || position length()) { System.out.println(插入位置不合理); return; } // 如果位置为0即在链表头部插入 if (position 0) { insertHead(num); } else if (position length()) { // 如果位置等于链表长度即在链表尾部插入 insert(num); } else { // 在链表的中间位置插入新节点 Node node new Node(num); Node index head; Node pre null; int count 0; // 遍历链表找到插入位置的前一个节点 while (index ! null) { if (count position) { // 找到插入位置执行插入操作 pre.next node; node.next index; return; } pre index; index index.next; count; } // 如果遍历完成后仍未找到插入说明position超出链表长度将新节点添加到链表尾部 pre.next node; node.next index; } }5.删除增加一个哑节点任何情况下通用写法头结点也能删public void delete(int value) { Node dummy new Node(-1); // 1. 虚拟头统一头节点删除 dummy.next head; Node prev dummy, curr head; while (curr ! null) { if (curr.value value) { // 2. 找到要删的节点 prev.next curr.next; // 3. 跳过它 } else { prev curr; // 4. 正常前进 } curr curr.next; // 5. 继续扫描 } head dummy.next; // 6. 真实头可能改变 }四、总体node类初始化一个节点后续才有头插尾插
![[GESP202606 四级] 扫雷](http://pic.xiahunao.cn/yaotu/[GESP202606 四级] 扫雷)
