5. c++学习笔记

c++学习笔记


  • 用vector和unique删除重复元素

    我们都知道unique的功能是去除相邻的重复元素（只保留一个），还有一个容易忽视的特性是它并不真正把重复的元素删除，不知道这个特性用起来就会出问题。比如下面这个例子，企图输出无重复的元素，

    #include <iostream> 
#include <vector> 
#include <algorithm> 
#include <iterator> 
using namespace std; 
int main()...{ 
　　vector<int> ivec; 
　　copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(ivec)); 
　　sort(ivec.begin(),ivec.end()); 
　　unique(ivec.begin(),ivec.end()); 
　　copy(ivec.begin(),ivec.end(),ostream_iterator<int>(cout," ")); 
　　system("pause"); 
　　return 0; 
}

    如果输入3 2 1 1 2 3，它的输出是1 2 3 2 3 3——没到达要求。

    unique只是把重复的元素放到容器的后面，而它本身会返回一个迭代器，只向这些元素的开始部分。因此要向真正删除这些元素，还是要“手工”处理一下。对于上面的例子，可以用vector窗口的erase：

    int main()
{ 
    vector<int> ivec; 
    copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(ivec)); 
    sort(ivec.begin(),ivec.end()); 
    vector<int>::iterator iter=unique(ivec.begin(),ivec.end()); 
    ivec.erase(iter,ivec.end()); 
    copy(ivec.begin(),ivec.end(),ostream_iterator<int>(cout," ")); 
    system("pause"); 
    return 0; 
}

    STL equal_range用法

    equal_range是C++ STL中的一种二分查找的算法，试图在已排序的[first,last)中寻找value，它返回一对迭代器i和j，其中i是在不破坏次序的前提下，value可插入的第一个位置（亦即lower_bound），j则是在不破坏次序的前提下，value可插入的最后一个位置（亦即upper_bound），因此，[i,j)内的每个元素都等同于value，而且[i,j)是[first,last)之中符合此一性质的最大子区间

    如果以稍许不同的角度来思考equal_range,我们可把它想成是[first,last)内"与value等同"之所有元素形成的区间A，由于[fist,last)有序（sorted），所以我们知道"与value等同"之所有元素一定都相邻，于是，算法lower_bound返回区间A的第一个迭代器，算法upper_bound返回区间A的最后一个元素的下一个位置，算法equal_range则是以pair的形式将两者都返回

    即使[fist,last)并未含有"与value等同"之任何元素，以上叙述仍然合理，这种情况下，"与value等同"之所有元素形成的，其实是一个空区间，在不破坏次序的情况下，只有一个位置可以插入value，而equal_range所返回的pair，其第一和第二（都是迭代器）皆指向该位置。

    e.g:

    给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

    class Solution {
public:
  vector<vector<int>> fourSum(vector<int>& nums, int target) {
      vector<vector<int>> result;
      if(nums.size() < 4) return result;
      sort(nums.begin(), nums.end());
      unordered_multimap<int , pair<int, int>> cache;
      for (int i = 0; i < nums.size()-1; i++)
      {
          for (int j = i+1; j < nums.size(); j++){
              cache.insert(make_pair(nums[i] + nums[j], make_pair(i, j)));
          }
      }
      
      for (auto i = cache.begin(); i != cache.end(); i++){
          int gap = target - i->first;
          auto range = cache.equal_range(gap);
          for ( auto j = range.first; j != range.second; j++){
               int a = i->second.first;
               int b = i->second.second;
               int c = j->second.first;
               int d = j->second.second;
              if(a != c && a != d && b !=c && b!=d){
                  vector<int> tmp = { nums[a], nums[b], nums[c], nums[d]};
                  sort(tmp.begin(), tmp.end());
                  result.push_back(tmp);
              }
          }
          
      }
      sort(result.begin(), result.end());
      result.erase(unique(result.begin(), result.end()), result.end());
      return result;
  }
};

    数组去重

    Given an array and a value, remove all instances of that value in place and return the new length.
    The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

    // 使用remove()时间复杂度 O(n) 空间复杂度O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int target) {
return distance(nums.begin(), remove(nums.begin(), nums.end(), target));
}
};

    堆排序原理与实现（小顶堆）

    堆排序实际上是利用堆的性质来进行排序的，要知道堆排序的原理我们首先一定要知道什么是堆。

    堆的定义：

    堆实际上是一棵完全二叉树。

    堆满足两个性质:

    1、堆的每一个父节点都大于（或小于）其子节点；
    2、堆的每个左子树和右子树也是一个堆。

    堆的分类：

    堆分为两类：

    1. 最大堆（大顶堆）：堆的每个父节点都大于其孩子节点；
    2. 最小堆（小顶堆）：堆的每个父节点都小于其孩子节点；

    堆的存储：

    一般都用数组来表示堆，i结点的父结点下标就为 (i−1)/2(i-1)/2。它的左右子结点下标分别为2∗i+12 * i + 1和2∗i+22 * i + 2。

    堆排序：

    由上面的介绍我们可以看出堆的第一个元素要么是最大值（大顶堆），要么是最小值（小顶堆），这样在排序的时候（假设共n个节点），直接将第一个元素和最后一个元素进行交换，然后从第一个元素开始进行向下调整至第n-1个元素。所以，如果需要升序，就建一个大堆，需要降序，就建一个小堆。
    堆排序的步骤分为三步:

    1. 建堆（升序建大堆，降序建小堆）；
    2. 交换数据；
    3. 向下调整。
    void AdjustDown(int arr[], int i, int n)
{
    int j = i * 2 + 1;//子节点 
    while (j<n)
    {
        if (j+1<n && arr[j] > arr[j + 1])//子节点中找较小的
        {
            j++;
        }
        if (arr[i] < arr[j])
        {
            break;
        }
        swap(arr[i],arr[j]);
        i = j;
        j = i * 2 + 1;
    }
}
void MakeHeap(int arr[], int n)//建堆
{
    int i = 0;
    for (i = n / 2 - 1; i >= 0; i--)//((n-1)*2)+1 =n/2-1
    {
        AdjustDown(arr, i, n);
    }
}
void HeapSort(int arr[],int len)
{
    int i = 0;
    MakeHeap(arr, len);
    for (i = len - 1; i >= 0; i--)
    {
        swap(arr[i], arr[0]);
        AdjustDown(arr, 0, i);
    }

}

    STL 优先队列

    一、相关定义

    优先队列容器与队列一样，只能从队尾插入元素，从队首删除元素。但是它有一个特性，就是队列中最大的元素总是位于队首，所以出队时，并非按照先进先出的原则进行，而是将当前队列中最大的元素出队。这点类似于给队列里的元素进行了由大到小的顺序排序。元素的比较规则默认按元素值由大到小排序，可以重载<操作符来重新定义比较规则。

    优先级队列可以用向量(vector)或双向队列(deque)来实现(注意list container不能用来实现queue，因为list的迭代器不是任意存取iterator，而pop中用到堆排序时是要求randomaccess iterator 的!)：

    priority_queue<vector<int>, less<int> > pq1;
