Neo's Blog

不抽象就无法深入思考
不还原就看不到本来面目!

0%

Posted on Edited on In , Valine:

输入两个链表，找出它们的第一个公共结点。

当不存在公共节点时，返回空节点。

样例
给出两个链表如下所示：
A： a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3

输出第一个公共节点c1

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *h1, ListNode *h2) {
        int c1 = 0, c2 = 0;
       for (auto p = h1; p; p = p->next) c1++;
       for (auto p = h2; p; p = p->next) c2++;
       
       auto p1 = h1;
       auto p2 = h2;
        while (c2 < c1) {
            p1 = h1 = h1->next;
            c2++;
        }
        while (c1 < c2) {
            p2 = h2 = h2->next;
            c1++;
        }

       while (p1 && p2 && p1 != p2) {
           p1 = p1->next;
           p2 = p2->next;
       }

       return p1;
    }
};

Posted on Edited on Valine:

建立秩序，省却搜索。—德国谚语

计算机解决问题，就靠搜索。 而通过建立秩序，可以让计算机更聪明的完成搜索。

而这里的建立秩序，就包括：

  1. 为具体场景设计更合适的数据结构。这一块对应数据结构。
  2. 为具体场景设计更好的搜索策略。 这一块对应算法。

两大类存储引擎：

日志结构（log-structured） 的存储引擎，以及面向页面（page-oriented） 的存储引擎（例如B树）。

SSTable

排序字符串表（Sorted String Table）

参考：https://vonng.gitbooks.io/ddia-cn/content/glossary.html

Posted on Edited on Valine:

一般ACM或者笔试题的时间限制是1秒或2秒。

在这种情况下，C++代码中的操作次数控制在 $10^7$ 为最佳。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

n≤30 => 指数级别, dfs+剪枝，状态压缩dp

n≤100 => $O(n^3)$，floyd，dp，高斯消元

n≤1000 => $O(n^2),O(n^2logn)$，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford

n≤10000 => $O(n*\sqrt{n})$，块状链表、分块、莫队

n≤100000 => $O(nlogn)$ => 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分

n≤1000000 => $O(n)$, 以及常数较小的 $O(nlogn)$ 算法 => 单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 $O(nlogn)$ 的做法：sort、树状数组、heap、dijkstra、spfa

n≤10000000 => $O(n)$， 双指针扫描、kmp、AC自动机、线性筛素数

n≤$10^9$ => $O(\sqrt{n})$， 判断质数

n≤$10^{18}$ => $O(logn)$， 最大公约数，快速幂

n≤$10^{1000}$ => $O((logn)^2)$， 高精度加减乘除

n≤$10^{100000}$ => $O(logk×loglogk)$，k表示位数， 高精度加减、FFT/NTT

Posted on Edited on In Valine:

区间大类的常见套路

猜出一般步骤

  1. 对区间进行排序（按照左端点、右端点）
  2. 挨个对区间进行进行枚举，选择局部最优解

证明选择的策略是否是正确的

经典题目

区间选点问题

问题描述：给定N个区间[a,b]，取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以重复）

本质：取尽可能的点，使他们可以穿过所有的区间。

解法：

  1. 按照右端点排序

  2. 枚举区间，选择区间的右端点作为候选集（显然最右边是局部最优解）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range + n);

    int res = 0, ed = -2e9;
    for (int i = 0; i < n; i ++ )
        if (ed < range[i].l)
        {
            res ++ ;
            ed = range[i].r;
        }

    printf("%d\n", res);

    return 0;
}

最大不相交区间数量

类似于选课，课程有交集，我们需要选择最多的课程，使得课程之间没有时间冲突。

本质：选择尽可能多的区间，使他们没有任何重合。

  1. 按照右端点排序

  2. 枚举区间，选择区间的右端点作为候选集（显然最右边是局部最优解）

如果我多选择一个区间，就会出现相交；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>eg[i].l>>eg[i].r;

    }
    sort(eg, eg+n);
    int res=0, ed=-2e9;
    for(int i=0;i<n;i++){
        if(ed<eg[i].l) {
            res++, ed=eg[i].r;
        }else{

        }
    }
    cout<<res;
}

区间分组

给定N个闭区间，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。 输出最小组数。

本质：对区间进行分组，组内无交；极限思考：每一个区间一组是满足条件，但是组数太多；

例题：

主持人调度（每一个主持人不能主持两场节目，使主持人最少）

排序 + 利用小根堆来动态维护最大值（max_r)

top()返回最小的最大值，既然最小的都有交集，更大的就更不用说啦。

  1. 按照左边排序
  2. 枚举区间，能否将该区间加入到当前分组中（L[i] > Max_r）
    1. 如果不存在这样子的组，则开新组
    2. 加入到当前组中，更新max_r
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

bool cmd(const PII& a, const PII& b) {
    return a.first < b.first;
}

sort(a, a+n, cmp);

priority_queue<int, vector<int>, greater<int>> q;

q.push(a[0].second);
for (int i = 1; i < n; ++i) {
    int ed = q.top();
    if (a[i].first > ed) {
        q.pop(); //先pop，再push，相当于更新了该分组的max_r
    }
    q.push(a[i].second);
}

return q.size();

区间覆盖

给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出 −1。

本质：多个区间都能够覆盖某个start位置，我应该选择哪一个呢？

  1. 左端点从小到大排序
  2. 从前往后依次枚举每个区间，在所有能覆盖start的区间中，选择右端点最大的区间，然后将start更新为右端点的最大值。
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
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;

typedef pair<int, int> PII;

const int N = 1e5 + 10;
PII a[N];

bool cmp(const PII& a, const PII& b) {
    return a.first < b.first;
}

