【C++笔试强训】如何成为算法糕手Day7

小文要打代码

发布于 2024-10-16 15:28:37

830

发布于 2024-10-16 15:28:37

文章被收录于专栏：C++学习历程

字符串中找出连续最长的数字串

牛客网做题链接：字符串中找出连续最长的数字串_牛客题霸_牛客网 (nowcoder.com)

思路：

模拟+双指针。

当j指针和i指针之间长度len大于之前的值时更新len

#include <iostream>
using namespace std;
#include<string>
int main() {
  string str;

  cin>>str;
  int begin=-1,len=0;

  for(int i=0;i<str.size();i++)
  {
    int j=i;
    while(j<str.size() && str[j]>='0' && str[j]<='9')j++;
    if(j-i>len)
    {
        begin=i;
        len=j-i;
    }
    i=j;
  }
  cout<<str.substr(begin,len)<<endl;
  
}

岛屿数量

leetcode网做题链接：200. 岛屿数量 - 力扣（LeetCode）

思路：

深度优先遍历DFS

目标是找到矩阵中 “岛屿的数量” ，上下左右相连的 1 都被认为是连续岛屿。

dfs方法：设目前指针指向一个岛屿中的某一点 (i, j)，寻找包括此点的岛屿边界。

从 (i, j) 向此点的上下左右 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 做深度搜索。
终止条件：
- (i, j) 越过矩阵边界;
- grid[i][j] == 0，代表此分支已越过岛屿边界。
搜索岛屿的同时，执行 grid[i][j] = ‘0’，即将岛屿所有节点删除，以免之后重复搜索相同岛屿。
主循环：
- 遍历整个矩阵，当遇到 grid[i][j] == ‘1’ 时，从此点开始做深度优先搜索 dfs，岛屿数 count + 1 且在深度优先搜索中删除此岛屿。
复杂度：所有的数遍历一遍，所以复杂度是O(N*M)

class Solution {
public:
    void dfs(vector<vector<char>>& grid, int i, int j)
    {
        // 当前部分走过了，因此把当前部分置为0
        grid[i][j] = '0';
        // 依次看看上下左右是不是还有同属岛屿的其他部分
        // 若有，则依次遍历并置为0
        if (i > 0 && grid[i-1][j] == '1')
            dfs(grid, i-1, j);
        if (i < grid.size()-1 && grid[i+1][j] == '1')
            dfs(grid, i+1, j);
        if (j > 0 && grid[i][j-1] == '1')
            dfs(grid, i, j-1);
        if (j < grid[0].size()-1 && grid[i][j+1] == '1')
            dfs(grid, i, j+1);
    }
 
    int numIslands(vector<vector<char>>& grid) {
        // 分别记录行、列以及岛屿总数
        int row = grid.size();
        int col = grid[0].size();
        int cnt = 0;
        // 从第一行第一列开始，寻找有没有是'1'的位置，若有，则登岛遍历，岛屿数加1
        for (int i = 0; i < row; ++i)
        {
            for (int j = 0; j < col; ++j)
            {
                if (grid[i][j] == '1')
                {
                    dfs(grid, i, j);
                    ++cnt;
                }
            }
        }
        // 返回岛屿的总数
        return cnt;
    }
};

广度优先遍历 BFS

主循环和思路一类似，不同点是在于搜索某岛屿边界的方法不同。
bfs 方法：
- 借助一个队列queue，判断队列首部节点(i, j)是否未越界而且为1
  - 如果是则置（删除此岛屿），并将此节点上下左右节点(i+1,j),(i-1,j),(i,j+1),(i,j-1)加入队列
  - 如果不是则跳过此节点
- 循环pop队列首节点，直到整个队列为空，此时已经遍历完此岛屿

class Solution {
public:
 
    int numIslands(vector<vector<char>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        int cnt = 0;
 
        for (int i = 0; i < row; ++i)
        {
            for (int j = 0; j < col; ++j)
            {
                // 只要找到了一个为'1'的，那么登岛
                if (grid[i][j] == '1')
                {
                    // 当前找到的新岛屿，数量加1
                    ++cnt;
                    // 广度优先，那么需要借助队列来实现
                    queue<pair<int, int>> bfs_q;
                    // 把当前走过的地方置0
                    grid[i][j] = 0;
                    bfs_q.push({i, j});
                    // 只要队不空就循环
                    while (!bfs_q.empty())
                    {
                        // 取出队头元素，出队
                        auto cur = bfs_q.front();
                        bfs_q.pop();
                        // 判断队头元素的上下左右是否有岛屿的其他部分，有的话则入队并置0
                        if (cur.first > 0 && grid[cur.first-1][cur.second] == '1')
                        {
                            bfs_q.push({cur.first-1, cur.second});
                            grid[cur.first-1][cur.second] = 0;
                        }
                        if (cur.first < row-1 && grid[cur.first+1][cur.second] == '1')
                        {
                            bfs_q.push({cur.first+1, cur.second});
                            grid[cur.first+1][cur.second] = 0;
                        }
                        if (cur.second > 0 && grid[cur.first][cur.second-1] == '1')
                        {
                            bfs_q.push({cur.first, cur.second-1});
                            grid[cur.first][cur.second-1] = 0;
                        }
                        if (cur.second < col-1 && grid[cur.first][cur.second+1] == '1')
                        {
                            bfs_q.push({cur.first, cur.second+1});
                            grid[cur.first][cur.second+1] = 0;
                        }
                    }
                }
            }
        }
        return cnt;
    }
};

