月度归档:2018年07月

最长上升子序列(LIS)问题

(iBus的输入法真的难用啊。。。用起来的感觉就像被电脑和键盘cj/(ㄒoㄒ)/~~,写到一半忍不住去换了fcitx+搜狗,然而可能是我的使用姿势不对,总出BUG,不过现在终于对上号了owo~)

 

这个问题让我想了N久N久N久,深深地感到智商欠费怀疑人生,我真是应该自挂东南枝。。


      问题:给出一个序列 例如(2 1 5 3 6 4 8 9 7),求该序列的最长上升子序列长度(1 3 4 8 9,长度为5)。

最长上升子序列问题,常用解法有两种,都用到了动态规划的思想,一种是直接用动态规划,比较好想,但是算法复杂度为O(n^2),另一种算法进行了优化,把时间复杂度降低到了O(nlogn),此两种方法本文都进行讲解,先看第一种

  • 通称O(n^2)算法

         设a为存储序列的数组,设f[i]为以i结尾最长子序列的长度,那么如何递推出f[i]的值呢?我们设一个变量j来表示,1<=j<=i-1,对于所有的a[j],只有当a[j]<a[i]的时候,我们才需要判断是否需要把a[i]添加到f[j]中,当然我们需要注意,f[i]的以i结尾的最长子序列的长度,所以我们要在所有可以添加a[i]的子序列中,找到最长的那个子序列,然后我们把a[i]添加进子序列中,另f[i]=f[j]+1即可。

         我在某篇博客上看到了f[i]=max(f[j](0<=j<i))+(a[i]>a[j]?1:0) 这样的公式,仔细研究这个公式其实是有BUG的,因为他找到的子序列max(dp[j])不一定能满足a[i]可以被添加进去,这点要注意仔细思考,不然很容易就出错。

         正确的推理公式应该是:f[i]=max( f[j] | (1<=j<=i-1,a[i]>a[j]) ) + 1

         我觉得这个算法是达不到O(n^2)的复杂度的。

代码:

int lis1(int a[],int n)
{
    int *f=new int[n+1];
    for(int i=0;i<=n;i++){f[i]=0;}//初始化
    int Max;
    for (int i = 1; i <= n; ++i){
        Max = 0;
        for (int j = 1; j <= i-1; ++j){
            if (a[i] > a[j]){
                Max = max(Max, f[j]);//找到可以把a[i]作为结尾的最长子序列
            }
        }
        f[i] = Max + 1;//把a[i]加入到这个子序列中
    }
    Max = 0;
    for (int i = 1; i <= n; ++i){//找到最长上升子序列
        if (f[i] > Max)    Max = f[i];
    }
    return Max;
}
  • O(nlogn算法)

         分析上面的算法发现,每次都要从i-1个数里面遍历,再找到最长的子序列,这就提高了计算时间,那么如何优化呢?是否有一种办法把这个寻找的过程简化?

        我们使用b[i]来记录长度为i的上升子序列的末尾元素的最低值 ,这是什么意思?长度为i的子序列可能有很多个,而我们为了寻找整个序列的最长上升序列,只需要关注长度为i的序列末尾元素的最低值,因为末尾元素的值越低,我们越可能得到更长的上升子序列,这是一种贪心算法的思想,显然b数组的递增的。用反证法简单地证明一下,假若存在i<j,b[i]=a,b[j]=b,且a>b,那么长度为j的上升序列里面一定包含一个长度为i的子上升序列,且b[i]<b[j],与假设矛盾。

         我们假设b最开始是没有长度的,通过依次读取每一个a[i]来更新b的长度以及b数组中存储的值。

         当我们读取到的a[i] 大于当前最长子序列的末尾元素最低值,那么a[i]可以被加入到这个子序列中,我们把当前最长子序列长度+1,并且更新b数组的值。

         如果条件不成立,那么我们无法添加a[i]到当前最长的子序列中,这时候我们用a[i]更新长度不是最长的子序列末尾元素的最低值,如何更新呢,我们在b数组中从前向后找到 第一个大于a[i]的数,然后用a[i]去更新这个值,这是什么诡异操作?假如b[1-5]=1 3 4 6 9,a[i]=5,那么a[i]可以加入的子序列就只有b[1-3]=1 3 4,不过我们既然要求最长子序列,那就让a[i]并入长度为3的子序列,并入后长度为4,这时我们要更新b[4]的值,忘记b存储的是什么了嘛?是长度为i的上升子序列的末尾元素的最低值,a[i]是小于原来的b[4]的,所以把a[i]并入长度为3的子序列之后及时用a[i]更新b[4]的值。

         如果对这里的操作还不是很明白的话,可以自己模拟一遍,在纸上写一写画一画~也可以点击这个链接:https://www.felix021.com/blog/read.php?1587 ,看一遍他的模拟过程。

