// 本题测试链接 : https://leetcode.com/problems/binary-tree-cameras/
public class Code02_MinCameraCover {
public static class TreeNode {
public int value;
public TreeNode left;
public TreeNode right;
}
public static int minCameraCover1(TreeNode root) {
Info data = process1(root);
return (int) Math.min(data.uncovered + 1, Math.min(data.coveredNoCamera, data.coveredHasCamera));
}
// 潜台词：x是头节点，x下方的点都被覆盖的情况下
public static class Info {
public long uncovered; // x没有被覆盖，x为头的树至少需要几个相机
public long coveredNoCamera; // x被相机覆盖，但是x没相机，x为头的树至少需要几个相机
public long coveredHasCamera; // x被相机覆盖了，并且x上放了相机，x为头的树至少需要几个相机
public Info(long un, long no, long has) {
uncovered = un;
coveredNoCamera = no;
coveredHasCamera = has;
}
}
// 所有可能性都穷尽了
public static Info process1(TreeNode X) {
if (X == null) { // base case
return new Info(Integer.MAX_VALUE, 0, Integer.MAX_VALUE);
}
Info left = process1(X.left);
Info right = process1(X.right);
// x uncovered x自己不被覆盖，x下方所有节点，都被覆盖
// 左孩子： 左孩子没被覆盖，左孩子以下的点都被覆盖
// 左孩子被覆盖但没相机，左孩子以下的点都被覆盖
// 左孩子被覆盖也有相机，左孩子以下的点都被覆盖
long uncovered = left.coveredNoCamera + right.coveredNoCamera;
// x下方的点都被covered，x也被cover，但x上没相机
long coveredNoCamera = Math.min(
// 1)
left.coveredHasCamera + right.coveredHasCamera,
Math.min(
// 2)
left.coveredHasCamera + right.coveredNoCamera,
// 3)
left.coveredNoCamera + right.coveredHasCamera));
// x下方的点都被covered，x也被cover，且x上有相机
long coveredHasCamera =
Math.min(left.uncovered, Math.min(left.coveredNoCamera, left.coveredHasCamera))
+ Math.min(right.uncovered, Math.min(right.coveredNoCamera, right.coveredHasCamera))
+ 1;
return new Info(uncovered, coveredNoCamera, coveredHasCamera);
}
public static int minCameraCover2(TreeNode root) {
Data data = process2(root);
return data.cameras + (data.status == Status.UNCOVERED ? 1 : 0);
}
// 以x为头，x下方的节点都是被covered，x自己的状况，分三种
public static enum Status {
UNCOVERED, COVERED_NO_CAMERA, COVERED_HAS_CAMERA
}
// 以x为头，x下方的节点都是被covered，得到的最优解中：
// x是什么状态，在这种状态下，需要至少几个相机
public static class Data {
public Status status;
public int cameras;
public Data(Status status, int cameras) {
this.status = status;
this.cameras = cameras;
}
}
public static Data process2(TreeNode X) {
if (X == null) {
return new Data(Status.COVERED_NO_CAMERA, 0);
}
Data left = process2(X.left);
Data right = process2(X.right);
int cameras = left.cameras + right.cameras;
// 左、或右，哪怕有一个没覆盖
if (left.status == Status.UNCOVERED || right.status == Status.UNCOVERED) {
return new Data(Status.COVERED_HAS_CAMERA, cameras + 1);
}
// 左右孩子，不存在没被覆盖的情况
if (left.status == Status.COVERED_HAS_CAMERA || right.status == Status.COVERED_HAS_CAMERA) {
return new Data(Status.COVERED_NO_CAMERA, cameras);
}
// 左右孩子，不存在没被覆盖的情况，也都没有相机
return new Data(Status.UNCOVERED, cameras);
}
}
给定一个数组arr，
返回如果排序之后，相邻两数的最大差值
要求：时间复杂度O(N)
import java.util.Arrays;
public class Code03_MaxGap {
public static int maxGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int len = nums.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < len; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
if (min == max) {
return 0;
}
// 不止一种数，min~max一定有range, len个数据，准备len+1个桶
boolean[] hasNum = new boolean[len + 1]; // hasNum[i] i号桶是否进来过数字
int[] maxs = new int[len + 1]; // maxs[i] i号桶收集的所有数字的最大值
int[] mins = new int[len + 1]; // mins[i] i号桶收集的所有数字的最小值
int bid = 0; // 桶号
for (int i = 0; i < len; i++) {
bid = bucket(nums[i], len, min, max);
mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
hasNum[bid] = true;
}
int res = 0;
int lastMax = maxs[0]; // 上一个非空桶的最大值
int i = 1;
for (; i <= len; i++) {
if (hasNum[i]) {
res = Math.max(res, mins[i] - lastMax);
lastMax = maxs[i];
}
}
return res;
}
// 如果当前的数是num，整个范围是min~max，分成了len + 1份
// 返回num该进第几号桶
public static int bucket(long num, long len, long min, long max) {
return (int) ((num - min) * len / (max - min));
}
// for test
public static int comparator(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
Arrays.sort(nums);
int gap = Integer.MIN_VALUE;
for (int i = 1; i < nums.length; i++) {
gap = Math.max(nums[i] - nums[i - 1], gap);
}
return gap;
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
if (maxGap(arr1) != comparator(arr2)) {
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
}
}
