第一题
给定一个数组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会报错 但是搞反了
