Re: [請益] Amazon online test

看板Tech_Job作者bleed1979 (十三)時間12年前 (2013/03/25 10:43)推噓1(1推 0噓 4→)

留言5則, 2人參與討論串4/4 (看更多)

※ 引述《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; } } -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.43.112.210 ※ bleed1979:轉錄至看板 Soft_Job 03/25 10:46

→

lancert

03/25 13:06, , 1^F

03/25 13:06, 1^F

→

lancert

03/25 13:07, , 2^F

03/25 13:07, 2^F

→

lancert

03/25 13:08, , 3^F

03/25 13:08, 3^F