当前位置: 首页 > news >正文

网站制作台州360优化大师官方下载

网站制作台州,360优化大师官方下载,一站式做网站报价,找人做彩票网站多少钱目录 Leetcode127. 单词接龙Leetcode841.钥匙和房间Leetcode463. 岛屿的周长Leetcode1971. 寻找图中是否存在路径Leetcode684.冗余连接Leetcode685.冗余连接II Leetcode127. 单词接龙 文章链接:代码随想录 题目链接:127. 单词接龙 思路:广搜搜…

目录

  • Leetcode127. 单词接龙
  • Leetcode841.钥匙和房间
  • Leetcode463. 岛屿的周长
  • Leetcode1971. 寻找图中是否存在路径
  • Leetcode684.冗余连接
  • Leetcode685.冗余连接II

Leetcode127. 单词接龙

文章链接:代码随想录
题目链接:127. 单词接龙

思路:广搜搜出来直接就是最短路径,深搜还需要判断;广搜相当于先把这一层路径的单词下一步走法都扫出来再走下一步;而深搜找到一条路径就先走到头,再返回来走下一条路径,需要判断路径长度,麻烦
另外需要标记位,wordMap,避免死循环

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> wordSet(wordList.begin(), wordList.end());if (wordSet.find(endWord) == wordSet.end()) return 0;unordered_map<string, int> wordMap;wordMap.insert(pair<string, int>(beginWord, 1));queue<string> que;que.push(beginWord);while(!que.empty()){string word = que.front();que.pop();int path = wordMap[word];for (int i = 0; i < word.size(); i++){string newword = word;for (int j = 0; j < 26; j++){newword[i] = j + 'a';if (newword == endWord) return path + 1;if (wordSet.find(newword) != wordSet.end() && wordMap.find(newword) == wordMap.end()) {wordMap.insert(pair<string, int>(newword, path + 1));que.push(newword);}}}}return 0;}
};

Leetcode841.钥匙和房间

文章链接:代码随想录
题目链接:841.钥匙和房间

思路:dfs

class Solution {
public:void dfs(vector<vector<int>>& rooms, vector<bool>& visited, int key){if (visited[key]) return;visited[key] = true;for (int i : rooms[key]){dfs(rooms, visited, i);}}bool canVisitAllRooms(vector<vector<int>>& rooms) {vector<bool> visited(rooms.size(), false);dfs(rooms, visited, 0);for(int i : visited){if (i == false) return false;}return true;}
};

Leetcode463. 岛屿的周长

文章链接:代码随想录
题目链接:463. 岛屿的周长

思路:不用深搜或广搜,遍历就好,不要想复杂。

class Solution {
public:int count = 0;int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};    int islandPerimeter(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (grid[i][j] == 1){for (int k = 0; k < 4; k++){int nex = i + dir[k][0];int ney = j + dir[k][1];if (nex < 0 || nex >= grid.size() || ney < 0 || ney >= grid[0].size() || grid[nex][ney] == 0){count++;}}}}}return count;}
};

Leetcode1971. 寻找图中是否存在路径

文章链接:代码随想录
题目链接:1971. 寻找图中是否存在路径

思路:并查集入门

class Solution {
private:int n = 200005;vector<int> father = vector<int> (n);void init(){for (int i = 0; i < n; i++) father[i] = i;}int find(int u){return u == father[u] ? u : father[u] = find(father[u]);}bool isSame(int u, int v){u = find(u);v = find(v);return u == v;}void join(int u, int v){u = find(u);v = find(v);if (u == v) return ;father[v] = u;}public:bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {init();for (int i = 0; i < edges.size(); i++){join(edges[i][0], edges[i][1]);}return isSame(source, destination);}
};

Leetcode684.冗余连接

文章链接:代码随想录
题目链接:684.冗余连接

思路:并查集入门,用于解决无向有环图问题

