建堆O(n)时间复杂度证明

建堆复杂度先考虑满二叉树,计算完全二叉树建堆复杂度基本相同。

对满二叉树而言,第i层(根为第0层)有$2^i$个节点。由于建堆过程自底向上,以交换作为主要操作,因此第i层任意节点在最不利情况下,需要经过$(n-i)$次交换操作才能完成以该节点为堆根节点的建堆过程。因此,时间复杂度计算如下:

$T(n) = 2^0 * (n - 0) + 2^1 * (n - 1) + … + 2^n * (n - n) = sum((n - i) * 2^i)$

采用错位相减法:

  • 原式乘2得:
  • $T(n) * 2 = 2^1 * (n - 0) + 2^2 * (n - 1) + … + 2^{n+1} * (n - n) = sum((n - i) * 2^{i+1})$
  • 原式如下:
  • $T(n) = 2^0 * (n - 0) + 2^1 * (n - 1) + … + 2^n * (n - n) = sum((n - i) * 2^i)$
  • 相减得:
  • $2T(n) - T(n) = -n + 2^1 + 2^2 + … + 2^n = 2 * (1 - 2^n) / (1 - 2) - n = 2^{n+1} - 2 - n$

上面推导中,n为层数编号(自0层根节点开始)。故总节点数为$(1 + 2 + 4 + … + 2^n) = 2^{n+1} - 1$。渐进时,忽略减1取$N = 2^{n+1}$。

$T(N) = 2^{n+1} - n - 2 = N * (1 - logN / N - 2 / N) ≈ N$

故时间复杂度为$O(N)$,得证。

左偏树和斜堆

左偏树的性质

  • 本节点的键值key小于其左右子节点键值key(与二叉堆相同);
  • 本节点的左子节点的距离大于等于本节点的右子节点(这意味着每个节点中除了要存储键值外, 还需要一个额外的dist存储距离);
  • 节点的距离是其右子节点的距离+1(这意味着, 一个节点的dist是从它出发到达最近终端节点的距离);

斜堆的性质

  • 本节点的键值key小于其左右子节点键值key;
  • 斜堆节点不存储距离dist值, 取而代之的是在每次合并操作时都做swap处理(节省了存储空间);

大数乘法(Multiply Strings)

大数乘法的算法

大数乘法的关键在于如何用字符串来模拟大数乘法。方法有如下几种:模拟普通的手算乘法、利用代数方法优化的乘法、快速傅立叶变换FFT

各算法的优点

  • 模拟普通手算乘法:算法简单、空间复杂度小。时间复杂度为O(n^2)
  • 利用代数方法优化的乘法:使用递归求解,空间复杂度较大。算法复杂,需要定义大数加法大数减法。时间复杂度降低到O(n^1.5)
  • 快速傅立叶变换FFT:基于FFT的大数乘法时间复杂度O(nlogn)。快速傅立叶变换据数值分析老师说是本世纪最为伟大的算法。

下边主要对利用代数方法优化的乘法进行介绍。

分析

代数优化

  • 假设大数P、Q的长度为m和n,P = (A * 10^k + B)Q = (C * 10^k + D)
  • k = min(m / 2, n / 2)
  • PQ = (A * 10^k + B)(C * 10^k + D) = AC * 10 ^2k + (AD + BC) * 10^k + BD
  • 乘法操作作为主要操作,采用master定理可知,时间复杂度为O(n^2)。此时与普通的手算乘法并没有不同。
  • 用于减少时间复杂度的关键(A - B)(C - D) = AC - AD - BC + BD
  • 带入后得,AC * 10 ^2k + (AC + BD - (A-B)(C-D)) * 10^k + BD
  • 由于我们以乘法操作作为主要操作,因此每一层递归中只需要3次乘法。因此时间复杂度减少为O(n^1.5)

LeetCode174-Dungeon Game

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2(K) -3 3
-5 -10 1
10 30 -5(P)

Notes:

  • The knight’s health has no upper bound.
  • Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

分析

骑士只能向下或向右移动,每个方格如果是正数表示加血,如果是负数表示扣血。血量等于或低于0时骑士死亡。求骑士从左上角出发并顺利到达右下角条件下的最小初始血量。

初步分析本题采用动态规划。分别从正向反向考虑。

