每天N道算法高频题-DAY2

落日映苍穹つ 2023-10-13 15:47 43阅读 0赞

每天早上看书看不进 就做题吧 虽然这博客发出去的时间是晚上

## 题目一 ##

给你一个由若干 `0` 和 `1` 组成的二维网格 `grid`，请你找出边界全部由 `1` 组成的最大 **正方形** 子网格，并返回该子网格中的元素数量。如果不存在，则返回 `0`  
例如:  
01111  
01001  
01001  
01111  
01011  
其中边框全是1的最大正方形的大小为4\*4.所以返回4。

首先我们要了解 一下 在N\*N的面积中 有多少个长方形 的数量级是O(N四次方)

而有多少个正方形的数量级是 O(N³) 那我们遍历正方形的复杂度还要O(N) 也就是说暴力解的时间复杂度是O(N四次方) 好家伙 这绝对ac不了啊

这题还是用预处理数组的方法

如果我们有每个位置的右侧的有效1长度和下方的有效长度(用一个定点 和 边长确定最大值) 不就出来每个位置的正方形长度了吗

然后还有一个小加速 当当前点为0的时候 绝对不可能是正方形的定点

OK 大流程敲定了我们来看具体实现

怎么取得每个点向下的有效长度和向右的有效长度呢 不能直接遍历吧 那岂不是和暴力解一样了吗

这里决定采用动态规划的方式 创建两个个dp数组 一个保存下 一个保存右

对于右来说 每个格子的结果依赖于 右边的结果

对于下来说 每个格子的结果依赖于 下面的结果

0 **1** 1 1 1 比如对于这个红色的位置来讲 它的右边有效1个数就是 它右边格子数+1 它右边格子同  
0 1 0 0 1 理,依赖于更右面格子加1 所以我们只要获得最右侧一列的结果 就可以推出 全部的结果  
0 1 0 0 1  
0 1 1 1 1 那它下面的有效个数呢 就依赖于下面的有效1个数+1 以此类推 所以只需要最下面一行  
0 1 0 1 1 结果

你可能会问(谁问了?几十阅读量的博客谁问了?我自己问的) 那么一定要+1吗 如果当前位置为0不就不加了吗 何止不加了 当前位置为0就代表着不可能以这个位置为顶点做正方形 直接把该位置数据为0即可

然后有这两个辅助数组了 就可以遍历每种情况了(遍历size的可能性 反正就那么多种 最多也就是N

如果遍历每个点找SIZE的话 行数列数什么特殊情况找到吐 我最开始就是这么错的)

public static void setBorderMap(int[][] m, int[][] right, int[][] down) {
    		int r = m.length;
    		int c = m[0].length;
    		if (m[r - 1][c - 1] == 1) {
    			right[r - 1][c - 1] = 1;
    			down[r - 1][c - 1] = 1;
    		}
    		for (int i = r - 2; i != -1; i--) {
    			if (m[i][c - 1] == 1) {
    				right[i][c - 1] = 1;
    				down[i][c - 1] = down[i + 1][c - 1] + 1;
    			}
    		}
    		for (int i = c - 2; i != -1; i--) {
    			if (m[r - 1][i] == 1) {
    				right[r - 1][i] = right[r - 1][i + 1] + 1;
    				down[r - 1][i] = 1;
    			}
    		}
    		for (int i = r - 2; i != -1; i--) {
    			for (int j = c - 2; j != -1; j--) {
    				if (m[i][j] == 1) {
    					right[i][j] = right[i][j + 1] + 1;
    					down[i][j] = down[i + 1][j] + 1;
    				}
    			}
    		}
    	}
    
    	public static int getMaxSize(int[][] m) {
    		int[][] right = new int[m.length][m[0].length];
    		int[][] down = new int[m.length][m[0].length];
    		setBorderMap(m, right, down); // O(N^2); + 
    		
    		for (int size = Math.min(m.length, m[0].length); size != 0; size--) {
    			if (hasSizeOfBorder(size, right, down)) {
    				return size*size;
    			}
    		}
    		return 0;
    	}
    
    	public static boolean hasSizeOfBorder(int size, int[][] right, int[][] down) {
    		for (int i = 0; i != right.length - size + 1; i++) {
    			for (int j = 0; j != right[0].length - size + 1; j++) {
    				if (right[i][j] >= size && down[i][j] >= size
    						&& right[i + size - 1][j] >= size
    						&& down[i][j + size - 1] >= size) {
    					return true;
    				}
    			}
    		}
    		return false;
    	}
        public static int largest1BorderedSquare(int[][] grid) {
    	     return getMaxSize(grid);
    	    }

