c cpp string in out summary

比较熟悉的大神可以飘过了。。。之前对于C C++ string char* 尤其是输入的一堆东西弄得晕头转向,主要是用getline 输入string来处理,但是
如果让写C风格的,可能我就挂了。。。

getline(istream& istr, string str, delim)//一般是用这个来输入字符串的

后来看到一个很像的cin.getline(char* str, delim=’\n’), 如果是读一行,还是建议写\n吧,默认参数这么多指不定那条搞晕了= = 如果是写C++,尽量用前者好像

于是后面有出来了 gets fgets scanf(), 这么一堆输入char的函数,gets网上说是不安全的,因为没有设置输入缓存区,有溢出的风险,尽量
用fgets去代替,但是谁知道呢:
fgets(char
str, int num, FILE stream),当然File 也可以传入stdin来表示从标准输入,有点奇怪,后来查了才知道stdin就是File*类型的。
但是我后来漏看了cplusplus文档,有个重要的漏了,就是fgets如果输入的最后有个\n,最后读到str里面的字符串也会加一个\n,这不得不说是个巨大的隐患,还是应该相信fawks大神的,
用gets,先不管隐患,至少目前编的代码还不会有溢出的隐患。

cin>>输入的话,默认delim 是 space \t 和\n,这个要记住,因为没有参数的,所以数字由于中间不可能有这些delim,可以安全用,但是字符串不是通过
这些delim来区分的,所以完全可能中间有这些字符,用cin就悲剧了,cplusplus官网也说cin是notorious的,

scanf() ACMer C C++混编混C的部分主要是由于C++流输入输出比较慢,采用C的函数直接把输入写到内存地址处来提高效率。
scanf(“%d”, &x);记住这个是输入地址,和printf只需要print值不一样

另外要特别留意输入int之后的string,如果敲回车的话,因为fgets gets getline cin.getline 这一系列输入字符串都是默认\n结束的,而如果前面整数是敲回车结束的(多数是这样的),那么
后面输入字符串的就是空串,因为\n还留在输入缓冲区里,那么这些读取直到\n就相当于读了空串了,所以最好之前再读取一次把空串读掉,其实scanf(%c)会有这个问题,scanf(%s) cin不会存在这个问题,但是字符串中间又空格就截断了。

总结下来tips就是,输入C字符串用gets可以不指定长度,感觉似乎方便,如果不写大的项目,隐患也还好,fgets需要指定长度和源stdin,可能麻烦点,也可以用cin.getline,而且这个优点在于还有
delim参数,因此如果有其他要求的话可能只能用cin.getline了。

C++字符串必须是getline(cin,str,delim=’\n’),输入字符串特别当心前面有int输入的时候,是否留了一个\n在缓冲区里,之前还有做法是cin.clear来清空。
另外stdin和cin是同步的,cin是C++的,但是好像stdin好像是标准输入,默认是键盘,如果需要freopen重定向的时候,一般都用stdin

基本delim默认都是\n, 例如getline(string::getline), cin.getline(istream::getline), cin是空格,\t \n来区分整数或者字符串的,用在字符串可能就挂了。

特别注意cin.getline(char*str, int num, delim=’\n’) 里面的num是指包含结束符的

另外今天看到一个代码还是不清楚为啥

#include <iostream>
using namespace std;
int main()
{
    char str[8];
    cin.getline(str, 5);
    cout<<str<<endl;
    cin.getline(str, 5);
    cout<<str<<endl;
    return 0;
}

代码来自 http://www.cnblogs.com/A-Song/archive/2012/01/29/2331204.html 对notorious的cin进行了一番批评似乎

34哥说过了,因为有一个问题,第一次输入就因为截断了,flag置1,然后后面就不读了。

Posted by richard爱闹 - 7月 21 2014
如需转载,请注明: 本文来自 Richard

back k node in linklist

今天偶然看到09CS考研题,DS的最后一题,之前肯定是做过的,但是今天看到又忘记了,面试问到估计后悔死了。。。

求链表倒数第k个结点,k>=1, 这种题时属于另一类,并不会渐进意义上降低时间复杂度,但是可以减少比较次数,其实当数据量打上去之后,也会有明显的提升。
我还是想到最朴素的遍历一遍求长度,然后在便利到l-k+1个。

