一些常用的算法

这些算法和技巧都是我从其他地方看到的，在这里整理了一下。

1. 拓扑排序

一个有向图G的拓扑排序：
存在对于图G的节点编号的一种排列，满足任意一条有向边 [latex](u, v)[/latex]，[latex]u[/latex] 在排列中都出现在 [latex] v [/latex] 的前面。

根据以上定义，可以得出两个结论：

如果有向图G存在环，那么图G不存在拓扑排序
如果图 G 是有向无环图，那么它的拓扑排序可能不止一种。举一个最极端的例子，如果图 G 只有节点没有边，那么任意一种编号的排列都可以作为拓扑排序。

求有向图的拓扑排序有两种，我是从LeetCode上学来的。出处点这里。

1. 深度搜索优先：

设计：

相邻节点：从一个节点 [latex]u[/latex] 出发，通过一条有向边可以到达的所有节点。
对于一个节点 [latex]u[/latex]，如果它的所有相邻节点都已经搜索完成，那么在搜索回溯到 [latex]u[/latex] 的时候，[latex]u[/latex] 本身也变成一个搜索完成的节点。
将已搜索完成的节点存入一个栈中。
假设当前搜索到了节点 [latex]u[/latex]，若其所有相邻节点都已经搜索完成，那么这些节点都已被压入栈中了。此时，可以把节点 [latex]u[/latex] 压入栈中。
从栈顶往栈低看，节点 [latex]u[/latex] 处于栈顶的位置，故 [latex]u[/latex] 出现在所有与 [latex]u[/latex] 相邻的节点的前面。因此节点 [latex]u[/latex] 是满足拓扑排序的。

实现：

对于图中的节点，在搜索过程中三种状态：

未搜索：还未接触（reach）这个节点
搜素中：已经接触到，但还没有回溯到该节点——当前节点还未入栈，正在搜索其相邻的节点
搜索完成：接触并回溯过这个节点，即这点节点已入栈，并且该节点的所有节点都在栈中比其更底部的位置（满足拓扑排序的要求）。

通过上述三种状态，就可给出使用深度优先搜索算法得出拓扑排序的流程。

1. 在每一轮搜索开始时，任意选取一个未曾搜索的节点开始进行深度优先搜索。

2. 将当前搜索的节点 [latex]u[/latex] 标记为搜索中，遍历该节点的每一个相邻节点 [latex]v[/latex]

若 [latex]v[/latex] 为未搜索：搜索节点[latex]u[/latex]，待搜索完成回溯到[latex]u[/latex]
若 [latex]v[/latex] 为搜索中：那么图中存在环，故不存在拓扑排序
若 [latex]v[/latex] 为搜索完成：说明 [latex]v[/latex] 已经在栈中了，而 [latex]u[/latex] 还不在栈中。因此，[latex]u[/latex] 一定比 [latex]v[/latex] 晚入栈，不会影响到 [latex](u,v)[/latex] 之前的拓扑关系，所以不用做任何操作。

3. 当 [latex]u[/latex] 所有相邻的节点都为已完成时，将 [latex]u[/latex] 压入栈中，并标记其为已完成状态。

整个深度优先搜索完成后，如果图中没有环，那么从栈顶到栈底的节点排序即为一种拓扑排序。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        status.resize(numCourses);
        vector<int> ans;

        for(auto temp : prerequisites)
            edges[temp[1]].push_back(temp[0]);

        for(int u=0; u<numCourses && !existLoop; u++)
        {
            if(status[u] == 0)
                dfs(u);
        }

        if(existLoop)
            return(ans);

        ans.resize(numCourses);
        int index = 0;

        while(!record.empty())
        {
            ans[index] = record.top();
            index++;
            record.pop();
        }

        return(ans);
    }

    void dfs(int u) {
        status[u] = 1;

        for(int v : edges[u])
        {
            if(status[v] == 0)
            {
                dfs(v);
                if(existLoop)
                    return;
            }               
            else if(status[v] == 1)
            {
                existLoop = true;
                return;
            }
            else
                continue;
        }

        status[u] = 2;
        record.push(u);
    }

