连续子数组的最大和
思路：
当前和为cuurrentsum，当前要加的数为num。若cuurrentsum是一个负数，那么不论num是正数还是负数。num+current总小于num。所以要舍弃currentsum。从num开始往后计算。
代码：
int Maxarrsuminarr(int arr[], int len, bool *Invalid )
{
if (arr == NULL || len <= 0)
{
*Invalid = true;
return 0;
}
int currentsum = 0;
int maxsum = 0x80000000; //32位的最小数
//cout << maxsum;
for (int i = 0; i < len; i++)
{
if (currentsum <= 0)
currentsum = arr[i];
else
{
currentsum += arr[i];
}
if (currentsum > maxsum)
maxsum = currentsum;
}
return maxsum;
}
从1到n中1出现的次数
思路：
1.每个数进行判断。 %10/ 时间复杂度O(n*logn)
2.找到k位数中1的个数与两个找到k-1位数中1的个数有关。
如12 F(12)=F(10-1)+F（12-10)+3(10,11,12).
代码：
int Tonumof1(int num)
{
int cnt = 0;
if (num == 0)
return 0;
if (num < 10 && num>0)
return 1;
int highest = num; //最高位的数
int bit = 0; //位数
while (highest >= 10)
{
highest /= 10;
bit++;
}
if (highest == 1)
{
cnt = Tonumof1(10*bit-1)+ Tonumof1(num - 10 * bit) + num - bit * 10 + 1;
}
else
{
cnt = highest * Tonumof1(10 * bit - 1) + Tonumof1(num - 10 * bit) + 10 * bit;
}
return cnt;
}
找第n个丑数
描述：
只能质因子只有2，3，5的数。如4，8。 14不是，有质因子7。
思路：
1.逐个判断
2.逐个判断做了太多比较。可以只找丑数，并排序。每次对数2，3，5，选出最小的并且大于当前数组最大值max的数放在数组最后。存在t2，t2前的数2都小于max，t2后的数*2都大于max。t3，t5也是如此。
代码：
bool IsUgly(int num) //一个数是丑数，则它被2，3，5除后余数为1
{
while (num % 2 == 0)
{
num /= 2;
}
while (num % 3 == 0)
{
num /= 3;
}
while (num % 5 == 0)
{
num /= 5;
}
return (num == 1) ? true : false;
}
int Min(int a, int b, int c)
{
int min = a < b ? a : b;
min = min < c ? min : c;
return min;
}
int GetuglyNumber_N(int N)
{
if (N <= 0)
{
return 0;
}
int *numbers = new int[N]; //保存排序的丑数
numbers[0] = 1;
int index = 1;//将要放入丑数的下标
int index2= 0;
int index3 = 0;
int index5 = 0;
while (index < N)
{
int min = Min(numbers[index2]*2, numbers[index3]*3, numbers[index5]*5); //竞争丑数
numbers[index] = min; // 也是当前数组中的最大值
while (numbers[index2] * 2 <= numbers[index]) //找到刚好大于最大值的丑数下标，用于下一轮的竞争
index2++;
while (numbers[index3] * 3 <= numbers[index])
index3++;
while (numbers[index5]* 5 <= numbers[index])
index5++;
index++;
}
int ugly = numbers[index - 1];
delete[] numbers;
return ugly;
}