1.連續(xù)子數(shù)組和最大值
題目描述
輸入一個整型數(shù)組，數(shù)組里有正數(shù)也有負數(shù)朱沃。數(shù)組中一個或連續(xù)多個整數(shù)組成一個子數(shù)組。求所有子數(shù)組的和的最大值茅诱，要求時間復(fù)雜度為O(n)逗物。例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個開始,到第3個為止)。給一個數(shù)組瑟俭，返回它的最大連續(xù)子序列的和翎卓。
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;
}
}
注意數(shù)組所有數(shù)都為負數(shù)的情況，也就是 result > max_result 時的賦值位置摆寄。
2.整數(shù)中1出現(xiàn)的次數(shù)（從1到n整數(shù)中1出現(xiàn)的次數(shù)）
題目描述
輸入一個整數(shù)n失暴，求從1到n這n個整數(shù)的十進制表示中1出現(xiàn)的次數(shù)。例如輸入12微饥，從1到12這些整數(shù)中包含1的數(shù)字有1,10,11和12,1一共出現(xiàn)了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數(shù)組中查找每一項直接使用ch[i]，不用花里胡哨的charAt和indexOf
