给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000

示例：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

输入: "cbbd"
输出: "bb"

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.empty() || s.length()==1)
            return s;
        //分别存放回文串的起点终点
        int range[2]={0,0};
        for(int i=0;i<s.length();++i)
        {
            i=findLongest(s,i,range);
        }
        //返回起点和终点间的字符串
        return s.substr(range[0],range[1]-range[0]+1);
    }

    int findLongest(string s,int low,int range[])
    {
        int high=low;
        //找到第一个不相同的位置
        while(high<s.length()-1 && s[high+1]==s[low])
            ++high;
        //把回文左右对称，保存中间位置
        int ans=high;
        //从中间向两边扩展
        while(low>0 && high<s.length()-1 && s[low-1]==s[high+1])
        {
            --low;
            ++high;
        }
        //记录最大长度
        if(high-low>range[1]-range[0])
        {
            range[0]=low;
            range[1]=high;
        }
        return ans;
    }
};

/**************************************************************
先假设我们有一个这样的二叉树
	30
   /  \
  20  40
 /	 /  \
10  35  50

它的中序遍历和后序遍历父节点都不在叶子节点前先输出，这样我么你无法确定父节点和它孩子的位置
但是前序遍历则没有这个问题，父节点总是在叶子节点前先输出，我们先构造父节点，然后确定孩子节点
但是在操作时，需要记录空节点，否则处理上会有问题
**************************************************************/

void readBST(struct node *&root, ifstream &fin) 
{
    int val;
    fin >> val;	//先读取根节点数据
    readBSTHelper(INT_MIN, INT_MAX, val, root, fin);//传入父节点数据，递归调用函数来确定左右孩子
}
void readBSTHelper(int min,int max,int &insertVal,class node *&p,ifstream &fin) 
{
    if (insertVal > min && insertVal < max)
    {
        p = newNode(insertVal);	//构造父节点
        while(fin >> insertVal && insertVal=="#") fin>>insertVal;//继续读取数据，并跳过空节点
        readBSTHelper(min, val, insertVal, p->left, fin);
        readBSTHelper(val, max, insertVal, p->right, fin);
    }
}

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;

//插入排序
void InsertSort(vector<int> &a, int l, int r)
{
    for(int i=l+1; i<=r;i++)
    {
        if(a[i-1]>a[i])
        {
            int t=a[i];
            int j=i;
            while(j>l && a[j-1]>t)
            {
                a[j] = a[j-1];
                j--;
            }
            a[j]=t;
        }
    }
}
 
//寻找中位数的中位数
int FindMid(vector<int> &a,int l,int r)
{
    if(l==r) return l;
    int i=0;
    int n=0;
    for(i=l; i<r-5; i+=5)
    {
        InsertSort(a,i,i+4);
        n=i-l;
        swap(a[l+n/5],a[i+2]);
    }
 
    //处理剩余元素
    int num=r-i+1;
    if(num>0)
    {
        InsertSort(a,i,i+num-1);
        n=i-l;
        swap(a[l+n/5],a[i+num/2]);
    }
    n/=5;
    if(n==l) return l;
    return FindMid(a,l,l+n);
}
 
//进行划分过程
int Partion(vector<int> &a,int l,int r,int p)
{
    swap(a[p],a[l]);
    int i=l;
    int j=r;
    int pivot=a[l];
    while(i<j)
    {
        while(a[j]>=pivot && i<j)
            j--;
        a[i]=a[j];
        while(a[i]<=pivot && i<j)
            i++;
        a[j]=a[i];
    }
    a[i]=pivot;
    return i;
}
 
int BFPRT(vector<int> &a,int l,int r,int k)
{
    int p=FindMid(a,l,r);    //寻找中位数的中位数
    int i=Partion(a,l,r,p);
 
    int m=i-l+1;
    if(m==k) return a[i];
    if(m>k)  return BFPRT(a,l,i-1,k);
    return BFPRT(a,i+1,r,k-m);
}
 