正向

按正向考虑,dp[i][j]表示从起点出发到(i, j)点所需的最小初始血量。但发现计算dp[i][j]时不能单纯地取dp[i-1][j]dp[i][j-1]的较小值。原因在于,当前到达(i, j)位置时的剩余血量会对后面的结果产生影响。

简单地说,比如A=dp[i-1][j]B=dp[i][j-1]remainAremainB分别对应A和B的剩余血量。当A>B同时remainA>remainB时,如果我们选择B,在后续路径中如果有较大的负值出现,那么B较小的优势并不能传递,此时剩余血量反而更重要。

但引入剩余血量对路径的选择又会使算法变的复杂。所以从反向考虑。

反向

按反向考虑,dp[i][j]表示从(i, j)点出发到达右下角点所需的踏入(i, j)点前的最小剩余血量。那么,状态转移方程如下:

1
dp[i][j]=max{ min{ dp[i+1][j], dp[i][j+1] } - dungeon[i][j], 0 }

在边界上的情况需要做简单的处理。

由于反向时考虑了从当前点到终点的路径,因此dp[0][0]就是踏入(0,0)点前的最小剩余血量,即最小初始血量。这里可以发现,正向考虑时纠结的剩余血量,在这里就是求的dp[i][j]。反向求解过程非常自然,最重要的就是正确选择了dp的目标

AC代码

1
class Solution {
2
public:
3
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
4
        int row = dungeon.size();
5
        int col = dungeon[0].size();
6
        for (int i = row - 1; i >= 0; --i) {
7
            for (int j = col - 1; j >= 0; --j) {
8
                solveCurrentMinValue(dungeon, row, col, i, j);
9
            }
10
        }
11
        return dungeon[0][0] + 1;
12
    }
13
14
    void solveCurrentMinValue(vector<vector<int>>& dungeon, int row, int col, int i, int j) {
15
        pair<int, int> rightPoint(make_pair(i, j + 1)), lowerPoint(make_pair(i + 1, j));
16
        int lower, right, min, MAX_INT;
17
        bool hasLower, hasRight;
18
        lower = right = 0;
19
        hasLower = hasRight = true;
20
        MAX_INT = 999999999;
21
22
        if (rightPoint.first < row && rightPoint.second < col) {
23
            right = dungeon[rightPoint.first][rightPoint.second];
24
        } else {
25
            hasRight = false;
26
        }
27
        if (lowerPoint.first < row && lowerPoint.second < col) {
28
            lower = dungeon[lowerPoint.first][lowerPoint.second];
29
        } else {
30
            hasLower = false;
31
        }
32
33
        if (!hasLower && !hasRight) {
34
            min = 0;
35
        } else {
36
            min = minValue(hasLower ? lower : MAX_INT, hasRight ? right : MAX_INT);
37
        }
38
39
        int current = min - dungeon[i][j];
40
        dungeon[i][j] = current >= 0 ? current : 0;
41
    }
42
43
    int minValue(int x, int y) {
44
        return x < y ? x : y;
45
    }
46
};

LeetCode187-Repeated DNA Sequences

思路

  • 由于碱基无非ACGT四种类型,可以使用00 01 10 11四个状态代替ACGT四种碱基,比如AAGCT就是00 00 10 01 11,对任意一个长度为10的子串都可以转化使用20个位的int值hint。这样就可将unordered_set<string> repeated转变为unordered_set<int> repeated, 一定程度上减少了所需的存储空间。
  • 对于如何去重, 其一可以先收集所有答案,再sort,unique去重,当然这样很慢也很麻烦。其二,可以再构造一个unordered_set check,用于存储已经存入answer中的重复子串对应的hint值;
  • 值得一提的是,每次从s[i]->s[i+9]变为s[i+1]->s[i+10],使用了这样一个方法:
    1
    hint = ((hint & eraser) << 2) + ati[s[i]];
    其中eraser是一个宏定义, 值为0x3ffff, 二进制是00111111111111111111, 用于擦除hint中的最高2位s[i]碱基对应的值, 再左移2, 最后加上s[i+10]的碱基对应的值。
