Amazon online test - 考試

※ 引述《lancert (本來沒有我)》之銘言：
: ※ 引述《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];
: }

第一題是對的，複雜度要把S也算進去，但可以更簡潔。提供以下代碼：

static int min_coins(int[] a, int N, int S)
{
int i, j;

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

num[0] = 0;

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

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

return num[S] == S + 1 ? -1 : 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;
: }
: }

第二題是錯的，你忘了考慮負數，這也是唯一的陷阱。

可以分成 n < 0, n > 0和 n = 0來做。提供以下代碼：

static int complement1(int n)
{
int ret = 0;
int i;
if (n < 0)
{
for (i = 0; i < 32; ++i)
{
ret |= (1 - ((n >> i) & 1)) << i;
}
}
else if (n > 0)
{
for (i = 0; n > 0; ++i, n >>= 1)
{
ret |= (1 - (n & 1)) << i;
}
}
else
{
ret = 1;
}
return ret;
}
}


--