int main()
{
    int n,k;    //数据数量和K值
    cin>>n;
    vector<int> a(n,0);
    for(int i=0;i<n;i++) cin>>a[i];
    cin>>k;
    for(auto i:a) cout<<i<<" ";
    cout<<"\n第"<<k<<"大数字: "<<BFPRT(a,0,n-1,k)<<endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <time.h>

using namespace std;

void bubble_sort(vector<int> &vec)
{
    for(int i=0;i<vec.size()-1;++i)
    {
        for(int j=0;j<vec.size()-i-1;++j)
        {
            if(vec[j]>vec[j+1]) swap(vec[j],vec[j+1]);
        }
    }
}

int main()
{
    vector<int> vec;
    for(int i=0;i<10;++i)
    {
        vec.push_back(rand()%20);
    }
    for(auto i:vec) cout<<i<<"\t";
    cout<<endl;
    bubble_sort(vec);
    for(auto i:vec) cout<<i<<"\t";
    cout<<endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <time.h>

using namespace std;

void insertion_sort(vector<int> &vec)
{
    for(int i=1;i<vec.size();++i)
    {
        for(int j=i;j>0;--j)
        {
            if(vec[j]<vec[j-1]) swap(vec[j],vec[j-1]);
        }
    }
}

int main()
{
    vector<int> vec;
    for(int i=0;i<10;++i)
    {
        vec.push_back(rand()%20);
    }
    for(auto i:vec) cout<<i<<"\t";
    cout<<endl;
    insertion_sort(vec);
    for(auto i:vec) cout<<i<<"\t";
    cout<<endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <time.h>

using namespace std;

void selection_sort(vector<int> &vec)
{
    for(int i=0;i<vec.size();++i)
    {
        int min=i;
        for(int j=i+1;j<vec.size();++j)
        {
            if(vec[j]<vec[min]) min=j;
        }
        swap(vec[min],vec[i]);
    }
}

int main()
{
    vector<int> vec;
    for(int i=0;i<10;++i)
    {
        vec.push_back(rand()%20);
    }
    for(auto i:vec) cout<<i<<"\t";
    cout<<endl;
    selection_sort(vec);
    for(auto i:vec) cout<<i<<"\t";
    cout<<endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <time.h>

using namespace std;

void shell_sort(vector<int> &vec)
{
    int gap=1;  //把步长先设为1
    while(gap<vec.size()/3) gap=gap*3+1;    //把数组分为3部分进行排序
    while(gap>=1)
    {
        for(int i=gap;i<vec.size();++i)
        {
            
            for(int j=i;j>=gap&&vec[j]<vec[j-gap];j-=gap)
            {
                swap(vec[j],vec[j-gap]);
            }
        }
        gap=gap/3;
    }
}

int main()
{
    vector<int> vec;
    for(int i=0;i<10;++i)
    {
        vec.push_back(rand()%20);
    }
    for(auto i:vec) cout<<i<<"\t";
    cout<<endl;
    shell_sort(vec);
    for(auto i:vec) cout<<i<<"\t";
    cout<<endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <time.h>

using namespace std;

void merge_vec(vector<int> &vec,vector<int>& tmpVec,int start,int middle,int end)
{
    for(int s=start;s<=end;++s) tmpVec[s]=vec[s];
    int left=start;
    int right=middle+1;
    for(int k=start;k<=end;++k)
    {
        if(left>middle) vec[k]=tmpVec[right++];
        else if(right>end) vec[k]=tmpVec[left++];
        else if(tmpVec[right]<tmpVec[left]) vec[k]=tmpVec[right++];
        else vec[k]=tmpVec[left++];
    }
}

void merge_sort(vector<int> &vec,vector<int>& tmpVec,int start,int end)
{
    if(start>=end) return;
    int middle=start+(end-start)/2;
    merge_sort(vec,tmpVec,start,middle);
    merge_sort(vec,tmpVec,middle+1,end);

    merge_vec(vec,tmpVec,start,middle,end);
}

void merge_sort(vector<int> &vec)
{
    vector<int> tmpVec(vec.size(),0);
    merge_sort(vec,tmpVec,0,vec.size()-1);
}

int main()
{
    vector<int> vec;
    for(int i=0;i<10;++i)
    {
        vec.push_back(rand()%20);
    }
    for(auto i:vec) cout<<i<<"\t";
    cout<<endl;
    merge_sort(vec);
    for(auto i:vec) cout<<i<<"\t";
    cout<<endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <time.h>

using namespace std;

int partition(vector<int> &vec,int low,int high)
{
    int pivot = vec[low];
    int i=low;
    while (low<high)
    {
        //要先移动右边
        while (vec[high] > pivot && low < high) --high;
        while (vec[low] <= pivot && low < high) ++low;
        if (low < high) swap(vec[low],vec[high]);
    }
    swap(vec[i],vec[low]);
    return low;
}

void quick_sort(vector<int> &vec,int low,int high)
{
    if(low>=high) return;
    int middle=partition(vec,low,high);
    quick_sort(vec,low,middle-1);
    quick_sort(vec,middle+1,high);
}

void quick_sort(vector<int> &vec)
{
    if(vec.size()<2) return;
    quick_sort(vec,0,vec.size()-1);
}

int main()
{
    vector<int> vec;
    for(int i=0;i<10;++i)
    {
        vec.push_back(rand()%100);
    }
    for(auto i:vec) cout<<i<<"\t";
    cout<<endl;
    quick_sort(vec);
    for(auto i:vec) cout<<i<<"\t";
    cout<<endl;
    return 0;
}

void heap_sort(vector<int> &vec)
{
    int size = vec.size();
    buildHeap(vec,length);	//构建堆
    for ( int i = size - 1; i > 0; i-- )
    {
        swap(vec[0],vec[i]);	//将堆顶元素与末位元素调换
        size--;	//数组长度-1 隐藏堆尾元素
        sink(vec,0,size);	//将堆顶元素下沉 目的是将最大的元素浮到堆顶来
    }
}
void buildHeap(vectror<int> &vec,int size)
{
    for (int i = size / 2; i >= 0; i--)
        sink(vec,i,size);
}

/**
 * 下沉调整
 * @param arr 数组
 * @param index 调整位置
 * @param length 数组范围
 */
void sink(vector<int> &vec,int index,int size)
{
    int leftChild = 2 * index + 1;	//左子节点下标
    int rightChild = 2 * index + 2;	//右子节点下标
    int present = index;	//要调整的节点下标

    //下沉左边
    if (leftChild < size && vec[leftChild] > vec[present])
        present = leftChild;

    //下沉右边
    if (rightChild < length && vec[rightChild] > vec[present])
        present = rightChild;

    //如果下标不相等 证明调换过了
    if (present != index)
    {
        //交换值
        swap(vec[index],vec[present]);

        //继续下沉
        sink(vec,present,size);
    }
}

void count_sort(vector<int> &vec)
{
    //找出数组中的最大值
    int max = vec[0];
    for (int i = 1; i < vec.size(); i++)
    {
        if (vec[i] > max) {
            max = vec[i];
        }
    }
    //初始化计数数组
    vector<int> countArr(max+1,0);

    //计数
    for (int i = 0; i < vec.size(); i++)
    {
        countArr[vec[i]]++;
        arr[i] = 0;
    }

    //排序
    int index = 0;
    for (int i = 0; i < countArr.size(); i++)
    {
        if (countArr[i] > 0) {
            vec[index++] = i;
        }
    }
}

void stable_sort(vector<int> &vec)
{
    //找出数组中的最大值
    int max = vec[0];
    for (int i = 1; i < vec.size(); ++i) {
        if (vec[i] > max) {
            max = vec[i];
        }
    }

    //初始化计数数组
    vector<int> countArr(max + 1,0);

    //计数
    for (int i = 0; i < ve.size(); ++i)
        countArr[arr[i]]++;

    //顺序累加
    for (int i = 1; i < max + 1; ++i)
        countArr[i] = countArr[i-1] + countArr[i];

    //排序后的数组
    vector<int> sortedArr(vec.size(),0);

    //排序
    for (int i = vec.size() - 1; i >= 0; --i)
    {
        sortedArr[countArr[vec[i]]-1] = arr[i];
        countArr[arr[i]]--;
    }

    //将排序后的数据拷贝到原数组
    for (int i = 0; i < vec.size(); ++i)
        vec[i] = sortedArr[i];
}

void sort(vector<int> &vec){
    //最大最小值
    int max = vec[0];
    int min = vec[0];
    int size = vec.size();

    for(int i=1; i<size; i++)
    {
        if(vec[i] > max)
            max = vec[i];
        else if(vec[i] < min)
            min = vec[i];
    }

    //最大值和最小值的差
    int diff = max - min;

    //桶列表
    vector<vector<int>> bucketVec(size,vector<int>);	//桶的数量我设置成数组的长度
    
    //每个桶的存数区间
    float section = (float) diff / (float) (length - 1);

    //数据入桶
    for(int i = 0; i < size; i++){
        //当前数除以区间得出存放桶的位置 减1后得出桶的下标
        int num = (int) (vec[i] / section) - 1;
        if(num < 0) num = 0;
        bucketVec[num].push_back(vec[i]);
    }

    //桶内排序
    for(int i = 0; i < bucketVec.size(); i++)
        sort(bucketVec.begin(),bucketVec.end());

    //写入原数组
    int index = 0;
    for(auto b:bucketVec)
        for(auto value:b)
            vec[index++]=value;
}

void sort(vector<int> &vec)
{
    int size = arr.size();

    //最大值
    int max = vec[0];
    for(int i = 0;i < size;i++){
        if(vec[i] > max){
            max = vec[i];
        }
    }
    //当前排序位置
    int location = 1;

    //桶列表
    vector<vector<int>> bucketVec(10,vector<int>);	//桶的数量我设置成数组的长度

    while(true)
    {
        //判断是否排完
        int dd = (int)Math.pow(10，(location - 1));
        if(max < dd){
            break;
        }

        //数据入桶
        for(int i = 0; i < size; i++)
        {
            //计算余数 放入相应的桶
            int number = ((vec[i] / dd) % 10);
            bucketVec[number].push_back(vec[i]);
        }

        //写回数组
        int nn = 0;
        for (int i=0;i<10;i++){
            int s = bucketVec[i].size();
            for(int ii = 0;ii < s;ii ++){
                vec[nn++] = bucketVec[i][ii];
            }
            bucketVec[i].clear();
        }
        location++;
    }
}

auto_ptr<string> p1(new string("test"));
auto_ptr<string> p2;
p2=p1;	//此时并不报错
//p2剥夺了p1的所有权，当程序运行时如果访问到p1将会报错
//这是auto_ptr的缺点：存在潜在的内存崩溃问题

//保证同一时间内只有一个智能指针可以指向该对象，对于避免资源泄露特别有用
unique_ptr<string> p3(new string("test"));
unique_ptr<string> p4;
p4=p3;	//报错，编译器认为p3=p4非法

//此外，unique_ptr还有一个更聪明的地方，当程序试图将一个unique_ptr赋值给另一个时，如果源unique_ptr是临时右值，编译器允许会这么做，但是如果源unique_ptr将存在一段时间，编译器将禁止这一行为
unique_ptr<string> p5(new string("test"));
unique_ptr<string> p6;
p6=p5;	//非法，因为这样会留下悬挂的p5，可能有潜在危害
//如果非要这么做的话，需要用安全的做法，同时也能给它赋新值
p6=move(p5);	//转移所有权
p5=new string("new string");	//赋新值

unique_ptr<string> p7=unique_ptr<string>(new unique_ptr<string>("test"));	//允许

//通过计数机制表明资源b被几个指针共享，可以通过use_count()查看资源所有者个数，可通过new进行构造，也可通过auto_ptr、unique_ptr、weak_ptr来构造，当调用release()时，当前指针释放所有权，计数减1，当计数为0时资源释放
/*
成员函数如下:
use_count	返回引用计数个数
unique	返回是否是独占所所有权(use_count为1)
swap	交换两个shared_ptr所拥有的对象
reset	放弃内部对象的所有权或拥有对象的变更，会引起原有对象引用计数的减少
get		返回内部对象指针，由于已经重载了()方法，因此和直接使用对象是一样的
*/

/*
指向一个shared_ptr管理的对象，进行该对象的内存管理是那个强引用的shared_ptr
weak_ptr只是提供了对管理对象的一个访问手段
设计目的是为配合shared_ptr而引入的一种智能指针来协助shared_ptr进行工作
它可以从一个shared_ptr或l另一个weak_ptr对象构造，其构造和析构不会引起计数的变化
用来解决shared_ptr的死锁问题
*/
class B;
class A
{
public:
    shared_ptr<B> pb_;
    ~A();
};

class B
{
    public:
    shared_ptr<A> pa_;
    ~B();
};

void fun()
{
    shared_ptr<B> pb(new B());
    shared_ptr<A> pa(new A());
    
    //pa和pb相互引用
    pb->pa_=pa;
    pa->pb_=pb;
    cout<<pb.use_count()<<endl;
    cout<<pa.use_count()<<endl;
}

int main()
{
    fun();
    return 0;
}

/*
当跳出fun函数时，智能指针pa和pb析构时两个资源引用计数会减1，但二者引用计数还是为1，导致跳出函数时资源没有b被释放(即析构函数没有被调用)，这时把其中一个shared_ptr改为weak_ptr即可

另外，weak_ptr不能直接访问对象的方法，需要先转化为shared_ptr才能进行操作
*/