← 返回学习路线

SYSTEM

数组

八股1.1 数组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]);
            }
        }
    }
}