还有两个半小时就要去捐款了。。。

DallasAutumn · Dec 5, 2020 · 4a6e6aa · 4a6e6aa
1 parent 6220281
commit 4a6e6aa
Show file tree

Hide file tree

Showing 8 changed files with 259 additions and 20 deletions.
diff --git a/A1038.md b/A1038.md
@@ -0,0 +1,44 @@
+# A1038 Recover the Smallest Number
+
+## 1.题意理解
+把给定的序列拼接到一起，拼成一个最小的数
+
+## 2.思路分析
+用字符串拼接，要求拼接结果最小（按字符串和按整数规则是等效的），按照这个思想来排序。
+
+## 3.参考代码
+```cpp
+#include <bits/stdc++.h>
+using namespace std;
+
+bool cmp(string a, string b)
+{
+    return a + b < b + a; // 很巧妙的比较函数
+}
+
+int main()
+{
+    int n;
+    scanf("%d", &n);
+    string s;
+    vector<string> v;
+
+    for (int i = 0; i < n; i++)
+    {
+        cin >> s;
+        v.push_back(s);
+    }
+
+    sort(v.begin(), v.end(), cmp);
+    string ans = "";
+    for (string t : v)
+        ans += t;
+    while (ans.length() && ans[0] == '0')
+        ans.erase(ans.begin()); // 去掉前导0
+    if (ans.length() == 0)
+        cout << 0;
+    else
+        cout << ans << endl;
+    return 0;
+}
+```
diff --git a/A1094.md b/A1094.md
@@ -0,0 +1,61 @@
+# A1094 The Largest Generation
+
+## 1.题意理解
+求一棵树的最大宽度，以及是哪一层
+
+## 2.思路分析
+遍历这棵树，把每一层的结点数统计出来，找最大的
+
+## 3.参考代码
+```cpp
+#include <bits/stdc++.h>
+using namespace std;
+
+const int N = 128;
+int n, m;
+int ans[N] = {0};
+vector<int> child[N];
+
+int maxdepth = 0;
+void dfs(int root, int depth)
+{
+    if (child[root].size() == 0)
+    {
+        ans[depth]++;
+        maxdepth = max(depth, maxdepth);
+        return;
+    }
+
+    ans[depth]++;
+    for (int i = 0; i < child[root].size(); i++)
+        dfs(child[root][i], depth + 1);
+}
+
+int main()
+{
+    int k, id, c;
+    scanf("%d%d", &n, &m);
+
+    for (int i = 0; i < m; i++)
+    {
+        scanf("%d %d", &id, &k);
+        for (int j = 0; j < k; j++)
+        {
+            scanf("%d", &c);
+            child[id].push_back(c);
+        }
+    }
+
+    dfs(1, 1);
+
+    int ansLevel = 1, ansNum = 1;
+    for (int i = 1; i <= maxdepth; i++)
+        if (ans[i] > ansNum)
+        {
+            ansLevel = i;
+            ansNum = ans[i];
+        }
+    printf("%d %d\n", ansNum, ansLevel);
+    return 0;
+}
+```
diff --git a/A1097.md b/A1097.md
@@ -0,0 +1,65 @@
+# A1097 Deduplication on a Linked List
+
+## 1.题意理解
+给原始链表去重，重复的结点按顺序组成一个新链表
+
+## 2.思路分析
+记录关键字绝对值是否出现，第一次出现的结点加入result，出现过的加入removed
+
+## 3.参考代码
+```cpp
+#include <bits/stdc++.h>
+using namespace std;
+
+const int N = 100100;
+int n, k;
+
+struct node
+{
+    int Address, Key, Next;
+    node() {}
+    node(int addr, int key, int next) : Address(addr), Key(key), Next(next) {}
+};
+vector<node> nodes(N);
+vector<node> result, removed, lis;
+bool vis[N] = {false};
+
+int main()
+{
+    int head, addr, key, next;
+    scanf("%d %d", &head, &n);
+
+    for (int i = 0; i < n; i++)
+    {
+        scanf("%d %d %d", &addr, &key, &next);
+        nodes[addr] = node(addr, key, next);
+    }
+
+    for (int i = head; i != -1; i = nodes[i].Next)
+        lis.push_back(nodes[i]); // 提取有效节点
+
+    for (node it : lis)
+    {
+        int temp = abs(it.Key);
+        if (vis[temp])
+            removed.push_back(it);
+        else
+        {
+            result.push_back(it);
+            vis[temp] = true;
+        }
+    }
+
+    for (int i = 0; i < result.size() - 1; i++)
+        printf("%05d %d %05d\n", result[i].Address, result[i].Key, result[i + 1].Address);
+    printf("%05d %d -1\n", result.back().Address, result.back().Key);
+
+    if (removed.size())
+    {
+        for (int i = 0; i < removed.size() - 1; i++)
+            printf("%05d %d %05d\n", removed[i].Address, removed[i].Key, removed[i + 1].Address);
+        printf("%05d %d -1\n", removed.back().Address, removed.back().Key);
+    }
+    return 0;
+}
+```
diff --git a/A1101.md b/A1101.md
@@ -0,0 +1,52 @@
+# A1101 Quick Sort
+
+## 1.题意理解
+快速排序算法的核心——partition操作每次会确定一个主元（pivot）的位置，现在给序列让找出所有可能的主元。
+
+## 2.思路分析
+主元需要满足的条件：**左边最大数 <= 主元 <= 右边最小数**
+
+开一个leftMax和一个rightMin数组，从左到右填充leftMax，从右到左填充rightMin
+
+## 3.参考代码（晴神版）
+```cpp
+#include <iostream>
+#include <cstdlib>
+#include <algorithm>
+#include <vector>
+using namespace std;
+const int N = 1e5 + 10;
+const int INF = 0x3f3f3f3f;
+int A[N] = {}, leftMax[N] = {}, rightMin[N] = {};
+vector<int> ans;
+
+int main()
+{
+    int n, cnt = 0;
+    scanf("%d", &n);
+    for (int i = 0; i < n; i++)
+        scanf("%d", &A[i]);
+
+    leftMax[0] = 0; // 初始化为一个足够小的数
+    for (int i = 1; i < n; i++)
+        leftMax[i] = max(A[i - 1], leftMax[i - 1]);
+
+    rightMin[n - 1] = INF; // 初始化为一个足够大的数
+    for (int i = n - 2; i >= 0; i--)
+        rightMin[i] = min(A[i + 1], rightMin[i + 1]);
+
+    for (int i = 0; i < n; i++)
+        if (leftMax[i] < A[i] && rightMin[i] > A[i]) // 是否满足主元必要条件
+            ans.push_back(A[i]);
+
+    printf("%d\n", ans.size());
+    for (int i = 0; i < ans.size(); i++)
+    {
+        printf("%d", ans[i]);
+        if (i < ans.size() - 1)
+            printf(" ");
+    }
+    printf("\n");
+    return 0;
+}
+```
diff --git a/A1112.md b/A1112.md
@@ -25,6 +25,7 @@ int main()
 
     cin >> k >> s;
 
