Posted on | In |

前言

学数据结构的时候，就没有真正的手写过快排，思想是简单，但是算法思想和实现上，还是有一定的差距的，这中间的差距，可能就是所谓的编程能力吧。

这里整理下快排的实现，包括递归方式，非递归方式，pivot不同选取方式等的实现。

基本思想

基本思想描述起来还是很简单的，找到一个pivot元素，每趟把所有元素中，小于的放到左边，大于的放到右边，然后递归的进行就好了。

具体怎么放，就是两边向中间扫，碰到不合适的，就swap。

实现

递归实现

这里pivot选取的是第一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
int partition(vector<int> &a, int l, int r) {
    int pivot = a[l];
    while (l < r) {
        while (l < r && a[r] >= pivot)
            r--;
        a[l] = a[r];
        while (l < r && a[l] <= pivot)
            l++;
        a[r] = a[l];
    }
    a[l] = pivot;
    return l;
}
1
2
3
4
5
6
7
void quicksort(vector<int> &a, int l, int r) {
    if (l >= r)
        return;
    int pivot = partition(a, l, r);
    quicksort(a, l, pivot);
    quicksort(a, pivot + 1, r);
}

这里其实还是很精巧的，简洁对称，在partition的while循环中。

两个while，让l和r运作到指定的位置，但两者并不是同时到达，然后进行swap，而是利用a[0]当做pivot之后，位置空出，正好借此达成互换的目的：先把a[r]放到原来pivot的位置，然后把a[l]放到上一步的a[r]位置，这样，a[l]再一次空出，可以重复这个过程。

非递归实现

非递归的实现，主要是分治的时候，记录当前的l,r位置，这里用栈来存储：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void quicksortIterative(vector<int> &a, int l, int r) {
    if (l >= r)
        return;
    stack<int> s;
    s.push(l);
    s.push(r);
    int pivot;
    while (!s.empty()) {
        r = s.top();
        s.pop();
        l = s.top();
        s.pop();
        pivot = partition(a, l, r);
        if (l < pivot - 1) {
            s.push(l);
            s.push(pivot - 1);
        }
        if (pivot + 1 < r) {
            s.push(pivot + 1);
            s.push(r);
        }
    }
}

pivot选取非0位置元素

这里不讨论如何选取这个pivot，有各种选取方式，什么第一个，最后一个，中间的，三个里边的中间值，随机选等等。

其实这些都是大同小异，只不过，上边用a[0]的时候，有一些小trick，如果用其它的话，就不能用哪个trick了，这里自己再单独实现以下。

啊，我好傻啊，干嘛那么想不开，既然不是第一个，换到第一个就对了嘛，还想那么多干嘛…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int partitionRandomPivot(vector<int> &a, int l, int r) {
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<int> distribution(l, r);
    int pivotIdx = distribution(gen);
    int pivot = a[pivotIdx];
    a[pivotIdx] = a[l];
    // below is the same
    while (l < r) {
        while (l < r && a[r] >= pivot)
            r--;
        a[l] = a[r];
        while (l < r && a[l] <= pivot)
            l++;
        a[r] = a[l];
    }
    a[l] = pivot;
    return l;
}

算了，权当是，学习一下modern c++中，随机数的用法吧hhh

Posted on | In , |

题目

https://leetcode.com/problems/kth-largest-element-in-an-array/description/

-w950

想法

可以说是非常经典的题目了。

基本是，快排的划分思想，但是，不用全拍完，判断与k的大小关系，选择性的排一边就好，所以时间复杂度应该是O(n)，空间复杂度为O(1).

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
private:
    int partition(vector<int>& nums, int l, int r) {
        int pivot = nums[l];
        while (l < r) {
            while (l < r && nums[r] <= pivot)
                r--;
            nums[l] = nums[r];
            while (l < r && nums[l] >= pivot)
                l++;
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        return l;
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        int left = 0, right = nums.size() - 1;
        while (true) {
            int mid = partition(nums, left, right);
            if (mid == k - 1)
                return nums[mid];
            if (mid < k - 1)
                left = mid + 1;
            else
                right = mid - 1;
        }
    }
};

Posted on | Edited on | In |

前言

KMP算法，之前都没有听说过，考研竟然要考？？excuse me？不过了解了之后，发现，这个算法还是很有用，同时也是很经典的，在此将自己的学习历程以及总结记录下来。