后来看到答案,设置两个指针,一开始就间隔k一直移后指针到尾,直接返回前一指针就可以啦。我愣是没想起来。
相比之前的算法,我感觉指针移动的次数是一样的,只是不需要记录链表长度这样一个变量而已啦,都是移动l+l-k次指针吧,但是舆论还是觉得后面的算法要好,感觉高端点么。。。所谓的逼格高。。。

于是总结链表经典题目的解法好像很多都是用多个指针,我当时都没想到多用几个指针,然后要么是快慢指针(每次移动的速度恒定,且不一样),要么是interval 指针,始终保持
k的距离,感觉这几种思路都是这样,还有逆置链表是三个指针,prev,p, pnext这三个。

Posted by richard爱闹 - 7月 20 2014
如需转载,请注明: 本文来自 Richard

数组跳跃遍历减少比较次数

这道题目找了一个同学一起想,后来发现题目是野路子来的,最后题目意思理解除了偏差,衰。。。。再次表示诚挚的抱歉,是我错了。。。不过正好拓宽了思路,也把另一种问法解决了

原题描述:
在相邻元素相差1的数组中查找某一特定元素第一次出现的位置(非遍历)

通过各种渠道传到我这里,就变成了:
数组A中任意两个相邻元素大小相差1,现给定这样的数组A和目标整数t,找出t在数组A中的位置。

我想先自己思考,于是也没细究题目,认为题目是指找出所有的t的index出来,如果元素不重复的话,那就太简单了,直接定位i=|t-a[0]|,如果是的话返回index,不是的话,直接退出循环说找不到了。
我已开始以为这个是在时间复杂度渐进意义上要从线性减少,首先想到的是对数,但是感觉又想不到对数复杂度的算法。

思考这种题目,感觉就是需要归纳一些性质出来,提高效率,不论能够降低时间复杂度,都至少可以减少次数吧。

性质1:如果两个元素a[i] a[j]的差和index差相等,那么之间的元素一定是从(a[i],a[j])之间逐个递增或递减,也即不可能出现等于a[i]或a[j]

性质2:相邻2个元素一定是奇偶性相反,所以如果当前t和i同奇偶性,则解不可能是i-1 i+1的话,也一定只可能是i+2,不可能是i+1, i+3,

所以针对这些性质,如果对于问题输出所有t的index的话,我有了下面的代码:

void FindXIndex(int* a, int n, int x)
{
    int xi,j,tmp;
    for(int i=0;i<n;i++)
    {
        if(a[i]==x)
        {
            xi=i;
            break;
        }
    }
    printf("%d ", xi);
    while(abs(j-xi)>=2)
    {
        if(abs(a[j]-a[xi])==abs(j-xi))
            break;
        else if(a[j]==x)
        {
            printf("%d ", j);
            if(xi<j)
            {
                tmp=xi, xi=j, j=tmp+1;
            }
            else
            {
                tmp=xi, xi=j, j=tmp-1;
            }
        }
        else 
        {
            if(xi<j) j--;
            else j++;
        }
    }
    return;
}

先从找到一个t的index,然后从另一端向这段搜索,如果存在差值等于index差值,则直接返回,因为中间不可能还有t了,也即区间收缩到0了。所以循环的条件是区间长度是否大于1,如果等于1的话也不用了,只有一个元素,必为已经搜过的xi,
且程序里a[xi]=t的。然后j始终从当前值向xi靠近,注意根据和xi大小关系,判断++ 还是 —

这个算法是输出所有的index,后来看了下题目,原始不需要全部,好吧,自己做了一道新题。。。。

如果是只要返回任意一个,当然效率尽可能高,也即如何最快找到t的一个index,可以先从一端开始,例如0,先和a[0]比较,|t-a[0]|+0,是可能的t的位置,而且从(0 , |t-a[0]|+0)之间 是不可能出现解的,因为最快的增长(下降)速度才能使得边界达到t,
如果t=a[0]的话,0也可能, 所以第一步就大胆往前跳,同时第一步跳到的一定是奇偶性和t一致的点,所以改点两边的点和t奇偶性反,不可能是解,于是乎可以大胆的两步一跳。

