牛客算法-第三章

1.给定一个无序矩阵，其中有正，有负，有 0，求子矩阵的最大和。

上面求解的是一个无序矩阵的子矩阵。初次看到可能会感觉无从下手。首先，再次应该强调学习的过程中遇到新知识要有把新问题拆解成一个或多个熟悉的问题进行求解。

矩阵其实就是多行数组的组成。所以我们可以进行拆解。
举例：
二阶矩阵
1 2 3 4
4 3 2 1
--------

将上下两行相加：

5 5 5 5 
在这个过程中，我们也就实现了，将2行n列的矩阵变形为了一行的数组模式。

这里有需要提到之前第二章总结的算法原型：求解最大子数组和。

这样就可以求出对应的最大子矩阵和，二者是一一对应的。

因为我们在将两行数据相加的过程中，就已经将二者捆绑在了一起。

在一般的情况下，求解该问题需要用到O(N^6),问题经过这样的算法之后，可以优化到O（N^3）。

我们这里提到如何求解一个子矩阵的最大和：

比如一个3行n列矩阵。
1行组成的数组，求解最大子数组和，max更新；
1，2行相加组成的数组，求解最大子数组和，max更新；
1,2,3行相加组成的数组，求解最大子数组和，max更新；
2行组成的数组，求解最大子数组和，max更新；
2,3行相加组成的数组，求解最大子数组和，max更新；
3行组成的数组，求解最大子数组和，max更新。

以上过程，实际上就是遍历所有可能的“数组构造方式”，也就是求解一个组合，如果有n行，组合一共有n*（n-1）*…*1;

2.给定一个无序矩阵，其中有正，有负，有 0，再给定一个值 k，求累加和小于等于 k 的最
大子矩阵大小，矩阵的大小用其中的元素个数来表示

总结，分解部分还是和上面的第一题一样，将矩阵问题分解为数组问题的集合。

只不过这里是换了另外一种算法原型。还是针对数组的：

举例：
0 1 2 3 4 5
假设 0_{i的累加和为sumn[i];0}j的累加和为sum[j]。
也就是说，可以将sum[j]分解为sum[i]+{i+1…j},
所以，如果存在sum[i]+k>=sum[j];
也就是k>={i+1…j};

此时，我们已经实现了转化问题。当以j结尾的求小于等于k的最长的子数组时，其实就是也就是求左边第一个sum[i]>=sum[j]
-k的情况。

比如以j结尾的时候sum[j]=10,我们设定k=4，其实我们求解这个问题的时候，只需要找到从0出发第一个>=sum[j]-k=10-4=6时候的sum[i],就求解出来了。i~j就是我们求解的答案。

而在本题中为了加快速度，我们设置的累积数组其实是只增不减的。
举例如下：

原始数组       3 -1 2 -1 4 -1 4
累加数组       3  2 4  3 7  5 9
改进累加数组    3 3 4 4 7 7 9

通过改进的累积和数组，我们可以通过二分，快速地求出第一个出现大于等于某个数的地方。

3.给定一个无序矩阵，其中只有 1 和 0 两种值，求只含有 1 的最大的子矩阵大小，矩阵的大
小用其中的元素个数来表示。

总结，首先谈大体的解法：

矩阵：
1…
2…
3…
4…
5…

解决的过程就是求解以第一排为底的情况，求解以第二排为底的情况。。。求解以第n排为底的情况。

**关键点，把相加的一排的数组的数据想象成一个直方图。**这时，就是求解最大面积的矩形。

所以，现在的关键的算法原型变成：如何在一个直方图中求解最大的矩形面积。

那么，这个算法原型是怎样实现的呢？

以直方图中某一坐标点i为例，从i向左遍历，直到找到第一个小于arr[i]的位置l；从i向右遍历，同样的，直到找到第一个小于arr[i]的位置r，这时候，以i为根的矩形不能实现“拓展”了。所以矩形的范围就是长度为{l+1,r-1}的范围，高度是arr[i];

但是，这里在实际处理的时候，我们用到了数据结构栈。

arr从左到右判断，如果当前数大于栈顶元素top或者stack.empty()的话，将arr[i]压入栈中；
否则，如果当前数小于等于top元素的时候，就把栈顶元素弹出。

而在上面的过程中，导致top元素弹出的元素，就是top元素右边第一个小于等于top的元素就是top元素形成最大矩形的右边界，而top-1元素就是top元素形成最大矩形的的左边界。

这里还有一个注意点就是如果pop 栈顶元素top元素的时候，他是栈里唯一的一个元素，也就是不存在top-1元素了，此时他的最大矩形的左边界就是-1.

但是上面为什么等于top元素的时候也是弹出呢？因为这个过程中同样top值元素得到的矩形范围不正确，但是因为相同值，总是连通的。我们求解到最后的一个==top元素值的i坐标时，是可以求出这个连通的矩形的最大面积的正确值的。

为什么呢？因为我们的问题是求解最大的矩形，不是为了求解每一个矩形，我们在这样的遍历过程中不会漏掉每一个可能的最大矩形。只不过是，在求解一个大范围的连同矩形时，中间过程中求解的矩形是错误的但是最后的一个同样值一定会算出这个连通矩形的正确面积。

4.给定一棵完全二叉树的头节点 head，求其中的节点个数。

完全二叉树，就是如果可以遍历到第i层，那么0_{i-1层一定都是满的，也就是0}i-1层就是个满二叉树，可以直接公式计算了。

首先，遍历，最左边的二叉树，得到的depth就是max_depth。

然后，遍历。根结点的最右边的二叉树的最左子树，得到depth2.

如果depth2==depth,也就是说根结点的左子树是个满二叉树。接下来就是递归求解根结点的右子树。

还有另外的一种情况，也就是depth2!-=depth,也就是说根结点的右子树是个满二叉树。接下来就是递归求解根结点的左子树。

总结上面的想法，就是找完全二叉树总是可以分成两部分，一部分如果是满二叉树，可以根据depth直接公式求解；另一部分如果不是满二叉树，就直接递归求解。而在这个过程中是如何区分那部分是否使满二叉树的呢？就是靠遍历得到depth，所以复杂度是O（(logN)^2）。

5.给定一个字符串类型的数组，其中不含有重复的字符串，如果其中某一个字符串是另一个
字符串的前缀，返回 true；如果没有任何一个字符串是另一个字符串的前缀，返回 false。

总结，这一道题，涉及到前缀树，边上权值是字母。寻找单词的过程就是遍历前缀树的过程。

建树的过程中进行判断。
两种情况符合前缀的情况：
第一种，我总在别人的路上走，我的单词结束了，还在树上；
第二种，我总在别人的路上走，走完别人的路了，我的单词还有剩余。
第一种情况说明我是之前的单词的前缀。
第二种情况说明之前的某个或某些单词是我的前缀。

而针对把字符挂在边上，所以用hashmap来实现。key当前一个有向边，value是对应的值。