shared_ptr

3月 13 2015

给定N个直线，问最多将一个平面划分为几个区域，fn=fn-1+n, f1=1; 按照递推 fn=1+Sn
给定N个折线，只有一半，划分为几个区域，gn=f2n-2n, 因为对于每个折线，区域从原来4个变为2，损失2，

C++STL sort 解决最坏情况就是对于一般的进行快速排序，如果数据量特别大，则如果递归层次过大，采用heap sort来排序

mark一个Latex错误，如果出现while converting from UNICODE to CP 0 错误
那么需要将.tex文件先转为UTF-8编码，可以用Notepad++转，然后用WinEdt打开

shared_ptr用法。
赋值运算符函数，直接上代码: )

r->left=make_shared<Node>();

这段调用了make_shared来构造一个临时的shared_ptr对象，其实SP就是封装了指针，使得内存使用安全的类，这里会调用Node的构造函数，然后我们定义在这里。其他用法都不对，例如
r->left=new Node(), 因为Node*不能赋值给shared_ptr, r->left(new Node), 这种也不行，因为这里不是构造函数，而是赋值运算符函数。

struct Node
{
int value;
shared_ptr left,right;
Node() : value(INT_MIN), left(NULL), right(NULL){}
};

用了shared_ptr就记住不要有*，这是cpp最带刺的地方。

顺便附上一个算法黑书输入颗二叉树，输出层序遍历的代码。如果构造出错的，例如内部点没赋值，或者一个点出现多次，都输出-10

input:
(3,L) (4,R) (2,) ()
(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()

#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <cstdio>
#include <memory>
#include <climits>
using namespace std;

struct Node
{
    int value;
    shared_ptr<Node> left,right;
    Node() : value(INT_MIN), left(NULL), right(NULL){}
};
shared_ptr<Node> root;
int stoi(string x)
{
    int sum=0;
    for(auto e: x)
        sum=sum*10+e-'0';
    return sum;
}
bool invalid;
void addNode(string s,int v)
{
    int len = s.length();
    shared_ptr<Node> r = root;
    for(auto e:s)
    {
        if(e == 'L'){
            if(r->left == NULL) r->left=make_shared<Node>();
            r = r->left;
        }
        else if(e == 'R'){
            if(r->right == NULL) r->right=make_shared<Node>();
            r = r->right;
        }
    }
    if(r->value==INT_MIN)
        r->value = v;
    else invalid=1;
}

int main()
{
    invalid = 0;
    string str;
    root = make_shared<Node>();
    while(cin>>str)
    {
        int len = str.size();
        str = str.substr(1,len-2);
        int pos = str.find(",");
        if (pos == -1) break;
        int val = stoi(str.substr(0,pos));
        string dir = str.substr(pos+1, str.size()-pos-1);
        addNode(dir,val);
    }
    queue<shared_ptr<Node>> q;
    vector<int> ans;
    q.push(root);
    while(!q.empty())
    {
        auto cur=q.front();q.pop();
        if(cur->value!=INT_MIN) ans.push_back(cur->value);
        else
        {
            invalid=1;
            break;
        }
        if(cur->left) q.push(cur->left);
        if(cur->right) q.push(cur->right);
    }
    if(invalid) cout<<"-1"<<endl;
    else
    {
        for(auto e: ans) cout<< e << " ";
        cout << endl;
    }
    return 0;
}

Posted by richard爱闹 - 3月 13 2015
如需转载，请注明：本文来自 Richard

留言