int findpos(int a[],int n,int v)  
{  
    for(int i = abs(v-a[0]); i < n; i+=2)  
        if(a[i] == v)  
            return i;  
    return -1;  
}

代码来自:http://blog.csdn.net/u010590166/article/details/17250653#cpp
后来发现这个其实还不够优,看到下面童鞋的代码,好像更优
http://m.blog.csdn.net/blog/pein0119/11678997
不止是第一步跳跃,而是每次都是跳跃前进,直到找到或者遍历完位置,

i=abs(a[i]-t);

通过这句代码来实现的。

另外再加深一下印象,C语言的scanf 后面参数是地址, printf后面是变量,为什么是这样呢?思考一下原因更容易记住用法,因为输入是要把变量从键盘输到内存某个地址去,自然需要地址了,而打印只需要这个值传过来就行了,例如输出缓冲区,
实际上C++已经封装好了一切,所以不需要我们考虑,一律都是变量名了。C语言会更底层一些。

Posted by richard爱闹 - 7月 20 2014
如需转载,请注明: 本文来自 Richard

Difference between MSVC and gcc

最近发现VS2010(MSVC系列编译器), 和GCC比要弱很多,有些方便程序员的语法在GCC可以完美支持,到了VS就不行了,例如下面的代码:

double findMedianSortedArrays(int A[], int m, int B[], int n) 
{
    if(m+n==0) return 0;
    if(m+n==1)
    {
        if(m==0)
            return B[0];
        else if(n==0)
            return A[0];
    }
    int C[m+n];
    //vector<int> C(100);
    merge(A,A+m,B,A+n,C);
    int mid=0+(m+n-1)/2;
    if((m+n)%2==1)
        return C[mid];
    else
    {
        return double(C[mid]+C[mid+1])/2;
    }

}

int main()
{
    int a[]={}, b[]={2,3};
    cout<<findMedianSortedArrays(a,sizeof(a)/sizeof(int),b,sizeof(b)/sizeof(int))<<endl;
    return 0;
}

我最近发现cplusplus站点有个很好的类似于脚本语言立马知道函数或者语法正确性的一个site,点击example代码右侧的edit run,可以直接在web里面
emulate cpp的执行,而且我也突然体会到为啥大家喜欢用脚本语言了,因为有个解释器,而不是编译器,不确定函数或者定义正确否,到解释器里一试便知,
只可惜之前最熟悉的脚本语言是几乎只被researcher玩的matlab= =,工业界几乎不用。。。。之前偶然看到某大神说的,python库按照比较方便,库也越来越多了,
如果不确定可以到解释器里试,我还是因为来一来debugger,觉得python不方便debug而一直没有上手,现在知道自己错了,python打法好,退*保平安!

回到正题,上面几处是符合GCC标准的,例如编译变长,执行定长的数组定义,int C[m+n]; 当时刚学C++发现了这个在VS中不允许的语法。

另外还有空数组 GCC允许,VS不允许int a[]={},于是我在VS里写了代码,拿G++编译的= =,G++是包含GCC的一个编译器,多出一些C++的语法编译,G++ GCC对待
.c .cpp这四种组合,只有gcc 对.c 是当成C编译的,其他除非写个extern “C” 否则都是当CPP,默认是C98(C03和C98差别非常小,几乎当成一样,虽然是随后对C98的
小的修改), 加上-std=c++0x, 是C++11, 可以用很多STL里面新的东西,例如unordered_*之类的。

Posted by richard爱闹 - 7月 20 2014
如需转载,请注明: 本文来自 Richard

BinarySearch and its variant

今天看到一道有点需要借助二分的一道leetcode题,于是想起当时编程之美(Beauty Of Programming)还有一系列课后题还没搞定,加之之前不经意见问了下高富帅思路,突然有了一些感觉,于是把这些题目都做一做,都是BinarySearch的一些变形。

