概述
第一天主要学习的是数组相关的内容，相关学习的内容包括数组的基本特性的学习，二分搜索方法的学习。
概念
数组特点
数组的基本特点包括：
- 下标从 0 开始
- 内存连续性（Java 中定义数组需要直接声明其空间大小）
- 数组元素不可以删，只能覆盖
- ArrayList 底层是数组实现，其实际上应该叫一种容器
- 二维数组，array[i][j], 指的是 i 行 j 列的元素，后续会有二维数组上的相关题目，如搜索等。
- 哈希表结构也会用到数组，如果确认元素范围，比如字母 a-z，不妨定义 boolean 数组，通过数组快速判断元素是否存在过。
public static void main(String[] args) { boolean[] visited = new boolean[26]; String input = "abcdaz"; for (char c : input.toCharArray()) { if (visited[c - 'a']) { System.out.println("字母" + c + "重复"); } visited[c - 'a'] = true; } }
相关的 API
此前发现有的公司会要求在编辑器里面写代码，平常习惯了有 IDE 的提示，一下子忽然没了 IDE，设置连几个常见的 API 都搞混淆了。再记录一下：
public static void main(String[] args) { // 数组的长度, API是 .length boolean[] visited = new boolean[26]; System.out.println("visited.length = " + visited.length); // String的长度, API是 .length() String s = "example"; System.out.println("s.length() = " + s.length()); // 集合类型的大小，API是 .size() List<Integer> result = List.of(1, 2, 3); System.out.println("result.size() = " + result.size()); }
经典题型
- 纯编程题
- 二分查找
- 需要数组有序
- 套二分法模板
- 双指针
作业题
class Solution { public int search(int[] nums, int target) { int low = 0, high = nums.length - 1; while(low <= high) { // 不直接使用(high+low)/2，避免加法越界的问题 int mid = low + (high - low) / 2; // 找到目标,直接返回 if(nums[mid] == target) { return mid; } // 当前的中间值比目标大，说明目标在左半边，故缩小区间到 [left, mid - 1] if(nums[mid] > target) { high = mid -1; } else { // 当前的中间值比目标小，说明目标在右半边，故缩小区间到 [mid + 1, right] low = mid + 1; } } // 未找到目标，返回-1 return -1; } }
class Solution { public int removeElement(int[] nums, int val) { int left = 0; for(int right = left; right < nums.length; right++) { // 非待删除的元素，进行搬迁 if(nums[right] != val) { nums[left] = nums[right]; left++; } } return left; } }
