顺序表ADT模板设计及简单应用：找匹配

时间限制: 1S类别: DS：线性表->线性表应用

问题描述：

输入范例：

100000
100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99954 99953 99952 99951 99950 99949 99948 99947 99946 99945 99944 99943 99942 99941 99940 99939 99938 99937 99936 99935 99934 99933 99932 99931 99930 99929 99928 99927 99926 99925 99924 99923 99922 99921 99920 99919 99918 99917 99916 99915 99914 99913 99912 99911 99910 99909 99908 99907 99906 99905 99904 99903 99902 99901 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149

输出范例：

100000,99999,99998,99997,99996,99995,99994,99993,99992,99991,99990,99989,99988,99987,99986,99985,99984,99983,99982,99981,99980,99979,99978,99977,99976,99975,99974,99973,99972,99971,99970,99969,99968,99967,99966,99965,99964,99963,99962,99961,99960,99959,99958,99957,99956,99955,99954,99953,99952,99951,99950,99949,99948,99947,99946,99945,99944,99943,99942,99941,99940,99939,99938,99937,99936,99935,99934,99933,99932,99931,99930,99929,99928,99927,99926,99925,99924,99923,99922,99921,99920,99919,99918,99917,99916,99915,99914,99913,99912,99911,99910,99909,99908,99907,99906,99905,99904,99903,99902,99901,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149

51

从题目可以观察出来这里用的算法是：哈希表

我的代码如下：

 1 //序表ADT模板设计及简单应用：找匹配
 2 #include<iostream>
 3 #include<cstring>
 4 #include<sstream>
 5 #include<vector>
 6 #include<cstdlib>//atoi!
 7 using namespace std;
 8 template<class T>
 9 int getCount(vector<T>& A, int N)
10 {
11     int ans = 0;
12     //哈希表法
13     vector<int>hash(N);
14     hash.assign(N + 1, 0);//先预留N+1的空间
15     typename vector<T>::iterator it = A.begin();//制造遍历迭代器
16     while (it != A.end())
17     {
18         hash.at(*it) = 1;//标记为1
19         it++;
20     }
21     it = A.begin();
22     while (it != A.end())
23     {
24         int temp = (int)*it;//要强制转换 
25         hash.at(temp) = 0;//防止出现50+50=100的情况！
26         if (hash.at(N + 1 - temp) == 1)
27         {
28             ans+=1;
29             
30         }
31         it++;
32     }
33     
34     return ans;
35 }
36 int main()
37 {
38     vector<string>a;
39     vector<int>b;
40     int n;
41     cin >> n;
42     cin.get();//吸收一下回车
43 
44     //从字符串中提取数 插入到vector b中
45     string str;
46     getline(cin, str);
47     stringstream room;
48     room.str(str);
49     string temp;
50     while (room >> temp)
51     {
52         a.push_back(temp);
53     }
54     for (int i = 0; i < a.size(); ++i)
55     {
56         int ttemp;
57         ttemp = atoi(a[i].c_str());
58         b.push_back(ttemp);
59     }
60 
61     //遍历输出
62     for (int i = 0; i < b.size() - 1; ++i)
63     {
64         cout << b[i] << ",";
65     }
66     cout << b[b.size() - 1];
67     cout << endl<<endl;
68     int ans = getCount(b, n);
69     cout << ans;
70     return 0;
71 }