代码片段

作者: 认真学计算机 | 来源:发表于2016-10-14 21:06 被阅读130次

标签（空格分隔）： C++ leetcode

一些成型的代码段
A: 去除 vector<int> 型的数组

vector<int> new_num(vector<int>& nums) {  
    sort(nums.begin(),nums.end());  
    nums.erase(unique(nums.begin(),nums.end()),nums.end());  
    return nums;  
}

A_: 将一串数组的任何两个值的和以及他们的对应的下标给记录下来

//这里的时间复杂度是O(n^2)
         unordered_map<int,vector<pair<int,int>>> mapping;
         for(int i =0;i<nums.size();i++){
             for(int j =i+1;j<nums.size();++j)
             mapping[nums[i]+nums[j]].push_back(pair<int,int>(a,b));
         }
// 通过这种方式，可以将一串数组的任何两个值的和以及他们的对应的下标给记录下来

B: 从字符串里面读取所需要的int 和 char 型的数据

void build_tree(string s1,string s2) {
   string vec="";
   map<int,string> tree;
   istringstream v1(s1);
   int i;
   char c;
   while(v1.good()){
        v1>>c>>i;
        tree[i]=tree[i]+c;
        // 
   }
}

对于 map 和 unordered_map 的初始化操作

void load_op(map<string,int>& record, string name){
    if(record.find(name)==record.end()) record[name]=1;
    else ++record[name];
}

对于 map 如何根据value值进行排序（爱死了 sort 这个函数，直接重载这个函数运算符）
map默认按照key值排序，而map又没有像vector一样的sort()函数，那么如果将map按照value值排序呢？有两种方法：

方法1. 将map中的key和value分别存放在一个pair类型的vector中，然后利用vector的sort函数排序，其中map_verb存放我的map值：
存放我的map值：

#include<algorithm>

typedef pair<string, int> PAIR; // typedef 这里是有类型检查的
int cmp(const PAIR &x, const PAIR &y){
    return x.second > y.second;
}

for (map<string, int>::iterator map_iter = map_verb.begin(); map_iter != map_verb.end(); ++map_iter){
    pair_vec.push_back(make_pair(map_iter->first, map_iter->second));
}

sort(pair_vec.begin(), pair_vec.end(), cmp);
for (vector<PAIR>::iterator curr = pair_vec.begin(); curr != pair_vec.end(); ++curr){
    outfile << curr->first << "\t" << curr->second << endl;
}

提炼，pair对的生成：

int main(void){
    vector<pair<int,char>> vec;
//  pair<int,char> p1 = pair<int,char>(1,1);
//  pair<int,char> p2 = pair<int,char>(2,2);
    vec.push_back(pair<int,char>(1,'a'));    // vec.push_back(make_pair(1,'a'));
    vec.push_back(pair<int,char>(2,'b'));    // vec.push_back(make_pair(2,'b'));
    vector<pair<int,char>>::iterator itr;
    for(itr=vec.begin();itr!=vec.end();itr++){
        cout<<itr->first<<itr->second<<endl;
    }
    return 0;
}

方法2. 再新建一个map结构，然后把已知的map值得key和value分别作为新map的value和key，这样map结构就会自动按照value值排序啦.

对于 string 类型的数据，怎么进行查找 find(vec.begin(),vec.end(),c)==vec.end()

string 的查找的数据的位置：

int main(void){
    string str="abcdef";
    auto i = str.begin();
    auto j = find(str.begin(),str.end(),'d');
    cout<<distance(i,j); // 3 正好是d的下标 
    return 0;
}

char 是一个数字，怎么转为 int, 以及怎么将一个 int 转为一个 char：

int main(void){
//  char c = '3' ;
//  int n = c -'0';
//  cout<< n;
    int n = 3;
    char c = n + '0';
    cout<<c-'1';
    return 0;
}

另外用以下static_cast<type_id>() 这个是进行基础类型和类对象之间强制转换的函数：