下面放代码:

int lis2(int a[],int n){
    int ans=0;//假设b最开始的长度为0
    int *b=new int[n+1];
    for(int i=0;i<=n;i++){b[i]=0;}//初始化b的值
    for(int i=1;i<=n;i++){//依次读取a[i]的值并更新数组b
        if(b[ans]<a[i]){//如果可以被添加到长度为ans的子序列里面
            b[++ans]=a[i];//添加并且ans++;
            continue;
        }else{
            b[insert_x(b,ans,a[i])]=a[i];//否则就使用a[i]更新b数组的值
        }
    }
    delete []b;
    return ans;//最后数组的长度ans就是答案。
}
int insert_x(int b[],int n,int x){//寻找插入点,插入第一个大于x的位置,b是数组,查找范围是[0,n]
    int mid=0;
    int front=0;
    int rear=n;
    while(front!=rear-1){//使用二分查找
        mid=(front+rear)/2;
        if(x>b[mid]){
            front=mid;
        }else{
            rear=mid;
        }
    }
    return front+1;
}

注意这个算法为什么比第一个算法快,因为b是递增的数列,所以查找插入点的时候可以使用二分查找,二分查找的速度远远快于遍历整个数组,所以,这就体现了数据结构对算法的重要程度。

下面贴一个完整可以运行的代码:

#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
int lis1(int a[],int n);
int lis2(int a[],int n);
int insert_x(int b[],int n,int x);//在前N个数据里面,返回应该插入的位置
int main(){
    int n=0;
    cin>>n;
    int *a=new int[n+1];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    cout<<lis1(a,n)<<endl;
    cout<<lis2(a,n)<<endl;
    delete []a;
    return 0;
}
int lis1(int a[],int n)
{
    int *f=new int[n+1];
    for(int i=0;i<=n;i++){f[i]=0;}//初始化
    int Max;
    for (int i = 1; i <= n; ++i){
        Max = 0;
        for (int j = 1; j <= i-1; ++j){
            if (a[i] > a[j]){
                Max = max(Max, f[j]);//找到可以把a[i]作为结尾的最长子序列
            }
        }
        f[i] = Max + 1;//把a[i]加入到这个子序列中
    }
    Max = 0;
    for (int i = 1; i <= n; ++i){//找到最长上升子序列
        if (f[i] > Max)    Max = f[i];
    }
    return Max;
}
int lis2(int a[],int n){
    int ans=0;
    int *b=new int[n+1];
    for(int i=0;i<=n;i++){b[i]=0;}
    for(int i=1;i<=n;i++){
        if(b[ans]<a[i]){
            b[++ans]=a[i];
            continue;
        }else{
            b[insert_x(b,ans,a[i])]=a[i];
        }
    }
    delete []b;
    return ans;
}
int insert_x(int b[],int n,int x){
    int mid=0;
    int front=0;
    int rear=n;
    while(front!=rear-1){
        mid=(front+rear)/2;
        if(x>b[mid]){
            front=mid;
        }else{
            rear=mid;
        }
    }
    return front+1;
}

输入:第一行输入一个数字N,后面输入N个数字,使用tab、空格、回车进行间隔

输出:使用两个算法进行计算的最长上升子序列长度

样例:

    输入:

         9
         2 1 5 3 6 4 8 9 7

    输出:

         5

         5

 

突然想重新练字

      昨天晚上突然想起,很久以前教我练字的ZZ,很久没有练字了,有点怀念,思来想去决定重新开始练。

在此立贴为证,每日练字,立下Flag,Over。

同余定理与快速幂取模详解

      快速幂取模,是指求(a^n)%m , a和n都非常的大,如果直接计算a^n可能直接溢出,在这种情况下取模,需要用到同余定理的一些推论。

