updated

DallasAutumn · Mar 22, 2020 · 101c5bd · 101c5bd
1 parent 91dffad
commit 101c5bd
Show file tree

Hide file tree

Showing 6 changed files with 334 additions and 0 deletions.
diff --git a/A1041.md b/A1041.md
@@ -0,0 +1,44 @@
+# A1041 Be Unique
+
+## 1.题意理解
+给出一串数，要求找到只出现一次的那个。
+
+## 2.思路分析
+直接遍历，统计出现次数即可
+
+## 3.参考代码
+```cpp
+#include <bits/stdc++.h>
+using namespace std;
+
+const int N = 100100;
+int n;
+unordered_map<int, int> mp;
+vector<int> v;
+
+int main()
+{
+    int x;
+    scanf("%d", &n);
+
+    for (int i = 0; i < n; i++)
+    {
+        scanf("%d", &x);
+        mp[x]++;
+        v.push_back(x);
+    }
+    int ans = 0;
+    for (int it : v)
+        if (mp[it] == 1)
+        {
+            ans = it;
+            break;
+        }
+    if (ans)
+        printf("%d\n", ans);
+    else
+        printf("None\n");
+    system("pause");
+    return 0;
+}
+```
diff --git a/A1048.md b/A1048.md
@@ -0,0 +1,49 @@
+# A1048 Find Coins
+
+## 1.题意理解
+直接翻译成人话：给出一串数，要求找到这样的V1，V2，使得```V1 + V2 == M```，并且```V1 <= V2```，如果有多个解，输出V1最小的
+
+## 2.思路分析
+本题可以使用散列实现，但我采取了two pointers的策略，供参考。即先对序列进行排序，然后从两边往中间寻解。
+
+## 3.参考代码
+```cpp
+#include <bits/stdc++.h>
+using namespace std;
+
+const int N = 100100;
+const int M = 1024;
+int n, m;
+int a[N] = {0};
+
+int main()
+{
+    bool flag = false;
+    scanf("%d%d", &n, &m);
+    for (int i = 0; i < n; i++)
+        scanf("%d", &a[i]);
+
+    sort(a, a + n);
+    int pos = lower_bound(a, a + n, m) - a;
+    int i = 0, j = pos - 1;
+    while (i < j)
+    {
+        if (a[i] + a[j] == m)
+        {
+            flag = true;
+            break;
+        }
+        else if (a[i] + a[j] < m)
+            i++;
+        else
+            j--;
+    }
+
+    if (flag)
+        printf("%d %d\n", a[i], a[j]);
+    else
+        printf("No Solution\n");
+    system("pause");
+    return 0;
+}
+```
diff --git a/A1050.md b/A1050.md
@@ -0,0 +1,35 @@
+# A1050 String Subtractino
+
+## 1.题意理解
+题目定义了一个字符串相减操作：$S=S_1-S_2$，意思是从S1中剔除S2的所有字符。题目乍看很简单，但是时间复杂度要求较高。
+
+## 2.思路分析
+题目提示了```However, it might not be that simple to do it fast.```，傻瓜式的对于S1中每一个字符都在S2中查找是肯定TLE的，想到使用哈希方法。
+
+## 3.参考代码
+```cpp
+#include <bits/stdc++.h>
+using namespace std;
+
+const int N = 10010;
+char str[N], sig[N];
+unordered_map<char, int> mp;
+
+int main()
+{
+    char c;
+    fgets(str, N, stdin);
+    // getchar();
+    while (c != '\n')
+    {
+        scanf("%c", &c);
+        mp[c] = 1;
+    }
+    for (int i = 0; str[i]; i++)
+        if (!mp[str[i]])
+            printf("%c", str[i]);
+    system("pause");
+    return 0;
+}
+```
+这应该是最简洁的代码，使用```unordered_map```可以方便地实现哈希。注意```gets()```方法已经废除，要读整行，以fgets作为替代就好。
diff --git a/A1078.md b/A1078.md
@@ -0,0 +1,61 @@
+# A1078 Hashing
+
+## 1.题意理解
+很直接的考察hash平方探测基础，按照题目要求插入和输出即可。
+
+## 2.思路分析
+没啥思路，看图写字
+
+## 3.参考代码
+```cpp
+#include <bits/stdc++.h>
+using namespace std;
+
+const int N = 10010;
+int MSize, n;
+int hashTable[N] = {0};
+
+bool isPrime(int num)
+{
+    if (num <= 1)
+        return false;
+    for (int i = 2; i * i <= num; i++)
+        if (num % i == 0)
+            return false;
+    return true;
+}
+
+int main()
+{
+    int x, pos;
+    scanf("%d%d", &MSize, &n);
+    while (!isPrime(MSize))
+        MSize++;
+    for (int i = 0; i < n; i++)
+    {
+        bool flag = false;
+        scanf("%d", &x);
+        for (int k = 0; k < MSize; k++)
+        {
+            pos = (x + k * k) % MSize;
+            if (!hashTable[pos])
+            {
+                hashTable[pos] = x;
+                flag = true;
+                break;
+            }
+        }
+        if (flag)
+            printf("%d", pos);
+        else
+            printf("-");
+        if (i == n - 1)
+            printf("\n");
+        else
+            printf(" ");
+    }
+    system("pause");
+    return 0;
+}
+```
+注意：实现判断素数的函数时一定要注意```n <= 1```情况，题目第二个测试点就在卡这个。
diff --git a/A1084.md b/A1084.md
@@ -0,0 +1,62 @@
+# A1084 Broken Keyboard
+
+## 1.题意理解
+键盘侠战斗多了，可能会把键盘上某些键用坏。
+
+给出两个字符串，第一个是正确的，第二个是错误的。要求通过错误字符串，确定键盘上缺了哪些按键。
+
+要求按照发现顺序输出，每个坏键只能输出一次，字母按大写输出。
+
+## 2.思路分析
+遍历正确字符串，逐个与错误字符串进行比对，若对上了则比较下一个，没对上则说明发现坏键。
+
+## 3.参考代码
+```cpp
+#include <bits/stdc++.h>
+using namespace std;
+
+const int MAXL = 100;
+unordered_map<char, int> mp;
+
+int main()
+{
+    string s1, s2;
+    cin >> s1 >> s2;
+    int j = 0;
+    for (int i = 0; i < s1.size(); i++)
+        if (s1[i] == s2[j])
+            j++;
+        else
+        {
+            char c = s1[i];
+            if (!mp[c])
+            {
+                if (isalpha(c))
+                {
+                    if (c >= 'a' && c <= 'z')
+                    {
+                        mp[c - 32] = mp[c] = 1;
+                        printf("%c", c - 32);
+                    }
+                    else
+                    {
+                        mp[c + 32] = mp[c] = 1;
+                        printf("%c", c);
+                    }
+                }
+                else
+                {
+                    mp[c] = 1;
+                    printf("%c", c);
+                }
+            }
+        }
+    system("pause");
+    return 0;
+}
+```
+本题代码的条件判断比较复杂，一定要严格按照题目要求输出。
+
+使用了unordered_map容器实现hash。
+
+同时还要牢记：```小写字母 = 大写字母 + 32```，当发现缺失字母键时，小写大写都打不了了，要同时标记上。
diff --git a/A1145.md b/A1145.md
@@ -0,0 +1,83 @@
+# A1145 Hashing - Average Search Time
+
+## 1.题意理解
+本题考查的是基本的散列操作。给出n个数的插入序列，m个数的查找序列，用正向的平方探测法处理冲突。
+
+## 2.思路分析
+根据题意，首先要把用户指定的TSize向上转化为比它大的最小素数，然后再进行插入和查找
+
+## 3.参考代码
+```cpp
+#include <bits/stdc++.h>
+using namespace std;
+
+const int MAX = 10010;
+int MSize, n, m;
+int hashTable[MAX] = {0};
+
+bool isPrime(int n)
+{
+    if (n <= 1)
+        return false;
+    for (int i = 2; i * i <= n; i++)
+        if (n % i == 0)
+            return false;
+    return true;
+}
+
+int change(int n)
+{
+    while (!isPrime(n))
+        n++;
+    return n;
+}
+
+int hashFunc(int key)
+{
+    return key % MSize;
+}
+
+int main()
+{
+    int x, value;
+    scanf("%d%d%d", &MSize, &n, &m);
+    MSize = change(MSize);
+    for (int i = 0; i < n; i++)
+    {
+        scanf("%d", &x);
+        value = hashFunc(x);
+        bool flag = false;
+        for (int k = 0; k < MSize; k++)
+        {
+            int addr = (value + k * k) % MSize;
+            if (!hashTable[addr])
+            {
+                hashTable[addr] = x;
+                flag = true;
+                break;
+            }
+        }
+        if (!flag)
+            printf("%d cannot be inserted.\n", x);
+    }
+
+    int ans = 0;
+    for (int i = 0; i < m; i++)
+    {
+        scanf("%d", &x);
+        int value = hashFunc(x);
+        for (int k = 0; k <= MSize; k++)
+        {
+            ans++;
+            int addr = (value + k * k) % MSize;
+            if (hashTable[addr] == x || !hashTable[addr])
+                break;
+        }
+    }
+    printf("%.1lf\n", 1.0 * ans / m);
+
+    system("pause");
+    return 0;
+}
+```
+注意：本题在插入时，```k < MSize```，但是在查找时```k <= MSize```，这是因为在使用平方探测法时，只要k在$[0, TSize)$内找不到，以后也找不到。但是在查找过程中，如果```k == TSize - 1```时发生冲突，仍要再进行一次比较，最后一次比较发现```k == TSize```时无元素，才能确认查找失败。