Amazon online test - 考試

※ 引述《sinread (電腦真耗錢)》之銘言：
: 小弟不才剛剛也去考試了, 回報一下試題:
: 1. 給一個int array, 再給一個S, 請利用array 內的東西組成S, 如果組不出來
: 回傳-1
: EX1: {1,3,5}, S= 11
: A: 3; --> 3 = 5+5+1
: EX2: {5, 5, 5, 5, 5, 5}, S=11
: A: -1;

Dynamic Programming O(N)

C#
static int mincoins(int[] a, int N, int S)
{
int i,j,k;

int[] num = new int[S+1];

num[0] = 0;

for(i=1;i<=S;i++)
{
num[i]=-1;
}

for (i = 0; i <= S; i++)
{
if (num[i] != -1)
{
for (j = 0; j < N; j++)
{
k = i+a[j];
if (k <= S)
{
if (num[k] == -1 || num[k] > num[i] + 1)
{
num[k] = num[i] + 1;
}
}
}
}
}

return num[S];
}




: 2. 取 int 的 1's 補數
: EX1: 50 -> 110010
: A: 13 -> 001101
: EX2: 100 -> 1100100
: 27 -> 0011011

Basic Logic O(logn)

C#
static int complement(int n)
{
int[] bits = new int[32];
int bit_length = 0;
int i;

if (n == 0)
{
return 1;
}
else
{
bit_length = 0;
while (n > 0)
{
if (n % 2 == 0)
{
bits[bit_length++] = 1;
}
else
{
bits[bit_length++] = 0;
}
n /= 2;
}
n = 0;
for (i = bit_length - 1; i >= 0; i--)
{
n = n + n + bits[i];
}
}
return n;
}
}

--