今天博客看到比我这个变种还多的大神,实在是膜拜啊,http://blog.csdn.net/luckyxiaoqiang/article/details/8937978

  1. 正常BinarySearch
    这个是基本的二分,之前还阅读编程珠玑(Progamming Pearls)证明过,注意low<=high, 后面就是正常的high=mid-1, low<high, 后面就是high=mid, 那些proof感觉不实用,难道写了代码,还花那么多时间去找一个assertion去proof它的correctness么?
    因此我总结了一个方法,就是看是否每个分支是否会至少减小search size 1个大小(除掉return),如果每次都减,一定不会死循环,因为size大小固定,<0就exit loop了。关键就是mid=(low+high)/2这个语句了,因为奇数除会丢精度,
    由于bit right shift的原因,所以这个是是否reduce size的关键。这个,我猜也是为啥46年就提出了BS的思想,但是62年才有第一个正确的algorithm吧。
  1. find max i, arr[i]=x
    这个是受高富帅点播的,如果找到相等了,low=mid, 包含当前元素向高区间找,然后如果区间size=1就返回这个mid,否则low=mid.但是一个样例测发现死循环了,后来分析发现了当时size=2,low+1=high, mid=(low+high)/2=low, 所以low=mid赋值就原地不动
    ,size不变,于是死循环了,所以两个element时候,特别处理,直接看a[low] a[high] 就行了,如果a[high]==x 就是high了,否则就是low了。

代码如下:

int BS_MaxIEqualX(int A[], int n, int x)
{
    int low=0, high=n-1;
    while(low<=high)
    {
        if(low==high) return A[low]==x ? low : -1;
        if(low+1==high) return A[high]==x ? high : (A[low]==x ? low : -1);//two ele not process, may nonterminal loop
        int mid=(low+high)/2;
        if(A[mid] < x) low=mid+1;
        else if(A[mid] > x) high=mid-1;
        else
            low=mid;
    }
    return -1;
}

上面的代码似乎有问题,没有拿OJ测,今天看到一道找找相等元素在数组中上下界的问题,然后重新写了一下代码,代码通过了OJ,应该是正确的。这里面是找等于元素的上下界,因此1,2两问的代码嵌在里面,
而且逻辑更加清楚,Knuth说过,过早优化是万恶的源头,确实如此,因为一开始你未必分析清楚逻辑,不要想着怎么把条件合并,就像印度人代码,虽然冗长但是正确,不容易有bug。这一系列都得益于高富帅
的点播,不愧是华科一哥啊,代码思路至少已经比较清晰了,只是还没证明正确性,未必正确,但是对AC至少有一定信心了。

    vector<int> searchRange(int a[], int n, int target) {
        int lowequal=-1,highequal=-1;

        int low=0,high=n-1;
        while(low<=high)
        {
            int mid=low+(high-low)/2;
            if(target==a[mid])
            {
                if(low==high)
                {
                    lowequal=low;break;
                }
                else
                {
                    high=mid;
                }
            }
            else if(target<a[mid])
            {
                high=mid-1;
            }
            else
                low=mid+1;
        }

        low=0,high=n-1;
        while(low<=high)
        {
            int mid=low+(high-low)/2;
            if(a[mid]==target)
            {
                if(high==low)//avoid unlimited loop
                {
                    highequal=low;//high
                    break;
                }
                else if(high==low+1)//avoid unlimited loop
                {
                    if(a[high]==target)
                    {
                        highequal=high;
                        break;
                    }
                    else
                    {
                        highequal=low;
                        break;
                    }
                }
                else//at least three elements
                {
                    low=mid;
                }
            }
            else if(a[mid]<target)
            {
                low=mid+1;
            }
            else if(a[mid]>target)
            {
                high=mid-1;
            }

        }

        vector<int> range;
        range.push_back(lowequal);
        range.push_back(highequal);
        return range;
    }
  1. find min i, arr[i]=x
    这个和上面类似,但是其实比那个还简单一些,因为两个元素的时候,mid=(low+high)/2=low, high=mid使得size-1了,不会死循环。这个也是和上面的微妙差别

    int BS_MinIEqualX(int A[], int n, int x)
    {

     int low=0, high=n-1;
     while(low<=high)
     {
         if(low==high) return A[low]==x ? low : -1;
         int mid=(low+high)/2;
         if(A[mid] < x) low=mid+1;
         else if(A[mid] > x) high=mid-1;
         else high=mid;
     }
     return -1;
    

    }

  2. find max i arr[i]<x
    和上面的区别在于分支修改不同,这里x<=a[mid] 说明mid及以上的都不可能是解,于是修改a[mid]<x 里面,解在这里面,一个元素直接return mid,两个元素注意unlimited loop了,x<=a[high], high不可能了,所以return low,否则就return high了

    int BS_MaxILowerX(int A[], int n, int x)
    {

     int low=0, high=n-1;
     while(low<=high)
     {
         if(low==high) return A[low]<x ? low : -1;
         if(low+1==high) return A[high] < x ? high : (A[low] < x ? low : -1);
         int mid=(low+high)/2;
         if(A[mid] < x) low=mid;
         else high=mid-1;
     }//do not exit loop
    

    }

    另外这道算法是否可以直接改写基本的BS呢,我手动模拟感觉就是找不到,循环退出时的high,但是不知道怎么证明的. 感觉如果x一定是找不到的,这个写法似乎是对的,如果找得到就不知道了。如果对的话,同理可得下面的代码

    int BS_MaxiLowerX(int *a, int n, int x)
    {

     int low=0,high=n-1;
     while(low<=high)
     {
         int mid=low+(high-low)/2;
         if(a[mid]<x)
         {
             low=mid+1;
         }
         else if(x<a[mid])
             high=mid-1;
         else
             return mid;
     }
     return high;
    

    }

  1. find min i arr[i]>x
    同上,只是不需要特殊处理了,因为high=mid 必reduce search size

    int BS_MinIHigherX(int A[], int n, int x)
    {

     int low=0, high=n-1;
     while(low<=high)
     {
         if(low==high) return A[low]>x ? low : -1;
         //if(low+1==high) return A[high] < x ? high : (A[low] < x ? low : -1);
         int mid=(low+high)/2;
         if(A[mid] <= x) low=mid+1;
         else high=mid;
     }//do not exit loop
    

    }