class Solution {
private:int n = 1005;vector<int> father = vector<int>(n);void init(){for (int i = 0; i < n; i++){father[i] = i;}}int find (int u){return u == father[u] ? u : father[u] = find(father[u]);}bool isSame(int u, int v){u = find(u);v = find(v);return u == v;}void join(int u, int v){u = find(u);v = find(v);if (u == v) return ;father[u] = v;}public:vector<int> findRedundantConnection(vector<vector<int>>& edges) {init();for (int i = 0; i < edges.size(); i++){if (isSame(edges[i][0], edges[i][1])) return edges[i];else join(edges[i][0], edges[i][1]);}return {};}
};

Leetcode685.冗余连接II

文章链接:代码随想录
题目链接:685.冗余连接II

思路:将有向图问题拆解成两个无向图有环问题。
另外注意const int n = 1005; n前需加const,否则用n初始化数组会报错,因为n 是一个可变的值

class Solution {
private:const int n = 1005;vector<int> father = vector<int>(n);void init(){for (int i = 0; i < n; i++){father[i] = i;}}int find(int u){return u == father[u] ? u : father[u] = find(father[u]);}bool isSame(int u, int v){u = find(u);v = find(v);return u == v;}void join(int u, int v){u = find(u);v = find(v);if (u == v) return;father[v] = u;}vector<int> getRemoveEdge(const vector<vector<int>>& edges){init();for (int i = 0; i < edges.size(); i++){if (isSame(edges[i][0], edges[i][1])) return edges[i];join(edges[i][0], edges[i][1]);}return {};}bool isTree(const vector<vector<int>>& edges, int i){init();for (int j = 0; j < edges.size(); j++){if (j == i) continue;if (isSame(edges[j][0], edges[j][1])) return false;join(edges[j][0], edges[j][1]);}return true;}public:vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {int inDegree[1005] = {0};for (int i = 0; i < edges.size(); i++){inDegree[edges[i][1]]++;}vector<int> vec;for (int i = edges.size() - 1; i >= 0; i--){if(inDegree[edges[i][1]] == 2) vec.push_back(i);}if (vec.size() > 0){if (isTree(edges, vec[0])) return edges[vec[0]];else return edges[vec[1]];}return getRemoveEdge(edges);}
};

图论第三天打卡,目前随想录上的图论问题刷完,加油!!!

http://www.ds6.com.cn/news/25899.html

相关文章:

  • 拱墅网站建设上海seo怎么优化
  • 您的网站空间即将过期平台优化是指什么
  • 类似于美团的网站怎么做博客营销案例
  • asp购物网站客户查看购物车刚刚北京传来重大消息
  • 零食店网站构建策划报告2023年度最火关键词
  • 商丘柘城做网站利尔化学股票股吧
  • 网站除了域名还要什么用广告推广计划
  • 秦皇岛网站制作看b站视频软件下载安装手机
  • 新网站内部优化怎么做信息流广告优秀案例
  • 网站字体大小是多少合适网站推广苏州
  • 什么软件可以做dj视频网站seo招聘职责
  • 网站上传到万网主机百度营销登录
  • 做销售的 都有什么网站品牌策划公司排名
  • 管理网站开发seo优化基础教程pdf
  • 深圳宝安住房和建设局网站官网2024年新闻摘抄
  • 日本平面设计大师个人网站郑州seo方案
  • 网站版权符号淘宝关键词排名怎么查询
  • 不需要证件做网站百度seo关键词怎么做
  • 企业建立网站需要网络seo招聘
  • 门店零售管理系统网站优化培训学校
  • 人民日报客户端上海频道seo培训赚钱
  • 东莞做网站排名优化推广网站推广的方法
  • 学做网站论坛vip网络运营策划
  • 微信网站模板免费下载seo引擎优化专员
  • 网页设计软件官网模板网站首页关键词优化公司
  • 广东省建设执业注册中心网站软文推广媒体
  • 湖南网站建设哪里好百度一下的网址
  • 济源网站建设的公司个人能接广告联盟吗
  • 做玩网站怎么上传青岛网站建设维护
  • 网站开发过程可分为网络营销方案策划论文