剑指Offer 31 连续子数组的最大和

题目描述

输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。

这道题应该做过一遍，所以思路比较清楚，第一种是说直接将数从头加到尾，每一位都变成之前所有数的和；然后你就会发现，有些数是负的啊，一看就知道不应该要他；所以想法就是如果是负数，就变成当前值；
（1，-2，3）–>（1，-1，2）；你-1加3肯定更小啊；所以是这样的
（1，-2，3）–>（1，-1，3）；前边是负值，你就重新计算的啦；
动态规划：
很明显的，如果前面是负的，就重新来，否则继续加；
more >>

2017-03-30

堆分为大根堆和小根堆，是完全二叉树。
完全二叉树我们知道，就是不太满的满二叉树；大根，小跟代表，父节点和子节点的关系；如果每一个父节点都不小于它的两个子节点，就可以认为是大根堆了；

从定义看，我们就知道了，对于大根堆来说，根节点一定是最大的，那我们就每次把根节点拿走，让大根堆重新排序，然后再取得最大值就可以了嘛；

那么重要的问题就来了，大根堆是怎么从一个普通的堆转换过来的的呢？
其实也很简单，就是说父节点如果比子节点小，就交换一下，如果交换之后，发现下面还有一层，就继续；

然后呢，由于是完全二叉树，就会有这么一个关系：
K[i]是K[2i]和K[2i+1]的父节点；也就是说父节点的位置，和子节点位置是固定的，所以就可以用数组来表示大根堆了；因为位置是确定的嘛；
代码上的话，一定要注意边界，还有就是数组起始位置的0；

2017-03-30

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

2017-03-29

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

快排，快排的思想就是分区，放置一个哨兵，左边比他小，右边比他大；
他自然就是中位数了，而出现超过一半的数，在排序的时候一定有一个会出现在中间；（2，3，2）–>（2，2，3）大概就这个意思；
快排的想法除了分区以外就是递归的想法；一个哨兵，找出一大一小两个区，那么接着往下分解，最后到无法再分解时，就有序了；
而我们并不需要有序，我们只想得到中位数，左边小，右边大；所以我们只需要找到这么一个哨兵恰好在中间，而且分好区；这样他肯定就是中位数了；
智力的思考
简单地说，这种方法正常人恐怕想不到；

如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。

在遍历数组时保存两个值：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。然后再判断它是否符合条件即可。

2017-03-29

今天真的是多事的一天,问题真的是很多；
首先是上传，运行代码，死活都return

       // 判断提交表单的类型是否为multipart/form-data
//        if (!upload.isMultipartContent(request)) {
//
//            return;
//        }

2017-03-28