KMP算法

来源

由字符串模式匹配引进的。

直观来看，对于字符串匹配，也就是strstr()函数的功能，首先想到的是直接的遍历比较，对于长度为m的字符串以及长度为n的pattern，复杂度是O(m * n)。而应用KMP算法，可以将时间复杂度降到O(m + n)。

基本思想

这个到处都有说，各种“循循善诱”引出的。简单来说，就是：
对于pattern，当比到第k位，发现不匹配了，这个时候，前k位匹配的自己其实已经知道是什么了，所以这一段的最后一部分，可能和pattern的前一部分相同，直接从这之后开始比就好了。

这样一来，扫字符串的时候，指针是不用往后挪的，当到达p位置发现pattern的第k位不匹配，此时，string的[p-k, p-1]这一段和pattern的[0, k-1]这k位是匹配的。
如果是原来，那么string的指针得回去，从现在的p回到p-k+1的位置，然后pattern也向前挪一位比较。KMP的话，不把string的指针往后挪，而是只把pattern向前挪，当然，相同的就对齐，比较之后的了。

于是，pattern挪的距离就成了关键。对于[0, k-1]这k位，如果有相同的前缀和后缀，那么就挪到前缀和原来后缀这一段对齐。

具体操作

1. next数组

next数组是什么呢：

1
next[i] = pattern[0, i-1]这一子串的最长相同前后缀

比如说ABCABD，在D处，也就是next[5]为2。
另外，规定next[0] = -1。

其实，这样的说明个人是非常不喜欢的，只说了是什么，并没有说为什么这样定义，只知道这样后边要用到，然后就能够解决问题。就像好多线代教材上的证明，我看的过程中很恼火，你倒是告诉我为什么要这样做，鬼才想得到这里。

那么这里为什么要算next呢，算了有什么用呢？

这里next数组有两层意思，一个就是上边说的这个位置之前的子串的最长相同前后缀长度；另一个是，下一次比较时，在pattern的第j位开始比较。这两者本质上是一致的。

如果之前有k位的相同前后缀，即next[j] = k，那么，说明前k位[0, k-1]可以对齐到原来后缀的位置，而开始比较新的，可以从第k位开始比。

这样一来，这个next数组就直接告诉了我们，当string中的指针i不后退的时候，pattern中的指针应该从何处开始。

2. 计算next数组

先上伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def genNext(string p):
    n = p.length
    for i in [0, n):
        next[i] = 0
    next[0] = -1
    curr = -1 # [1]
    i = 0
    while i+1 < n:
        if curr == -1 or p[i] == p[curr]:
            curr++
            i++
            next[i] = curr
        else:
            curr = next[curr] # [2]
    return next

这个代码还是很短的，但其实并不是很好理解，至少对我来说..

curr代表当前相同前后缀的长度，同时也可以当做下标用，这个上文讨论过类似的用法

有两个点需要注意，在代码中已经标出：

[2] curr = next[curr]

先看第二点，curr = next[curr]，if后边的很好理解（先忽略curr == -1的判断），就是相同的话，往前走就是了，下一位的next就是curr加之后的结果。如果不相等，就有趣了，并不是相同前后缀的长度就是0了，没有最长，还有第二长嘛：

1
2
3
4
              p         i
        0 1 2 3 4 5 6 7 8 9
        a b a c d a b a b x
next   -1 0 0 1 0 0 1 2 3 2

如上图，curr(p)和i到达如图所示的位置，发现s[3]和s[8]并不相同，但这时不能简单的认为这一段就没有相同的前后缀，虽然之前最长的a b a无法延续下去，但是说不定次长的还可以。

次长的是什么呢？其实就是[0, p-1]这一段的最长相同前后缀！

于是，就有了curr = next[curr]

这样一来，p变为1，再去比较s[1]和s[8]时，发现相等了，这样就可以愉快的前进了。

[1] -1的使用

出现了3处-1，这其实算是算法设计中的一个小trick吧，用于控制边界条件。