// 使用递增less<int>函数对象排序
priority_queue<deque<int>, greater<int> > pq2; 
// 使用递减greater<int>函数对象排序

    其成员函数有“判空(empty)” 、“尺寸(Size)” 、“栈顶元素(top)” 、“压栈(push)” 、“弹栈(pop)”等。

    二、priority_queue

    基本操作：

    1. empty() 如果队列为空，则返回真

    2. pop() 删除对顶元素，删除第一个元素

    3. push()加入一个元素

    4. size()返回优先队列中拥有的元素个数

    5. top()返回优先队列对顶元素，返回优先队列中有最高优先级的元素

    在默认的优先队列中，优先级高的先出队。在默认的int型中先出队的为较大的数。

    头文件：

    #include <queue>

    声明方式：

    1、普通方法：

    priority_queue<int> q;   　　　　　　　　　　　　
//通过操作，按照元素从大到小的顺序出队
priority_queue<int,vector<int>, greater<int> > q;
//通过操作，按照元素从小到大的顺序出队

    2、自定义优先级：

    struct cmp {     
　　operator bool ()(int x, int y)     
　　{        
　　　　 return　x > y;　　 // x小的优先级高
　　　　 //也可以写成其他方式，如：
　　　　 //return p[x] > p[y];表示p[i]小的优先级高
　　}
};
priority_queue<int, vector<int>, cmp> q;
//定义方法
//其中，第二个参数为容器类型。第三个参数为比较函数。

    3、结构体声明方式：

    struct node {     
　　int x, y;     
　　friend bool operator < (node a, node b)     
　　{         
　　　　return a.x > b.x;    //结构体中，x小的优先级高     
　　}
};
priority_queue<node>q;
//定义方法
//在该结构中，y为值, x为优先级。
//通过自定义operator<操作符来比较元素中的优先级。
//在重载”<”时，最好不要重载”>”，可能会发生编译错误

    优先队列 priority_queue

    说明

    优先队列是一种功能强大的队列，可以自动排序

    头文件 & 声明

    #include<queue>

    一个优先队列的基本声明方式是

    priority_queue<结构类型> 队列名;

    e.g.

    priority_queue<int> p;
priority_queue<double> i;

    常用的有：

    priority_queue <node> q;
//node是一个结构体
//结构体里重载了‘<’小于符号

priority_queue <int, vector<int>, greater<int> > q;
//不需要#include<vector>头文件
//注意后面两个“>”不要写在一起，“>>”是右移运算符
priority_queue <int, vector<int>, less<int> >q;

    基本操作

    与队列一样

    q.size();//返回q里元素个数
q.empty();//返回q是否为空，空则返回1，否则返回0
q.push(k);//在q的末尾插入k
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素
q.back();//返回q的末尾元素

    特性

    自动排序

    默认的优先队列（结构体，重载小于）

    #include<cstdio>
#include<queue>
using namespace std;
priority_queue <int> q;
int main()
{
    q.push(10),q.push(8),q.push(12),q.push(14),q.push(6);
    while(!q.empty())
        printf("%d ",q.top()),q.pop();
}

    程序大意就是在这个优先队列里依次插入10、8、12、14、6，再输出。
    结果是什么呢？

    14 12 10 8 6

    也就是说，它是按从大到小排序的！

    less 和 greater 优先队列

    声明

    priority_queue <int,vector<int>,less<int> > p;
priority_queue <int,vector<int>,greater<int> > q;

    验证程序

    #include<cstdio>
#include<queue>
using namespace std;
priority_queue <int,vector<int>,less<int> > p;
priority_queue <int,vector<int>,greater<int> > q;
int a[5]={10,12,14,6,8};
int main()
{
    for(int i=0;i<5;i++)
        p.push(a[i]),q.push(a[i]);

    printf("less<int>:")
    while(!p.empty())
        printf("%d ",p.top()),p.pop();  

    pritntf("\ngreater<int>:")
    while(!q.empty())
        printf("%d ",q.top()),q.pop();
}

    结果

    less<int>:14 12 10 8 6 
greater<int>:6 8 10 12 14

    可以看出，less是从大到小排序，greater是从小到大排序

    回复 引用 0
回复
 

Copyright © 2018 bbs.dian.org.cn All rights reserved.

与 Dian 的连接断开，我们正在尝试重连，请耐心等待