第一题

给定一个数组arr 求子数组最大累加和

最暴力的 枚举每一个子数组 出结果

优化解 用一个cur指针保存累加和 每次cur变大 就用它更新max 如果cur累加到0以下 回复成0

假设答案法 假设我们最大的子数组是i 到 j位置上的

那么这个i 到j 之间 必不存在一个k使i...k累加和小于0 因为如果小于0了 那这个子数组就不是最大的

而且这个 i-1....k不可能大于0 如果大于0了 那为什么不把i-1算进来 让这个子数组变得更大?

所以这个cur是什么含义 我们使用cur在累加数组 也就是说 当cur回滚成0的时候 就是新的子数组的开始 

当cur累加到0以下 就说明 我们已经走到一个k...i累加和小于0的部分了 这部分肯定不是答案

(如果下一个数字还是负数 那cur还是0 也就是说这个点也不要)

或者我们用自然思维想一下 这个cur累加<0 就说明前面这一部分已经是<0了 我们加上它只会让累加和变小 那就要舍弃掉  你是不是在想 那当这个 减小的区间 前面有一个大的区间 那我们岂不是把这个更大的区间舍弃掉了 并不会 我们的cur会先累加大区间 然后再去加小区间 如果这个大区间还没有被小区间抵消的话 就不会被舍弃掉 

 public int maxSubArray(int[] nums) {
       int cur = 0;
       int max = Integer.MIN_VALUE;
       for (int i : nums) {
		cur += i;
		
		max = Math.max(cur, max);
		cur = cur<0?0:cur;
	}
       return max;
    }

当<0的时候 它调整为0这一步 不加入max的计算 假如说nums 只有-1 吧 你调整回0去了 再比 那最大累加和就是0了

还有我刚开始写成这样了

那总要跳过 不如直接把它放在最后一步 是一样的 还不会跳过max的比较操作(面对-1用例的时候不行)

第二题

给定一个正整数、负整数和 0 组成的 N × M 矩阵编写代码找出元素总和最大的子矩阵。

返回一个数组 [r1, c1, r2, c2]其中 r1, c1 分别代表子矩阵左上角的行号和列号r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵返回任意一个均可。
给一个矩阵 

 5 -3  2   7

-6  3  2  -1

7  2  -5   4

矩阵有一个什么特点呢  如果我想要5 -3和 7 2 的话 那中间的-6 3 2 -1也得要 这个耦合性很强 我们可以用这个特点优化

先遍历每一个满长方形 就是每一行全要 比如

 5 -3  2   7

-6  3  2  -1

7  2  -5   4

这三个长方形是 高度为1的

 5 -3  2   7

-6  3  2  -1

-6  3  2  -1

7  2  -5   4

这两个是高度为2的

 5 -3  2   7

-6  3  2  -1

7  2  -5   4

这个是高度为3的

由于矩阵的耦合性 要一行必须要其他的行 我们可以直接把它压缩成一行 然后在这个行上面找 最大子数组累加和

lass RES{
	int max;
	int [] row = new int [2];
    int [] col = new int [2];
}
class Solution {
    public int[] getMaxMatrix(int[][] matrix) {
 int [] sum = null;
        int max = Integer.MIN_VALUE;
        RES maxres = new RES();
        maxres.max = Integer.MIN_VALUE;
        for(int i = 0;i<matrix.length;i++) {
        	sum = new int [matrix[0].length];
        	for(int j = i;j<matrix.length;j++) {
        		for(int t = 0;t<matrix[0].length;t++) {
        			sum[t]+=matrix[j][t];
        		}
        		RES res = getMax(sum);
        		res.col = new int [] {i,j};
        		if(res.max>maxres.max) {
        			maxres = res;
        		}
        	}
        }
        
        return new int [] {maxres.col[0],maxres.row[0],maxres.col[1],maxres.row[1]};
        
    }
    public  RES getMax(int [] arr) {
	int cur = 0;
		int max = Integer.MIN_VALUE;
		int size = 0;
		int fin = 0;
		int maxsize = 0;
		for (int i = 0;i<arr.length;i++) {
			cur+=arr[i];
      size++;
			if(cur>max) {
				max = cur;
				fin = i;
				maxsize = size;
			}
			if(cur<0) {
				cur = 0;
        size = 0;			 
			}

			
		}
		RES res = new RES();
		res.max = max;
		res.row = new int [] {fin-maxsize+1,fin};
		return res;
	}
}

累死我了

题目三

求完全二叉树节点的个数要求时间复杂度低于O(N)

每层都是满的 如果最后一层不满 那也是从左往右变满的

找到他最左边的那条边 直接扎到底

看它有多少层

然后再找 右树的最左节点 如果和刚才的层数相同 那就说明左树全满

那下一步就是查右树的节点数

那要是没有左树高呢 那就说明右树 是满的 但是比左树的 高度 要矮一层

递归查左树的节点数

 public int countNodes(TreeNode root) {
          return Process(root);
    }
    public int Process(TreeNode root) {
		if(root==null) {
			return 0;
		}
		TreeNode leftcur = root;
		int left = 1;
		int right = 1;
		while(leftcur.left!=null) {
			leftcur = leftcur.left;
			left++;
		}
		if(root.right!=null) {
			right++;
		}
		TreeNode rightcur = root.right;
		while(rightcur!=null&&rightcur.left!=null) {
			rightcur = rightcur.left;
			right++;
		}
		if(right==left) {
			return (int) (Math.pow(2, left-1)+Process(root.right));
		}else {
			return (int) (Math.pow(2, right-1)+Process(root.left));
		}
	}

(rightcur!=null&&rightcur.left!=null)

hhh 虽然这里记得null.right会报错 但是搞反了