跟[1]有联系，在curr = next[curr]过程中，curr其实一直再找更短的最长相同前后缀，所以curr一直再往后退，那么什么时候是个头呢？就是根本没有共同的前后缀，那么必然会出现curr = next[curr] = 0的情况，这时，下一步的时候，next[curr]也就是next[0]该有一个合适的值，让这个后退的过程停下来，这里取了-1。
于是，也就有了if判断时候的curr == -1，停下，curr赋0（正好+1是0，用-1也有这个好处），然后赋给next。
至于初始curr = -1，是初始化的技巧。如果不这样，可能还需给s[1]赋初值，这样不够优雅，也增添了好多判断的麻烦等等。

3. 计算字符串模式匹配位置

1
2
3
4
5
6
7
8
9
10
11
12
def kmpMatch(s, p):
    next = genNext(p)
    i = 0
    j = 0
    while i < s.lenth && j < p.length:
        if j == -1 || s[i] == p[j]:
            i++
            j++
        else:
            j = next[j]
    if j == p.length:
        return i - j

精巧啊，这个KMP算法，求next以及之后的匹配，第一次看到原理及实现，真的是觉得很精巧，值得反复揣摩。

应用

1. 字符串匹配（strstr()实现）

LeetCode 28. Implement strStr()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
private:
    void genNext(string& p, vector<int>& next) {
        next[0] = -1;
        int i = 0;
        int j = -1;
        int n = p.length();
        while (i + 1 < n) {
            if (j == -1 || p[i] == p[j]) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
    }
public:
    int strStr(string s, string p) {
        if (p.empty())
            return 0;
        vector<int> next(p.length(), 0);
        genNext(p, next);
        int i = 0;
        int j = 0;
        int sLen = s.length(), pLen = p.length();
        while (i < sLen && j < pLen) {
            if (j == -1 || s[i] == p[j]) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == pLen) {
            return i - j;
        } else {
            return -1;
        }
    }
};

算是上述算法的一个C++实现吧，没有一句多余的废话。

另外注意一点，如果有负数，和s.size()，s.length()之类无符号数比，会有问题哦，记得转成有符号数，或者采用其它方法防止之类的问题。

2. 重复子串问题

LeetCode 459. Repeated Substring Pattern

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
private:
    void genNext(string& s, vector<int>& next) {
        next[0] = -1;
        int i = 0;
        int j = -1;
        int len = s.length();
        while (i < len) {
            if (j == -1 || s[i] == s[j]) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
    }
public:
    bool repeatedSubstringPattern(string s) {
        if (s.empty())
            return true;
        vector<int> next(s.length() + 1, 0);
        genNext(s, next);
        return (next[s.length()] != 0) && (s.length() % (s.length() - next[s.length()]) == 0);
    }
};

参考资料

阮一峰: 字符串匹配的KMP算法
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

很详细的 KMP 算法讲解，逻辑清晰，易懂
https://juejin.im/entry/58edc67461ff4b006925d2e9

Posted on | In , |

题目

1087 All Roads Lead to Rome (30)（30 分）

Indeed there are many different tourist routes from our city to Rome. You are supposed to find your clients the route with the least cost while gaining the most happiness.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers N (2<=N<=200), the number of cities, and K, the total number of routes between pairs of cities; followed by the name of the starting city. The next N-1 lines each gives the name of a city and an integer that represents the happiness one can gain from that city, except the starting city. Then K lines follow, each describes a route between two cities in the format “City1 City2 Cost”. Here the name of a city is a string of 3 capital English letters, and the destination is always ROM which represents Rome.

Output Specification:

For each test case, we are supposed to find the route with the least cost. If such a route is not unique, the one with the maximum happiness will be recommended. If such a route is still not unique, then we output the one with the maximum average happiness — it is guaranteed by the judge that such a solution exists and is unique.

Hence in the first line of output, you must print 4 numbers: the number of different routes with the least cost, the cost, the happiness, and the average happiness (take the integer part only) of the recommended route. Then in the next line, you are supposed to print the route in the format “City1->City2->…->ROM”.

Sample Input:

1
2
3
4
5
6
7
8
9
10
11
12
13
6 7 HZH
ROM 100
PKN 40
GDN 55
PRS 95
BLN 80
ROM GDN 1
BLN ROM 1
HZH PKN 1
PRS ROM 2
BLN HZH 2
PKN GDN 1
HZH PRS 1

Sample Output:

1
2
3 3 195 97
HZH->PRS->ROM

想法

很经典的一道最短路径的题目

由于加入了场景，字符串的处理等，稍微烦一点

需要记录的东西比较多，需要记录路径、cost、happiness、经过的节点数