关于同余定理,可以看这里,注意幂运算部分,“幂运算:如果a ≡ b (mod m),那么a^n ≡ b^n (mod m)“ ,若a、b取m同余,则a^n、b^n关于m同余,注意a与a%m是同余的,所以把b替换为a%m,得a^n ≡ (a%m)^n (mod m),即(a^n)%m=((a%m)^n)%m快速幂取模就是运用了这个公式,把a^n拆开运算。

  • 先来看直接运用这个公式。

         直接运用就是直接把aaaa……拆开,拆成(a%m)(a%m)(a%m)(a%m)……然后再取模,上代码

long long solve(int a, int n, int m) {求a^n的模
    long long ans = 1;
    a = a%m;//先取一次模把数变小,a%m%m=a%m
    for (int i = 1; i <= n; i++) {
        ans = ans*(a%m);
    }
    return ans%m;
}

注意到这里展开就变成了(a%m)(a%m)(a%m)*(a%m),值得警惕的是,当m和n比较大,还是有很大的可能会溢出,因为要连乘法n次,于是有了第二种写法。

long long solve(int a, int n, int m) {求a^n的模
    long long ans = 1;
    a = a%m;//先取一次模把数变小,a%m%m=a%m
    for (int i = 1; i <= n; i++) {
        ans = (ans*a)%m;
    }
    return ans%m;
}

只改动了代码的第5行,改动后展开变成了((((a%m)a)%ma)%ma)%m……稍微推一下就可以推出这个式子和上面的(a%m)(a%m)(a%m)(a%m)……是同余的,那这样写有什么好处呢,好处就是降低了溢出的可能性,每次*a后都要%m,相当于每次都把结果控制在了0~m-1的范围内,大大减小了溢出的可能性。所以这种写法是比第一种要更安全的。

但是这两种方法都有一个问题,那就是,时间复杂度为O(N),每次都要乘啊,这么写代码,难道计算机不会痛嘛!于是就有了第二种算法,快速幂取模。

 

  • 快速幂取模

         快速幂取模,是一种二分的思想,怎么说呢,举个栗子吧,6^16==36^8==(66)^8,怎么运用这个来快速取模呢,(6^16)%m=((66)^8)%m={[(66)^4][(6*6)^4]}%m,看起来好不方便,那我们直接上代码吧

ps:如果是6^17次方呢?怎么二分,答案是,我们先提出来一个6变成(66^16)%m==((6%m)(6^16%m))%m,这样就可以正常运算了。

