【C++】“334. 队列检查”题目解析及所用vector相关用法总结

​前言

刷 LintCode 等时，针对 “ 334. 队列检查 ” 题目进行解析。

点击 C++ 代码常用的是 vector。为防忘记，文章最后特此结合题目总结 vector 一些常用的用法。

LintCode 传送门：LintCode 炼码

目录

​前言

一、练习：队列检查

（一）题目及答案

 （二）可运行代码及演示结果

 二、vector 用法总结

（一）复制整个 vector

（二）排序

一、练习：队列检查

（一）题目及答案

班上的学生根据他们的年级照片的身高升序排列，确定当前未站在正确位置的学生人数。

•  
•  

输入:  heights = [1,1,3,3,4,1]
输出:  3
解释:  经过排序后 heights变成了[1,1,1,3,3,4]，有三个学生不在应在的位置上

public:
    int orderCheck(vector<int> &heights) {   
        vector<int> after;
        after.assign(heights.begin(), heights.end());   //复制 heights 到 after
        sort(after.begin(), after.end());  //排序
        int count = 0;
        for (int i = 0; i < heights.size(); i++){ 
            //通过比较两个vector的值，得出位置不同的个数 count
            if (after[i] != heights[i]) {
                count++;
            }
        }
        return count;
    }
};

c++优先队列用法知识点总结

pdf 0星 超过10%的资源 52KB

下载

 （二）可运行代码及演示结果

#include
#include
#include
using namespace std;
 
void printVector(vector<int>& v)
{
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
 
int main() {
    vector<int> heights;
    int a[6] = { 1,1,1,3,4,1 };
    for (int k = 0; k < 6; k++)
    {
        heights.push_back(a[k]);
    }
    cout << "输出原序列：";
    printVector(heights);
    
    vector<int> after;
    after.assign(heights.begin(), heights.end());
    sort(after.begin(), after.end());  //由小到大排序
    cout << "输出排序后的序列：";
    printVector(after);    //此时 heights 的序列保持不变
 
    int count = 0;
    for (int i = 0; i < heights.size(); i++) {
        if (after[i] != heights[i]) {
            count++;
        }
    }
    cout << "学生不在应在的位置上的数量: " << count;
 
    return 0;
}

 二、vector 用法总结

（一）复制整个 vector

1、关键代码

vector<int> heights;
int a[6] = { 1,1,1,3,4,1 };
for (int k = 0; k < 6; k++)
{
    heights.push_back(a[k]);   //输入
}
vector<int> after1;
vector<int> after2;
 
// 第一种
after1.assign(heights.begin(), heights.end());
 
//第二种
after2 = heights;
 
//第三种
vector<int> after3(heights);

2、可执行代码及输出结果

#include
#include
#include
using namespace std;
 
void printVector(vector<int>& v)  //输出序列
{
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl << endl;
}
 
int main() {
    vector<int> heights;
    int a[6] = { 1,1,1,3,4,1 };
    for (int k = 0; k < 6; k++)
    {
        heights.push_back(a[k]);
    }
    cout << "输出原序列：";
    printVector(heights);
    
    vector<int> after1;
    vector<int> after2;
    vector<int> after3(heights);
    after1.assign(heights.begin(), heights.end());
    after2 = heights;
    cout << "输出after1：";
    printVector(after1);
    cout << "输出after2：";
    printVector(after2);
    cout << "输出after3：";
    printVector(after3);
    return 0;
}

（二）排序

1、关键代码

//从小到大排序
sort(after.begin(), after.end());  
 
//从大到小排序
sort(after.rbegin(), after.rend());

2、可执行代码及输出结果

#include
#include
#include
using namespace std;
 
void printVector(vector<int>& v)  //输出序列
{
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl << endl;
}
 
int main() {
    vector<int> heights;
    int a[6] = { 1,1,1,3,4,1 };
    for (int k = 0; k < 6; k++)
    {
        heights.push_back(a[k]);
    }
    cout << "输出原序列：";
    printVector(heights);
    
    vector<int> after;
    after.assign(heights.begin(), heights.end());
 
    //由小到大排序
    sort(after.begin(), after.end());   
    //begin 指向第一个元素，end 指向最后一个元素的后一个位置
    cout << "输出由小到大排序后的序列：";
    printVector(after);    //此时 heights 的序列保持不变
 
    
    //从大到小排序
    sort(after.rbegin(), after.rend());
    //rbegin 指向最后一个元素，rend 指向第一个元素的前一个元素
    cout << "输出由大到小排序后的序列：";
    printVector(after);    //此时 heights 的序列保持不变
 
    cout << endl;
    return 0;
}