路径可以记录前驱

费了好大劲，处理完各种各样的要求：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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
//
// Created by Zhao Xiaodong on 2018/8/14.
//
#include <iostream>
#include <queue>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_map>
#include <string>
using namespace std;
int main() {
    int N, K;
    string start;
    start.reserve(3);
    cin >> N >> K >> start;
    vector<string> name(N);
    vector<int> happy(N);
    unordered_map<string, int> id;
    name[0] = start;
    id[start] = 0;
    happy[0] = 0;
    for (int i = 1; i < N; i++) {
        string s;
        s.reserve(3);
        int h;
        cin >> s >> h;
        name[i] = s;
        id[s] = i;
        happy[i] = h;
    }
    vector<vector<int>> m(N, vector<int>(N, INT_MAX));
    for (int i = 0; i < K; i++) {
        string a, b;
        a.reserve(3);
        b.reserve(3);
        int cost;
        cin >> a >> b >> cost;
        m[id[a]][id[b]] = m[id[b]][id[a]] = cost;
    }
    vector<bool> visited(N, false);
    vector<int> prev(N, -1);
    vector<int> cost(N, INT_MAX);
    vector<int> hop(N, INT_MAX);
    vector<int> selections(N, 0);
    vector<int> happiness(N, 0);
    selections[0] = 1;
    cost[0] = 0;
    hop[0] = 0;
    for (int k = 0; k < N; k++) {
        int minCost = INT_MAX;
        int curr = -1;
        for (int j = 0; j < N; j++) {
            if (!visited[j] && cost[j] < minCost) {
                minCost = cost[j];
                curr = j;
            }
        }
        visited[curr] = true;
        for (int i = 0; i < N; i++) {
            if (!visited[i] && m[curr][i] < INT_MAX) {
                if (selections[i] == 0 || cost[i] == m[curr][i] + cost[curr]) {
                    selections[i] += selections[curr];
                }
                if (cost[i] > m[curr][i] + cost[curr] ||
                    (cost[i] == m[curr][i] + cost[curr] && happiness[i] < happy[i] + happiness[curr]) ||
                    (cost[i] == m[curr][i] + cost[curr] && happiness[i] == happy[i] + happiness[curr] &&
                     hop[i] > hop[curr] + 1)
                        ) {
                    prev[i] = curr;
                    cost[i] = m[curr][i] + cost[curr];
                    happiness[i] = happy[i] + happiness[curr];
                    hop[i] = hop[curr] + 1;
                }
            }
        }
    }
    int endIdx = id["ROM"];
    vector<int> prevChain;
    int p = endIdx;
    while (prev[p] >= 0) {
        prevChain.push_back(prev[p]);
        p = prev[p];
    }
    reverse(prevChain.begin(), prevChain.end());
    cout << selections[endIdx] << " " << cost[endIdx] << " " << happiness[endIdx] << " "
         << (happiness[endIdx] == 0 ? 0 : ((int) ((double) happiness[endIdx] / hop[endIdx]))) << "\n";
    for (int i = 0; i < prevChain.size(); i++) {
        cout << name[prevChain[i]] << "->";
    }
    cout << "ROM";
    return 0;
}

还有一个测试点没有过！！

不解。

TODO..

Posted on | In , |

题目

1057 Stack (30)（30 分）

Stack is one of the most fundamental data structures, which is based on the principle of Last In First Out (LIFO). The basic operations include Push (inserting an element onto the top position) and Pop (deleting the top element). Now you are supposed to implement a stack with an extra operation: PeekMedian — return the median value of all the elements in the stack. With N elements, the median value is defined to be the (N/2)-th smallest element if N is even, or ((N+1)/2)-th if N is odd.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<= 10^5^). Then N lines follow, each contains a command in one of the following 3 formats:

Push key\ Pop\ PeekMedian

where key is a positive integer no more than 10^5^.

Output Specification:

For each Push command, insert key into the stack and output nothing. For each Pop or PeekMedian command, print in a line the corresponding returned value. If the command is invalid, print “Invalid” instead.

Sample Input:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop

Sample Output:

1
2
3
4
5
6
7
8
9
10
11
12
Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid

想法

最傻的办法，就用一个数组，当栈维护
要找中位数的时候，复制一份sort一下
这样肯定是会超时的