Posted by richard爱闹 - 7月 19 2014
如需转载,请注明: 本文来自 Richard

Review DFS-Permutation-Combination-NextPermutation

今天看到一道next_permutation的题目,于是打算串一下之前写的基于DFS或者backtrack的permutation和combination算法,顺便回顾了MS实习的一道题

突然发现next_permutation自己好像还不会,手动实现,而combination的下一个字典序当初也是直接调用next_permutation的。。。

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <iomanip>
#include <unordered_set>
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define read freopen("in.txt","r",stdin)
#define write freopen("out.txt","w",stdout)
using namespace std;

void permutation(int k, int n, int*a)
{
    if(k==n)
    {
        for(int i=0;i<n;i++)
            cout<<a[i]<<" ";
        cout<<endl;
    }
    else
    {
        for(int i=k;i<=n-1;i++)
        {
            swap(a[k],a[i]);
            permutation(k+1,n,a);
            swap(a[k],a[i]);
        }
    }
}

void combination(bool* select, int selectk, int k, int selectn, int n, int*a, int &count, int K)
{
    if(selectn==n)
    {
        if(selectk==k)
        {
            count++;
            if(count==K)
            {
                for(int i=0;i<n;i++)
                {
                    if(select[i])
                    {
                        cout<<"1";
                    }
                    else
                        cout<<"0";
                }
                cout<<endl;
            }
        }
    }
    else
    {
        select[selectn]=false;
        combination(select,selectk,k,selectn+1,n,a,count,K);
        select[selectn]=true;
        combination(select,selectk+1,k,selectn+1,n,a,count,K);

    }
}

int main()
{
    read;
    //write;
    int a[]={1,2,3,4,5};
    //permutation(0,5,a);
    bool select[100];
    memset(select,0,sizeof(bool)*10);

    int N,M,K,count=0;
    while(cin>>N>>M>>K)
    {
        string str;
        for(int i=0;i<N;i++)
            str+='0';
        for(int i=0;i<M;i++)
            str+='1';
        int i=1;
        while(i<K)
        {
            bool has=next_permutation(str.begin(),str.end());
            if(has==false) 
                break; 
            i++;
        }
        if(i<K)
            cout<<"Impossible"<<endl;
        else
            cout<<str<<endl;
        /*
        count=0;
        combination(select,0,M,0,N+M,a,count,K);
        if(count<K)
            cout<<"Impossible"<<endl;
            */
    }


return 0;

}
分别用next_permutaion和自己手写的combination来实现 kth 01 string, C(n,k)这个会复杂些,参数比较多,我还用了一个count引用参数传递,这样是不好的,参数多了可能会有溢出的风险,或者定义全局变量也是一样的。
然后记住next_permutation如果回到头了,会返回一个false其他都是返回true。还有传入的k是M的话(1的个数)那么需要注意内部select true为1,false为0, 如果传入N的话,就反过来。然后递归出口,我一直都是这么写的,也没有剪枝,
搜完整个2^(N+M)的空间,之前剪枝好像逻辑出了点问题,就不敢剪了。。。。