散步的时候突然想起来 这个size从大往小遍历的意义 算是一个加速 如果从小到大 需要所有size遍历 从大到小只要遍历出第一次出结果即可

## 题目二 ##

生成一个长度为M的数组 假设a<b<c 满足任意一组abc满足arr\[a\]+arr\[c\] ! =2arr\[b\]

这题 说实话我觉得有点天外飞仙 机械降题的感觉

首先我们讲一下原理 有三不个相邻的数 1 5 3 是不是满足这个条件? 那么对应的 第1个奇数 第5个奇数 第3个奇数也满足? 数学证明一下 a + c != 2b 那么 2a-1 + 2c - 1 ?= 2(2\*b-1) 随便化简一下就知道仍满足条件

那么第1个偶数 第5个偶数 第三个偶数 也满足这个条件 比如 a + c != 2b 所以2a+2c!=4b

我们再把这三个奇数 三个偶数拼在一起呢 奇 奇 奇 偶 偶 偶 奇和奇之间满足 偶和偶之间满足 刚才已经证过了 那么奇和偶之间呢? 奇+偶为奇数 而2b肯定为 偶数 所以 一定满足条件

所以我们就清楚了 我们可以三个数三个数的这么拼 第1个奇数 第5个奇数 第3个奇数 为1,9,5那么之后呢 就是第一个奇数 第九个奇数 第五个奇数 以此类推 三个为1一组 我们可以拼出任意的数

那你可能会想 懂了 那三个三个的拼 就能把数组拼出来了 很好 我就是这么错的 因为只在一组奇数一组偶数的时候成立 如果一组奇数一组偶数再一组奇数就不绝对成立

所以我们的想法是 那就这样 加入你需要你个长度为 7 的数组 那我就给你生成8个 然后再截断

8个呢 也就是四个奇数 四个偶数 这样的一组 也就是我们需要一组 长度为4的arr\[a\]+arr\[c\] ! =2arr\[b\] 长度为4的arr\[a\]+arr\[c\] ! =2arr\[b\] 又需要2个的 生成 2个的就需要1个的生成 一个就是1本身

1生成第一个奇数 第一个偶数

1 2

生成第一个奇数 第二个奇数 第一个偶数 第二个偶数

1 3 2 4

生成第1,3,2,4个奇数 和 第1,3,2,4个偶数

.....

然后截断

public static int [] createArr(int N) {
    
    		if(N==1) {
    			return new int [] {1};
    		}
    		int half = (N+1)/2; //当N为奇数的时候 按偶数生成 当N为整数时 多的一个1也不影响结果 8+1/2 = 4;
    		int [] base = createArr(half); 
    		int [] res = new int [N];
    		for(int i = 0;i<half;i++) {
    			res[i] = base[i]*2-1;//如果N是奇数前一半肯定不影响 后一半也好办 直接生成到N
    		}
    		for(int i = half;i<N;i++) {
    			res[i] = base[i-half]*2;
    		}
    		return res;
    	}

## 题目三 ##

给定一个二叉树的头节点head,路径的规定有以下三种不同的规定:  
1)路径必须是头节点出发，到叶节点为止，返回最大路径和  
2)路径可以从任何节点出发，但必须往下走到达任何节点，返回最大路径和  
3)路径可以从任何节点出发，到任何节点，返回最大路径和

### 问题1 ###

这个简单

public static int Maxlength(Node head) {
    		if(head==null) {
    			return 0;
    		}
    		int left = Maxlength(head.left);
    		int right = Maxlength(head.right);
    		int max = Math.max(left, right);
    		return max+head.value;
    	}

### 问题2 ###

这里就要考虑负数的问题了 如果多走一个点 可能会使路径和变小

class Info{
    	int allTreeMaxSum = 0;
    	int fromHeadMaxSum = 0;
    	public Info(int no,int yes) {
    		allTreeMaxSum = no;
    		fromHeadMaxSum = yes;
    	}
    }
    
    public static Info Maxlength(Node head) {
    		if(head==null) {
    			return new Info(0, 0);
    		}
    		Info left = Maxlength(head.left);
    		Info right = Maxlength(head.right);
    		int p1 = left.allTreeMaxSum;
    		int p2 = right.allTreeMaxSum;
    		int p3 = head.value;
    		int p4 = left.fromHeadMaxSum + p3;
    		int p5 = right.fromHeadMaxSum + p3;
    		int allTreeMaxSum = Math.max(Math.max(Math.max(p1, p2),Math.max(p3, p4)),p5);
    		int fromHeadMaxSum = Math.max(Math.max(p4,p5),p3);
    		return new Info(allTreeMaxSum, fromHeadMaxSum);
    	}

