leetcode解题思路分析（二十九）207—213题

2024-09-05 05:08
文章标签 leetcode 分析 解题 思路 二十九 213 207

本文主要是介绍leetcode解题思路分析（二十九）207—213题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  1. 课程表
    你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
    在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
    给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

本题可以采取DFS，如果找到了环路则证明不可以，否则可以

const int maxn=1000050;
class Solution {
public:
//DFS，模板题vector<int>ans[maxn];//定义一个二维数组，也可以下面这种定义方法：bool dfs(int x,vector<int>&vis){vis[x]=0;//表示当前这个节点已近访问过了。bool ret=true;for(auto v:ans[x]){if(vis[v]==0)return false;if(vis[v]==-1)ret=ret&&dfs(v,vis);}vis[x]=-1;//表示以这个点出发的所有能够遍历的点已经遍历完了。。这个点出发不存在环啦。。。return ret;}bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<int> vis(numCourses,-1);//表示的是是否访问过,初始化-1，表示没有访问过for(auto v:prerequisites){ans[v[1]].push_back(v[0]);}bool ret=true;for(int i=0;i<numCourses;i++){if(vis[i]==-1){ret=ret&&dfs(i,vis);}}return ret;}
};
  1. 实现Trie树
    实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
class Trie {bool isEnd;Trie* next[26];
public:Trie() {isEnd = false;memset(next, 0, sizeof(next));}void insert(string word) {Trie* node = this;for (char c : word) {if (node->next[c-'a'] == NULL) {node->next[c-'a'] = new Trie();}node = node->next[c-'a'];}node->isEnd = true;}bool search(string word) {Trie* node = this;for (char c : word) {node = node->next[c - 'a'];if (node == NULL) {return false;}}return node->isEnd;}bool startsWith(string prefix) {Trie* node = this;for (char c : prefix) {node = node->next[c-'a'];if (node == NULL) {return false;}}return true;}
};
  1. 长度最小的子数组
    给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。

采用双指针滑动易解

class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums)
{int n = nums.size();int ans = INT_MAX;int left = 0;int sum = 0;for (int i = 0; i < n; i++) {sum += nums[i];while (sum >= s) {ans = min(ans, i + 1 - left);sum -= nums[left++];}}return (ans != INT_MAX) ? ans : 0;
}
};
  1. 课程表2
    现在你总共有 n 门课需要选，记为 0 到 n-1。
    在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
    给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
    可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

可以采取DFS或者BFS求解

class Solution {
private:// 存储有向图vector<vector<int>> edges;// 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成vector<int> visited;// 用数组来模拟栈，下标 0 为栈底，n-1 为栈顶vector<int> result;// 判断有向图中是否有环bool invalid;public:void dfs(int u) {// 将节点标记为「搜索中」visited[u] = 1;// 搜索其相邻节点// 只要发现有环，立刻停止搜索for (int v: edges[u]) {// 如果「未搜索」那么搜索相邻节点if (visited[v] == 0) {dfs(v);if (invalid) {return;}}// 如果「搜索中」说明找到了环else if (visited[v] == 1) {invalid = true;return;}}// 将节点标记为「已完成」visited[u] = 2;// 将节点入栈result.push_back(u);}vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {edges.resize(numCourses);visited.resize(numCourses);for (const auto& info: prerequisites) {edges[info[1]].push_back(info[0]);}// 每次挑选一个「未搜索」的节点，开始进行深度优先搜索for (int i = 0; i < numCourses && !invalid; ++i) {if (!visited[i]) {dfs(i);}}if (invalid) {return {};}// 如果没有环，那么就有拓扑排序// 注意下标 0 为栈底，因此需要将数组反序输出reverse(result.begin(), result.end());return result;}
};
class Solution {
private:// 存储有向图vector<vector<int>> edges;// 存储每个节点的入度vector<int> indeg;// 存储答案vector<int> result;public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {edges.resize(numCourses);indeg.resize(numCourses);for (const auto& info: prerequisites) {edges[info[1]].push_back(info[0]);++indeg[info[0]];}queue<int> q;// 将所有入度为 0 的节点放入队列中for (int i = 0; i < numCourses; ++i) {if (indeg[i] == 0) {q.push(i);}}while (!q.empty()) {// 从队首取出一个节点int u = q.front();q.pop();// 放入答案中result.push_back(u);for (int v: edges[u]) {--indeg[v];// 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了if (indeg[v] == 0) {q.push(v);}}}if (result.size() != numCourses) {return {};}return result;}
};
  1. 添加与搜索单词
    本题采用Trie树+DFS搜索解决
