力扣记录：贪心算法3较难(2)其他问题——53 最大子序和，134 加油站，968 监控二叉树

本次题目

• 53 最大子序和
• 134 加油站
• 968 监控二叉树

53 最大子序和

• 局部最优：当子序列求和为负数时放弃当前子序列，从下一个元素重新求和，定义整数记录过程中最大的和。可以动态规划。

class Solution {
    public int maxSubArray(int[] nums) {
        //定义整数记录过程中最大的和
        int max = nums[0];
        //求和
        int sum = 0;
        //开始遍历
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            if(sum > max) max = sum;
            //当子序列求和为负数时放弃当前子序列，从下一个元素重新求和
            if(sum < 0) sum = 0;
        }
        //返回结果
        return max;
    }
}

134 加油站

• 分情况讨论：
  1. 如果加油数组总和小于耗油数组，则一定无法跑完一圈；
  2. 从0开始，计算当天加油减耗油为剩油，如果过程中每天累积的剩油都大于等于0，则可以跑完一圈；
  3. 如果过程中出现某天累积的剩油为负数，记录最小负数，则从后向前查找能填平这个负数的节点，该点为出发点。
• 局部最优：定义当前剩油和总剩油，从0开始累积当前剩油，若当前累积剩油为负数，则记录下一个节点为起点，从下一个节点重新累积，最后如果总累积剩油大于等于0，则返回起点。
• 分情况：

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        //分情况讨论
        //定义累积剩油
        int rest = 0;
        //定义最小剩油
        int restMin = 0;
        //从0开始，计算当天加油减耗油为剩油
        for(int i = 0; i < gas.length; i++){
            rest += (gas[i] - cost[i]);
            restMin = Math.min(restMin, rest);
        }
        //如果加油数组总和小于耗油数组，则一定无法跑完一圈
        if(rest < 0) return -1;
        //如果过程中每天累积的剩油都大于等于0，则可以跑完一圈
        if(restMin >= 0) return 0;
        //如果过程中出现某天累积的剩油为负数，记录最小负数，
        //则从后向前查找能填平这个负数的节点，该点为出发点
        for(int j = gas.length - 1; j > 0; j--){
            restMin += (gas[j] - cost[j]);
            if(restMin >= 0) return j;
        }
        //最后返回-1
        return -1;
    }
}

• 局部最优：

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        //局部最优
        //定义当前剩油和总剩油
        int restCur = 0;
        int restAll = 0;
        //定义起点
        int start = 0;
        //从0开始，计算当天加油减耗油为剩油
        for(int i = 0; i < gas.length; i++){
            restCur += (gas[i] - cost[i]);
            restAll += (gas[i] - cost[i]);
            //若当前累积剩油为负数，则记录下一个节点为起点，从下一个节点重新累积
            if(restCur < 0){
                start = i + 1;
                restCur = 0;
            }
        }
        //最后如果总累积剩油大于等于0，则返回起点
        if(restAll >= 0) return start;
        //最后返回-1
        return -1;
    }
}

968 监控二叉树

• 局部最优：在叶子节点的父节点安装摄像头。
  1. 递归遍历二叉树（后序遍历），返回左右孩子的情况，判断中间节点是否叶子节点；
  2. 使用状态转移，每个节点可能的状态有无覆盖、有摄像头、有覆盖，返回当前节点状态，将空节点状态设为有覆盖；
  3. 如果左右孩子都有覆盖，则中间节点无覆盖，如果左右孩子至少有一个无覆盖（不管另一个是不是有摄像头），则中间节点应该放摄像头，如果左右孩子有一个有摄像头，则中间节点为有覆盖。
  4. 递归结束后，如果头节点为无覆盖，则需要在头节点添加摄像头。
• 注意：添加摄像头过程中记录数量。

class Solution {
    //定义摄像头数量
    int result = 0;
    public int minCameraCover(TreeNode root) {
        //递归结束后，如果头节点为无覆盖，则需要在头节点添加摄像头
        if(minCamera(root) == 1) result++;
        return result;
    }
    //递归遍历二叉树（后序遍历）
    //使用状态转移，每个节点可能的状态有无覆盖1、有覆盖2、有摄像头3
    private int minCamera(TreeNode root){
        //将空节点状态设为有覆盖
        if(root == null) return 2;
        //左右
        int left = minCamera(root.left);
        int right = minCamera(root.right);
        //返回左右孩子的情况，判断中间节点是否叶子节点
        //如果左右孩子都有覆盖，则中间节点无覆盖
        if(left == 2 && right == 2){
            return 1;
        }else if(left == 1 || right == 1){
            //如果左右孩子至少有一个无覆盖（不管另一个是不是有摄像头），则中间节点应该放摄像头
            result++;
            return 3;
        }else{
            //如果左右孩子有一个有摄像头，则中间节点为有覆盖
            return 2;
        }
    }
}