另外有一点就是,int*a, a+1其实会自动地址值+4,自动定位到数组中下一个元素的地址

Posted by richard爱闹 - 7月 19 2014
如需转载,请注明: 本文来自 Richard

BinaryAdd

这个题真的是自己摔了好多跤才爬起来的。。。自己还是考虑问题不全面,在软件测试的时候,估计会摔得更惨。。。
一开始想两种方案,二进制加,后者转十进制加,然后转回二进制,心想二进制加还要reverse才好加,不然对不齐,于是十进制,结果溢出了,用最大的unsigned long long还是溢出,这个可是20位十进制啊。。。
所以这种题目设计的就不是用十进制加法,而是要自己去实现一个加法,考虑各种情况,就像int的 +一样。

于是开始考虑情况,需要forward表示进位,然后还有长度不一样多出的怎么办,而且首先要reverse的,这样才对得齐。。。
于是由一般的写起,a[i]+b[i]+forward-2 >= <0来判断是否进位,然后后面也forward变为0 1,相应的,=0的我已开始忘记赋了,只记得比较重要的,进位需要赋1.。。
长度超出了怎么办?一定不能越界,于是判断是否超出任意一个的长度,如果超出了,且有进位,还要注意,可能一直进位,所以不能直接append后面多出的,如果forward=0 就append,然后还有最后多出一个
进位还要单独加一个”1”。我主要是一开始没有想清楚就coding,然后后面一个一个改,还是弄了一会儿,另外指针后移是每一个都后移,其他的break,我已开始最后全部 if else case都写了++,最后里面分支有的又
写了++,这个也忘记了。感觉这个逻辑的复杂度不亚于atoi函数的。。。。

summary:forward=0 且至少一个越界,直接append后面多出的部分,因为后面不再进位(注意此处两个都越界可以放到其中任意一个里,因为substr() startpos如果长度超过了,则返回空串,刚好符合要求)
forward=1 且至少一个越界,区分拿一个越界,然后加上a[i]+foward 看是否有进位,i++(这里两个都越界要单独处理,因为访问b[i]会越界,不想substr()能够tackle这种case,然后看如果进位,直接+”1”)
都不越界(forward=0 1可以统一起来), 普通处理
附上代码:

string addBinary(string a, string b)
    {
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        int forward=0,i=0;
        string c="";
        while(1)
        {
            if(forward==0 && (i>= a.size() || i>= b.size()))
            {
                if(i>= a.size())
                {
                    c+=b.substr(i);
                }
                else if(i>= b.size())
                    c+=a.substr(i);
                break;
            }
            else if(forward==1 && (i>= a.size() || i>= b.size()))
            {
                if(i>=a.size() && i< b.size())
                {
                    if(b[i]-'0'+forward>=2)
                    {

                        c+=char(b[i]-'0'+forward-2+'0');
                        forward=1;
                    }
                    else
                    {
                        c+=char(b[i]-'0'+forward+'0');
                        forward=0;

                    }
                    i++;
                }
                else if(i>=b.size() && i< a.size())
                {
                    if(a[i]-'0'+forward>=2)
                    {

                        c+=char(a[i]-'0'+forward-2+'0');
                        forward=1;
                    }
                    else
                    {
                        c+=char(a[i]-'0'+forward+'0');
                        forward=0;

                    }
                    i++;
                }
                else if(i>=b.size() && i>= a.size())
                {
                    c+="1";
                    break;

                }

            }
            else if(i<a.size()&&i<b.size())
            {
                if(a[i]-'0'+b[i]-'0'+forward>=2)
                {

                    c+=char(a[i]-'0'+b[i]-'0'+forward-2+'0');
                    forward=1;
                }
                else
                {
                    c+=char(a[i]-'0'+b[i]-'0'+forward+'0');
                    forward=0;
                }
                i++;
            }

            //i++;
        }
        reverse(c.begin(),c.end());
        return c;
    }

