本文主要是介绍9.29（ 75. 颜色分类 539. 最小时间差），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
75. 颜色分类（通过）
效率战胜83%左右的他人，看来还是有更加优秀的解法
思路：使用三个指针，i指向开头，j指向结尾，k至下关中间的某个元素，当k指向0的时候，和前面的某个元素交换位置，若指向2和后面的某个元素交换位置。
程序代码：
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<stack>//引入数据结构堆栈
//75、颜色分类，使用快速排序的变形
using namespace std;class Solution {
public:void sortColors(vector<int>& nums) {int i = 0, j = nums.size() - 1, k=1;//i，j分别指向开头和结尾，k是一个可以自由活动的指针（其实就是下标而已）while (nums[i] == 0 && i < j)i++;while (nums[j] == 2 && i < j)j--;k = i;while (k<=j&&i < j) {if (nums[k] == 0) {swap(nums[i], nums[k]);i++;if(k<i)k = i;}else if (nums[k] == 2) {swap(nums[k], nums[j]);j--; }else k++;}}/void swap(int &a, int &b) {int tmp = a;a = b;b = tmp;}
};int main()
{Solution bb;int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}bb.sortColors(a);for (int i = 0; i < n; i++) {cout<<a[i]<<" ";}return 0;
}更加优秀的解法如下所示：
class Solution {
public:void sortColors(vector<int>& nums) {int l = nums.size();int i = 0, j = 0, k = 0;for(int t = 0; t < l; t++){if(nums[t] == 0){nums[k] = 2;nums[j] = 1;nums[i] = 0;i++;j++;k++;}else if(nums[t] == 1){nums[k] = 2;nums[j] = 1;j++;k++;}else{nums[k] = 2;k++;}}}
};
539. 最小时间差（通过）
思路：
首先把时间按照从小到大的顺序进行排列，分别找出时间差，并存储，然后找出最小值
程序代码：
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<sstream>
#include<stack>//引入数据结构堆栈
//539、最小时间差
using namespace std;class Solution {
public:int findMinDifference(vector<string>& timePoints) {vector<int> time = Trans(timePoints);sort(time.begin(), time.end());//排序int n = timePoints.size();//表示个数vector<int> diff(n);//表示记录下的时间差for (int i = 0; i < n - 1; i++) {diff[i] = time[i + 1] - time[i];}diff[n - 1] = 1440 + time[0] - time[n - 1];//构建了差别向量double min = diff[0];for (int i = 0; i < n; i++) {if (diff[i] < min)min = diff[i];}//已经找到了最小的的时间差return min;}vector<int> Trans(vector<string> &timePoints) {int n = timePoints.size();vector<int> time(n);string a1 = "", a2 = "";int b1 = 0, b2 = 0;//初始化for (int i = 0; i < n; i++) {istringstream Isa(timePoints[i]);getline(Isa, a1, ':');getline(Isa, a2);time[i] = stoi(a1.c_str()) * 60 + stoi(a2.c_str());}return time;}
};int main()
{Solution bb;int n;//表示时间字符串的个数cin >> n;vector<string> str(n);for (int i = 0; i < n; i++) {cin >> str[i];}cout<<bb.findMinDifference(str)<<endl;return 0;
}效率战胜了32%的其他用户，稍微有点低。。。
这篇关于9.29（ 75. 颜色分类 539. 最小时间差）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
