30. 连续子数组的最大和
输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个字数组，求所有子数组的和的最大值，要求时间复杂度为O(n)。例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)
思路：利用动态规划思想。f(i)为当前长度为i的数组的和的最大值，则f(i) = max{f(i -1) + array(i), array(i)}；利用greatestSum存储连续子数组的最大和，那么在第i处，greatestSum是否更新，取决于当前f(i)是否大于greatestSum，即greatestSum = max(f(i), greatestSum)。
例，
如数组[6, -3, -2, 7, -15, 1, 2, 2]
初始状态， f(0) = 6，greatestSum = 6
| i | f(i) | greatestSum |
|---|---|---|
| 1 | max(6-3, -3) = 3 | max(6, 3) = 6 |
| 2 | max(3-2, -2) = 1 | max(6, 1) = 6 |
| 3 | max(1+7, 7) = 8 | max(6, 8) = 8 |
| 4 | max(7 - 15, -15) = -8 | max(8 ,-8) = 8 |
以此类推，最终greatestSum的值为8。
1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int sum = array[0];
int max = array[0];
for(int i = 1; i < array.length; i++){
sum = Math.max(array[i], sum + array[i]);
max = Math.max(max, sum);
}
return max;
}
}
31. 整数中1出现的次数（从1到n）
输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如12，从1到12这些整数中包含1的数字有1，10，11和12，因此1一共出现了5次。
思路： 这题需要分析数字本身含有1的规律。假定abcde是一个5位数，我们要数1～abcde中1出现的个数，可以由a==1的次数，加上b==1的次数，加上c==1的次数，加上d==1的次数，再加上e==1的次数所得。假定我们此时要求十位数上d==1出现的次数k，k实际上由d的高位数字abcd和低位数字e决定。
若d=0，d出现1的次数k，只由高位数字决定，即出现了abcd*10次；
若d=1，d出现1的次数k，由高位数字和地位数字同时决定，即出现了abcd + e + 1次；
若d>=2, d出现的次数k，只由高位数字决定，即(abcd + 1)*10。
如此，我们计算每一位出现1的次数，累加即可得到总次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int high = 0, current = 0, low = 0, i =1;
int count = 0;
while(n / i != 0){
high = n/(i*10);
current = (n - high*i*10)/i;
low = n - high*i*10 - current*i;
if(current == 0) count += high*i;
else if(current == 1) count += high*i + low + 1;
else if(current >=2) count += (high+1)*i;
i *= 10;
}
return count;
}
}
32. 把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
思路： 实际上是一个排列问题，最粗暴的方法是全排列之后找出最小。但是实际上，在排列的过程中，会发现，实际上数组在做排序。
假定数组中每个数都是1位整数，那么很简单，将数组从小到大排列即可；但是数组中的数字位数并不相同，例如当遇到3和32的时候，如何比较这两个数字的大小？
根据题目意思，我们可以定义这样的规则，当两个数字合并，有两种可能，即332和323，332>323，因此3>32。
即，两个数字a和b，
若ab > ba，则a > b；
若ab = ba，则a = b;
若ab < ba，则a < b。
在我们能够比较不同长度的数字之后，就可以把它们都看作是1位整数，整个数组升序排列之后，就能得到结果。
利用库函数重写，可以轻易实现规则的重定义。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Arrays;
import java.util.Comparator;
public class Solution {
public String PrintMinNumber(int [] numbers) {
int len = numbers.length;
if(len == 0) return "";
String[] strlist = new String[len];
for(int i = 0; i < len; i++) strlist[i] = String.valueOf(numbers[i]);
Arrays.sort(strlist, new Comparator<String>(){
@Override
public int compare(String s1, String s2){
String c1 = s1 + s2;
String c2 = s2 + s1;
return c1.compareTo(c2);
}
});
StringBuffer sb = new StringBuffer();
for(int i = 0; i < len; i++) sb.append(strlist[i]);
return sb.toString();
}
}