江西师范大学两学一做专题网站,电子商务网站建设论文开题报告,圣诞树html网页代码,深圳哪些公司做网站文章目录1.内容概述2.岛屿数量2.1 题目描述2.2 DFS深度搜索算法思路2.3 BFS宽度搜索算法思路2.4 C代码实现3.单词接龙3.1 题目描述3.2 算法思路3.3 C代码实现4.单词接龙 II4.1 题目描述4.2 算法思路5.火柴拼正方形5.1 题目描述5.2 算法思路5.3 代码实现5.4 算法思路25.5 代码实…
文章目录1.内容概述2.岛屿数量2.1 题目描述2.2 DFS深度搜索算法思路2.3 BFS宽度搜索算法思路2.4 C代码实现3.单词接龙3.1 题目描述3.2 算法思路3.3 C代码实现4.单词接龙 II4.1 题目描述4.2 算法思路5.火柴拼正方形5.1 题目描述5.2 算法思路5.3 代码实现5.4 算法思路25.5 代码实现1.内容概述 2.岛屿数量
2.1 题目描述 给你一个由 ‘1’陆地和 ‘0’水组成的的二维网格请你计算网格中岛屿的数量。 岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外你可以假设该网格的四条边均被水包围。 示例 1输入grid [[1,1,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[0,0,0,0,0]
]
输出1示例 2输入grid [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]
]
输出32.2 DFS深度搜索算法思路 #includeiostream
#includevector
using namespace std;void DFS(vectorvectorint mark, vectorvectorchar grid, int x, int y) {mark[x][y] 1;int dx[] { -1,1,0,0 };int dy[] { 0,0,-1,1 };for (int i 0; i 4; i) {int new_x x dx[i];int new_y y dy[i];if (new_x 0 || new_y 0 || new_x mark.size() || new_y mark[new_x].size()) {continue;}if (mark[new_x][new_y] 0 grid[new_x][new_y] 1) {DFS(mark, grid, new_x, new_y);}}
}int main()
{vectorvectorchar grid { {1,1,1,0,0},{1,1,0,0,0},{0,0,1,0,0},{0,0,0,1,1} };vectorvectorint mark { {0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},};DFS(mark, grid, 1, 1);for (int i 0 ; imark.size(); i) {for (int j 0; j mark[i].size(); j) {cout mark[i][j] ;}cout endl;}return 0;
}1 1 1 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 0 02.3 BFS宽度搜索算法思路 2.4 C代码实现 class Solution {
public:void DFS(vectorvectorint mark,vectorvectorchar grid,int x,int y){mark[x][y]1;int dx[]{-1,1,0,0};int dy[]{0,0,-1,1};for(int i0;i4;i){int new_xxdx[i];int new_yydy[i];if(new_x0||new_y0||new_xmark.size()||new_ymark[new_x].size()){continue;}if(mark[new_x][new_y]0grid[new_x][new_y]1){DFS(mark,grid,new_x,new_y);}}}void BFS(vectorvectorint mark, vectorvectorchar grid, int x, int y) {queuepairint, int Q;int dx[] { -1,1,0,0 };int dy[] { 0,0,-1,1 };Q.push(make_pair(x, y));mark[x][y] 1;while (!Q.empty()) {x Q.front().first;y Q.front().second;Q.pop();for (int i 0; i 4; i) {int new_x x dx[i];int new_y y dy[i];if (new_x 0 || new_y 0 || new_x mark.size() || new_y mark[new_x].size()) {continue;}if (mark[new_x][new_y] 0 grid[new_x][new_y] 1) {mark[new_x][new_y] 1;Q.push(make_pair(new_x, new_y));}}}}int numIslands(vectorvectorchar grid) {int island0;vectorvectorint mark;for(int i0;igrid.size();i){mark.push_back(vectorint());for(int j0;jgrid[i].size();j){mark[i].push_back(0);}} for(int x0;xgrid.size();x){for(int y0;ygrid[x].size();y){if(mark[x][y]0grid[x][y]1){DFS(mark,grid,x,y);//或者BFS(mark,grid,x,y);island;}}} return island;}
};3.单词接龙
3.1 题目描述 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 序列中第一个单词是 beginWord 。
序列中最后一个单词是 endWord 。
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典 wordList 中的单词。给你两个单词 beginWord 和 endWord 和一个字典 wordList 找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列返回 0。 示例 1输入beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log,cog]
输出5
解释一个最短转换序列是 hit - hot - dot - dog - cog, 返回它的长度 5。示例 2输入beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log]
输出0
解释endWord cog 不在字典中所以无法进行转换。3.2 算法思路 bool connect(const string word1,const string word2){int cnt0;for(int i0;iword1.length();i){if(word1[i]!word2[i]){cnt;}}return cnt1;}void construct_graph(string beginWord,vectorstring wordList,mapstring,vectorstring graph){wordList.push_back(beginWord);for(int i0;iwordList.size();i){graph[wordList[i]]vectorstrng();}for(int i0;iwordList.size();i){for(int ji1;jwordList.size();j){if(connect(wordList[i]),wordList[j]){graph[wordList[i]].push_back(wordList[j]);graph[wordList[j]].push_back(wordList[i]);}}}}3.3 C代码实现 class Solution {
public:bool connect(const string word1,const string word2){int cnt0;for(int i0;iword1.length();i){if(word1[i]!word2[i]){cnt;}}return cnt1;}void construct_graph(string beginWord,vectorstring wordList,mapstring,vectorstring graph){wordList.push_back(beginWord);for(int i0;iwordList.size();i){graph[wordList[i]]vectorstring();}for(int i0;iwordList.size();i){for(int ji1;jwordList.size();j){if(connect(wordList[i],wordList[j])){graph[wordList[i]].push_back(wordList[j]);graph[wordList[j]].push_back(wordList[i]);}}}}int BFS_graph(string beginWord,string endWord,mapstring,vectorstring graph){queuepairstring,int Q;setstring visit;Q.push(make_pair(beginWord,1));visit.insert(beginWord);while(!Q.empty()){string nodeQ.front().first;int stepQ.front().second;Q.pop();if(nodeendWord){return step;}vectorstring neighborgraph[node];for(int i0;ineighbor.size();i){if(visit.find(neighbor[i])visit.end()){Q.push(make_pair(neighbor[i],step1));visit.insert(neighbor[i]);}}}return 0;}int ladderLength(string beginWord, string endWord, vectorstring wordList) {mapstring,vectorstring graph;construct_graph(beginWord,wordList,graph);int resultBFS_graph(beginWord,endWord,graph);return result;}
};4.单词接龙 II
4.1 题目描述 按字典 wordList 完成从单词 beginWord 到单词 endWord 转化一个表示此过程的 转换序列 是形式上像 beginWord - s1 - s2 - … - sk 这样的单词序列并满足 每对相邻的单词之间仅有单个字母不同。
转换过程中的每个单词 si1 i k必须是字典 wordList 中的单词。
注意beginWord 不必是字典 wordList 中的单词。
sk endWord给你两个单词 beginWord 和 endWord 以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 如果不存在这样的转换序列返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, …, sk] 的形式返回。 示例 1输入beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log,cog]
输出[[hit,hot,dot,dog,cog],[hit,hot,lot,log,cog]]
解释存在 2 种最短的转换序列
hit - hot - dot - dog - cog
hit - hot - lot - log - cog示例 2输入beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log]
输出[]
解释endWord cog 不在字典 wordList 中所以不存在符合要求的转换序列。4.2 算法思路 5.火柴拼正方形
5.1 题目描述 还记得童话《卖火柴的小女孩》吗现在你知道小女孩有多少根火柴请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴可以把火柴连接起来并且每根火柴都要用到。 输入为小女孩拥有火柴的数目每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。 示例 1:输入: [1,1,2,2,2]
输出: true解释: 能拼成一个边长为2的正方形每边两根火柴。示例 2:输入: [3,3,3,3,4]
输出: false解释: 不能用所有火柴拼成一个正方形。5.2 算法思路 5.3 代码实现
class Solution {
public:bool makesquare(vectorint matchsticks) {if(matchsticks.size()4){return false;}int sum0;for(int i0;imatchsticks.size();i){summatchsticks[i];}if(sum%4){return false;}sort(matchsticks.rbegin(),matchsticks.rend());int bucket[4]{0};return generate(0,matchsticks,sum/4,bucket);}
private:bool generate(int i,vectorint matchsticks,int target,int bucket[]){if(imatchsticks.size()){return bucket[0]targetbucket[1]targetbucket[2]targetbucket[3]target;}for(int j0;j4;j){if(bucket[j]matchsticks[i]target){continue;}bucket[j]matchsticks[i];if(generate(i1,matchsticks,target,bucket)){return true;}bucket[j]-matchsticks[i];}return false;}
};5.4 算法思路2 5.5 代码实现
class Solution {
public:bool makesquare(vectorint matchsticks){if(matchsticks.size()4){return false;}int sum0;for(int i0;imatchsticks.size();i){summatchsticks[i];}if(sum%4){return false;}int targetsum/4;vectorint ok_subset;vectorint ok_half;int all1matchsticks.size();for(int i0;iall;i){int sum0;for(int j0;jmatchsticks.size();j){if(i(1j)){summatchsticks[j];}}if(sumtarget){ok_subset.push_back(i);}}for(int i0;iok_subset.size();i){for(int ji1;jok_subset.size();j){if((ok_subset[i]ok_subset[j])0){ok_half.push_back(ok_subset[i]|ok_subset[j]);}}}for(int i0;iok_half.size();i){for(int ji1;jok_half.size();j){if((ok_half[i]ok_half[j])0){return true;}}}return false;}
}