讲一下代码奥 这里面的Info是指每一个节点给上层节点的数据

allTreeMaxSum是指目前这条路径上的最大值  
fromHeadMaxSum是指之前路径的和

为什么要这么分呢 因为如果之前有一个节点没要 那后面的节点就要不了 所以我们要想要这个点的话 我们就需要一个之前节点全要的数据(订正 不是全要 因为可能会出现只要前面几个节点的情况 这种情况是通过和p3比较实现的 比如 5 -1 我可以只要5就是最大的 那在下一个点也就形成 3 5 -1 那么当前的fromHeadMaxSum就是3 5 所以p3的情况不是只为了处理当前点最大的情况 而是处理只要靠近当前节点的部分节点的情况 因为是线性的 如果不要尾端的点可以让路径更大的话 那就可以永远舍弃它了)

而这个allTreeMaxSum 是指之前出现过的 所有可能性(这个点要 那个点不要的) 所以可能这个数都不需要当前节点的参与

它分五种情况

1.左树出现过的最大值

2.右树出现过的最大值

3.左树目前的长度(包含当前节点)

4.右树目前的长度(包含当前节点)

如果确实这条路径上的节点一直都是正数 那确实1和3 2和4 的值是一样的

**5.这种是最特殊的情况 假如一棵树上面 只有我一个正数 其他都是负数 所以我自己本身一个节点**

**(我就忽略了这种情况)**

那3 4结果不是包含在1 2里面了吗 我们为啥还要3 4呢 因为如果不保留这个数的话 那么想计算包含这个头结点的路径就找不到之前的路径和了

### 问题3 ###

这题我们要考虑 它会拐弯的情况 当然重复走过的节点不能再走

我们仍然分情况讨论

1.不包含头的

a.左树的当前最大路径

b.右树的当前最大路径

2.包含头的

a.本节点+左树全路径

b.本节点+右树全路径

c.本节点+左右树全路径(订正:不是全路径 是以当前节点为头的最大路径 通过p3的控制实现的)

d.本节点自己

(不包含头的没有限制(它子树的最大值无论是包不包含头都不影响 反正我们已经对包含头的做了限制) 包含头的才有)

p6 肯定是要

这次的fromHeadMaxSum 不能包含p6 因为拐过弯的

class Info{
    	int allTreeMaxSum = 0;
    	int fromHeadMaxSum = 0;
    	public Info(int no,int yes) {
    		allTreeMaxSum = no;
    		fromHeadMaxSum = yes;
    	}
    }
    
    class Solution {
    	public Info Maxlength(TreeNode root) {
    		if(root==null) {
    			return null;//在看到输入为[-3]的时候 突然明白为啥 这里要直接返回空了(刚开始返回的是new Info(0,0)) 对应要改的话 p1....的初始值都要改成MIN 如果没有就当做最小处理
    		}
    		Info leftInfo = Maxlength(root.left);
    		Info rightInfo = Maxlength(root.right);
    		int p1 = Integer.MIN_VALUE;
    		if (leftInfo != null) {
    			p1 = leftInfo.allTreeMaxSum;
    		}
    		int p2 = Integer.MIN_VALUE;
    		if (rightInfo != null) {
    			p2 = rightInfo.allTreeMaxSum;
    		}
    		int p3 = root.val;
    		int p4 = Integer.MIN_VALUE;
    		if (leftInfo != null) {
    			p4 = root.val + leftInfo.fromHeadMaxSum;
    		}
    		int p5 = Integer.MIN_VALUE;
    		if (rightInfo != null) {
    			p5 = root.val + rightInfo.fromHeadMaxSum;
    		}
    
    		int p6 = Integer.MIN_VALUE;
    		if (leftInfo != null && rightInfo != null) {
    			p6 = root.val + leftInfo.fromHeadMaxSum + rightInfo.fromHeadMaxSum;
    		}
    		int allTreeMaxSum = Math.max(Math.max(Math.max(p1, p2),Math.max(p3, p4)),Math.max(p5, p6));
    		int fromHeadMaxSum = Math.max(Math.max(p4,p5),p3);
    		return new Info(allTreeMaxSum, fromHeadMaxSum);
    	}
        public int maxPathSum(TreeNode root) {
           return Maxlength(root).allTreeMaxSum;
        }
    }

LeetCode原题这个是[力扣链接][Link 1]

[Link 1]: https://leetcode.cn/problems/jC7MId/solutions/