MyC++CodeforLeetCodeOJ.zip_C++ code for online judges资源-CSDN下载

共2000个文件

md：2000个

需积分: 50 175 浏览量 2023-12-31 11:12:58 上传评论收藏 11.34MB ZIP 举报

"My C++ Code for LeetCode OJ.zip" 提供了关于使用C++编程语言解决LeetCode在线判题平台（Online Judge）问题的知识点。LeetCode是一个广受欢迎的平台，它提供了各种算法和数据结构题目，帮助程序员提升技能并准备技术面试。 "My C++ Code for LeetCode OJ" 暗示这组代码包含了作者在LeetCode上尝试解决的算法问题的C++实现。这些代码可能包括了对排序、搜索、动态规划、图论、字符串处理、二分查找等各种算法的应用。通过分析和解决这些问题，开发者可以加深对C++语言特性和算法理解。虽然没有提供具体的标签，但我们可以推断出以下相关知识点： 1. **C++编程**：C++是一种静态类型、编译型、通用的、面向对象和泛型编程的语言。它继承自C语言，并加入了类、模板、异常处理等特性，使得它在处理复杂问题时更加高效。 2. **算法**：LeetCode上的问题主要考察的是算法设计和实现能力。这包括基础算法如排序（快速排序、归并排序、堆排序等）、搜索（二分查找、深度优先搜索、广度优先搜索等），以及高级算法如动态规划、回溯、贪心策略等。 3. **数据结构**：解决问题时常会用到各种数据结构，如数组、链表、栈、队列、哈希表、树（二叉树、平衡树等）、图等。理解和熟练使用这些数据结构是解决问题的关键。 4. **效率优化**：LeetCode通常有时间复杂度和空间复杂度的要求，因此优化代码以减少运行时间和内存占用是重要的技巧。 5. **调试与测试**：编写代码后，需要进行调试和单元测试以确保代码正确性。C++中的断点、调试器工具、GTest等测试框架可以帮助完成这个过程。 6. **代码组织**：良好的代码组织和注释习惯可以提高代码可读性和可维护性。这在多人协作或长期项目中尤为重要。 7. **LeetCode平台使用**：了解如何在LeetCode平台上提交代码、查看测试结果、参与讨论区的讨论等也是学习的一部分。【压缩包子文件的文件名称列表】"sss"没有提供具体文件名，通常在LeetCode上每个问题都会有一个对应的文件，文件名可能是问题的ID或者简化的描述。这些文件会包含解题思路、代码实现以及可能的注释。这个压缩包是学习C++编程和算法实践的好资源。通过对每个问题的代码进行阅读、理解、修改和优化，你可以提升自己的编程技能和算法思维。同时，也可以通过比较不同解法来拓宽视野，学习更优的解决方案。

资源推荐

资源详情

资源评论

收起资源包目录

My C++ Code for LeetCode OJ.zip （2000个子文件）

README.md 98KB

README.md 66KB

README.md 32KB

README.md 18KB

README.md 17KB

README.md 14KB

README.md 12KB

README.md 11KB

README.md 10KB

README.md 9KB

README.md 8KB

README.md 7KB

共 2000 条