+    // 第一步，识别坏键
     int i = 0;
     while(i < s.size())
     {
@@ -43,6 +44,7 @@ int main()
             stucked[c] = 0;
     }
 
+    // 第二步，按顺序输出坏键
     i = 0;
     while(i < s.size())
     {
@@ -56,24 +58,25 @@ int main()
     }
     printf("\n");
 
+    // 第三步，剔除坏键，输出正确串
     i = 0;
     while(i < s.size())
     {
         char c = s[i];
         int cnt = 0;
 
-        if(stucked[c])
+        if(stucked[c]) // 如果是坏键
         {
             while(i < s.size() && s[i] == c)
             {
-                cnt++;
+                cnt++; // 记录此坏键连续出现的次数
                 i++;
             }
 
             for(int j = 0; j < cnt / k; j++)
                 printf("%c", c);
         }
-        else
+        else // 如果不是坏键，直接输出就好
         {
             printf("%c", c);
             i++;

diff --git a/A1140.md b/A1140.md
@@ -12,13 +12,15 @@
 using namespace std;
 
 const int N = 50;
+// seq的每行0号位记录序列长度，之后存储序列
 int seq[N][100000]; // 序列会变得很长！开10000最后一个3分case拿不了
 
 int main()
 {
     int d, n;
     scanf("%d%d", &d, &n);
 
+    // 初始化，look-and-say是迭代处理的
     seq[1][1] = d;
     seq[1][0] = 1;
 
@@ -28,10 +30,10 @@ int main()
 
         while(j <= seq[i - 1][0])
         {
-            int tmp = seq[i - 1][j];
+            int tmp = seq[i - 1][j]; // 当前数字
             seq[i][++idx] = tmp;
             int cnt = 0;
-            while(seq[i - 1][j] == tmp && j <= seq[i - 1][0])
+            while(seq[i - 1][j] == tmp && j <= seq[i - 1][0]) // 统计一共有几个重复的
             {
                 cnt++;
                 j++;

diff --git a/dijkstra+dfs.md b/dijkstra+dfs.md
@@ -8,8 +8,9 @@ void dijkstra(int s)
     fill(d, d + MAXV, INF);
     d[s] = 0;
 
-    for(int i = 0; i < n; i++)
+    for(int i = 0; i < n; i++) // 循环n次，每次加入一个点
     {
+        // 先找距离最短的点
         int u = -1, MIN = INF;
         for(int j = 0; j < n; j++)
         {
@@ -19,11 +20,13 @@ void dijkstra(int s)
                 MIN = d[j];
             }
         }
-    }
 
-    if(u == -1) return;
+    if(u == -1) 
+        return;
+
     vis[u] = true;
 
+    // 以当前找到的u为中转，进行松弛操作
     for(int v = 0; v < n; v++)
     {
         if(!vis[v] && G[u][v] != INF)

diff --git a/rebuild_bintree.md b/rebuild_bintree.md
@@ -116,29 +116,38 @@ void getIn(int preL, int preR, int postL, int postR) {
 ```cpp
 Node* buildBiTree(vector<int> layer,vector<int> in,int inL,int inR)
 {
-    if(layer.size()==0 || inL>inR) return nullptr;
-    int rootVal=layer[0];
-    Node* root=new Node(rootVal);
-    int pos=inL;
-    while(in[pos]!=rootVal) pos++;
+    if(layer.size()==0 || inL>inR) 
+        return nullptr;
+
+    int rootVal = layer[0];
+    Node* root = new Node(rootVal);
+    int pos = inL;
+    while(in[pos] != rootVal) 
+        pos++;
  
-    vector<int> layerLeft,layerRight;//存放左、右子树的层序序列
-    for(int i=1;i<layer.size();i++){
+    vector<int> layerLeft,layerRight; //存放左、右子树的层序序列
+    for(int i = 1; i < layer.size(); i++)
+    {
         int j;
-        for(j=inL;j<pos;j++){
-            if(layer[i]==in[j]){
+        for(j = inL; j < pos; j++)
+        {
+            if(layer[i] == in[j])
+            {
                 layerLeft.push_back(layer[i]);  //如果在pos前找到，插入左子树
                 break;
             }
         }
-        if(j==pos) layerRight.push_back(layer[i]);  //超过pos，插入右子树（层序遍历保持左右子树层序遍历顺序的一致性）
+        if(j == pos) 
+            layerRight.push_back(layer[i]);  //超过pos，插入右子树（层序遍历保持左右子树层序遍历顺序的一致性）
     }
-    root->lchild=buildBiTree(layerLeft,in,inL,pos-1);
-    root->rchild=buildBiTree(layerRight,in,pos+1,inR);
+    
+    root -> lchild = buildBiTree(layerLeft, in, inL, pos - 1);
+    root -> rchild = buildBiTree(layerRight, in, pos + 1, inR);
  
     return root;
 }
 ```
+这里也可以用一个```unordered_map<int, int> in_pos```来记录中序序列下标，就不用j遍历了，直接可以查出与pos的大小关系
 
 ## 7. 总结
 - 时刻牢记三种遍历顺序：