记得最后要reverse回来

Posted by richard爱闹 - 7月 19 2014
如需转载,请注明: 本文来自 Richard

Min Path Num--Typical DP

我和刘辉师兄坐在一起,就是你做事情,我突然哈哈大笑,然后我做做事情,你突然哈哈大笑O(∩_∩)O

这道题目属于容易看出的DP,从曹博PPT了看到例子后就反应更快了,不过感觉这个已经是曹博PPT最容易make sense的DP了= =
二维表格记录DP,初始化0 0, 以及0 j, i 0, 这样保证后面计算的子问题前面都计算出来了,注意下表不越界,还有就是
leetcode题目都没给数据范围,因此都不敢用全局变量了,正如fawks大神说的,global的比较简单,于是我还是用heap了。。。

附上代码:

int Min(int x, int y)
    {
        if(x<y) return x;
        else return y;
    }
    int minPathSum(vector<vector<int> > &grid) {
        int row=grid.size();
        if(row==0) return 0;
        int col=grid.at(0).size();
        if(col==0) return 0;

        int **dp=new int*[row];
        for(int i=0;i<row;i++)
            dp[i]=new int[col];

        dp[0][0]=grid.at(0).at(0);
        for(int j=1;j<col;j++)
            dp[0][j]=dp[0][j-1]+grid.at(0).at(j);
        for(int i=1;i<row;i++)
            dp[i][0]=dp[i-1][0]+grid.at(i).at(0);

        for(int i=1;i<=row-1;i++)
        {
            for(int j=1;j<=col-1;j++)
            {
                dp[i][j]=Min(dp[i-1][j],dp[i][j-1])+grid.at(i).at(j);
            }
        }
        int max=dp[row-1][col-1];


        for(int i=0;i<row;i++)
            delete[] dp[i];
        delete[] dp;
        return max;
    }

里面需要注意的是没有C++11,所以没有min可能。。。另外我每次都是写完general case再在前面加exception case的,比较舒服,之前一次提交还忘记返回值了= =
自己要逐渐转向不debug,因为后面纸上代码比较多些,直接在leetcode写了,眼睛看了submit

另外今天突然意识到vector可以当数组用的[], 之前一直at写起来麻烦,但是[]不越界检查,后果自负,我还是习惯[]呢,只是list就没有[]了。。
http://zhuyanfeng.com/archives/783

最近发现小米手机Wifi老是断,其他的小米却没有。感觉排除了wifi信号的问题,于是还是之前一直怀疑的系统故意设计这样,节约资源,例如电之类的,不需要的时候自动断掉,但是我需要的时候
也经常断掉啊%>_<%,之前查到好像是德州电器写的wifi驱动里面代码有这么节约资源的设计,好像点到wifi他才连上。。。不太确定,之前想找找帖子解决这个问题的,一直没搞定o(╯□╰)o

一个阿三和我说,她又认识了一个美女,而且是fb主动勾引他的。。。这位可真是把把妹当成一生的主题啊,他还尤其喜欢Chinese girls,尤其是她们的hair style,说一看背后就知道中国女孩,她们都
比印度女孩漂亮,还问我是不是jealous = =

Posted by richard爱闹 - 7月 19 2014
如需转载,请注明: 本文来自 Richard

from Word Break to substr function note

https://oj.leetcode.com/problems/word-break/
这道题目不是重点,重点是用string::substr的一点体会。
substr(size_t pos, size_t len=string::npos)

这个是substr的document,默认第二个参数npos表示取到字符串源串最后面,而且特别注意都是size_t类型,
我有一次掉到坑里去了,第二个参数一定要是>=0的,如果负数就会返回整个源串,要特别注意,另外pos也是>=0,这个倒好理解。
而且这个比较好,只有一种参数列表,这样比较容易记忆使用,当然如果参数列表多,用多了一般也是用自己比较熟悉的那一种。

