数据结构学习 jz13衣橱整理

2023-12-28 01:06:14

关键词:搜索算法 dfs bfs 回溯

题目:

各数位之和:

求法代码:

    int sums(int x)
    {
        int s=0;
        while(x!=0)
        {
            s+=x%10;
            x=x/10;
        }
        return s;
    }

总的思路:

这道题是求可以到达的格子数,想到可以用搜索算法来做,可以用dfs或者bfs。

可以去看这位大佬的分析。我基本是按照他的思路写的,但是把代码写的好看了一些。求各数位之和我用了封装好的sums函数,看起来舒服一些。

我一开始用传统的dfs做不出来也不知道为什么。

解法一:dfs 回溯

思路:

复杂度计算:

时间复杂度O(nm)

空间复杂度O(nm)

代码:

class Solution {
public:
    int wardrobeFinishing(int m, int n, int cnt) {
        vector<vector<int>> visited(m,vector<int>(n));
        return dfs(0,0,0,0,visited,m,n,cnt);
    }
    int dfs(int i,int j,int si,int sj,vector<vector<int>>& visited,int m,int n,int cnt)
    {
        if(si+sj>cnt||i>=m||j>=n||visited[i][j]) return 0;//中止条件
        visited[i][j]=1;//标记
        return 1+dfs(i+1,j,sums(i+1),sj,visited,m,n,cnt)+dfs(i,j+1,si,sums(j+1),visited,m,n,cnt);
    }
    int sums(int x)
    {
        int s=0;
        while(x!=0)
        {
            s+=x%10;
            x=x/10;
        }
        return s;
    }
};

解法二:bfs

思路:

?

复杂度计算:

时间复杂度O(nm)

空间复杂度O(nm)

代码:

class Solution {
public:
    int wardrobeFinishing(int m, int n, int cnt) {
        vector<vector<int>> visited(m,vector<int>(n));
        int res=0;
        queue<vector<int>> que;
        que.push({0,0,0,0});
        while(!que.empty())
        {
            vector<int> x=que.front();
            que.pop();
            int i=x[0],j=x[1],si=x[2],sj=x[3];
            if(i>=m||j>=n||si+sj>cnt||visited[i][j])
                continue;
            visited[i][j]=1;
            res++;
            que.push({i+1,j,sums(i+1),sj});
            que.push({i,j+1,si,sums(j+1)});
            
        }
        return res;
    }

    int sums(int x)
    {
        int s=0;
        while(x!=0)
        {
            s+=x%10;
            x=x/10;
        }
        return s;
    }
};

文章来源:https://blog.csdn.net/rainssssss/article/details/135256973
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。