一个人的角落,也许并没人会看到这里~~ 祝福你,工作顺心,学习快乐~

安卓7.x下重新打包第三方ROM

最近对安卓底层比较更兴趣，打算研究一番ROM的制作与移植，汉化之类技术，苦于这方面的比较有技术的文章比较少，多数还借鉴国外帖子，在工具方面也比较少，没有形成一个好的技术圈。

漂在天空的日子

  • 你有没有听说过，这个世界上有一种鸟……

  • 听过啦，没脚的那种是嘛！这套哄女孩的可以啊，你像鸟吗?哪一寸像鸟啊?你只不是唐人街垃圾堆里捡回来的酒鬼。像鸟，你那要是会飞的话，会窝在这里么?飞呀，有本事飞给我看看啊！

  • 有机会的，不过到时候，你可不要自卑噢。

漂在天空的日子

考研日记

这段大学最充实的日子，终于结束。回想起来，花人生的一小段时光去奋斗，升学，提升自己，是很有必要的。 那么，也同样恭喜看到篇帖子的人，也许你也选择了与我同样的道路，不论结果如何，这段日子，也将成为你大学时光最难忘的一刻。 至少，你将会在这个时候，学到：

  • 什么叫做坚持，一年如一日的坚持
  • 什么叫做认真，不放过任何一个知识点的认真
  • 什么叫做态度，对待自己人生前途的态度

动态规划-最长增长子序列

最长递增子序列（LIS）的问题是要找到一个给定序列的最长子序列的长度，使得子序列中的所有元素被排序的顺序增加。

例如，{2,1,0,5,4,8,9} LIS为{2,4,8,9},{2,4,8,9},{1,5,8,9}….最长长度为4。

这里存在一个局部前后无关性的规律：

设 arr[0..m..m+1] 其中arr[0..m] 的最长子序列是包含于arr[0..m+1]的，且长度包含

所以，求arr[0..m]的最长子序列，只需要找出{ arr[0..m-i],其中m=>i>=1}的LIS，

此时，设{ arr[0..m-i],其中m=>i>=1}的最长子序列:i = k;

如果arr[k] < arr[m]的话，则arr[m]的LIS长度为arr[0..k]的LIS长度+1；

LIS = LIS + arr[m];

int arr[10] = {2,1,0,5,4,8,9};
int n = sizeof(arr) / sizeof(arr[0]);

//返回包含第n个元素作为最后一个元素的子序列的最长长度，
//a用于记录最长长度，
int lis(int n, int &a)
{
    if(n == 1) return 1;
    int cmax = 0;
    for(int i = 1; i < n; i++)
    {
        //第n个元素有可能不是LIS的最后一个元素,所以这里的递归不能放进if里面。
        int r = lis(i,a);
        if(arr[i-1]<arr[n-1])
        {
            if(r > cmax) cmax = r;
        }
    }
    a = max(a,cmax+1);
    return cmax + 1;
}

可以看到，每次lis(n)的执行都会调用n-1次lis，时间复杂度为O(n^2)， 下面进行优化： 方法与之前的背包问题和整分拆分问题非常相似。

int arr[10] = {2,1,0,5,4,8,9};
int nSize = sizeof(arr) / sizeof(arr[0]);
int lis2(int nSize)
{
    int *c;
    c = (int *) malloc(sizeof(int)*nSize);
    c[0] = 1;

    int gmax=0;
    for(int n = 1; n < nSize; n++ )
    {
        int cmax = 0;
        for ( int i = 0; i < n; i++ )
        {
            if ( arr[i]<arr[n] && c[i]>cmax ) 
                cmax = c[i];
        }
        c[n] = cmax + 1;

        if ( c[n] > gmax ) gmax = c[n];
    }

    free( c );
    return gmax;
}