1.连续子数组和最大值
题目描述
输入一个整型数组，数组里有正数也有负数。数组中一个或连续多个整数组成一个子数组。求所有子数组的和的最大值，要求时间复杂度为O(n)。例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和。
public class Solution {
boolean flag = true;
public int FindGreatestSumOfSubArray(int[] array) {
int len = 0;
if (array == null || (len = array.length) == 0) {
flag = false;
return -1;
}
int result = array[0];
int max_result = result;
for (int i = 1; i < len; i++) {
if (result + array[i] < array[i]) {
result = array[i];
} else {
result += array[i];
}
if (result > max_result) {
max_result = result;
}
}
return max_result;
}
}
注意数组所有数都为负数的情况，也就是 result > max_result 时的赋值位置。
2.整数中1出现的次数（从1到n整数中1出现的次数）
题目描述
输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字有1,10,11和12,1一共出现了5次。
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
if (n < 0) return 0;
int count = 0;
while (n != 0) {
char[] ch = String.valueOf(n).toCharArray();
for (int i = 0; i < ch.length; i++) {
if (ch[i] == '1') {
count++;
}
}
n--;
}
return count;
}
}
注意char数组中查找每一项直接使用ch[i]，不用花里胡哨的charAt和indexOf