int main(void){
    int n = 48;
    char c = static_cast<char>(n); //这里 ASCII码里面，48代表着就是0，所以，强行转换后，就变成了0；
    cout<<c; // 0
    return 0;
}

案例：

void find_depth(map<int ,string> tree,string vec, char c){
     if(find(vec.begin(),vec.end(),c)==vec.end()) return ;
     int i=distance(vec.begin(),find(vec.begin(),vec.end(),c)); //这个i就是那个元素的下标.
}

//这里的时间复杂度是O(n^2)
         unordered_map<int,vector<pair<int,int>>> mapping;
         for(int i =0;i<nums.size();i++){
             for(int j =i+1;j<nums.size();++j)
             mapping[nums[i]+nums[j]].push_back(pair<int,int>(a,b));
         }
通过这种方式，可以将一串数组的任何两个值的和以及他们的对应的下标给记录下来

算法应用：寻找出现次数最多的子串
对于 string 而言，如果要遍历它的子串，找到出现最多的子串是哪一个的时候，最简单的方法就是打算遍历所有的子串，利用map实现，其键值为对应的子串，value为子串出现的个数，遍历完所有的子串后，只要寻找最大的value的键值就可以了，这里就想到一个问题，map一般是按键排序，能否按value进行排序呢？

void substrCount(string str)
{
    map<string,int> substr;
    string subs;
    for(int i =1; i<str.size();i++)
        for(int j =0; j<=str.size()-i;j++)  // 这里的双循环的书写也是很讲究技巧的， 为了更好地控制字符串遍历的逻辑，只需控制好字符串的终端的部分。
        {
            subs = str.substr(j,i);                    //遍历每一个子串
            if(substr.find(subs)==substr.end())        //判断map中是否存在，存在则+1,不存在则插入
                substr[subs] = 1;
            else
                substr[subs] = substr[subs]+1;
        }

    pair<string, int> maxpair = *(substr.begin());     //寻找出现次数最多的子串
    map<string,int>::iterator it = substr.begin();
    while(it!=substr.end())
    {
        if(it->second >maxpair.second )
            maxpair = *it;
    }
    cout<<maxpair.first<<endl;
    cout<<maxpair.second<<endl;
}

对 pair 对使用的一个比较好的技巧：对于一个map而言，每一个键值对都可以转换为pair，所以，就出现了：pair<string,int> maxpair = *(substr.begin())

按键排序
为了实现快速查找，map内部本身就是按序存储的（比如红黑树）。在我们插入<key,value>键值对时，就会按照key的大小顺序进行存储，其中key的类型必须能够进行< 运算，且唯一，默认排序是按照从小到到大便利记忆联想到需要支持小于运算。

map 的模板定义如下：
template<class key, class T, class Compare = less<key>, class Allocator = allocator<pair<const key,T>> class map;

其中第三、四个均包含默认参数，可以不指定。我们可以通过指定Compare类来指定排序的顺序。其中less<Key> 是 stl 里面的一个函数对象（即调用操作符的类，其对象常称为函数对象（function object），它们是行为类似函数的对象，表现出一个函数的特征，就是通过“对象名+（参数列表）”的方式使用一个类，其实质是对operator()操作符的重载）

多线程单例模式

#include "afxmt.h"
class Lock
{
  private: 
         CCriticalSection m_cs; // 类CCriticalSection 的对象表示一个临界区，它是一个用于同步的对象，同一时刻只允许一个线程存取资源或代码区。
  public:
         Lock(CCriticalSection cs) : m_cs(cs)
        {
              m_cs.Lock();
        }
        ~Lock()
        {
              m_cs.Unlock();
        }
};

class Singleton
{
private:
      Singleton();
      Singleton(const Singleton &);
      Singleton& operator = (const Singleton &);
public:
      static Singleton *Instantialize();
      static Singleton *pInstance;
      static CCriticalSection cs;
};

