我的学习笔记

外观

本文字数: 1166 字 | 预计阅读: 8 分钟 | 最后更新于: 2026/07/20 20:58

双指针 ​

适用于数组划分的情况

数组划分：给一个标准或者制定一定规则，把数组划分为若干区间

283. 移动零 ​

  1. dest 与 cur 作用
    • dest: 零与非零元素的分割点，dest 所指向的是最后一个非零的下标
    • cur: 用来遍历数组
  2. 先分为三个区间
    • [0, dest] 表示非零元素,
    • [dest + 1, cur - 1] 表示零元素,
    • [cur, n - 1] 表示未处理元素
  3. 执行步骤：
    • 如果 nums[cur] 获取的变量是 0，那么执行 cur++
    • 如果 nums[cur] 获取的变量不是 0，那么先 dest++，然后交换 cur 与 dest 的下标，最后 cur++
步骤： 0 / 0
[0, dest]
已处理的非零元素
[dest + 1, cur - 1]
已处理的零元素
[cur, n - 1]
待处理未知元素

当前动作：等待输入...

Java
public void moveZeroes(int[] nums) {
    // [0, dest] 非零元素, [dest + 1, cur - 1] 零元素, [cur, n - 1] 未处理元素
    int dest = -1, cur = 0;
    while (cur < nums.length) {
        if (nums[cur] != 0) {
            dest++;
            int tmp = nums[cur];
            nums[cur] = nums[dest];
            nums[dest] = tmp;
        } 
        cur++;
    }
}

1089. 复写零 ​

思路：针对于数组排序先以异地的方式经行，如果成功了，那么就用就地的方式试试看

那么就用就地的方式不行，发现会覆盖其他元素，那么就以相反的方向试试看

异地 ​

创建一个新的数组，按照题目要求， 如果是0，那么就复写两次，如果不是，那么就写一次即可（不提供代码了，就提供流程）

步骤： 0 / 0
原数组 (Source)只读，使用指针 i 进行遍历扫描
↓ 读写分离 ↓
新数组 (Destination)只写，使用指针 j 写入，长度必须与原数组一致

当前动作：等待输入...

就地 ​

  1. 通过 virtualLength 来获取到虚拟长度（就是 arr 更新之后的长度），通过它来判断是否最后一位是 0
    1. 如果是非零元素，那么 virtualLength 加 1
    2. 如果是元素为零，那么 virtualLength 加 2
  2. 通过 virtualLength == arr.length + 1 判断是否过长
  3. 最后利用双指针从后往前遍历覆盖
步骤： 0 / 0

当前动作：等待输入...

Java
public void duplicateZeros(int[] arr) {
  // 先计算出最后有效数据的最后一位
  int i = 0;
  int size = arr.length;
  int virtualLength = 0; // 虚拟长度（就是 arr 更新之后的长度）
  for (; virtualLength < size; i++) {
      if (arr[i] == 0) {
          // 元素是0的情况下，加两次
          virtualLength += 2;
      } else {
          virtualLength += 1;
      }
  }
  // 判断一下，最后一位的 0 有没有复写
  if (virtualLength == size + 1) {
      // 最后一位一定是 0
      arr[size - 1] = 0;
      size--;
      i--;
  }
  // 然后利用双指针从后往前遍历覆盖
  int right = size - 1, left = i - 1;
  while(left >= 0 && right > left) {
      if (arr[left] == 0) {
          // 先复写一次
          arr[right--] = arr[left];
      }
      // 正常覆盖
      arr[right--] = arr[left--];
  }
}

202. 快乐数 ​

根据题意：它的结果要么是为 1，要么成环

下面的 执行一次 这个操作表示的是 将该数替换为它每个位置上的数字的平方和 这一个步骤

思路：

  1. 把成为 1 的这个结果看为成为一个环，只不过这个环上的内容全是 1
  2. 此时发现它们的结果都是成环，那么就可以想到 给定一个链表-判断链表中是否有环 这个题目
  3. 用 slow 表示 执行一次的值，用 fast 表示 执行二次的值，终止条件为 slow 与 fast 是否相等，最后判断 slow 是否为 1 即可

为什么呢一定成环呢？可以通过 鸽巢原理 来解释

  1. 查看输入参数的范围 1<=n<=231−1(2147483647)
  2. 那么它执行了一次后最大值为 99∗10(810)（把 n 看为最大的 9999999999，执行一次后一定小于这个）
  3. 获取到 “巢” 后，由于 810<9999999999 所以区间 [1,810] 里面的数执行一次后一定在这个区间里面
  4. 由此可以得出，最多执行 811 次后，里面的至少有一个数字会出现两次，即满足成环条件
步骤： 0 / 0

当前动作：等待输入...

Java
public boolean isHappy(int n) {
    int slow = func(n), fast = func(func(n));
    while(slow != fast) {
        slow = func(slow);
        fast = func(func(fast));
    }

    return slow == 1;
}

private int func(int n) {
    int ret = 0;
    while(n != 0) {
        int t = n % 10;
        ret = ret + t * t;
        n = n / 10;
    }

    return ret;
}

11. 盛最多水的容器 ​

思路：

  1. 先从两侧开始遍历，计算出体积

  2. 算出面积后，把对应值较小的坐标往另一侧移动

    • 面积计算公式： S=H∗L 其中 L1=right−left, H1=Min(height[left],height[right])
    • 此时把值较小（高度较小）的一侧固定，只移动较大的一侧，发现 L2<L1
    • 又因为高度比较小，所以此时高度一定小于等于原来的高度，即：H1<=H2
    • 所以内部面积一定不会大于最外围的面积，那么就不需要管较小的一侧了，也就可以移动较小的一侧了

  3. 反复循环，直到结束即可

步骤： 0 / 0

当前动作：等待输入...

Java
public int maxArea(int[] height) {
    // 从两边开始
    int right = height.length - 1, left = 0;
    int max = -1;
    int tmp = 0;
    while (left < right) {
        max = (tmp = getMaxV(left, right, height)) > max ? tmp : max;
        // 只需要除去最小的一侧即可
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return max;
}

private int getMaxV(int left, int right, int[] array) {
    int minH = array[left] < array[right] ? array[left] : array[right];
    return (right - left) * minH;
}