codility新增了練習lesson 2。 有三個題: (1) Perm-Check 給定整數數組有N個數，問它是不是1-N的一個排列，也就是說是否每個數都是1-N,並且只出現一次。輸出1和0表示是與否，輸入范圍N [1..10^5],數組裡地整數[1..10^5]，要求復雜度時間空間都是O(N)。 分析：空間復雜度O(N)的算法很簡單，我們可以建立一個bool數組表示1-N，每個數是否出現過。代碼如下： [cpp] // you can also use includes, for example: // #include <algorithm> int solution(vector<int> &A) { // write your code here... vector<bool> have; int i,n = A.size(); have.resize(n, false); for (i = 0; i < n; ++i) { if ((--A[i] >= n) || (have[A[i]])) { return 0; } have[A[i]] = true; } return 1; } 事實上，我們有空間復雜度為O(1)的算法。利用練習(1)裡Perm-Missing-Elem的方法，把A[i]換到A[A[i] - 1]的位置上，代碼如下： [cpp] // you can also use includes, for example: // #include <algorithm> int solution(vector<int> &A) { // write your code here... int n = A.size(),i,x,t; for (i = 0; i < n; ++i) { for (x = A[i]; (x <= n) && (A[x - 1] != x); ) { t = A[x - 1]; A[x - 1] = x; x = t; } if (x > n) { return 0; } } for (i = 0; i < n; ++i) { if (A[i] != i + 1) { return 0; } } return 1; } 我們還可以把它做得更美觀一點，假設我們試圖讓A[0..i]分別是1..i + 1,對於當前的A[i] != i + 1，從A[0..i - 1]已經是1..i了，我們考慮如果A[i] < i + 1，那說明重復了，還有A[i] > n也不行，因為所有數只能1..n，另外就是看一下A[A[i] - 1]的位置上的數和A[i]是否重復，重復也不行，不重復就交換一下直到A[i]滿足要求為止，代碼如下： [cpp] // you can also use includes, for example: // #include <algorithm> int solution(vector<int> &A) { // write your code here... int n = A.size(),i,t; for (i = 0; i < n; ++i) { while (A[i] != i + 1) { if ((A[i] > n) || (A[i] < i + 1) || (A[A[i] - 1] == A[i])) { return 0; } t = A[i]; A[i] = A[A[i] - 1]; A[t - 1] = t; } } return 1; } 這裡面雖然有個while循環，但是事實上是O(n)的，因為每次交換至少把一個數換到了它應該在的位置。我們還可以不用這個while循環，思路一致，我們可以試圖修改循環變量i的值……代碼如下： [cpp] int solution(vector<int> &A) { // write your code here... int n = A.size(),i,t; for (i = 0; i < n;) { if (A[i] == i + 1) { ++i; } else { if ((A[i] > n) || (A[i] < i + 1) || (A[A[i] - 1] == A[i])) { return 0; } t = A[i]; A[i] = A[A[i] - 1]; A[t - 1] = t; } } return 1; } (2) Frog-River-One 背景很有意思，實質是問一個長度為N的整數數組是否包含了從1-X的全部整數。N和X都是[1..10^5]，並且數組中的數都是1..X。如果數組A[0..r]包含了1..X的全部數，返回r，否則返回-1。要求復雜度時間O(N),空間O(X)。 這個題其實和前一個題差不多，空間方面我們同樣可以建立一個長度為X的bool數組表示出現沒出現過。其實我們還是有空間為O(1)的做法。首先如果解存在我們至少要有X項，我們把數組的前X項，利用前面所講的交換，交換到應該放的位置，然後看一下從X..N - 1項那些值是否在0..X -1的位置需要，如果需要就要放過去，並且更新r，代碼有點小麻煩，但是思路不變： [cpp] // you can also use includes, for example: // #include <algorithm> int solution(int X, vector<int> &A) { // write your code here... int i, r,t,n = A.size(); if (X > n) { return -1; } for (i = 0; i < X;) { if ((A[i] > X) || (A[A[i] - 1] == A[i])) { ++i; } else { t = A[i]; A[i] = A[A[i] - 1]; A[t - 1] = t; /*if (t < i + 1) { ++i; }*/ } } r = X - 1; for (i = X; i < n; ++i) { if ((A[i] <= X) && (A[A[i] - 1] != A[i])) { A[A[i] - 1] = A[i]; r = i; } } for (i = 0; i < X; ++i) { if (A[i] != i + 1) { return -1; } } return r; } (3) Max-Counters 一個數組，長度為N，起初全部數都為0，有兩種操作，一個是對某個元素加1，另一個是把所有元素變為目前的最大值，給定若干次這樣的操作之後，求數組最終狀態。數組長度N和操作個數M都在[1..10^5]。要求復雜度時間O(N + M)，空間O(N)。 我們對於數組中得每個操作維護一個時間戳，根據時間戳決定數組元素的值是之前的最大值，還是當前的值，記錄每次第二種操作之前的最大值，代碼如下： [cpp] // you can also use includes, for example: // #include <algorithm> vector<int> solution(int N, vector<int> &A) { // write your code here... int i,m = A.size(), lastv = 0, lastt = -1, v = 0; vector<int> r, t; r.resize(N , 0); t.resize(N, -1); for (i = 0; i < m; ++i) { if (--A[i] < N) { v = max(r[A[i]] = ((t[A[i]] > lastt)?r[A[i]]:lastv) + 1, v); t[A[i]] = i; } else { lastv = v; lastt = i; } } for (i = 0; i < N; ++i) { if (lastt > t[i]) { r[i] = lastv; } } return r; } 其實時間戳可以省略，代碼如下： [cpp] // you can also use includes, for example: // #include <algorithm> vector<int> solution(int N, vector<int> &A) { // write your code here... int i,m = A.size(), lastv = 0, v = 0; vector<int> r; r.resize(N , 0); for (i = 0; i < m; ++i) { if (--A[i] < N) { v = max(v, r[A[i]] = max(r[A[i]], lastv) + 1); } else { lastv = v; } } for (i = 0; i < N; ++i) { r[i] = max(r[i], lastv); } return r; }