private:
    vector<vector<int>> edges;
    vector<int> status;
    bool existLoop;
    stack<int> record;
};

时间复制度：[latex] O(No. nodes + No. edges) [/latex]
空间复杂度：[latex] O(No. nodes + No. edges) [/latex]

2. 广度搜索优先

设计：

上面的方法是逆向思维——最先放入的节点是拓扑排序中最后的节点。我们可以使用正向思维，按照拓扑排序的顺序放入节点。

对于拓扑排序后的第一个节点，它一定不会有入边。当我们把这个节点放入到栈中后，就可以移除它的所有出边。那么与它相邻的节点就少了一个入边，要是有相邻的节点少了一个入边后就没有入边了，这种情况下就可以把这个相邻的节点放入栈中，重复之前的操作。

实现：

1. 将所有入度为0的节点放入到一个队列（queue）中

2. 从队列的首部取出一个节点

将该节点压入栈中
移除该节点的所有出边，即与其相邻的节点的入度减1；若出现入度为0的相邻节点，将其放入到队列中去
重复第2步，知道队列为空

3. 如果栈中包含了有向图的所有节点，那么从栈底到栈顶的顺序就是有向图的拓扑排序的顺序。否则，该有向图不存在拓扑排序。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        inputDegree.resize(numCourses);

        for(auto temp : prerequisites)
        {
            edges[temp[1]].push_back(temp[0]);
            inputDegree[temp[0]]++;
        }

        queue<int> q;

        for(int i=0; i<numCourses; i++)
        {
            if(inputDegree[i] == 0)
                q.push(i);
        }

        vector<int> ans;

        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            ans.push_back(u);

            for(int v : edges[u])
            {
                inputDegree[v]--;
                if(inputDegree[v] == 0)
                    q.push(v);
            }
        }

        if(ans.size() == numCourses)
            return(ans);
        
        vector<int> e;
        return(e);
    }

private:
    unordered_map<int,vector<int>> edges;
    vector<int> inputDegree;
};

2. 前缀和 + 状态压缩

今天（5/20/2020）我做 LeetCode 每日一题时，除了暴力法之外没有想到其他方法。题目请点这里。我曾以为自己在第一层，官方题解在第三层。直到我看了官方题解后，发现官方题解在第五层，而我还是在第一层。

在求子串或连续子数组中某些元素的出现的次数时，可以使用前缀和。这是一种以空间换时间的方法——将之前储存的结果保存下来，避免重复计算。

这一题的结果有5个字母的状态，我们可以定义一个 struct 去储存，但这里官方题解给出了一种更妙的解法（第五层的解法）。由于每个字母只有两种情况——出现了偶数次（包括0次）和奇数次，那我们就可以用整数的二进制表示来当作这5个字母的状态位。在32位程序中，一个 unsigned 整数是32位，可以表示32个元素的状态。在此题中，这五个字母的状态分别用 0~4 来表示。那么，状态的取值范围就是 [0, 31]。

更强的是，官方题解中并不是储存每个下标的状态，而是储存最早出现此状体的下标，大大节省了空间和时间。

int findTheLongestSubstring(string s) {
	int ans = 0;
	int status = 0;

	vector<int> previous(1 << 5, -1);
	previous[0] = 0;

	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == 'a')
			status ^= 1 << 0;
		else if (s[i] == 'e')
			status ^= 1 << 1;
		else if (s[i] == 'i')
			status ^= 1 << 2;
		else if (s[i] == 'o')
			status ^= 1 << 3;
		else if (s[i] == 'u')
			status ^= 1 << 4;

		if (~previous[status])
			ans = max(ans, i + 1 - previous[status]);
		else
			previous[status] = i + 1;
	}

	return(ans);
}

一些常用的算法

Comments | NOTHING

取消回复