并查集

是一种树型的数据结构，用于处理一些不相交的合并以及查询问题。

步骤：

遍历这个二维数组，将所有的1都认为是一个单独的集合
遍历这个二维数组，对于每一个1，只看它的左边和上边，如果发现有1，就做union操作（为甚只看左边和上边，因为右边和下边是对称的，而我们从左到右，从上到下遍历，所以不会重复和遗落）

class Solution {
public:
    int find(int idx)
    {
        // 若当前节点的父节点就是自己，那么只需要返回自己
        if (parent[idx] == idx) 
            return idx;
        // 路径压缩，只要idx节点的父节点不是整个集合的头节点，那么就把路径上每个节点都向集合的头结点
        parent[idx] = find(parent[idx]);
        // 返回idx的父节点（也是整个集合的头节点）
        return parent[idx];
    }
 
    void union_n (int idx_1, int idx_2)
    {
        int par_1 = find(idx_1);
        int par_2 = find(idx_2);
        // 若idx_1和idx_2的父节点是同一个，那就不做任何操作
        if (par_1 == par_2) 
            return;
        // 原本par_1和par_2分别是idx_1和idx_2的父节点，因此都指向自己
        // 这个赋值将par_1的父节点指向了par_2，完成了合并操作
        parent[par_1] = par_2;
        // 每当一块陆地拼进了岛屿，那么陆地数量自减
        --land_num;
    }
 
    int numIslands(vector<vector<char>>& grid) {
        // 输入的行与列
        int row = grid.size();
        int col = grid[0].size();
        // 初始化陆地数量以及数组
        land_num = 0;
        parent = vector<int> (row*col, -1);
        // 构建并查集
        for (int i = 0; i < row; ++i)
            for (int j = 0; j < col; ++j)
            {
                if (grid[i][j] == '1')
                    ++land_num;
                // 初始化父亲节点都为自己
                parent[i*col + j] = i*col + j;
            }
        // 进行并查的过程
        for (int i = 0; i < row; ++i)
            for (int j = 0; j <col; ++j)
            {
                if (grid[i][j] == '1')
                {
                    // 从左往右逐行遍历，若下方或者右方的节点也是陆地，那么就拼在一起
                    if (i + 1 < row && grid[i+1][j] == '1')
                        union_n(i*col+j, (i+1)*col+j);
                    if (j + 1 < col && grid[i][j+1] == '1')
                        union_n(i*col+j, i*col+j+1);
                }
            }  
        // 返回剩下的陆地数量（岛屿数量）
        return land_num;
    }
private:
    // 记录父节点以及陆地的数量
    vector<int> parent;
    int land_num;
};

拼三角

牛客网做题链接：A-拼三角_牛客小白月赛32 (nowcoder.com)

思路：

这道题所需要的，其实就是利用贪心算法，找出这条规律：能组成三角形的三条边中，两条最短边之和一定大于第三边。注意，是最短边，如果是任意两条边，那样会加大我们的工作量的。

但贪心的点就在于，要是连两条最短边相加，都大于第三边了，那其他任意两边之和，一定也会大于第三边的。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    vector<int> arr(6);
    for(int i = 0; i < n; ++i)
    {
        cin >> arr[0] >> arr[1] >> arr[2] >> arr[3] >> arr[4] >> arr[5];
        sort(arr.begin(), arr.end());
        if((arr[0] + arr[1] > arr[2] && arr[3] + arr[4] > arr[5]) ||
           (arr[0] + arr[2] > arr[3] && arr[1] + arr[4] > arr[5]) ||
           (arr[0] + arr[3] > arr[4] && arr[1] + arr[2] > arr[5]) ||
           (arr[0] + arr[4] > arr[5] && arr[1] + arr[2] > arr[3]))
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    return 0;
}

学习编程就得循环渐进，扎实基础，勿在浮沙筑高台

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-15，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历