代码是错的,有些case不行,可能需要回溯,类似dfs这种

bool wordBreak(string s, unordered_set<string> &dict) {
        if(s=="") return false;
        while(1)
        {
            if(s=="")
                return true;
            bool found=false;
            int startpos;
            string substr1,substr2;
            for(unordered_set<string>::iterator it=dict.begin();it!=dict.end();it++)
            {
                if((startpos=s.find(*it))!=string::npos)
                {
                    found=true;
                    if(startpos-1>=0)
                        substr1=s.substr(0,startpos);
                    else
                        substr1="";

                    string substr2=s.substr(startpos+(*it).size(),s.size()-(startpos+(*it).size()));
                    s=substr1+substr2;
                }
            }
            if(found==false) return false;
        }
    }

Posted by richard爱闹 - 7月 19 2014
如需转载,请注明: 本文来自 Richard

Gas Station

这道题目,有点难。我没想出线性算法,写了一个朴素的n^2的,最后TLE了,感觉很像最大字段和,最后看了题解,也确实如此,但是可能还是理解不够透彻吧,想起那句名言:

What I can not create, I can not understand.

所以还是只停留在运用这些经典题目的算法上,而没有完全掌握这一类题。
题目是https://oj.leetcode.com/problems/gas-station/
思路比较朴素,转化为每一站gasi-costi的diff,那么照这样一个starti,使得sum(starti,j)>=0 for j=starti->(starti-1+n)%n, 这里可能有loop,要取模变回来,抽象成这样一个
等价问题是不难的,但是后面如何一次遍历,就确定这个starti是难的。

注意题目说了只有唯一解,这个很重要,后面强的性质是基于这个条件的。

性质1:如果sum(starti,i)加起来<0,且sum(starti,k)>=0 starti<=k<i, 则最后一个i之前一直到starti都不可能是解

证明: 因为sum(starti,i)<0, 若存在i<="k=0 (由已知得到,除掉加到i sum<0, 前面都="">=0,不然是加不到这里的),则sum(k,i)=sum(starti,i)-sum(starti,k-1)<0, 因此
以k为起始的n个和里有一个必<0,所以k不可能是解。

性质2:如果sum(1,n)<0,则返回-1

哈哈,这个性质比较简单,我自己加的~~~

因此根据上述确立算法,如果起始开始,随意哪个作为起始都可以,加到第一次sum<0, 则前面的不可能是解,排除,记录解的变量j排除掉前面,j="i+1," sum="0,表示从新开始找一段和<0的index范围,排除掉之后" 最后退出loop时="" j记录的是前面几段负和的后一个index,同时看总和<0="" 的话返回-1,="" 总和都付不可能有节,因为任意一个必须n个sum="">0,且任意一个接都包含总和;否则,返回j,这是需要利用题目只有唯一解性质的,
因为后面可能还有节,但是题目说了唯一解,因此这个正确,但是可能最后一个元素 n 前面有段sum<0 那j岂不等于n+1越界了?这个不可能出现,因为如果出现,势必前面全是一段一段的sum<0, 总和<0 在另一个分支里面
O(∩_∩)O哈哈~

赋上代码,

int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
    {
        if(gas.size()==0) return -1;
        int n=gas.size();
        int sum=0,j=0,total=0;
        for(int i=0;i<n;i++)
        {
            sum+=gas[i]-cost[i];
            total+=gas[i]-cost[i];
            if(sum<0)
            {
                j=i+1;
                sum=0;
            }
        }
        if(total<0) return -1;
        else
            return j;
    }

另外赋上看的两个题解,
http://leetcodenotes.wordpress.com/2013/11/21/leetcode-gas-station-%E8%BD%AC%E5%9C%88%E7%9A%84%E5%8A%A0%E6%B2%B9%E7%AB%99%E7%9C%8B%E8%83%BD%E4%B8%8D%E8%83%BD%E8%B5%B0%E4%B8%80%E5%9C%88/
http://blog.csdn.net/kenden23/article/details/14106137

Posted by richard爱闹 - 7月 19 2014
如需转载,请注明: 本文来自 Richard