Singleton* Singleton::pInstance = 0;
Singleton* Singleton::Instantialize()
{
      if(pInstance == NULL)
      { 
            //double check
            Lock lock(cs); //用lock实现线程安全，用资源管理类，实现异常安全
            //使用资源管理类，在抛出异常的时候，资源管理类对象会被析构，析构总是发生的无论是因为异常抛出还是语句块结束。
            if(pInstance == NULL)
            {
                  pInstance = new Singleton();
            }
      }
      return pInstance;
}

vector 和 string 优先于动态分配的数组

首先，在性能上，由于vector能够保证连续内存，因此一旦分配了后，它的性能跟原始数组相当；
其次，如果用new，意味着你要确保后面进行了delete, 一旦忘记了，就会出现BUG，且这样需要都写一行delete,代码不够短。
再次，声明多维数组的话，只能一个一个new，例如：

    int** ary = new int*[row_num];
    for(int i = 0;i < row_num; ++i)
        ary[i] = new int[col_num];

用 vector 的话一行代码搞定:

      vector<vector<int> > ary(row_num, vector<int>(col_num, 0));

使用 reserve 来避免不必要的重新分配

在无序地情况下进行二分查找（用快排进行实现，但是快排有个最大的问题，就是如果是在有序地情况下会退化成冒泡排序，所以这个地方的种子数据，就需要选的相对随机一点）

输入

第1行：2个整数N,K。N表示数组长度，K表示需要查找的数；
第2行：N个整数，表示a[1..N]，保证不会出现重复的数，1≤a[i]≤2,000,000,000。（注意，这里2000000000< 2147483647 所以用Int 型就可以了，4个字节可以表示的数也是很大的。）

输出

第1行：一个整数t，表示K在数组中是第t小的数，若K不在数组中，输出-1。

样例输入
10 5180
2970 663 5480 4192 4949 1 1387 4428 5180 2761
样例输出
9

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int my_find(vector<int> &nums,int target,int left_,int right_){
    int left=left_,right=right_;
    if(left==right&&nums[left]!=target) return -1;
    swap(nums[left],nums[(left+right)/2]);
    int cur = nums[left];
    while(left<right){
        while(left<right&&nums[right]>=cur) right--;
        if(left<right) nums[left] = nums[right];
        while(left<right&&nums[left]<=cur) left++;
        if(left<right) nums[right] = nums[left];        
    }
    nums[left] = cur;
    
    if(target==cur) return left+1;
    else if(target<cur) return my_find(nums,target,left_,left-1);
    else if(target>cur) return my_find(nums,target,left+1,right_);
}

int main(){
    int row=0,target=0;
    vector<int> nums;
    scanf("%d",&row);
    scanf("%d",&target);
    int num=0;
    while(row>0){
        scanf("%d",&num);
        nums.push_back(num);
        row--;
    }
    cout<<my_find(nums,target,0,nums.size()-1);
    return 0;
}

二分查找之第第K小的数，以及二分查找之第k大的数的标准做法

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int my_find(vector<int> &nums,int target,int left_,int right_){
    int left=left_,right=right_;
    if(left==right&&left!=target) return -1;
    swap(nums[left],nums[(left+right)/2]);
    int cur = nums[left];
    while(left<right){
        while(left<right&&nums[right]>=cur) right--;
        if(left<right) nums[left] = nums[right];
        while(left<right&&nums[left]<=cur) left++;
        if(left<right) nums[right] = nums[left];        
    }
    nums[left] = cur;
    
    if(target==left) return cur;
    else if(target<left) return my_find(nums,target,left_,left-1);
    else if(target>left) return my_find(nums,target,left+1,right_);
}

int main(){
    int row=0,target=0;
    vector<int> nums;
    scanf("%d%d",&row,&target);
    int num=0;
    while(row>0){
        scanf("%d",&num);
        nums.push_back(num);
        row--;
    }
    cout<<my_find(nums,target-1,0,nums.size()-1); //第k小的数
    // cout<<my_find(nums,nums.size()-target,0,nums.size()-1); //第k大的数
    return 0;
}