me too vegetable

DallasAutumn · Mar 18, 2020 · 91dffad · 91dffad
1 parent 002b476
commit 91dffad
Show file tree

Hide file tree

Showing 3 changed files with 198 additions and 1 deletion.
diff --git a/A1044.md b/A1044.md
@@ -0,0 +1,58 @@
+# A1044 Shopping in Mars
+
+## 1.题意理解
+题目太长不看，直接翻译成人话：给出一个数列，再给出一个值m，输出所有连续子序列和最接近m的首尾端点。
+
+## 2.思路分析
+由于涉及到连续子序列和，考虑构造前n项和数列```sum[]```，序列下标从1到n，则第i项到第j项的和为```sum[j]-sum[i-1]```。（sum[0]=0即可。）
+
+sum天生是一个单调不减数列，这时就可以使用二分方法查找，枚举区间左端点i，查找目标为```sum[j]-sum[i-1] == m```。查找方法直接使用```<algorithm>```头文件提供的```lower_bound```和```upper_bound```方法即可。
+
+第一遍遍历，找到最接近m的ans（完全相等最好），第二遍查找目标即为```sum[j]-sum[i-1] == ans```，找到一个输出一个。
+
+## 3.参考代码
+```cpp
+#include <bits/stdc++.h>
+using namespace std;
+
+const int N = 100100;
+const int M = (int)1e8 + 10;
+int n, m, ans = M;
+int sum[N] = {};
+
+int main()
+{
+    scanf("%d%d", &n, &m);
+    sum[0] = 0;
+    int temp = 0;
+    for (int i = 1; i <= n; i++)
+    {
+        scanf("%d", &sum[i]);
+        sum[i] += sum[i - 1];
+    }
+    for (int i = 1; i <= n; i++)
+    {
+        int j = lower_bound(sum + i, sum + n + 1, sum[i - 1] + m) - sum;
+        temp = sum[j] - sum[i - 1];
+        if (temp == m)
+        {
+            ans = m;
+            break;
+        }
+        else if (j <= n && temp < ans)
+            ans = temp;
+    }
+    for (int i = 1; i <= n; i++)
+    {
+        int j = lower_bound(sum + i, sum + n + 1, sum[i - 1] + m) - sum;
+        temp = sum[j] - sum[i - 1];
+        if (temp == ans)
+            printf("%d-%d\n", i, j);
+    }
+    // system("pause");
+    return 0;
+}
+```
+注意点：
+- ```lower_bound```返回的是第一个```大于或等于```给定值的指针，如果没找到，返回目标插入位置的下标指针（其实就是最大下标+1）
+- sum数组可以读入时就计算好
diff --git a/A1098.md b/A1098.md
@@ -0,0 +1,135 @@
+# A1098 Insertion or Heap Sort
+
+## 1.题意理解
+给出一个初始序列，和排序过程中的一个中间结果序列（排序方法只可能是插入排序、堆排序）。判断使用的哪一种排序方法，并且输出下一轮迭代的结果。
+
+## 2.思路分析
+首先要熟练掌握插入排序和堆排序的操作。但是要解决这个问题还不够，需要对这两种排序方法的原理有清晰的认知。
+
+题目把插入排序和堆排序放到一起考是有原因的。因为插入排序是每次取一个元素插入到前面的有序序列中，中间结果表现为前半段有序。而堆排序每次把堆顶的最大元素放到最后，中间结果表现为后半段有序。
+
+但是这两个特征只是必要条件，完全可以构造输入序列满足前后半段都部分有序。
+
+所以，可以通过模拟两种排序过程中的一种来判断。堆排序的时间复杂度较低，更适合作为判断基准。
+
+## 3.参考代码
+```cpp
+#include <bits/stdc++.h>
+using namespace std;
+
+const int N = 128;
+int n;
+vector<int> initial(N);
+vector<int> partial(N);
+vector<int> maxheap(N);
+
+void downAdjust(int low, int high, vector<int> &heap)
+{
+    int i = low, j = 2 * i;
+    while (j <= high)
+    {
+        if (j + 1 <= high && heap[j + 1] > heap[j])
+            j++;
+        if (heap[j] > heap[i])
+        {
+            swap(heap[j], heap[i]);
+            i = j;
+            j = 2 * i;
+        }
+        else
+            break;
+    }
+}
+
+void upAdjust(int low, int high, vector<int> &heap)
+{
+    int i = high, j = i / 2;
+    while (j >= low)
+        if (heap[j] < heap[i])
+        {
+            swap(heap[j], heap[i]);
+            i = j;
+            j = i / 2;
+        }
+        else
+            break;
+}
+
+void insertion(vector<int> &v)
+{
+    int i, j;
+    for (i = 2; i <= n; i++)
+        if (v[i] < v[i - 1])
+        {
+            v[0] = v[i]; //0号位置空闲，可以作为暂存区域
+            for (j = i - 1; v[0] < v[j]; j--)
+                v[j + 1] = v[j];
+            v[j + 1] = v[0];
+            break; //only one iteration
+        }
+}
+
+int main()
+{
+    scanf("%d", &n);
+    for (int i = 1; i <= n; i++)
+    {
+        scanf("%d", &initial[i]);
+        maxheap[i] = initial[i];
+    }
+    for (int i = 1; i <= n; i++)
+        scanf("%d", &partial[i]);
+
+    //create heap
+    for (int i = n / 2; i >= 1; i--)
+        downAdjust(i, n, maxheap);
+
+    bool hs = false;
+    int i = n;
+    while (i > 1)
+    {
+        if (maxheap == partial)
+        {
+            hs = true;
+            break;
+        }
+        else
+        {
+            swap(maxheap[i], maxheap[1]);
+            downAdjust(1, i - 1, maxheap);
+            i--;
+        }
+    }
+
+    if (hs)
+    {
+        printf("Heap Sort\n");
+        swap(partial[i], partial[1]);
+        downAdjust(1, i - 1, partial);
+        for (int j = 1; j <= n; j++)
+        {
+            printf("%d", partial[j]);
+            if (j == n)
+                printf("\n");
+            else
+                printf(" ");
+        }
+    }
+    else
+    {
+        printf("Insertion Sort\n");
+        insertion(partial);
+        for (int j = 1; j <= n; j++)
+        {
+            printf("%d", partial[j]);
+            if (j == n)
+                printf("\n");
+            else
+                printf(" ");
+        }
+    }
+    system("pause");
+    return 0;
+}
+```
+本题一定要熟练掌握两种排序操作，特别是建堆、堆排序中的调整等操作。
diff --git a/rebuild_btree.md b/rebuild_btree.md
@@ -34,7 +34,11 @@ void solve(int preL, int inL, int postL, int n)
 ```cpp
 struct node {
     int data;
-    node* lchild, rchild;
+    node* lchild, *rchild;
+    node() {
+        this->lchild = NULL;
+        this->rchild = NULL;
+    }
 };
 
 node* create(int postL, int postR, int inL, int inR) {