# [727. Minimum Window Subsequence (Hard)](https://leetcode.com/problems/minimum-window-subsequence) Given strings <code>s1</code> and <code>s2</code>, return the minimum contiguous substring part of <code>s1</code>, so that <code>s2</code> is a subsequence of the part. If there is no such window in <code>s1</code> that covers all characters in <code>s2</code>, return the empty string <code>""</code>. If there are multiple such minimum-length windows, return the one with the left-most starting index.   Example 1: <pre>Input: s1 = "abcdebdde", s2 = "bde" Output: "bcde" Explanation: "bcde" is the answer because it occurs before "bdde" which has the same length. "deb" is not a smaller window because the elements of s2 in the window must occur in order. </pre> Example 2: <pre>Input: s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u" Output: "" </pre>   Constraints: <ul> <li><code>1 <= s1.length <= 2 * 104</code></li> <li><code>1 <= s2.length <= 100</code></li> <li><code>s1</code> and <code>s2</code> consist of lowercase English letters.</li> </ul> **Companies**: [Google](https://leetcode.com/company/google), [Snapchat](https://leetcode.com/company/snapchat), [eBay](https://leetcode.com/company/ebay) **Related Topics**: [String](https://leetcode.com/tag/string/), [Dynamic Programming](https://leetcode.com/tag/dynamic-programming/), [Sliding Window](https://leetcode.com/tag/sliding-window/) **Similar Questions**: * [Minimum Window Substring (Hard)](https://leetcode.com/problems/minimum-window-substring/) * [Longest Continuous Increasing Subsequence (Easy)](https://leetcode.com/problems/longest-continuous-increasing-subsequence/) ## Solution 1. DP Let `dp[i+1][j+1]` be the number of matched letters between `s[0..i]` and `t[0..j]`, `start[i+1][j+1]` be the starting index of the minimum window corresponding to `dp[i+1][j+1]`. Initially `dp[i+1][j+1] = 0`, `start[i+1][j+1] = -1`. If `s[i] == t[j]`, `dp[i+1][j+1] = 1 + dp[i][j]`. `start[i+1][j+1] = j == 0 ? i : start[i][j]`. If `s[i] != t[j]`, `dp[i+1][j+1] = max(dp[i][j+1], dp[i][j])`. If `dp[i+1][j+1] == dp[i][j+1]`, `start[i+1][j+1] = start[i][j + 1]`. Additionally, if `dp[i+1][j+1] = dp[i][j]`, `start[i+1][j+1] = max(start[i+1][j+1], start[i][j])` ```cpp // OJ: https://leetcode.com/problems/minimum-window-subsequence // Author: github.com/lzl124631x // Time: O(MN) // Space: O(MN) class Solution { public: string minWindow(string s, string t) { int M = s.size(), N = t.size(); vector<vector<int>> dp(M + 1, vector<int>(N + 1)), start(M + 1, vector<int>(N + 1, -1)); for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { if (s[i] == t[j]) { dp[i + 1][j + 1] = 1 + dp[i][j]; if (j == 0) { start[i + 1][j + 1] = i; } else { start[i + 1][j + 1] = start[i][j]; } } else { dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i][j]); if (dp[i + 1][j + 1] == dp[i][j + 1]) { start[i + 1][j + 1] = start[i][j + 1]; } if (dp[i + 1][j + 1] == dp[i][j]) { start[i + 1][j + 1] = max(start[i + 1][j + 1], start[i][j]); } } } } int minLen = INT_MAX, st = -1; for (int i = 0; i < M; ++i) { if (dp[i + 1][N] == N && i - start[i + 1][N] + 1 < minLen) { st = start[i + 1][N]; minLen = i - start[i + 1][N] + 1; } } return minLen == INT_MAX ? "" : s.substr(st, minLen); } }; ``` Since `dp[i + 1][j + 1]` only depends on `dp[i][j]` and `dp[i + 1][j]`, we can reduce the space complexity from `O(MN)` to `O(N)`. ```cpp // OJ: https://leetcode.com/problems/minimum-window-subsequence // Author: github.com/lzl124631x // Time: O(MN) // Space: O(N) class Solution { public: string minWindow(string s, string t) { int M = s.size(), N = t.size(), minLen = INT_MAX, st = -1; vector<int> dp(N + 1), start(N + 1, -1); for (int i = 0; i < M; ++i) { for (int j = N - 1; j >= 0; --j) { if (s[i] == t[j]) { dp[j + 1] = 1 + dp[j]; start[j + 1] = j == 0 ? i : start[j]; } else { dp[j + 1] = max(dp[j + 1], dp[j]); if (dp[j + 1] == dp[j]) start[j + 1] = max(start[j + 1], start[j]); } } if (dp[N] == N && i - start[N] + 1 < minLen) { st = start[N]; minLen = i - start[N] + 1; } } return minLen == INT_MAX ? "" : s.substr(st, minLen); } }; ``` ## Solution 2. Greedy <h4 id="intuition-2">Intuition</h4> Let <code>start</code> and <code>end</code> denote the left-most and right-most indices of a given window/substring in <code>s1</code>. We can try all possible values of <code>start</code>, and for each of them, find the smallest value of <code>end</code> such that <code>s2</code> is a subsequence of <code>s1[start..end]</code>. Let <code>m</code> denote the length of <code>s2</code>. We want to find a sequence of indices i0,i1,...,im−1i_0, i_1, ..., i_{m-1}i0,i1,...,im−1</

评论收藏

内容反馈