class050 双指针技巧与相关题目【算法】

package class050;
// 按奇偶排序数组II
// 给定一个非负整数数组 nums。nums 中一半整数是奇数 ，一半整数是偶数
// 对数组进行排序，以便当 nums[i] 为奇数时，i也是奇数
// 当 nums[i] 为偶数时， i 也是 偶数
// 你可以返回 任何满足上述条件的数组作为答案
// 测试链接 : https://leetcode.cn/problems/sort-array-by-parity-ii/
public class Code01_SortArrayByParityII {
  // 时间复杂度O(n)，额外空间复杂度O(1)
  public static int[] sortArrayByParityII(int[] nums) {
    int n = nums.length;
    for (int odd = 1, even = 0; odd < n && even < n;) {
      if ((nums[n - 1] & 1) == 1) {
        swap(nums, odd, n - 1);
        odd += 2;
      } else {
        swap(nums, even, n - 1);
        even += 2;
      }
    }
    return nums;
  }
  public static void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
  }
}

package class050;
// 寻找重复数
// 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n）
// 可知至少存在一个重复的整数。
// 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
// 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
// 测试链接 : https://leetcode.cn/problems/find-the-duplicate-number/
public class Code02_FindTheDuplicateNumber {
  // 时间复杂度O(n)，额外空间复杂度O(1)
  public static int findDuplicate(int[] nums) {
    if (nums == null || nums.length < 2) {
      return -1;
    }
    int slow = nums[0];
    int fast = nums[nums[0]];
    while (slow != fast) {
      slow = nums[slow];
      fast = nums[nums[fast]];
    }
    // 相遇了，快指针回开头
    fast = 0;
    while (slow != fast) {
      fast = nums[fast];
      slow = nums[slow];
    }
    return slow;
  }
}

package class050;
// 接雨水
// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
// 测试链接 : https://leetcode.cn/problems/trapping-rain-water/
public class Code03_TrappingRainWater {
  // 辅助数组的解法（不是最优解）
  // 时间复杂度O(n)，额外空间复杂度O(n)
  // 提交时改名为trap
  public static int trap1(int[] nums) {
    int n = nums.length;
    int[] lmax = new int[n];
    int[] rmax = new int[n];
    lmax[0] = nums[0];
    // 0~i范围上的最大值，记录在lmax[i]
    for (int i = 1; i < n; i++) {
      lmax[i] = Math.max(lmax[i - 1], nums[i]);
    }
    rmax[n - 1] = nums[n - 1];
    // i~n-1范围上的最大值，记录在rmax[i]
    for (int i = n - 2; i >= 0; i--) {
      rmax[i] = Math.max(rmax[i + 1], nums[i]);
    }
    int ans = 0;
    //   x              x
    //   0 1 2 3...n-2 n-1
    for (int i = 1; i < n - 1; i++) {
      ans += Math.max(0, Math.min(lmax[i - 1], rmax[i + 1]) - nums[i]);
    }
    return ans;
  }
  // 双指针的解法（最优解）
  // 时间复杂度O(n)，额外空间复杂度O(1)
  // 提交时改名为trap
  public static int trap2(int[] nums) {
    int l = 1, r = nums.length - 2, lmax = nums[0], rmax = nums[nums.length - 1];
    int ans = 0;
    while (l <= r) {
      if (lmax <= rmax) {
        ans += Math.max(0, lmax - nums[l]);
        lmax = Math.max(lmax, nums[l++]);
      } else {
        ans += Math.max(0, rmax - nums[r]);
        rmax = Math.max(rmax, nums[r--]);
      }
    }
    return ans;
  }
}

package class050;
import java.util.Arrays;
// 救生艇
// 给定数组 people
// people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit
// 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit
// 返回 承载所有人所需的最小船数
// 测试链接 : https://leetcode.cn/problems/boats-to-save-people/
public class Code04_BoatsToSavePeople {
  // 时间复杂度O(n * logn)，因为有排序，额外空间复杂度O(1)
  public static int numRescueBoats(int[] people, int limit) {
    Arrays.sort(people);
    int ans = 0;
    int l = 0;
    int r = people.length - 1;
    int sum = 0;
    while (l <= r) {
      sum = l == r ? people[l] : people[l] + people[r];
      if (sum > limit) {
        r--;
      } else {
        l++;
        r--;
      }
      ans++;
    }
    return ans;
  }
}

package class050;
// 盛最多水的容器
// 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
// 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水
// 返回容器可以储存的最大水量
// 说明：你不能倾斜容器
// 测试链接 : https://leetcode.cn/problems/container-with-most-water/
public class Code05_ContainerWithMostWater {
  // 时间复杂度O(n)，额外空间复杂度O(1)
  public static int maxArea(int[] height) {
    int ans = 0;
    for (int l = 0, r = height.length - 1; l < r;) {
      ans = Math.max(ans, Math.min(height[l], height[r]) * (r - l));
      if (height[l] <= height[r]) {
        l++;
      } else {
        r--;
      }
    }
    return ans;
  }
}

package class050;
import java.util.Arrays;
// 供暖器
// 冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
// 在加热器的加热半径范围内的每个房屋都可以获得供暖。
// 现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置
// 请你找出并返回可以覆盖所有房屋的最小加热半径。
// 说明：所有供暖器都遵循你的半径标准，加热的半径也一样。
// 测试链接 : https://leetcode.cn/problems/heaters/
public class Code06_Heaters {
  // 时间复杂度O(n * logn)，因为有排序，额外空间复杂度O(1)
  public static int findRadius(int[] houses, int[] heaters) {
    Arrays.sort(houses);
    Arrays.sort(heaters);
    int ans = 0;
    for (int i = 0, j = 0; i < houses.length; i++) {
      // i号房屋
      // j号供暖器
      while (!best(houses, heaters, i, j)) {
        j++;
      }
      ans = Math.max(ans, Math.abs(heaters[j] - houses[i]));
    }
    return ans;
  }
  // 这个函数含义：
  // 当前的地点houses[i]由heaters[j]来供暖是最优的吗？
  // 当前的地点houses[i]由heaters[j]来供暖，产生的半径是a
  // 当前的地点houses[i]由heaters[j + 1]来供暖，产生的半径是b
  // 如果a < b, 说明是最优，供暖不应该跳下一个位置
  // 如果a >= b, 说明不是最优，应该跳下一个位置
  public static boolean best(int[] houses, int[] heaters, int i, int j) {
    return j == heaters.length - 1 
        ||
         Math.abs(heaters[j] - houses[i]) < Math.abs(heaters[j + 1] - houses[i]);
  }
}

package class050;
// 缺失的第一个正数
// 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
// 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
// 测试链接 : https://leetcode.cn/problems/first-missing-positive/
public class Code07_FirstMissingPositive {
  // 时间复杂度O(n)，额外空间复杂度O(1)
  public static int firstMissingPositive(int[] arr) {
    // l的左边，都是做到i位置上放着i+1的区域
    // 永远盯着l位置的数字看，看能不能扩充(l++)
    int l = 0;
    // [r....]垃圾区
    // 最好的状况下，认为1~r是可以收集全的，每个数字收集1个，不能有垃圾
    // 有垃圾呢？预期就会变差(r--)
    int r = arr.length;
    while (l < r) {
      if (arr[l] == l + 1) {
        l++;
      } else if (arr[l] <= l || arr[l] > r || arr[arr[l] - 1] == arr[l]) {
        swap(arr, l, --r);
      } else {
        swap(arr, l, arr[l] - 1);
      }
    }
    return l + 1;
  }
  public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }
}