class WordDictionary {struct TrieNode{bool end;unordered_map<char, TrieNode*> map;TrieNode() : end(false) {}};TrieNode* m_root;public:/** Initialize your data structure here. */WordDictionary() {m_root = new TrieNode;}/** Adds a word into the data structure. */void addWord(string word) {if (word.empty()){return;}TrieNode* cur = m_root;for (int i = 0; i < word.size(); ++i){auto iter = cur->map.find(word.at(i));if (iter == cur->map.end()){cur->map[word.at(i)] = new TrieNode;}cur = cur->map[word.at(i)];}cur->end = true;}/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */bool search(string word) {if (word.empty()){return false;}return __dfs(m_root, word, 0);}private:bool __dfs(TrieNode* node, const string& word, int index){if (index == word.size()){if (node->end){return true;}               return false;}if (word.at(index) == '.'){bool ret = false;for (const auto& p : node->map){ret |= __dfs(p.second, word, index + 1);}return ret;}else{auto iter = node->map.find(word.at(index));if (iter != node->map.end()){return __dfs(iter->second, word, index + 1);}}return false;}
};/*** Your WordDictionary object will be instantiated and called as such:* WordDictionary* obj = new WordDictionary();* obj->addWord(word);* bool param_2 = obj->search(word);*/
  1. 单词搜索2
    给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

本题其实是基于上题的Trie树实现

class Trie
{
public:bool isEnd;Trie *nxt[26];string word;Trie(){isEnd = 0;for (int i = 0; i < 26; i++){nxt[i] = nullptr;}word = "";}void insert(string word){Trie *node = this;for (char each : word){if (node->nxt[each - 'a'] == nullptr){node->nxt[each - 'a'] = new Trie();}node = node->nxt[each - 'a'];}node->isEnd = 1;node->word = word;}
};class Solution
{
public:vector<string> ans;void dfs(Trie *now, int x, int y, vector<vector<char>> &board){if (now->isEnd){now->isEnd = 0;ans.push_back(now->word);return;}if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size())return;if (board[x][y] == '#')return;if (now->nxt[board[x][y] - 'a'] == nullptr)return;now = now->nxt[board[x][y] - 'a'];char cur = board[x][y];board[x][y] = '#';dfs(now, x + 1, y, board);dfs(now, x - 1, y, board);dfs(now, x, y + 1, board);dfs(now, x, y - 1, board);board[x][y] = cur;}vector<string> findWords(vector<vector<char>> &board, vector<string> &words){Trie *root = new Trie();for (auto word : words){root->insert(word);}for (int i = 0; i < board.size(); i++){for (int j = 0; j < board[0].size(); j++){dfs(root, i, j, board);}}return ans;}
};
  1. 打家劫舍2
    你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
    给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

相对于前题加一个区分即可

class Solution {
public:int rob(vector<int>& nums) {int len = nums.size();if (len == 0)return 0;if (len == 1)return nums[0];int val1 = 0, val2 = 0;vector<int> dp(len, 0);dp[0] = nums[0];dp[1] = max(dp[0], nums[1]);     for (int i = 2; i < len - 1; i++){dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);}val1 = dp[len - 2];dp[0] = 0;dp[1] = nums[1];for (int i = 2; i < len; i++){dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);}        val2 = dp[len - 1];return max(val1, val2);}
};

这篇关于leetcode解题思路分析（二十九）207—213题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1138035。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

引言 随着时间的发展，大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用，随着人们期望的不断增加，目标也发生了巨大的变化。在短短的几个月的时间里，人们对大模型的认识已经从对其zero-shot能力感到惊讶，转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构（例如Transformer）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...
SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

查看原文>>>全流程SWAP农业模型数据制备、敏感性分析及气候变化影响实践技术应用 SWAP模型是由荷兰瓦赫宁根大学开发的先进农作物模型，它综合考虑了土壤-水分-大气以及植被间的相互作用；是一种描述作物生长过程的一种机理性作物生长模型。它不但运用Richard方程，使其能够精确的模拟土壤中水分的运动，而且耦合了WOFOST作物模型使作物的生长描述更为科学。 本文让更多的科研人员和农业工作者
阅读更多...
MOLE 2.5 分析分子通道和孔隙

MOLE 2.5 分析分子通道和孔隙

软件介绍 生物大分子通道和孔隙在生物学中发挥着重要作用，例如在分子识别和酶底物特异性方面。 我们介绍了一种名为 MOLE 2.5 的高级软件工具，该工具旨在分析分子通道和孔隙。 与其他可用软件工具的基准测试表明，MOLE 2.5 相比更快、更强大、功能更丰富。作为一项新功能，MOLE 2.5 可以估算已识别通道的物理化学性质。 软件下载 https://pan.quark.cn/s/57
阅读更多...
leetcode-24Swap Nodes in Pairs

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L
阅读更多...
leetcode-23Merge k Sorted Lists

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists
阅读更多...
衡石分析平台使用手册-单机安装及启动

衡石分析平台使用手册-单机安装及启动

单机安装及启动​ 本文讲述如何在单机环境下进行 HENGSHI SENSE 安装的操作过程。 在安装前请确认网络环境，如果是隔离环境，无法连接互联网时，请先按照 离线环境安装依赖的指导进行依赖包的安装，然后按照本文的指导继续操作。如果网络环境可以连接互联网，请直接按照本文的指导进行安装。 准备工作​ 请参考安装环境文档准备安装环境。 配置用户与安装目录。 在操作前请检查您是否有 sud
阅读更多...
线性因子模型 - 独立分量分析（ICA）篇

线性因子模型 - 独立分量分析（ICA）篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型，它们通过引入潜变量（ latent variables \text{latent variables} latent variables）来更好地表征数据。其中，独立分量分析（ ICA \text{ICA} ICA）作为线性因子模型的一种，以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2