1
class Solution {
2
public:
3
    #define eraser 0x3ffff
4
    vector<string> findRepeatedDnaSequences(string s) {
5
        vector<string> answer;
6
        int hint = 0;//存储长度为10的子串翻译后的int值
7
        if (s.size() < 10)
8
            return answer;
9
        unordered_set<unsigned int> repeated, check;//repeated存储已出现的子串, check用于防止重复答案
10
        unordered_map<char, unsigned int> ati{{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};//此处ati是存储各碱基对应的值00 01 10 11(c++11新语法)
11
        for (int i = 0; i != 10; ++i) {
12
            hint = (hint << 2) + ati[s[i]];//用s的前10个碱基构造初始hint值
13
        }
14
        repeated.insert(hint);
15
        for (int i = 10; i != s.size(); ++i) {
16
            hint = ((hint & eraser) << 2) + ati[s[i]]; //子串变化对应hint值变化
17
            unordered_set<unsigned int>::iterator it = repeated.find(hint);
18
            if (it != repeated.end()) {
19
                it = check.find(hint);
20
                if (it == check.end()) {
21
                    answer.push_back(string(s, i - 9, 10));
22
                    check.insert(hint);
23
                }
24
            }
25
            else
26
                repeated.insert(hint);
27
        }
28
        return answer;
29
    }
30
};

一开始由于忽略了移位与其他运算符的优先级关系, 一直出问题,郁闷:(

LeetCode 200-Number of Islands

分析

只需要对每一个陆地区域做一次dfs,每次dfs中将已经遍历的陆地网格“1”变为水域网格“0”(防止再次遍历导致重复)。对每次dfs计数,总共dfs的次数即为岛屿总数。应注意,grid为空的特殊情况应该排除。

1
class Solution {
2
public:
3
    int numIslands(vector<vector<char>> &grid) {
4
        int row = grid.size();
5
        if (!row) return 0;
6
        int col = grid[0].size();
7
        int count = 0;
8
9
        for (unsigned i = 0; i != row; ++i) {
10
            for (unsigned j = 0; j != col; ++j) {
11
                if (grid[i][j] == '1') {
12
                    dfs(grid, i, j); ++count;
13
                }
14
            }
15
        }
16
17
        return count;
18
    }
19
    void dfs(vector<vector<char>> &grid, unsigned i, unsigned j) {
20
        int dx[4] = {1, 0, -1, 0};
21
        int dy[4] = {0, 1, 0, -1};
22
        int row = grid.size(), col = grid[0].size();
23
        grid[i][j] = '0';
24
25
        for (int k = 0; k != 4; ++k) {
26
            int new_i = i + dx[k], new_j = j + dy[k];
27
            if (new_i >=0 && new_i < row && new_j >= 0 && new_j < col && grid[new_i][new_j] == '1')
28
                dfs(grid, new_i, new_j);
29
        }
30
    }
31
};

LeetCode 201-Bitwise AND of Numbers Range

分析

如果真的在范围[m, n]内按顺序逐个数字做&操作显然效率不高。那么我们可以先列出一些数字去寻找规律:

12 1100 110 11
13 1101 110 11
14 1110 111 11
15 1111 111 11

上表区间中在移位过程中,逐渐抹去最后一位,最终会在某一次移位后区间内所有数的值相同(1101->110->11),移位次数为2,该范围内所有数按位与操作以后结果为1100,即12。由此我们可以知道,低位部分在范围内按位与操作中会因为0的存在而消去为0,只有高位部分会得以保留。因此我们可以用一个count计数器记录移位次数(即低位0的个数),而最终移位结果均一致时(如例子中最终为二进制11),即为其高位部分。此时只需将高位部分复原即可,也就是11->110->1100,做2次向左移位复原。
当然在计算过程中我们并不需要对区间内所有数做这种操作,只需对区间最小值m和最大值n进行操作(因为区间首尾是区分度最大的两个数,对区间内所有数做右移时,最有可能不相同的肯定是m和n)。

注意

当较小的数移位后为0时,就应该停止循环。最终结果肯定也是0。

1
class Solution {
2
public:
3
    int rangeBitwiseAnd(int m, int n) {
4
        int count = 0;//初始化计数器
5
        while (m && m != n) {//m为0时或m == n时退出循环
6
            ++count;//统计低位0的个数
7
            m >>= 1; n >>= 1;//抹去低位
8
        }
9
        return m << count;//低位复原, 因为0 << count仍为0, 因此此处不做区分
10
    }
11
};

LeetCode202-Happy Number

分析

题目中已经给了提示,当能出现1时,即退出循环返回true;如出现了一个不为1的循环则返回false(如4, 16, 37, 58, 89, 145, 42, 20, 4, …)。对happy number的详细描述见wiki百科:Happy Number。wiki还对Happy primes和Harshad number做了一些解释。为了快速确定是否发生非1的重复,使用unordered_set来记录已经出现过的数(我们并不关心数字的顺序,因此用hash效率更高)。

1
class Solution {
2
public:
3
    bool isHappy(int n) {
4
        int sum;
5
        unordered_set<int> check;
6
        check.insert(n);
7
        while (n != 1) {
8
            sum = 0;
9
            while (n) {
10
                int t = n % 10;
11
                n /= 10;
12
                sum += t * t;
13
            }
14
            if (check.find(sum) != check.end())
15
                return false;
16
            check.insert(sum);
17
            n = sum;
18
        }
19
        return true;
20
    }
21
};

LeetCode204-Count Primes

分析

这个题相当于求小于n的所有质数,曾在编程之美中看到过一个求一组质数的算法,叫厄拉多塞筛法,时间复杂度仅有O(nloglogn),这是一个相当好的算法(如果从1到n-1分别判断质数,时间复杂度为O(nsqrt(n)))。
厄拉多塞筛法的步骤:建立从2到n的集合G={2, 3, 4, …, n},每次从集合中取出最小的数A,这个数就是质数;然后将数A * times从集合中删除,其中1<=times<=n/A。得到一个新的集合G’,重复上述步骤直到集合为空,就取出了所有质数。
举例一个集合{2, 3, 4, …, 12}:
stp1:最小值为2,取出2并删除2,4,6,8,10,12,集合变为{3, 5, 7, 9, 11};
stp2:最小值为3,取出3并删除3,6,9,集合变为{5, 7, 11}

最后得到质数为2,3,5,7,11。

注意

  1. 一开始我用unordered_set来标记一个数是否被删除,后来内存使用超出要求。后来改用bool数组来记录就AC了。
  2. 注意是小于n,而非小于等于n。
1
class Solution {
2
public:
3
    int countPrimes(int n) {
4
        bool isDeleted[n];
5
        for (unsigned i = 0; i < n; ++i)
6
            isDeleted[i] = false;
7
8
        int count = 0;
9
        for (unsigned i = 2; i < n; ++i) {
10
            if (!isDeleted[i]) {
11
                ++count;
12
                for (unsigned times = 1; i * times <= n; ++times) {
13
                    isDeleted[i*times] = true;
14
                }
15
            }
16
        }
17
        return count;
18
    }
19
};

LeetCode 207-Course Schedule

分析

很显然,这是一个有向无环图的判断问题。只要所有课程中出现了环,就不可能修满所有课程。有向无环图的判断可采用dfs或bfs,至于生成图的形式可以是邻接矩阵,也可以是邻接表。为了减小时间复杂度,本题考虑采用邻接表的方法。

1
class Solution {
2
public:
3
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
4
        if (!prerequisites.size()) return true;
5
        vector<vector<int>> map(numCourses, vector<int>());
6
        for (int i = 0; i < prerequisites.size(); ++i) {
7
            map[prerequisites[i][0]].push_back(prerequisites[i][1]);
8
        }
9
        vector<bool> isVisited(numCourses, false);
10
        for (int i = 0; i < numCourses; ++i) {
11
            if (!isVisited[i]) {
12
                vector<bool> onStack(numCourses, false);
13
                if (hasCycle(map, i, isVisited, onStack))
14
                    return false;
15
            }
16
        }
17
        return true;
18
    }
19
    bool hasCycle(vector<vector<int>> &map, int i, vector<bool> &isVisited, vector<bool> &onStack) {
20
        isVisited[i] = true;
21
        onStack[i] = true;
22
        for (int k : map[i]) {
23
            if (onStack[k])
24
                return true;
25
            else
26
                if (hasCycle(map, k, isVisited, onStack))
27
                    return true;
28
        }
29
        onStack[i] = false;
30
        return false;
31
    }
32
};
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×