连续子数组的最大和
解题思路
第一次看到这个题的时候,最直观的思路应该是想办法枚举所有子数组并求其和,但是一个长度为n
的数组,枚举的子数组共有n(n+1)/2
个,因此最快也需要O(n^2)
时间。在算法题目中,凡是面对这种复杂度的解法,往往是不考虑这种解法的。
以下解法均以数组aray = {1,-2,3,10,-4,7,2,-5}
为例,该数组的最大和数组为{3,10,-4,7,2}
,最大和为18
。
解法一:分析数组的规律
可以先试着从头到尾累加数组中的每个数字。初始化和为0,第一次加上1,此时和为1。第二步加上-2,和变成了-1,如果再加上第三个数字3,我们注意到此前累加的和是-1,加上3后和为2,累加和的结果比3本身还要小。也就是说,从第一个数字开始的子数组的和比从第三个数字开始的子数组的和要小。因此,我们完全没有必要考虑从第一个数字开始的子数组,并且之前累加的和也可以抛弃。
然后我们从第三个数字开始累加,此时的和为3,第四步加10后和为13。第五步加上-4后和为9,这时我们发现由于-4是一个负数,那么累加之后的结果比原来的和还要小,因此我们需要把之前得到的累加和13保存下来,因为它有可能是最大子数组的和。然后第六步加上数字7得到和为16比保存的13要大,因此把最大子数组的和从13更新为16,然后再加2得到和为18,那么继续更新最大子数组的和为18。依此类推,最终结果为18。
那么我们用表总结一下上述过程:
步骤 | 操作 | 累加的子数组和 | 最大的子数组和 |
---|---|---|---|
1 | 加1 | 1 | 1 |
2 | 加-2 | -1 | 1 |
3 | 抛弃前面的和-1,加3 | 3 | 3 |
4 | 加10 | 13 | 13 |
5 | 加-4 | 9 | 13 |
6 | 加7 | 16 | 16 |
7 | 加2 | 18 | 18 |
8 | 加-5 | 13 | 18 |
代码实现
1 | public int FindGreatestSumOfSubArray(int[] array) { |
解法二:动态规划
这个题显然还可以使用DP来做,但是DP的状态转移方程比较难想到。
f(i)
:以array[i]
为末尾元素的子数组的和的最大值,子数组的元素的相对位置不变 。
那么可以列出转移方程:f(i) = max( f(i-1)+array[i] ,array[i] )
res
:所有子数组的和的最大值 ,那么res=max(res, f(i))
。
比如对于aray = {1,-2,3,10,-4,7,2,-5}
:
- 初始状态:
f(0)=1
,res=1
。 - 当
i=1
时,f(1)=max(f(0)-2,-2)=-1
,那么res=max(1,-2)=1
。 - 当
i=2
时,f(2)=max(f(1)+3,3)=3
,那么res=max(1,3)=3
。 - 当
i=3
时,f(3)=max(f(2)+10,10)=13
,那么res=max(3,13)=13
。 - 当
i=4
时,f(4)=max(f(3)-4,-4)=9
,那么res=max(13,9)=13
。 - 当
i=5
时,f(5)=max(f(4)+7,7)=16
,那么res=max(16,13)=16
。 - 当
i=6
时,f(6)=max(f(5)+2,2)=18
,那么res=max(18,16)=18
。 - 当
i=7
时,f(7)=max(f(6)-5,-5)=13
,那么res=max(13,18)=18
。
因此最终结果为18。
代码实现
1 | public int FindGreatestSumOfSubArray1(int[] array) { |
上述两种思路的时间复杂度均为O(n)
。
最小的k个数
解题思路
这个题最直观的思路,也是能够直接解决问题的解法就是直接对数组进行排序,然后取最小的前k个数就可以了。这种思路的平均时间复杂度为O(nlong),并且不适合用于海量数据,面试的时候会提示有更快的解法。
还有一种思路就是用最大堆保存这k个数,每次只和堆顶比,如果比堆顶小,删除堆顶,然后新数入堆。这种思路下时间复杂度为O(nlogk),并且可以处理海量数据。
代码实现
解法一:对数组进行排序实现
1 | public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { |
解法二:基于最大堆实现
1 | public ArrayList<Integer> GetLeastNumbers_Solution1(int[] input, int k) { |
数组中出现次数超过一半的数字
解题思路
刚看到这个题的时候,最直观的思路应该还是使用排序,这样时间复杂度为O(nlogn),但是还是那句话,最直观的思路往往不是面试官满意的算法。
首先在思路上可以想到,能够使用HashMap
,由于HashMap
不能存储相同的键,那么把数组中的数字作为键,如果相同,则其值加1,这样最后直接判断HashMap
中的键对应的值是否超过了数组的一半即可,并且这种解法时间复杂度为O(n)。
除去HashMap
之外,针对数组本身,我们还可以想到一种O(n)的解法,那就是只遍历一次数组,在这次遍历中找到其中重复次数最多的数字,然后跟数组长度的一半进行比较。这种解法的时间复杂度也为O(n)。
代码实现
解法一:对数组进行排序
1 | public int MoreThanHalfNum_Solution(int [] array) { |
解法二:使用HashMap
1 | public int MoreThanHalfNum_Solution(int[] array) { |
解法三: 基于数组本身的特点
1 | public int MoreThanHalfNum_Solution(int [] array) { |
整数中1出现的次数
解题思路
设N = abcde
,其中abcde分别为十进制中各位上的数字。 如果要计算百位上1出现的次数,它要受到3方面的影响:百位上的数字、百位以下(低位)的数字、百位以上(高位)的数字。
- 如果百位上数字为0,百位上可能出现1的次数由更高位决定。比如:12013,则可以知道百位出现1的情况可能是:100~199,1100~1199,2100~2199,,…,11100~11199,一共1200个。可以看出是由更高位数字(12)决定,并且等于更高位数字(12)乘以 当前位数(100)。
- 如果百位上数字为1,百位上可能出现1的次数不仅受更高位影响还受低位影响。比如:12113,则可以知道百位受高位影响出现的情况是:100~199,1100~1199,2100~2199,,….,11100~11199,一共1200个。和上面情况一样,并且等于更高位数字(12)乘以 当前位数(100)。但同时它还受低位影响,百位出现1的情况是:12100~12113,一共114个,等于低位数字(113)+1。
- 如果百位上数字大于1(2~9),则百位上出现1的情况仅由更高位决定,比如12213,则百位出现1的情况是:100~199,1100~1199,2100~2199,…,11100~11199,12100~12199,一共有1300个,并且等于更高位数字+1(12+1)乘以当前位数(100)。
代码实现
1 | public int NumberOf1Between1AndN_Solution(int n) { |
把数组排成最小的数
解题思路
这个题目拿到手会有一个直接思路,那就是直接获取所有可能的结果,然后排序获取其中最小的数就可以了,这种暴力解法肯定是零分解法,所以直接pass掉这种思路。
其实再仔细想一想,问题实际上并不复杂,要找到这个数组排序的最小值,我们只需要对这个数组进行遍历的时候,找到相邻值进行相加,然后以升序重新排列这个数组即可,最后再按照排序后的结果依次相加即可得到最终的结果。
代码实现
1 | public String PrintMinNumber(int [] numbers) { |