怎么维护这个大小信息呢？是个关键
两个信息需要维护，一个是顺序信息，一个是大小信息
顺序信息用位置来表示，那么大小信息呢？开个链表来存吗？不是很合理。

参考了这位：https://blog.csdn.net/frozenshore/article/details/47836935 的解法，可以用set，set自带排序

维护两个set，A和B，保证A中元素都小于等于B，且A.size() == B.size() || A.size() - 1 == B.size()

push或pop之后，要更新这两个set来保持正确性

学习了，学习了！

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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
//
// Created by Zhao Xiaodong on 2018/8/13.
//
#include <iostream>
#include <algorithm>
#include <set>
#include <stack>
#include <vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    stack<int> s;
    multiset<int> A, B;
    for (int i = 0; i < N; i++) {
        string op;
        op.reserve(20);
        cin >> op;
        if (op == "Pop") {
            if (s.empty()) {
                cout << "Invalid\n";
            } else {
                int num = s.top();
                cout << num << "\n";
                s.pop();
                if (num > *A.rbegin()) {
                    B.erase(B.find(num));
                    if (A.size() > B.size() + 1) {
                        B.insert(*A.rbegin());
                        A.erase((--A.end()));
                    }
                } else {
                    A.erase(A.find(num));
                    if (B.size() > A.size()) {
                        A.insert(*B.begin());
                        B.erase(B.begin());
                    }
                }
            }
        } else if (op == "Push") {
            int num;
            cin >> num;
            s.push(num);
            if (A.empty()) {
                A.insert(num);
            } else {
                if (num > *A.rbegin()) {
                    B.insert(num);
                    if (B.size() > A.size()) {
                        A.insert(*B.begin());
                        B.erase(B.begin());
                    }
                } else {
                    A.insert(num);
                    if (A.size() > B.size() + 1) {
                        B.insert(*A.rbegin());
                        A.erase((--A.end()));
                    }
                }
            }
        } else {
            if (A.empty()) {
                cout << "Invalid\n";
            } else {
                cout << *A.rbegin() << "\n";
            }
        }
    }
    return 0;
}

用了multi_set

总结

借用STL中的东西来方便自己，尽管是大材小用。

set自带排序，也可以自己指定Compare方法。

顺便复习下set的使用方法：

1
2
auto cmp = [](int a, int b) { return ... };
set<int, decltype(cmp)> s(cmp);

Posted on | Edited on | In , |

前言

唉，这个OJ，不是很友好。

谨记下自己做题过程中的一些坑，既然改变不了这个OJ，只能改变自己了。

注意事项

cin，cout慢

可用的解决方法有：

1
ios::sync_with_stdio(false);

这一句可以提高一些速度，但是这样，cin，cout就不能与scanf，printf混用。

用scanf，很不好的就是不能读入到string，很难过。cstring和std::string转换如下：

1
2
3
char *c_s = "hello";
std::string s = c_s;
printf("%s", s.c_str());

另外，不要用endl，真的很慢很慢，用"\n"

但是，很遗憾的是，std::string某些情况下，也很慢

std::string慢

如果输入限定了长度，尽量用reserve控制下，这样会快不少

1
2
int N = 10;
s.reserve(N);

map，set等慢

不要管什么优雅，政治正确，做对题是硬道理。PAT一般对空间复杂度要求不高，一些用到map之类的，可以考虑开一个很大的数组直接存。

getline()

注意如果之前cin读入一个数，后边还有换行，记得先getchar()

1
2
3
cin >> N;
getchar();
getline(cin, s);

总结

  1. 能全局就全局，省得传参
  2. 看空间要求，如果没有特别限制，能全开就全开，5w的数组都没有问题
  3. 不要用endl
  4. ios::sync_with_stdio(false); cin.tie(nullptr);
  5. 用string的时候，如果没有变长要求，用reserve，可以省不少时间
  6. 如果输出有较复杂格式要求，iomanip写不来，那就不要用cin、cout，否则可能超时
  7. scanf不支持std::string，考虑读到char*里，然后两者相互转换
  8. 如果遇到多个测试点没有过，多半是题意理解有问题，先不要找着一些奇奇怪怪的边界条件BUG

Posted on | In , |

题目

https://leetcode.com/problems/find-k-closest-elements/description/

-w947

想法

既然是排序好的，肯定要用到二分查找

