功課：一組位的快速操作（表示爲一個字符數組）

Question

存在已經有點兒佔用我很多時間網站interviewstreet一定的實踐問題...

下面的代碼只跨越8/11個測試案例。剩下的時間超過了時間限制。我真的很感激，如果你能提出一些優化

的問題如下.....

there are two binary numbers of length n    
there are three kinds of operation  
set_a idx x : it sets A[idx] = x 
set_b idx x : sets B[idx] = x 
get_c idx : Print C[idx], where C=A+B, and 0<=idx 

Sample Input 
5 5 
00000 
11111 
set_a 0 1 
get_c 5 
get_c 1 
set_b 2 0 
get_c 5 

Sample Output 
100 

，所以我需要優化get_c操作

void reverse(char*a, int len) 
{ 
    //this function reverses the string 
} 

void get_c(int i) 
{ 
    k = i-1; 
    f = 0; 
    while (k>=0) 
    { 
      if (a[k] == '1' && b[k] == '1') 
      { 
       f = 1; 
       break; 
      } 
      else if (a[k] == '0' && b[k] == '0') 
       break; 
      --k; 
    } 
    if (f==0) 
     cout<<(a[i] == b[i]?0:1); 
    else if (f==1) 
      cout<<(a[i] == b[i]?1:0); 
} 

int main() 
{ 
    scanf("%d %d", &n, &q); // n = number of bits in number, q = number of operations 
    // enter the strings a and b 
    reverse(a, n); 
    reverse(b, n); 
    while (q--) 
    { 
      scanf("%s", query); 
      scanf("%d", &idx); 
      if (query is get_c) 
      { 
      get_c(idx); 
      } 
      else if (query is set_a) 
      { 
       cin>>x; 
       a[idx] = x; 
      } 
      else if (query is set_b) 
      { 
       cin>>x; 
       b[idx] = x; 
      } 
    } 
    return 0; 
} 

Answer 1

看來你已經使用數組實現了你的二進制數，因爲它只是簡單地將它們實現爲數字，並使用位掩碼和位移查詢/修改它們會更快。這將消除您需要在get_c中使用迭代方法;你的get_c函數將是恆定的時間而不是線性時間。