int main() {
    int res = 0, i = 0;
    bool success = false;
    for (i = 0; i < n; ) {
        int max_r = -INF;
        while (i < n && a[i].first <= lr) {
            max_r = max(max_r, a[i].second);
            i++;
        }
        
        if (max_r == -INF) { //没有找到任何能够覆盖start的区间
            res = -1;
            break;
        }
        
        res++;
        if (max_r >= rr) {
            success = true;
            break;
        } 
        lr = max_r;
    }
    
    if (!success) res = -1;
}

合并区间

  1. 首先对区间按照起始端点（左断点）进行升序排序，
  2. 然后逐个判断当前区间是否与前一个区间重叠，如果不重叠的话将当前区间直接加入结果集，反之如果重叠的话，就将当前区间与前一个区间进行合并。
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
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<PII> d(intervals.size());
        vector<vector<int>> res;
        int n = intervals.size();
        for (int i = 0; i < n; ++i) {
            d[i].first = intervals[i][0];
            d[i].second = intervals[i][1];
        }
        sort(d.begin(), d.end());
        int st = 0, ed = -inf;
        for (int i = 0; i < n; ++i) {
            if (d[i].first > ed) {
                if (ed != -inf) {
                    vector<int> t = {st, ed};
                    res.push_back(t);
                } 
                //把当前区间扩充一下
                st = d[i].first, ed = d[i].second;
            }
            else {
                ed = max(ed, d[i].second);
            }
        }

        vector<int> t = {st, max(ed, d.back().second)};
        res.push_back(t);

        return res;
    }
};

Posted on Edited on In , Valine:

数字以0123456789101112131415…的格式序列化到一个字符序列中。

在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数求任意位对应的数字。

样例
输入：13

输出：1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int digitAtIndex(int n) {
        if(n<=9){
            return n;
        }
        int len = 1;
        long count = 9;
        int start = 1;
        while(n>len*count){
            n-=len*count;
            len+=1;
            count*=10;
            start *= 10;
        }
        start += (n-1)/len;
        string str = to_string(start);
        return str[(n-1)%len]-48;
    }
};

Posted on Edited on In , Valine:

题目描述

0, 1, …, n-1这n个数字(n>0)排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。

求出这个圆圈里剩下的最后一个数字。

样例
输入：n=5 , m=3

输出：3

思路

  1. 递归

代码

1
2
3
4
5
6
7
class Solution {
public:
    int lastRemaining(int n, int m){
        if (n == 1) return 0;
        return (lastRemaining(n - 1, m) + m) % n;
    }
};

Posted on Edited on In , Valine:

实现函数double Power(double base, int exponent)，求base的 exponent次方。

不得使用库函数，同时不需要考虑大数问题。

注意：

不会出现底数和指数同为0的情况
当底数为0时，指数一定为正
样例1
输入：10 ，2

输出：100
样例2
输入：10 ，-2

输出：0.01

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
class Solution {
public:
    double Power(double base, int e) {
        if (e < 0) {
            return 1.0 / Power(base, -e); 
        }
        
        double res = 1.0;
        double t = base;
        while (e) {
            if (e & 1) res = res * t;
            t = t * t;
            e >>= 1; //执行次数是1不同于e = e & (e - 1)
            
        }
        
        /*
        double res = 1.0;
        for (int i = 0; i < e; ++i) {
            res *= base;
        }
        */
        return res;
    }
    
};

Posted on Edited on Valine:

题目描述

请你写一个函数StrToInt，实现把字符串转换成整数这个功能。

当然，不能使用atoi或者其他类似的库函数。

样例
输入：”123”

输出：123
注意:

你的函数应满足下列条件：

忽略所有行首空格，找到第一个非空格字符，可以是 ‘+/−’ 表示是正数或者负数，紧随其后找到最长的一串连续数字，将其解析成一个整数；
整数后可能有任意非数字字符，请将其忽略；
如果整数长度为0，则返回0；
如果整数大于INT_MAX(2^31 − 1)，请返回INT_MAX；如果整数小于INT_MIN(−2^31) ，请返回INT_MIN；

常规解法

我们先遍历一遍，找到字符串的长度，从而得出最高位的权重(10的几次方？)
然后再遍历一遍，进行累加计算。
时间复杂度：$O(2n)$

优化思路

我们可以在一遍搞定，每遍历到一个新的元素，需要做的步骤是：

(1) sum *= 10

(2) sum += NewElement

新的时间复杂度：$O(n)$

该题目其他部分无非就是模拟了，做模拟题目的时候切记思路清晰。

优化版代码

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
class Solution {
public:
    int strToInt(string s) {
        int i = 0;
        int sign = 1;
        bool has_num = false;
        long long val = 0;
        while (s[i]) {
            if (s[i] == ' ') {}
            else if (s[i] == '+'  || s[i] == '-') {
                if (!has_num) {
                    sign = s[i] == '+' ? 1 : -1;
                }
            } else if (s[i] >= '0' && s[i] <= '9') {
                has_num = true;
                val = val * 10 + (s[i] - '0');
                if (sign * val > INT_MAX) {return INT_MAX;}
                if (sign * val < INT_MIN) {return INT_MIN;}
            }
            else {
                if (!has_num) {
                    return 0;
                }
            }
            i++;
        }
        
        return sign * val;
    }
    
};

Posted on Edited on Valine:

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

例如输入数组[3, 32, 321]，则打印出这3个数字能排成的最小数字321323。

样例
输入：[3, 32, 321]

输出：321323
注意：输出数字的格式为字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    
    static int compare(int a, int b) {
        string ab = to_string(a) + to_string(b);
        string ba = to_string(b) + to_string(a);
        return ab < ba;
    }
    
    string printMinNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), compare);   
        
        string res;
        for (auto x : nums) {
            res += to_string(x);
        }
        return res;
    }
};