算法刷题日志——贪心

最大子数组和

动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for(int num: nums) {
            if(sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

加油站

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int totalSum = 0;
        int index = 0;
        for (int i = 0; i < gas.length; i++) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum < 0) {
                index = i + 1 ; // 起始位置更新为i+1
                curSum = 0; // curSum从0开始
            }
        }
        if (totalSum < 0) return -1;
        return index;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

监控二叉树

class Solution {
    int res=0;
    public int minCameraCover(TreeNode root) {       
       return  dfs(root)==0?res+1:res;//如果父节点是无覆盖状态，那么需要在父节点添加一台摄像机
    }
    public int dfs(TreeNode root){
        if(root==null)
           return 2;//节点有覆盖
        int left=dfs(root.left);
        int right=dfs(root.right);
        //0表示无覆盖，1表示有相机，2表示有覆盖，左右节点可以组成9种状态
        //(00,01,02,10,11,12,20,21,22)
               
        //只要有一个无覆盖，父节点就需要相机来覆盖这个子节点 00,01,10,20,02
        if(left==0||right==0){
            res++;
            return 1;
        }
         //子节点其中只要有一个有相机，那么父节点就会是有覆盖的状态11,21,12
        if(left==1||right==1){
            return 2;
        }
        //还有一个就是22，两个子节点都是有覆盖的状态，父节点可以没有相机，可以借助它自己的父节点
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26