找到与x距离最近，<=x的，然后开始拓展开来

嗯，一开始还是欠考虑了，找到<=x的最近元素之后，要向两边挨个比较，最后得到需要的值

这里有一个api还是查阅了下，记下备忘：

1
vec.insert(vec.begin(), 47); // vector头插入一个元素

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int l = 0, r = arr.size() - 1;
        int mid;
        while (l <= r) {
            mid = (l + r) / 2;
            if (arr[mid] > x) {
                r = mid - 1;
            } else if (arr[mid] == x) {
                break;
            } else {
                if (mid == l) {
                    break;
                } else {
                    l = mid + 1;
                }
            }
        }
        // cout << mid;
        vector<int> res;
        l = mid, r = mid + 1;
        for (int cnt = 0; cnt < k; cnt++) {
            if (l < 0) {
                res.push_back(arr[r]);
                r++;
            } else if (r >= arr.size()) {
                res.insert(res.begin(), arr[l]);
                l--;
            } else if (abs(arr[r] - x) < abs(arr[l] - x)) {
                res.push_back(arr[r]);
                r++;
            } else {
                res.insert(res.begin(), arr[l]);
                l--;  
            }
        }
        return res;
    }
};

Posted on | Edited on | In , |

题目

Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1 = { 11, 12, 13, 14 } is 12, and the median of S2 = { 9, 10, 15, 16, 17 } is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.

Given two increasing sequences of integers, you are asked to find their median.

Input Specification:
Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (≤2×10^5)is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int.

Output Specification:
For each test case you should output the median of the two given sequences in a line.

Sample Input:

1
2
4 11 12 13 14
5 9 10 15 16 17

Sample Output:

1
13

想法

把两个数组分成两个部分，得到中位数

要考虑时间复杂度和空间复杂度

emm 先写一个普通的版本：

将两个数组存下来，然后从头开始遍历，两个指针比较着向前走，直到到达一半为止

实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//
// Created by Zhao Xiaodong on 2018/8/7.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int M, N;
    cin >> M;
    vector<int> v1(M);
    for (int i = 0; i < M; i++) {
        cin >> v1[i];
    }
    cin >> N;
    vector<int> v2(N);
    for (int i = 0; i < N; i++) {
        cin >> v2[i];
    }
    int p1 = 0, p2 = 0;
    int sum = M + N;
    int half = (sum - 1) / 2;
    bool isV1 = !v1.empty();
    for (int i = 0; i <= half; i++) {
        if (p1 >= v1.size()) {
            isV1 = false;
            p2++;
        }
        else if (p2 >= v2.size()) {
            isV1 = true;
            p1++;
        }
        else {
            if (v1[p1] < v2[p2]) {
                p1++;
                isV1 = true;
            }
            else {
                isV1 = false;
                p2++;
            }
        }
    }
    cout << (isV1 ? v1[p1 - 1] : v2[p2 - 1]);
    return 0;
}

十分干净简单，但是最后一个测试点内存超限，而且，最后一个测试点10分，占了2/5的分数。

用的空间，也就存两个输入的数组，没有其它的空间了
这都内存超限的话，看来，不能把数据都存下来。

肯定要存输入的第一个数组。
对于第二个，必须边读入，边处理。

不存第二个，不就对了。

改进之后的版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//
// Created by Zhao Xiaodong on 2018/8/7.
//
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    int M, N;
    cin >> M;
    vector<int> v1(M);
    for (int i = 0; i < M; i++) {
        cin >> v1[i];
    }
    cin >> N;
    int p1 = 0, p2 = 0;
    int sum = M + N;
    int half = (sum - 1) / 2;
    int num1 = 0;
    int num2 = 0;
    bool isV1 = !v1.empty();
    queue<int> v2Buffer;
    for (int i = 0; i <= half; i++) {
        if (p1 >= M) {
            cin >> num2;
            p2++;
            isV1 = false;
        } else if (p2 >= N) {
            num1 = v1[p1];
            p1++;
            isV1 = true;
        } else {
            num1 = v1[p1];
            if (v2Buffer.empty()) {
                cin >> num2;
                v2Buffer.push(num2);
            } else {
                num2 = v2Buffer.front();
            }
            if (num1 < num2) {
                p1++;
                isV1 = true;
            } else {
                p2++;
                v2Buffer.pop();
                isV1 = false;
            }
        }
    }
    cout << (isV1 ? num1 : num2);
    return 0;
}

