数据结构学习 jz13衣橱整理

关键词：搜索算法 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;}
};