八、查找 🔎

二分查找

可以使用 upper_bound 和 lower_bound 来实现一些查找 这两个函数是使用二分查找实现的 upper_bound：在指定范围内查找大于目标值的第一个元素，不存在则返回 end lower_bound：在指定区域内查找大于等于目标值的第一个元素，不存在则返回 end

二分查找模板

  • 34：在排序数组中查找元素的第一个和最后一个位置
  • 35：给定递增序列，插入目标元素，保持数组递增
  • 2080：设计数据结构，多次查找区间内目标值出现次数

题目

【2187.完成旅途的最少时间】

【162. 寻找峰值】

可以用二分查找优化。

二叉索引树

深度优先搜索

题目

【200. 岛屿数量】

// [200] 岛屿数量 58.81 %  89.21 %
class Solution
{
public:
    void DFS(vector<vector<char>> &grid, int i, int j)
    {
        int row = grid.size();
        int col = grid[0].size();

        grid[i][j] = '0';
        if (i - 1 >= 0 && grid[i - 1][j] == '1')
            DFS(grid, i - 1, j);
        if (i + 1 < row && grid[i + 1][j] == '1')
            DFS(grid, i + 1, j);
        if (j - 1 >= 0 && grid[i][j - 1] == '1')
            DFS(grid, i, j - 1);
        if (j + 1 < col && grid[i][j + 1] == '1')
            DFS(grid, i, j + 1);
    }

    int numIslands(vector<vector<char>> &grid)
    {
        int row = grid.size();
        if (row == 0)
            return 0;
        int col = grid[0].size();
        int res = 0;
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (grid[i][j] == '1')
                {
                    res++;
                    DFS(grid, i, j);
                }
            }
        }
        return res;
    }
};

【574. 省份数量】

// DFS 92.37 % 42.28 %
class Solution
{
public:
    void DFS(vector<vector<int>> &isConnected, vector<int> &isVisited, int nodes, int startnode)
    {
        for (int i = 0; i < nodes; i++)
        {
            if (isConnected[startnode][i] == 1 && !isVisited[i])
            {
                isVisited[i] = 1;
                DFS(isConnected, isVisited, nodes, i);
            }
        }
    }
    int findCircleNum(vector<vector<int>> &isConnected)
    {
        int nodes = isConnected.size();
        vector<int> isVisited(nodes);
        int provinces = 0;
        for (int i = 0; i < nodes; i++)
        {
            if (!isVisited[i])
            {
                DFS(isConnected, isVisited, nodes, i);
                provinces++;
            }
        }
        return provinces;
    }
};

广度优先搜索

题目

【574. 省份数量】

// BFS 9.95 %  18.16 %
class Solution
{
public:
    int findCircleNum(vector<vector<int>> &isConnected)
    {
        int nodes = isConnected.size();
        vector<int> isVisited(nodes);
        int provinces = 0;
        queue<int> q;
        //从i开始作为起点，每个没被访问过的都进行一次BFS搜索
        for (int i = 0; i < nodes; i++)
        {
            if (!isVisited[i])
            {
                // BFS模板
                q.push(i);
                while (!q.empty())
                {
                    int j = q.front();
                    q.pop();
                    // 更新访问的数组
                    isVisited[j] = 1;
                    //将当前的所有与之相连的节点加入队列
                    for (int k = 0; k < nodes; k++)
                    {
                        if (isConnected[j][k] == 1 && !isVisited[k])
                            q.push(k);
                    }
                }
                provinces++;
            }
        }
        return provinces;
    }
};

并查集

典型题目

【574. 省份数量】

计算连通子图的个数，只有一个节点也算一个子图。可以用三种方法，DFS、BFS 和并查集。都是非常经典的写法，值得记忆。

//并查集 15.16 % 46.66 %
class Solution
{
public:
    int Find(vector<int>& parent,int index)
    {
        //向上递归查找
        if(parent[index]!=index)
            parent[index] = Find(parent,parent[index]);
        //返回最深的祖先
        return parent[index];
    }

    void Union(vector<int>& parent, int index1, int index2)
    {
        //合并祖先
        parent[Find(parent,index1)] = Find(parent,index2);
    }

    int findCircleNum(vector<vector<int>> &isConnected)
    {
        int nodes = isConnected.size();
        vector<int> parent(nodes);
        int provinces = 0;
        for(int i=0;i<nodes;i++)
            parent[i] = i;
        for(int i=0;i<nodes;i++)
        {
            for(int j=i+1;j<nodes;j++)
            {
                if(isConnected[i][j]==1)
                    Union(parent,i,j);
            }
        }
        for(int i=0;i<nodes;i++)
        {
            if(parent[i]==i)
                provinces++;
        }
        return provinces;
    }
};

results matching ""

    No results matching ""