SYSTEM
数组
src/content/notes/system/数组.md 一、必须掌握
1.1 数组
二分查找(模板 + 力扣 704)
二分查找的前提是数组有序。关键在于统一区间边界约定:以下采用”左闭右闭” [left, right],故循环条件为 left <= right,缩边界时 mid - 1 / mid + 1。
// 力扣 704. 二分查找
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防溢出
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
}
双指针(力扣 283 移动零、力扣 15 三数之和)
快慢双指针做原地搬移;对撞双指针配合排序处理三数之和去重。
// 力扣 283. 移动零(同向快慢指针)
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != 0) {
int t = nums[slow]; nums[slow] = nums[fast]; nums[fast] = t;
slow++;
}
}
}
}
// 力扣 15. 三数之和(排序 + 对撞双指针)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) break; // 最小值已 >0,不可能凑出 0
if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
int l = i + 1, r = nums.length - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum == 0) {
res.add(Arrays.asList(nums[i], nums[l], nums[r]));
while (l < r && nums[l] == nums[l + 1]) l++; // 去重
while (l < r && nums[r] == nums[r - 1]) r--;
l++; r--;
} else if (sum < 0) l++;
else r--;
}
}
return res;
}
}
滑动窗口(力扣 3 无重复字符最长子串、力扣 209 长度最小子数组)
滑动窗口用左右指针维护一个窗口,右指针扩张、左指针收缩,根据题意在窗口满足条件时更新答案。
// 力扣 3. 无重复字符的最长子串
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> last = new HashMap<>();
int left = 0, max = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (last.containsKey(c)) {
left = Math.max(left, last.get(c) + 1); // 跳过重复字符
}
last.put(c, right);
max = Math.max(max, right - left + 1);
}
return max;
}
}
// 力扣 209. 长度最小的子数组
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0, sum = 0, min = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) { // 满足条件,收缩左边界找更短
min = Math.min(min, right - left + 1);
sum -= nums[left++];
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
}
面试题:“二分查找的边界条件怎么处理?”
关键是固定区间约定:用左闭右闭 [l, r] 时 while (l <= r),命中后 r = mid - 1、l = mid + 1;用左闭右开 [l, r) 时 while (l < r),r = mid、l = mid + 1。算 mid 用 l + (r - l) / 2 防整数溢出。找第一个/最后一个满足条件的位置时,只在真正命中时不立刻返回,而是收紧边界继续逼近。
补充材料 · 数组
数组
bash支持一维数组(不支持多维数组),并且没有限定数组的大小。
定义数组
在 Shell 中,用括号来表示数组,数组元素用”空格”符号分割开
数组名=(值1 值2 ... 值n)
array_name=(value0 value1 value2 value3)
array_name=(
value0
value1
value2
value3
)
通过下标定义数组中的其中一个元素:
array_name[0]=value0
array_name[1]=value1
array_name[n]=valuen
可以不使用连续的下标,而且下标的范围没有限制
读取数组
读取数组元素值的一般格式是:
${数组名[下标]}
value=${array_name[n]}
echo ${value}
使用 @ 符号可以获取数组中的所有元素,例如:echo ${array_name[@]}
获取长度
获取数组长度的方法与获取字符串长度的方法相同,数组前加#
# 取得数组元素的个数
length=${#array_name[@]}
# 或者
length=${#array_name[*]}
#! /bin/bash
g=(a b c d e f)
echo "数组下标为2的数据为:" ${g[2]} #c
echo "数组所有数据为:" ${#g[@]} #6
echo "数组所有数据为:" ${#g[*]} #6
补充材料 · 数组
数组
数组的使用和 java 中的数组基本一致,在JavaScript 中的数组更加灵活,数据类型和长度都没有限制
-
定义格式
let 数组名 = [元素1,元素2,…]; -
索引范围:从 0 开始,最大到数组长度-1
-
数组长度:数组名.length
let arr = [10,20,30]; document.write(arr+"<br>")// 直接输出:10,20,30 for(let i = 0; i < arr.length; i++) { document.write(arr[i] + "<br>"); } -
数组高级运算符:…
-
数组赋值
let arr2 = [...arr]; -
合并数组
let arr3 = [40,50,60]; let arr4 = [...arr2 , ...arr3]; -
字符串转数组
let arr5 = [..."JavaScript"];
-
补充材料 · 数组
数组
初始化
数组就是存储数据长度固定的容器,存储多个数据的数据类型要一致,数组也是一个对象
创建数组:
- 数据类型[] 数组名:
int[] arr(常用) - 数据类型 数组名[]:
int arr[]
静态初始化:
- 数据类型[] 数组名 = new 数据类型[]{元素1,元素2,…}:
int[] arr = new int[]{11,22,33} - 数据类型[] 数组名 = {元素1,元素2,…}:
int[] arr = {44,55,66}
动态初始化
- 数据类型[] 数组名 = new 数据类型[数组长度]:
int[] arr = new int[3]
元素访问
-
索引:每一个存储到数组的元素,都会自动的拥有一个编号,从 0 开始。这个自动编号称为数组索引(index),可以通过数组的索引访问到数组中的元素
-
访问格式:数组名[索引],
arr[0] -
赋值:
arr[0] = 10
内存分配
内存是计算机中的重要器件,临时存储区域,作用是运行程序。编写的程序是存放在硬盘中,在硬盘中的程序是不会运行的,必须放进内存中才能运行,运行完毕后会清空内存,Java 虚拟机要运行程序,必须要对内存进行空间的分配和管理
| 区域名称 | 作用 |
|---|---|
| 寄存器 | 给 CPU 使用 |
| 本地方法栈 | JVM 在使用操作系统功能的时候使用 |
| 方法区 | 存储可以运行的 class 文件 |
| 堆内存 | 存储对象或者数组,new 来创建的,都存储在堆内存 |
| 方法栈 | 方法运行时使用的内存,比如 main 方法运行,进入方法栈中执行 |
内存分配图:Java 数组分配在堆内存
-
一个数组内存图

-
两个数组内存图

-
多个数组指向相同内存图

数组异常
-
索引越界异常:ArrayIndexOutOfBoundsException
-
空指针异常:NullPointerException
public class ArrayDemo { public static void main(String[] args) { int[] arr = new int[3]; //把null赋值给数组 arr = null; System.out.println(arr[0]); } }arr = null,表示变量 arr 将不再保存数组的内存地址,也就不允许再操作数组,因此运行的时候会抛出空指针异常。在开发中,空指针异常是不能出现的,一旦出现了,就必须要修改编写的代码
解决方案:给数组一个真正的堆内存空间引用即可
二维数组
二维数组也是一种容器,不同于一维数组,该容器存储的都是一维数组容器
初始化:
-
动态初始化:数据类型[][] 变量名 = new 数据类型[m] [n],
int[][] arr = new int[3][3]- m 表示这个二维数组,可以存放多少个一维数组,行
- n 表示每一个一维数组,可以存放多少个元素,列
-
静态初始化
- 数据类型[][] 变量名 = new 数据类型 [][]{{元素1, 元素2…} , {元素1, 元素2…}
- 数据类型[][] 变量名 = {{元素1, 元素2…}, {元素1, 元素2…}…}
int[][] arr = {{11,22,33}, {44,55,66}}
遍历:
public class Test1 {
/*
步骤:
1. 遍历二维数组,取出里面每一个一维数组
2. 在遍历的过程中,对每一个一维数组继续完成遍历,获取内部存储的每一个元素
*/
public static void main(String[] args) {
int[][] arr = {{11, 22, 33}, {33, 44, 55}};
// 1. 遍历二维数组,取出里面每一个一维数组
for (int i = 0; i < arr.length; i++) {
//System.out.println(arr[i]);
// 2. 在遍历的过程中,对每一个一维数组继续完成遍历,获取内部存储的每一个元素
//int[] temp = arr[i];
for (int j = 0; j < arr[i].length; j++) {
System.out.println(arr[i][j]);
}
}
}
}