用了一个buffer来存比较之后，并没有用num2的情况下的num2.

内存超限没有了，不过还有个测试点没过，而且也是10分！！！
问题出在哪里呢？？？

不解，实在想不到..

看来，还是，考虑的不周到，没有玄学，只是问题不明显而已，buffer没有考虑全。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//
// Created by Zhao Xiaodong on 2018/8/7.
//
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    int M, N;
    cin >> M;
    vector<int> v1(M);
    for (int i = 0; i < M; i++) {
        cin >> v1[i];
    }
    cin >> N;
    int p1 = 0, p2 = 0;
    int sum = M + N;
    int half = (sum - 1) / 2;
    long num1 = 0;
    long num2 = 0;
    bool isV1 = !v1.empty();
    int v2Buffer;
    bool hasBuffer = false;
    for (int i = 0; i <= half; i++) {
        if (!hasBuffer) {
            cin >> num2;
            hasBuffer = true;
        }
        if (p1 >= M) {
            p2++;
            hasBuffer = false;
            isV1 = false;
        } else if (p2 >= N) {
            num1 = v1[p1];
            p1++;
            isV1 = true;
        } else {
            num1 = v1[p1];
            if (num1 < num2) {
                p1++;
                isV1 = true;
            } else {
                p2++;
                hasBuffer = false;
                isV1 = false;
            }
        }
    }
    cout << (isV1 ? num1 : num2);
    return 0;
}

感想

  1. 找问题，仔细找，用到每个“变”量，都要审核是否符合条件
  2. PAT更新后的分数好迷
  3. ios::sync_with_stdio(false)大法好，应该不用担心cin超时了hhh

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/median-of-two-sorted-arrays/description/

-w953

想法

时间复杂度，要求很高

其实这道题，空间复杂度，也可以要求很高，PAT有一道类似的题：

https://pintia.cn/problem-sets/994805342720868352/problems/994805466364755968

-w991

leetCode上的solution:
https://leetcode.com/problems/median-of-two-sorted-arrays/solution/

总结下来，思想就是，根据中位数的定义，把两个数组各自分成两个部分，两个左侧部分是合并后的左侧，右侧部分是合并后的右侧。然后，根据两遍相等的关系，找到两者下标的关系，然后将两个变量化为一个变量，这样一来，二分就好了。

具体来看：

n1.size: M
n2.size: N

要找到i, j，满足：

分成两个部分：

1
2
n1[0] ~ n1[i - 1]; n1[i] ~ n1[M - 1]
n2[0] ~ n2[j - 1]; n2[j] ~ n2[N - 1]
  1. i + j == M-i + N-j || i + j == M-i + N-j + 1
  2. n1[i - 1] <= n2[j] && n2[j - 1] <= n1[i]

这样一来，也就是说: j = (M + N - 2 * i + 1) / 2

(这里默认N>=M，这样可以保证 j >= 0)

然后，找i即可
用二分查找的方式，验证是否满足条件2，找到最后的i

这样一来，没有占用额外的空间，O(1)复杂度
时间复杂度，二分查找，较小的那个数组，应该是O(log(min(m, n)))

答案

自己写的一个答案，边界情况考虑的很不优雅，最后是对着LeetCode的测试点一个一个改才AC了hhh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int>& n1 = nums1.size() > nums2.size() ? nums2 : nums1;
        vector<int>& n2 = nums1.size() > nums2.size() ? nums1 : nums2;
        int M = n1.size(), N = n2.size();
        int l = 0, r = n1.size();
        // cout << l << " " << r;
        int i = 0, j = (M + N + 1) / 2;
        while (l <= r) {
            i = (l + r) / 2;
            j = (M + N - 2 * i + 1) / 2;
            // cout << i << " " << j << endl;
            if ((i <= 0 || j >= N || n1[i - 1] <= n2[j]) && (j <= 0 || i >= M || n2[j - 1] <= n1[i])) {
                break;
            } else if ((i > 0 && j >= N) || n1[i - 1] > n2[j]) {
                r = i - 1;
            } else {
                l = i + 1;
            }
            // cout << l << " " << r << endl;
        }
        cout << endl << i << " " << j;
        if ((M + N) % 2 == 1) {
            if (i == 0)
                return n2[j - 1];
            if (j == 0)
                return n1[i - 1];
            return (double)max(n1[i - 1], n2[j - 1]);
        } else {
            if (n1.empty()) {
                return (double)(n2[j - 1] + n2[j]) / 2;
            }
            return (double)(max(i > 0 ? n1[i - 1] : INT_MIN, j > 0 ? n2[j - 1] : INT_MIN) + min(i < M ? n1[i] : INT_MAX, j < N ? n2[j] : INT_MAX)) / 2;
        }
    }
};

