c++-c++编程基础之leetcode题解第75题颜色分类.zip资源-CSDN下载

共1个文件

md：1个

需积分: 50 176 浏览量 2024-04-16 08:23:22 上传评论收藏 2KB ZIP 举报

在本压缩包中，主题聚焦于C++编程基础和LeetCode的第75题——颜色分类。这是一道关于算法的题目，旨在帮助C++初学者通过实战提升编程能力和解决问题的技巧。LeetCode是一个在线平台，提供了大量的编程题目，涵盖各种数据结构和算法，对于学习和提升编程技能非常有帮助。 C++是一种通用、面向对象的编程语言，由Bjarne Stroustrup在1983年基于C语言设计。它拥有丰富的库支持，高效且性能强大，广泛应用于系统软件、应用软件、游戏开发、驱动程序以及嵌入式系统等领域。掌握C++的基础知识，包括语法、类和对象、模板、异常处理等，是成为一名熟练C++程序员的必要条件。 LeetCode中的第75题——颜色分类，具体问题描述可能为：给定一个数组，其中元素仅为红色、白色或蓝色，你需要原地对数组进行排序，使得所有红色元素在前面，所有蓝色元素在而白色元素位于红蓝之间。不允许使用额外的空间，只能通过修改输入数组来实现。解决这个问题可以使用多种算法，但常见的方法是使用双指针。这里我们可以设定两个指针，一个从数组开头（i）开始，另一个从数组末尾（j）开始。i指向第一个蓝色元素，j指向最后一个红色元素。然后，我们可以通过比较中间元素的颜色来移动指针，将元素交换到正确的位置。当i与j相遇时，排序完成。这个过程可以分为以下步骤： 1. 初始化两个指针i和j，分别指向数组的首尾。 2. 当i < j时，进入循环。 3. 在循环内，如果当前元素是红色，将它与j指向的元素交换，然后j--；如果是蓝色，将其与i指向的元素交换，然后i++；如果是白色，不做任何操作，继续检查下一个元素。 4. 循环结束后，数组即按照题目要求排序。通过解答这样的LeetCode题目，不仅可以巩固C++编程基础，还能锻炼解决实际问题的能力，提高对数据结构和算法的理解。对于面试准备，尤其是技术面试，LeetCode题目也是必不可少的练习材料。这个压缩包提供了一个结合理论与实践的学习资源，可以帮助学习者深入理解C++编程，并通过解决实际问题来提升编程技巧。通过研究和解答这道题，你可以更熟练地运用C++解决实际问题，进一步增强你在编程领域的竞争力。

资源推荐

资源详情

资源评论

收起资源包目录

c++_c++编程基础之leetcode题解第75题颜色分类.zip （1个子文件）

c++_c++编程基础之leetcode题解第75题颜色分类

README.md 4KB

# [75. Sort Colors (Medium)](https://leetcode.com/problems/sort-colors/) Given an array <code>nums</code> with <code>n</code> objects colored red, white, or blue, sort them <a href="https://en.wikipedia.org/wiki/In-place_algorithm" target="_blank">in-place</a> so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers <code>0</code>, <code>1</code>, and <code>2</code> to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function.   Example 1: <pre>Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2] </pre>Example 2: <pre>Input: nums = [2,0,1] Output: [0,1,2] </pre>Example 3: <pre>Input: nums = [0] Output: [0] </pre>Example 4: <pre>Input: nums = [1] Output: [1] </pre>   Constraints: <ul> <li><code>n == nums.length</code></li> <li><code>1 <= n <= 300</code></li> <li><code>nums[i]</code> is <code>0</code>, <code>1</code>, or <code>2</code>.</li> </ul>   Follow up: Could you come up with a one-pass algorithm using only constant extra space? **Companies**: [Microsoft](https://leetcode.com/company/microsoft), [Amazon](https://leetcode.com/company/amazon), [Adobe](https://leetcode.com/company/adobe), [Apple](https://leetcode.com/company/apple), [Facebook](https://leetcode.com/company/facebook), [Bloomberg](https://leetcode.com/company/bloomberg), [Nvidia](https://leetcode.com/company/nvidia), [Swiggy](https://leetcode.com/company/swiggy) **Related Topics**: [Array](https://leetcode.com/tag/array/), [Two Pointers](https://leetcode.com/tag/two-pointers/), [Sorting](https://leetcode.com/tag/sorting/) **Similar Questions**: * [Sort List (Medium)](https://leetcode.com/problems/sort-list/) * [Wiggle Sort (Medium)](https://leetcode.com/problems/wiggle-sort/) * [Wiggle Sort II (Medium)](https://leetcode.com/problems/wiggle-sort-ii/) ## Solution 1. Count Sort ```cpp // OJ: https://leetcode.com/problems/sort-colors/ // Author: github.com/lzl124631x // Time: O(N) // Space: O(1) class Solution { public: void sortColors(vector<int>& nums) { vector<int> cnt(3, 0); for (int n : nums) cnt[n]++; int i = 0; for (int j = 0; j < 3; ++j) { while (cnt[j]--) nums[i++] = j; } } }; ``` ## Solution 2. ```cpp // OJ: https://leetcode.com/problems/sort-colors/ // Author: github.com/lzl124631x // Time: O(N) // Space: O(1) class Solution { public: void sortColors(vector<int>& nums) { int r = 0, g = 0, b = 0; for (int n : nums) { if (n == 0) { nums[b++] = 2; nums[g++] = 1; nums[r++] = 0; } else if (n == 1) { nums[b++] = 2; nums[g++] = 1; } else nums[b++] = 2; } } }; ``` ## Solution 3. [Dutch national flag problem](https://en.wikipedia.org/wiki/Dutch_national_flag_problem) ```cpp // OJ: https://leetcode.com/problems/sort-colors/ // Author: github.com/lzl124631x // Time: O(N) // Space: O(1) // Ref: https://leetcode.com/problems/sort-colors/solution/ class Solution { public: void sortColors(vector<int>& A) { int zero = 0, two = A.size() - 1; for (int i = 0; i <= two; ) { if (A[i] == 0) { swap(A[i++], A[zero++]); } else if (A[i] == 2) { swap(A[i], A[two--]); } else ++i; } } }; ```

评论收藏

内容反馈