2014-03-21 21:37

题目：给定一个字符串数组，但是其中夹杂了很多空串“”，不如{“Hello”, “”, “World”, “”, “”, “”, “Zoo”, “”}请设计一个算法在其中查找字符串。

解法：要么一次性将其中夹杂的空串去掉，要么在二分查找的过程中逐个跳过空串。反正整体思路仍是二分。

代码：

1 // 11.5 Given an array of strings interspersed with empty string ""s. Find out if a target string exists in the string. 2 #include 
     
       3 #include 
      
        4 #include 
       
         5 using namespace std; 6  7 int main() 8 { 9     int i, j, n;10     int ns;11     string s;12     vector
        
          v;13     int ll, rr, mm;14     15     while (cin >> n && n > 0) {16         cin >> ns;17         for (i = 0; i < ns; ++i) {18             v.push_back("");19         }20         for (i = 0; i < n; ++i) {21             cin >> s;22             v.push_back(s);23             cin >> ns;24             for (j = 0; j < ns; ++j) {25                 v.push_back("");26             }27         }28         cin >> s;29         30         ll = 0;31         while (v[ll] == "") {32             ++ll;33         }34         rr = (int)v.size() - 1;35         while (v[rr] == "") {36             --rr;37         }38         while (ll <= rr) {39             mm = (ll + rr) / 2;40             while (v[mm] == "") {41                 // go left or right, either is OK.42                 --mm;43             }44             if (s > v[mm]) {45                 ll = mm + 1;46                 while (ll <= rr && v[ll] == "") {47                     ++ll;48                 }49             } else if (s < v[mm]) {50                 rr = mm - 1;51                 while (rr >= ll && v[rr] == "") {52                     --rr;53                 }54             } else {55                 break;56             }57         }58         printf("%d\n", (ll <= rr ? mm : -1));59         60         v.clear();61     }62     63     return 0;64 }