Posted on | In , |

题目

1013 Battle Over Cities (25)（25 分）

It is vitally important to have all the cities connected by highways in a war. If a city is occupied by the enemy, all the highways from/toward that city are closed. We must know immediately if we need to repair any other highways to keep the rest of the cities connected. Given the map of cities which have all the remaining highways marked, you are supposed to tell the number of highways need to be repaired, quickly.

For example, if we have 3 cities and 2 highways connecting city~1~-city~2~ and city~1~-city~3~. Then if city~1~ is occupied by the enemy, we must have 1 highway repaired, that is the highway city~2~-city~3~.

Input

Each input file contains one test case. Each case starts with a line containing 3 numbers N (&lt1000), M and K, which are the total number of cities, the number of remaining highways, and the number of cities to be checked, respectively. Then M lines follow, each describes a highway by 2 integers, which are the numbers of the cities the highway connects. The cities are numbered from 1 to N. Finally there is a line containing K numbers, which represent the cities we concern.

Output

For each of the K cities, output in a line the number of highways need to be repaired if that city is lost.

Sample Input

1
2
3
4
3 2 3
1 2
1 3
1 2 3

Sample Output

1
2
3
1
0
0

想法

图算法，连通分量，需要修建的就是连通分量的数量-1

连通分量怎么求呢，早忘了，尴尬
只是数出来而已
BFS/DFS应该都可以
准备一个mark数组，visit就标记，碰到没有标记的点，分量+1

写了一个很臃肿的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//
// Created by Zhao Xiaodong on 2018/7/30.
//
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
void dfs(vector<vector<int>> &m, int k, vector<bool> &visited) {
    if (visited[k]) return;
    visited[k] = true;
    for (int i = 1; i < m[k].size(); i++) {
        if (m[k][i]) {
            dfs(m, i, visited);
        }
    }
}
int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<vector<int>> m(N + 1, vector<int>(N + 1, 0));
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        m[a][b] = m[b][a] = 1;
    }
    for (int i = 0; i < K; i++) {
        int t;
        cin >> t;
        vector<vector<int>> tmp = m;
        for (int j = 1; j <= N; j++) {
            tmp[t][j] = tmp[j][t] = 0;
        }
        vector<bool> visited(N + 1, false);
        visited[t] = true;
        int res = 0;
        for (int k = 1; k <= N; k++) {
            if (visited[k])
                continue;
            res++;
            dfs(tmp, k, visited);
        }
        cout << res - 1 << endl;
    }
    return 0;
}

竟然超时了？？？

F**k，换scanf就过了。。。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//
// Created by Zhao Xiaodong on 2018/7/30.
//
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
void dfs(vector<vector<int>> &m, int k, vector<bool> &visited) {
    if (visited[k]) return;
    visited[k] = true;
    for (int i = 1; i < m[k].size(); i++) {
        if (m[k][i]) {
            dfs(m, i, visited);
        }
    }
}
int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<vector<int>> m(N + 1, vector<int>(N + 1, 0));
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        m[a][b] = m[b][a] = 1;
    }
    for (int i = 0; i < K; i++) {
        int t;
        cin >> t;
        vector<vector<int>> tmp = m;
        for (int j = 1; j <= N; j++) {
            tmp[t][j] = tmp[j][t] = 0;
        }
        vector<bool> visited(N + 1, false);
        visited[t] = true;
        int res = 0;
        for (int k = 1; k <= N; k++) {
            if (visited[k])
                continue;
            res++;
            dfs(tmp, k, visited);
        }
        cout << res - 1 << endl;
    }
    return 0;
}

总结

做PAT，能用scanf、printf，就不要用cin、cout，真的是太坑了。。。

能用全局变量就用全局变量，OJ嘛，管那么多干嘛，所有的都全局，省的传参麻烦

还是没有做OJ的经验啊