LiMingjie0719
BAN USERO(n)
void replaceNextLargest(int *arr, size_t size)
{
int max = arr[size - 1];
for (int i = size - 2; i >= 0; --i)
{
if (arr[i] > max)
{
max = arr[i];
}
else
{
arr[i] = max;
}
}
}
The empty space in a is equal to the number of element in b, so we can merge from last element without extra space.
void mergeSortAB(int *a, int *b)
{
int ia = 3;
int ib = 2;
int last = 6;
while (ib >= 0)
{
if (ia >= 0 && a[ia] > b[ib])
{
a[last--] = a[ia--];
}
else
{
a[last--] = b[ib--];
}
}
}
// Given a number in an array form, Come up with an algorithm to push all the zeros to the end.
// Expectation: O(n) solution
#include <iostream>
void print(int *arr, size_t size)
{
using namespace std;
for (size_t i = 0; i < size; ++i)
cout << arr[i] << ' ';
cout << endl;
}
void pushZeroToEnd(int *arr, size_t size)
{
int *start = arr;
int *end = arr + size - 1;
while (start < end)
{
// Find first zero
while (*start != 0) ++start;
// Find last not zero
while (*end == 0) --end;
// Swap
*start++ = *end;
*end-- = 0;
}
}
int main()
{
int arr[] = { 1, 3, 0, 0, 0, 2, 0, 5, 4, 0, 3, 9, 0, 8, 0, 0 };
size_t size = sizeof(arr) / sizeof(int);
print(arr, size);
pushZeroToEnd(arr, size);
print(arr, size);
std::cin.get();
return 0;
}
x, y, z, n >= 0
- LiMingjie0719 March 05, 201420x + 9y + 6z = n
> 21x + 9y + 6z = n + x
> 7x + 3y + 2z = (n + x) / 3
because 3y + 2z >= 0 and <>1
So calculate x = 0, x = 1, x = 2
>
if (n+2) % 3 = 0, n >=40, n <> 43. return true
if (n+1) % 3 = 0, n >=20, n <> 23. return true
if n % 3 = 0, n <> 3. return true
other return false