long long solve(long long a, long long n, long long m)
{
    long long ans = 1;
    a = a % mode;
    while (n > 0) {
        if (n % 2 == 1) //判断是否是奇数,也可以使用&符合判断是否为奇数
            ans = (ans * a) % m; 
        a = (a * a) % m;// 不断的两两合并再取模
                n /= 2;//这里可以使用位运算 n>>=1 来除以2,使用位操作运算速度更快。
    }
    return ans%m;

让我们随便带个数进去看看~假若a是6,n是16,即求(6^16)%,在这个算法中会怎么走呢?

n=16;

a=6%m;

进入循环:

    a=( (6%m) * (6%m) )%m;// 即(6*6)%m  运用了公式(a*b)≡(a%m)*(b%m)(mod m),这个公式是因为a与a%m同余,b与b%m同余,所以a*b与a%m*b%m同余;

    n=8;

    a=(  (6*6)%m * (6*6)%m  )%m//即(6*6*6*6)%m

    n=4;

    a=(  (6*6*6*6)%m * (6*6*6*6)%m  )%m//即(6^8)%m;

    n=2;

    a=(6^16)%m;

    n=1;

    判断n是奇数,所以

    ans=(6^16)%m;

    后面对a的赋值已经没有比较管了,因为n/2=0会直接跳出循环,得到ans即为答案。

 

如果n是奇数会如何?假若a=6,n=17

n=17;

a=6%m;

进入循环:

    判断n(17)是奇数

    ans=6%m;

    a=( (6%m) * (6%m) )%m;// 即(6*6)%m  运用了公式(a*b)≡(a%m)*(b%m)(mod m);

    n=8;

    a=(  (6*6)%m * (6*6)%m  )%m//即(6*6*6*6)%m

    n=4;

    ……
可以看到,奇数的时候,程序先取出了一个6,然后剩下6^16正常处理
最后n=1时,ans = (ans * a) % m;会把第一个取出来的值也乘上去,
得到ans=(  (6%m) * ((6^16)%m)  )%m = (6^17)%m;即为所求

 

例题:

POJ1995

这题不仅用到了同余定理在乘法方面的推论,还用到了在加法方面的推论,堪称模板题。题解自行百度。

 

C++ STL容器——set

      容器用于存储数据,在STL中,set是一个类似数学中”集合”的容器,可以进行交集并集的计算,且容器中不允许出现重复元素,set在日常使用中经常见到,值得注意的是,set内部使用二叉树存储数据,运算速度很快。

参考手册:http://www.cplusplus.com/reference/set/set/

      set的声明如下,

template < class T,                        // set::key_type/value_type
           class Compare = less<T>,        // set::key_compare/value_compare
           class Alloc = allocator<T>      // set::allocator_type
           > class set;

      第一个参数T是容器类型,第二个和第三个参数都提供的默认值,其中第二个参数是 比较器,用于给容器中元素进行大小排序,默认为less<T>,也可以自己指定,第三个参数是分配器,该参数指定使用哪个分配器对象管理内存,如果省略该模板参数的值,则容器模板将默认使用allocator<T>,这个类使用new和delete

set容器的常用方法:

初始化:

set容器常用的初始化方法为:

默认初始化

使用区间初始化

使用复制构造函数初始化

#include <iostream>
#include <string>
#include <set>
#include <cmath>
 
struct Point { double x, y; };
struct PointCmp {
    bool operator()(const Point& lhs, const Point& rhs) const { 
        return std::hypot(lhs.x, lhs.y) < std::hypot(rhs.x, rhs.y); 
    }
};
 
int main()
{
  // (1) 默认初始化器!!常用
  std::set<std::string> a;
  a.insert("cat");
  a.insert("dog");
  a.insert("horse");
  for(auto& str: a) std::cout << str << ' ';
  std::cout << '\n';
 
  // (2) 迭代器初始化器!!常用//使用区间进行初始化,也可以用数组的区间进行初始化。
  std::set<std::string> b(a.find("dog"), a.end());
  for(auto& str: b) std::cout << str << ' ';
  std::cout << '\n';
 
  // (3) 复制构造函数
  std::set<std::string> c(a);
  c.insert("another horse");
  for(auto& str: c) std::cout << str << ' ';
  std::cout << '\n';
 
  // (4) 移动构造函数
  std::set<std::string> d(std::move(a));
  for(auto& str: d) std::cout << str << ' ';
  std::cout << '\n';
  std::cout << "moved-from set is ";
  for(auto& str: a) std::cout << str << ' ';
  std::cout << '\n';
 
  // (5) initializer_list 构造函数
  std::set<std::string> e {"one", "two", "three", "five", "eight"};
  for(auto& str: e) std::cout << str << ' ';
  std::cout << '\n';
 
  // 自定义比较器
  std::set<Point, PointCmp> z = {{2, 5}, {3, 4}, {1, 1}};
  z.insert({1, -1}); // 这会失败,因为 1,-1 的长度等于 1,1
  for(auto& p: z) std::cout << '(' << p.x << ',' << p.y << ") ";
  std::cout << '\n';
}




//输出:

cat dog horse 
dog horse 
another horse cat dog horse 
cat dog horse 
moved-from set is 
eight five one three two 
(1,1) (3,4) (2,5)

insert():插入元素

常用insert(A,B)//A,B分别是两个迭代器,或两个数组中的指针,把[A,B)区间的元素插入容器。

insert(E)//直接插入一个元素

 

erase():删除操作:

iterator  erase (const_iterator position);//删除迭代器指向位置的元素
size_type erase (const value_type& val);//删除这个元素
iterator  erase (const_iterator first, const_iterator last);//删除这个区间的元素

find():查找元素

如果找到了,则返回指向这个元素的迭代器,如果没有找到,则返回一个指向最后一个元素尾部的迭代器.   (end()的返回值,这个迭代器指向最后一个元素的下一个元素,所以无效)

// set::find
#include <iostream>
#include <set>

int main ()
{
  std::set<int> myset;
  std::set<int>::iterator it;

  // set some initial values:
  for (int i=1; i<=5; i++) myset.insert(i*10);    // set: 10 20 30 40 50

  it=myset.find(20);
  myset.erase (it);
  myset.erase (myset.find(40));

  std::cout << "myset contains:";
  for (it=myset.begin(); it!=myset.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

 


    begin()//返回一个指向元素开头的迭代器(ps:关于迭代器,我们可以把它当作指针)

    end()//返回一个指向最后一个元素尾部的迭代器

// set::begin/end
#include <iostream>
#include <set>

int main ()
{
  int myints[] = {75,23,65,42,13};
  std::set<int> myset (myints,myints+5);//使用数组初始化set容器中的元素

  std::cout << "myset contains:";
  for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it)
    std::cout << ' ' << *it;

  std::cout << '\n';

  return 0;
}

//输出:myset contains: 13 23 42 65 75

rbegin()/rend():返回反向迭代器

// set::rbegin/rend
#include <iostream>
#include <set>

int main ()
{
  int myints[] = {21,64,17,78,49};
  std::set<int> myset (myints,myints+5);

  std::set<int>::reverse_iterator rit;

  std::cout << "myset contains:";
  for (rit=myset.rbegin(); rit != myset.rend(); ++rit)
    std::cout << ' ' << *rit;

  std::cout << '\n';

  return 0;
}

//输出:myset contains: 78 64 49 21 17 
//参数中默认的比较器是从小到大排列的,所以这里反向输出的容器元素的值

cbegin()/cend():返回一个const的迭代器

crbegin()/crend():返回const的反向迭代器


empty()//测试容器是否为空,为空则返回true.

size()//返回容器有多少元素.

max_size()//返回容器存储元素的最大值.

 



最后介绍一下set在集合意义上的操作

set_union()//求并集

set_intersection//交集

set_difference//差集

这三个函数的接口是相同的,他们都有5个参数,分别是:第一个集合的区间,第二个集合的区间,输出迭代器,这个迭代器指出要将操作的结果输出到哪里。

今天写累了,明天再写

待更新

 

 

使用栈(stack)简单地判断表达式合法性

      栈Stack是一种常见的数据结构,常用于函数调用,表达式处理等方面,栈结构就像是一个井,push操作就是把东西扔进井里面,pop操作就是把东西捞上来,很显然,后面仍下去的东西会先被捞上来,所以我们说Stack结构是一种先进后出,后进先出的结构。

      大家可能注意到,我们写代码的时候,比较智能的编辑器都会有一些错误提示,如果我们写了“(”而没有对应的”)“,那么就会看到提示,所以这是咋做到的?其实是使用了Stack栈结构。下面我们看一下使用Stack进行验证的规则:

      做一个空栈,读取字符串,依次对每个字符进行处理,如果不是(){}等符号字符,则跳过,如果是一个起始符号例如”(“,”{“,则把字符仍入栈中,如果字符是一个结束符合,那么当栈空时报错,当栈非空时,弹出顶部元素,验证是否与当前处理的字符匹配,若匹配,处理下一个,若不匹配,产生错误。最后当字符结束时,查看栈是否为空,如果栈中依然有元素,则报错。

      看下面的代码(很简单的,耐心看一下哈):

#include <iostream>
#include <stack>
using namespace std;
bool isTrueExpression(char exp[]);//主要的验证函数
bool isMarch(char,char);
int main(){
    char exp1[]="int main(void){for(){}return 0;}";//三个待验证的表达式
    char exp2[]="int main(void){for({)}return 0;}";
    char exp3[]="int main(void{for(){}return 0;}(";
    if(isTrueExpression(exp1))  cout<<"Exp1:True"<<endl;
    if(isTrueExpression(exp2))  cout<<"Exp2:True"<<endl;
    if(isTrueExpression(exp3))  cout<<"Exp3:True"<<endl;
    return 0;
}
bool isTrueExpression(char exp[]){
    stack<char> sta;
    for(;(*exp)!='\0';){//依次对字符进行处理,直到结尾
        //cout<<"handle:"<<*exp<<endl;
        if((*exp)=='('|(*exp)=='{'|(*exp)=='['){//如果字符是( { [等起始符合,那么扔入栈中
            sta.push(*exp);
            //cout<<"push:"<<*exp<<endl;
        }else if((*exp)==')'|(*exp)=='}'|(*exp)==']'){//如果是) } ]等符合,那么继续进行验证
            if((int)sta.size()==0){//如果栈是空的,返回false
                //cout<<"return F size==0"<<endl;
                return false;
            }else if(!isMarch(sta.top(),*exp)){
             //如果盏不空,取栈顶元素进行匹配,如果匹配失败,返回false
                return false;
            }else{//匹配成功,则把栈顶元素弹出
                //cout<<"pop:"<<*exp<<endl;
                sta.pop();
            }
        }
        if(*++exp=='\0'&&(int)sta.size()!=0){//验证是否到达结尾,
            //如果到达结尾,验证Stack是否为空,如果栈非空,则返回false
            return false;
        }
    }
    return true;
}
bool isMarch(char c1,char c2){
    //cout<<"比较"<<c1<<"和"<<c2<<endl;
    if(c1=='('){
        if(c2==')') return true;
    }else if(c1=='{'){
        if(c2=='}') return true;
    }else if(c1=='['){
        if(c2==']') return true;
    }
    //cout<<"不匹配"<<endl;
    return false;
}

以上代码输出为:

Exp1:True

 

简单理解C/C++中有关指针的语法

      本Blog的第一篇技术性文章,为了避免虎头蛇尾的情况出现,我打算开个蛇头(虽然我比较害怕蛇这种生物。。。。)。

      简单的理解关于C/C++指针的语法,以及一些声明。起初学C语言的时候,我就经常被这坑爹语法所坑,例如

//eg.
int (*p)[3];
double (*p)(int a);

      后来看了一些书,对此就慢慢熟悉了。所以,以此开头写一篇小文章,也算是温习了。 继续阅读

很惭愧

      很惭愧,开博两天了,没有写些什么。

      本想今天写一些关于智能指针的内容,但是下午回家又耽搁了很长时间,到家之后吃吃晚饭,恍然间已经十点了,想来想去甚是惭愧,无法面对两天前兴致勃勃的自己。

      不过今天已经有些晚了,而且我现在在研究STL了的各种容器,所以打算明天再写。。。。。。。

      另外今天郑州的天空甚是美丽

(火车上拍的)

The New Beginning

      很久没有写过博客了,记得上次大概还是在一年前了,期间由于各种问题(主要是因为自己懒),原blog没有维持下来,服务器到期后,我也懒于管理,匆匆备份了一下数据就没有放在心上了。一年过去,重新想要写一些什么,却又找不到以前的数据了(雾),如此,那就重新开始吧。

       为什么我想要重新恢复blog呢,主要是因为最近期末考试。我逐渐发现,以前学过的很多东西,没有很好的总结记录,遍逐渐淡忘,当我再次用到时,却只留下一个囫囵的印象。

      第二点,我发现bwh的vps便宜又好用就买了一年,既然买了总要搞点事情吧~所以就用装上apache、php等用wordpress搭了一个小站。期间还尝试过typeecho,虽然简洁高速,但确实不如wp丰富。不过优点亦是缺点,wordpress虽然功能全面,却容易转移我们的注意力。我前天晚上装好的,直到现在才发这第一篇文章,期间尝试了各种各样的插件,各式的主题,我甚至还要自己画一套logo。不过,今天早上画logo的时候,我突然意识到自己已经”舍本逐末”了,wordpress的丰富让我偏离了重心,于是我重新调整方向,用了一套极简文字的主题,简单调配之后,就可以正常使用了~

     我知道写这个blog对我来说,很可能是一时冲动,我也很可能无法坚持下去,我只能说我会尽量坚持。在这个blog上我会放上一些有关计算机方面的心得、写一些技术性的问题,同时也会写一些杂谈、书评摘抄之类的,每篇文章我都会附一篇英文稿,我英语很渣,所以想要多接触多使用,以此来提高英文水平。当然由于水平问题,很可能会写出一些滑稽的英文句子~

     最后,希望我能一直坚持下去,慢慢充起这个Blog。