2018秋招总结


秋招终于结束了,趁着还有些记忆写下这篇面经,希望对学弟学妹有所帮助。

首先先介绍一下个人背景,任何面试总结脱离了作者的背景都可能误导读者。本人本科期间参加了一年多(从入HDU校队开始算)ACM/ICPC比赛,最好成绩是区域赛银牌。硕士在浙江大学体系结构实验室,主要研究linux内核和虚拟化相关的东西。

然后列一下我主要投的公司和offer情况。我投递的公司不多,如下:

(注:sp=special 不确定是否是special offer的我都标了offer,其中的创业公司都是sp offer

需要注意的一点是,因为一些原因,本文不打算详细叙述面试过程中的具体题目。

1.微信:

微信是我最早拿到的一个offer,因为是实习转正。实习面试分3轮,2轮技术面+1轮hr面。第一面技术面之前会给30分钟做4/5道算法题,写在一张A4纸上,题目比较简单。然后开始和面试官唠嗑,第一面基本上是我在讲简历上的项目,印象中没提什么问题。第二面问了一些操作系统和算法的基础知识,不难。然后开始了在广州的实习,这次实习对我帮助很大,我感觉学到很多东西。

实习是在基础消息组,实际实习时间1个月,完成了一个c++内存泄露检测工具,由于业务需求,所以检测泄漏的时候用了一种比较创新的方法,特别是针对协程做了优化。当然这里面有同事们的帮助。由于实习面试、实习表现以及后续转正面试成绩很不错,进入了技术类实习生前两名,所以有幸参加了技术大咖的面试,不过遗憾的是面试挂掉了。

总的来说,微信的经历对我培养在强压力下工作的能力很有帮助,由于入职较晚,离考核只有一个月时间(最开始通知是三个星期),所以基本上那一个月非常忙。不过令人欣慰的是最后写出来的工具确实发挥了作用,检测出一些微信业务代码中的陈年内存泄露。特别是检测出了gperftools中的一个bug,可惜新版本已经fix了。

微信的用户量很大,但其实开发团队相对来说很小,所以很多地方有点像创业公司。招聘门槛也比较高,基本上从我了解到的信息来说,腾讯内部转岗都很难进。待遇上来讲挺不错,推荐大家前往。

2.Hulu Beijing

Hulu也是实习转正,不过是去年G20的时候去实习的。

实习面试:实习面试分三面,因为我在杭州,所以都是电面。每一面都是算法题。

转正面试:Hulu的转正面试是需要先提名的,一般来讲由你实习时候的manager发起提名。面试分3轮,因为人在杭州所以也是skype面试。2轮技术面+1轮boss面。2轮技术面都是算法,在线做题题目不难。

总体感觉,一般如果你申请的是SDE,那么面试是在一个共享文档上写代码,感觉我遇到的题都不难,题目比较注重基本功的考察。但是也有同学遇到比较难的题,这个应该和面试官有关,但是总体而言Hulu目前的面试难度没有五六年之前传说级那么难了。

总结:Hulu是家很不错的公司,技术实力很强。这一点从北京研发中心的员工构成可窥一斑,你身边会有大量清北的同事,甚至是姚班的大神。交流起来会比较顺畅。

3.阿里巴巴

阿里我投的是阿里云,让以前在阿里实习时的同事内推了一下。面试(我记得)分为4面,3轮技术+1轮hr。第一面面试问了我实验室的项目,然后一些系统方面的基础知识。最后写了一道基础的编程题。二面问了我除了内存相关的东西,对linux内核还有哪些了解之类的问题,由于对内核其他方面不是很了解,答的比较尴尬。最后问了OS中的一个基础题,我没答好。三面是交叉面,面试官好像是阿里云数据库团队的。具体问了啥已经忘了基本上是问各方面的基础知识。由于数据库我不是很懂,聊不起来。

总结:总的感觉是阿里云很重视你的既有经验,特别是在某个领域的深度,面试过程中很看重基本功,编程方面基本没问,可能是因为我简历上写了acm经历的缘故。阿里云现在还是比较缺人的,因为这几年发展的很好。我投的是内核团队也就是早前的淘宝内核组。面试通过后,会认真和你交流,实际选组比较自由,当我表达对分布式有兴趣之后,也让块存储的同事和我交流了,总之会比较尊重你的选择。

4.网易游戏

网易游戏让实验室学长内推了一下,由于在hihocoder上做了几场offer收割赛成绩不错,所以免去了在线笔试。onsite面试在网易杭州园区,分为30分钟的白板(纸上)写题+2轮面试。白板写题部分我遇到的是实现LRU Cache,我是用unordered_map+双向链表来做的,leetcode上有原题。然后是面试,面试时间很长,问了很多东西,首先是LRU Cache这题,review代码之后问我用单链表怎么做,然后还有OS、network、database、data structure/algorithm方面的一些基础。问了最长公共子序列,秒杀,面试官也笑了,觉得这题不该问。。还有一题是给出一个结构体的定义,现在已知指向该结构体的一个实例中的一个成员的指针,求出该实例的起始内存地址。其实这是linux内核中的链表经常用的一个技巧,对应的宏叫container_of,但是面试时候一直没想起来是怎么做的,后来发现关键点是把常数强转为指向结构体的指针,这样就可以知道给出的成员与结构体起始位置的偏移量。另外还有一题是告诉你地图上有很多怪物和玩家,用二维坐标表示,怪物和玩家都是运动的,当玩家距离怪物距离R以内时会察觉并攻击,问怎么维护这个关系。这题没答好。二面没有具体考察,主要是问我在微信的项目,对实习过的各个公司的看法等等问题。

总结:如果喜欢玩游戏做游戏,去这家不会有错。

5.依图科技

依图是一家人工智能领域的创业公司,第一次听说是去年CAD一位学长去面试了,和我说很不错,后来一位本科同学也跳槽去了,问了下感觉不错就去面了。我投了算法工程师和后台开发两个岗位,其实我并不懂机器学习,但是当时有转机器学习的想法。

依图面试

面试分为4轮,3轮技术面+1轮大佬面。第一轮是算法面,个人感觉这轮面试是我整个秋招过程中面试难度最大的两轮面试之一,另一轮是微软的第一面。当然题目仍然是leetcode水平,并没有真的很难。第二轮有点忘了,只记得问了道非常有意思的智力题,回答的不错。第三轮没问算法,问了system design:如何设计一个微博系统,用户10亿,DAU 1亿。听完有点懵,以前没想过这些问题。这一面答的不好。基本是是在提示下一点点前进。这一轮收获很大,以前从没考虑过这种问题。这样一个系统,需要哪些功能,QPS怎么假设,数据表怎么设计,需要多少台服务器,业务需要多少台,存储需要多少台,每台配置如何,何种外存,ssd还是机械盘,机械盘转速多少,怎么算出具体iops,容灾怎么做,网络瓶颈等等,非常具体。

总结:依图现在发展很好,而且薪水给的心服口服。

6.拼多多

同学面完后向hr推荐了我,听HR介绍了之后感觉公司不错就投了简历。

笔试题很不错,不是都很简单那种。其中有一道是机器人扫地的题目,让人感觉耳目一新。

onsite分两轮,第一轮面试官尝试问了我一些网络方面的问题,因为我这块不熟,所以一直尬聊。最后做了一道dp题,回答的比较好

总结:

7.google

参加了kickstart笔试,onsite是在上海。第一轮比较顺利,第二轮时候沟通有点问题,面试官在回答我clearify的问题时给了错误的条件。

总结:google题不难但是一定要注意理解题意,做题前和面试官沟通清楚。如果面试官自己也搞错了,那就没办法了。google今年似乎只提供了北京和上海的岗位,无法申请海外岗。

8.facebook

找了学长内推但是联系我的是facebook London的hr说可以提供伦敦那边的机会,很可惜电面挂了。面试题是leetcode难度,但是第二题题目理解错了,写完之后又重写,最后时间不够了。

总结:fb的hr做事非常高效。面试前发了很多相关资料,回邮件也非常快。面试的时候我是边说边写代码的,感觉其实是有难度的,因为很多时候头脑中有一个中文转英文的过程会打断思考。现在我的看法是先说完思路,写代码的时候就不要解释了,写完之后再对必要之处进行解释从我的经历来推测今年fb可能是不会为处于美国之外的外国候选者(应届毕业生)sponsor H1B。目前H1B政策前景不明的情况下,没有美国学位的候选人劣势很大。如果真想去这家,还是去美国读个研吧。

9.微软西雅图

这是我今年秋招的最后一个面试。最后也选择了这个offer。

由于google和facebook纷纷挂掉导致心情很差。痛定思痛,我打算好好复习准备微软的面试。于是开始刷leetcode的median题,我发现对于acm选手来说,hard题并不算难,因为很多都是acm竞赛中的一些套路。反而一些median题思路清奇,万一遇到又没做过的话临场很难想到最优解。于是面试前几个星期,我认真刷了array、linkedlist、tree、string等几个专题。并且复习了以前打比赛时候的一些算法,比如莫队分块、BIT、线段树、manacher、最小表示法等比较简单好写又非常实用的算法。然而这些都没有什么卵用。事实证明,好好刷leetcode就好了。

微软面试是在上海,面试分4面,都是英文面。算法部分不是很难。但是设计题感觉没答好。不过最后还是拿到了offer。由于签了NDA,具体题目就不透露了。

总结:据我目前信息来看,MS是今年唯一一家为中国大陆应届毕业生提供美国岗位的公司,可以说是良心企业在中国大陆招收的人很少,个人估计在20人以内。

10.Jane Street Capital

JSC不是我接触的第一家金融类公司,我记得去年去上海面试过JP Morgen的quant岗(实习),话说JPMorgen的面试非常有意思,面了整整一天并且全是英文面,到最后真的够呛。话说回来,JSC是美国一家对冲基金,在NYC、HK、London都有office。最早知道这家公司是因为浙大以前有个大牛叫崔天翼——也就是网络上背包九讲的作者DD(据说是他高中时候写的。。)拒了google的offer去了这家公司。后来姚班的刘佳倩在blog中也提到了这家公司。据说JSC的bar非常高,而且hack氛围很好而且薪水逆天。抱着试一试万一成功了岂不是很爽重在参与的心态我在官网投递了简历。我投的是软件开发岗,一星期后hr打电话来聊了5分钟,询问了一些背景情况,说如果有匹配的岗位会发起面试。几天后发来拒信。。。

总结:这家的软件开发岗位招的人极少,我感觉有些年份是不招人的,并且候选人的各方面要求都非常高,可以说是精英主义了。而且据说会OCaml并不会为你加分,实际上对方不在乎你会什么,有哪些技能等,而是看重你的聪明程度这个公司的信息较少,相关的面经可以看:

http://blog.sina.com.cn/s/blog_52f526870102wkca.html

http://blog.sina.com.cn/s/blog_72f8a5d00102w6p3.html

11,其他还投递了一些公司,比如今日头条,但是面试流程太诡异了。很早就让同学内推了,但是一直没任何消息。结果过了一个月hr和我说在人才库中看到了我的简历也就是说我简历挂了然后又内推了一次。之后头条到浙大宣讲,当场笔试。做完又没消息了。当时hr说只要以前内推过的就可以不需要当场再投简历我就没投。但是当场投的好像去面试了。。后来11月多了终于联系我面试。。因为已经决定去微软了,于是拒了面试。

总的来讲,找工作不仅是看实力,运气也很重要,但是实力是前提。人总有发挥不好的时候,但机会只有一次,所以better safe than sorry,准备越充足越好。很多学弟学妹咨询我赴美工作相关的问题,有些问题我自己也没有答案,所以很难给出令人信服的解答。但是一些方向性和操作性的问题我还是有点经验的,欢迎与我交流。

        另一方面,从目前的形势上来说,国内在一些方面是领先美国的,而且现在国内的待遇也上来了(很多创业公司开出了很高的offer,和美国那边差距在缩小。所以出国并不一定就好,关键是要找到适合自己的道路。就到这里吧,以后有机会可以再聊聊我的一些实习经历。

        btw,最近在做区块链,主要是智能合约相关的研究。有兴趣有时间的同学可以一起交流。

cf#369 div2

很久没做题了,昨天这场codeforces时间比较早就做了一下。A
A.Bus to Udayland x5233
签到题

#include<stdio.h>
#include<string.h>
char mat[1000+10][5];
int main()
{
    int i,j;
    int n;
    char tmp;
    while(~scanf("%d",&n))
    {
        getchar();
        bool flag=0;
        for(i=1;i<=n;i++)
        {
            scanf("%c%c%c%c%c",&mat[i][1],&mat[i][2],&tmp,&mat[i][3],&mat[i][4]);
            getchar();
            if(flag) continue;
            if((mat[i][1]=='O') && (mat[i][2]=='O'))
            {
                mat[i][1]='+';mat[i][2]='+';
                flag=1;
                continue;
            }
            if((mat[i][3]=='O') && (mat[i][4]=='O'))
            {
                mat[i][3]='+';mat[i][4]='+';
                flag=1;
                continue;
            }
        }
        if(!flag) {printf("NO\n");continue;}
        printf("YES\n");
        for(i=1;i<=n;i++)
            printf("%c%c|%c%c\n",mat[i][1],mat[i][2],mat[i][3],mat[i][4]);
    }
    return 0;
}

B.Chris and Magic Square x3112
也很简单

#include<stdio.h>
#include<string.h>
typedef long long ll;
ll a[510][510];
int main()
{
    int i,j;
    int n;
    while(~scanf("%d",&n))
    {
        int x,y;
        int flag=1;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                scanf("%I64d",&a[i][j]);
                if(!a[i][j]) {x=i,y=j;}
            }
        if(n==1) {printf("1\n");continue;}
        ll ans=-1,tmp=0;
        for(i=1;i<=n;i++)
        {
            if(i==x) continue;
            for(j=1;j<=n;j++) tmp+=a[i][j];
            if(ans==-1) {ans=tmp;tmp=0;continue;}

            if(tmp!=ans)
            {
                flag=0;
                break;
            }
            tmp=0;
        }
        if(!flag){printf("-1\n");continue;}
        tmp=0;
        for(j=1;j<=n;j++)
        {
            if(j==y) continue;
            for(i=1;i<=n;i++) tmp+=a[i][j];
            if(tmp!=ans)
            {
                flag=0;
                break;
            }
            tmp=0;
        }
        if(!flag){printf("-1\n");continue;}
        tmp=0;
        for(i=1;i<=n;i++) tmp+=a[i][y];
        ll ret1=ans-tmp;
        tmp=0;
        for(j=1;j<=n;j++) tmp+=a[x][j];
        ll ret2=ans-tmp;
        if(ret1!=ret2 || ret1<1){printf("-1\n");continue;}
        a[x][y]=ret1;
        ll c1=0,c2=0;
        for(i=1;i<=n;i++) c1+=a[i][i],c2+=a[i][n+1-i];
        if(c1!=c2 || c1!=ans) {printf("-1\n");continue;}
        printf("%I64d\n",ret1);
    }
    return 0;
}

C.Coloring Trees x1710
题意:有一排树。每棵树有一种颜色或者还没被涂色,如果一棵树原本就有颜色,那么不能改色,只有没被上色的树可以涂颜色。相邻且颜色相同的树属于同一组。p[i][j]表示将第i棵树涂成颜色j的代价。问:通过上色将这些树分成k组的最小代价是多少?
树的数量、颜色的数量均<=100
序列?分组?最优解?直接往dp上去想
dp[i][j][t]表示将前i个分成t组且第i个涂成颜色j的最小代价。
转移如下:
(1)如果第i个是已经有颜色,且颜色为a[i]
dp[i][a[i]][t]=min(dp[i-1][a[i]][t],min of dp[i-1][not a[i]][t-1])(注意t==1时后一项时没有的)
(2)如果第i个没有颜色
dp[i][j][t]=min(dp[i-1][j][t],min of dp[i-1][not j][t-1])+p[i][j];
初始化dp[1][j][1]时也要如上分类讨论,其余初始化为inf。
时间复杂度O(n*m*n*n), 大概10^8数量级,能过。。。
这题耗费了比较多的时间,现在熟练度下降很多~

#include<stdio.h>
#include<string.h>
typedef long long ll;
const ll inf=100000000000000000LL;
int n,m,k,t,s;
ll dp[110][110][110],p[110][110];
int a[110];
ll min(ll a,ll b){return a<b?a:b;}
int main()
{
    int i,j;
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%I64d",&p[i][j]);
        if(k>n){printf("-1\n");continue;}
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                for(t=1;t<=n;t++)
                    dp[i][j][t]=inf;
        if(a[1]!=0)
        {
            dp[1][a[1]][1]=0;
        }
        else
        {
            for(i=1;i<=m;i++)
                dp[1][i][1]=p[1][i];
        }
        for(i=2;i<=n;i++)
            for(j=1;j<=m;j++)
                for(t=1;t<=k;t++)
                {
                    if(a[i]!=0)
                    {
                        if(j!=a[i]) continue;
                        ll tmp=inf;
                        dp[i][a[i]][t]=dp[i-1][a[i]][t];
                        if(t>1){
                            for(s=1;s<=m;s++)
                            {
                                if(s==a[i]) continue;
                                if(dp[i-1][s][t-1]<tmp) tmp=dp[i-1][s][t-1];
                            }
                        }
                        dp[i][a[i]][t]=min(dp[i][a[i]][t],tmp);
                        continue;
                    }
                    ll tmp=inf;
                    dp[i][j][t]=dp[i-1][j][t]+p[i][j];
                    if(t>1)
                    {
                        for(s=1;s<=m;s++)
                        {
                            if(s==j) continue;
                             if(dp[i-1][s][t-1]+p[i][j]<tmp) tmp=dp[i-1][s][t-1]+p[i][j];
                        }
                    }
                    dp[i][j][t]=min(dp[i][j][t],tmp);
                }
        ll ans=inf;
        for(i=1;i<=m;i++)
            ans=min(ans,dp[n][i][k]);
        if(ans<inf) printf("%I64d\n",ans);
        else printf("-1\n");
    }
    return 0;
}

D.Directed Roads x948
这题其实比上一题简单,个人感觉。
n个点,n条边。没有圈(自环)。每条弧可以反向,问有多少种将边反向的方案可以使得图没有环,两个方案不同当且仅当两个方案中至少存在一条不同的弧。
n<=2*10^5
容易想到对于一个环中的弧,只要不全部反向或者一条弧都不反向,其它方案都可以去掉改环。所以方案数是(2^len)-2.len 是环中弧的数量。
对于不在环中的弧,选不选无所谓,所以针对这些弧,所有方案都行, 方案数是2^k.k是这类弧的数量。最后乘法原理。
最后答案:∏((2^len)-2)*(2^k)
∏ 表示连乘
可见最后是一个简单的快速幂模mod

-_-#速度太慢了,这题没来得及submit。。。

#include<stdio.h>
#include<string.h>
typedef long long ll;
const int mod=(1e9)+7;
int n;
int a[200000+10];
int order[200000+10];
ll cal(int k)
{
    ll ans=1,p=2;
    while(k)
    {
        if(k%2)
        {
            ans=(ans*p)%mod;
            k--;
        }
        p=(p*p)%mod;
        k/=2;
    }
    return ans;
}
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        memset(order,0,sizeof(int)*(n+5));
        int cnt=0;
        ll ans=1;
        int m=n;
        for(i=1;i<=n;i++)
        {
            if(order[i]) continue;
            j=i;
            int end=cnt+1;
            while(!order[j])
            {
                //printf("%d ",j);
                order[j]=++cnt;
                end=order[j];
                j=a[j];
            }
            if(order[j]<order[i]) continue;
            int len=end-order[j]+1;
            //printf("%d\n",len);
            m-=len;
            ans=(ans*((cal(len)-2+mod)%mod))%mod;
        }
        ans=(ans*cal(m))%mod;
        printf("%I64d\n",ans);

    }
    return 0;
}

E.ZS and The Birthday Paradox x241

google code jam2016资格赛题解

A. Counting Sheep
小数据暴力,大数据也一样
B. Revenge of the Pancakes
小数据暴力,大数据没做
C. Coin Jam
小数据暴力,大数据没做
D. Fractiles
题意:一个序列由两种字符组成:L、G.给出k,c,s。表示序列初始长度k,变换了c次。每次变换:L的地方用最初始序列代替,G的地方用k个G代替。
现序列各个位置的值是看不到的,你可以选择查看其中的s个位置的值。问:能否通过小于等于s次查看,来推断出现序列是否包含G。
这题我是这样做的。小数据大数据一个做法。
如果查看一个位置发现是G,那么我们就知道序列是含有G的了,所以问题其实是在问:有没有一种查看的策略使得在查看的值都是L的情况下,可以断定序列必定没有G。
我们可以把整个变换的过程画出来,可以发现是一棵k叉树(注意一点这里我把原始序列的k个结点最为统一的“根结点”)。叶子节点是现序列。关键一点在于当得到了位置pos的值是L之后,我们就知道了pos位置的值是L之后,就知道了pos的父节点是L,它的父节点也是L。换言之,pos到树根的路径上的结点都是L。
那么为了尽可能通过一次查看得到最多信息,我们可以查看根节点的第二个子结点的第三个子结点的…………(一直到叶子结点)的值。这样就得到了min(c,k)个连续位置的值,接下来重复这个查看过程就行。
这个还是有个图比较好解释。。下次加个图。

#include<stdio.h>
#include<string.h>
typedef long long ll;
ll a[110];
ll ans[110],cnt;
inline ll min(ll a,ll b){return a<b?a:b;}
int main()
{
    //freopen("D-large.in","r",stdin);
    //freopen("D-large.out","w",stdout);
    ll i,j;
    int k,c,s;
    int t,cases=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&k,&c,&s);
        printf("Case #%d:",++cases);
        if(c==1)
        {
            if(s<k) {printf(" IMPOSSIBLE\n");continue;}
            for(i=1;i<=k;i++) printf(" %d",i);
            printf("\n");
            continue;
        }
        if(k==1)
        {
            if(s<k) {printf(" IMPOSSIBLE\n");continue;}
            printf(" 1\n");continue;
        }
        cnt=0;
        a[0]=1;a[1]=k;
        for(i=2;i<=c;i++)
            a[i]=a[i-1]*(ll)k;
        for(i=1;i<=k;)
        {
            ll tmp=0;
            for(j=-1;j<=c-2;j++)
            {
                if(i+j+1<=k)
                    tmp+=(i+j)*a1;
                else
                    tmp+=(k-1)*a1;
            }
            ans[++cnt]=tmp+1;
            i+=min(c,k-i+1);
        }
        if(s<cnt) {printf(" IMPOSSIBLE\n");continue;}
        for(i=1;i<=cnt;i++) printf(" %I64d",ans[i]);
        printf("\n");
    }

    return 0;
}

linux内核模块编程笔记

最近因为实验室项目,开始接触了一点linux内核模块编程
内核编译选项.config所在路径:/usr/src/相应内核版本/.config
内核符号表:在编写内核模块的时候,因为LKM是动态加载到内核中,也就是说这时的内核是在内存中运行的,所以正确获取内核函数和变量的地址很重要。如果我们在内核模块中直接将地址写死,那么显然不通用,在另一个内核上可能地址就变了。内核符号表就是用于解决这个问题。每个内核都有其内核符号表,里面是内核导出的符号及其地址。我们编写的内核模块通过访问这个内核符号表就可以得到当前正在运行的内核的可用函数和变量的确切地址。
那么怎样使用内核未导出的符号呢?
我们可以使用kallsyms_lookup_name(char*)这个函数,该函数参数是符号名,返回unsigned long型的函数/变量地址。这个方法有个前提,那就是kallsyms_lookup_name(char*)这个符号本身是被内核导出的,所以要用CONFIG_KALLSYMS=y来编译内核,或者修改内核源码中的kallsyms.c文件,增加EXPORT_SYMBOL(kallsyms_lookup_name);手动将该符号导出
————————————————————————————————————————————————————————————————————————————
过程中的问题和要点:
linux内核的三种内存模型
page结构中的_count和_mapcount
_mapcount:在页表中每增加一个映射项,_mapcount就加1.初始值是-1

使用page_address之后发现所有页帧的虚拟地址都是在内核地址空间?what the fuck
__________________________
x86_64的内存地址空间需要研究
——————————————————————————————
读某个内核虚拟地址出错。BUG: unable to handle kernel paging request at ffff880020000000

找到读取物理内存内容的方法了,如下:
前面失败的原因是较新版本的linux内核限制了对/dev/mem的读取,默认只能读取前1M字节的数据。解决方法时修改.config中的CONFIG_X86_PAT=n,CONFIG_STRICT_DEVMEM=n.然后重新编译内核
编译内核过程(抱歉,不要嫌弃我菜,我经常忘。所以记一下)
make menuconfig生成.config(如果要编译的内核和现有内核版本相同,可以从/boot/config-版本号 copy一份放到源码根目录)
make modules 编译一下内核模块
make modules_install 安装内核模块(到/lib/modules目录)
make install 安装内核(copy 生成的内核映像到/boot下面,修改gurb启动项等)

由于/dev/mem是整个物理地址空间的映像,包括了IO端口、ROM的地址,并不全是RAM,所以要先读取/proc/iomem文件得到System RAM的地址分布,之后读取System RAM的部分即可
代码如下,注意不要读到RAM之外的地方,可能会导致出错。

#include<stdio.h>
#include<string.h>
#include<unistd.h>
#include<sys/mman.h>
#include<sys/types.h>
#include<sys/stat.h>
#include<fcntl.h>
typedef long long ll;
const ll max_read=10000000;
char buf[max_read+10];
typedef struct Node{
	ll be,en;
}Node;
Node node[10010];
int cnt;
int main()
{
	freopen("/proc/iomem","r",stdin);
	cnt=0;
	int i;
	while(gets(buf))
	{
		int len=strlen(buf);
        if(strstr(buf,"System RAM")==NULL) continue;
        char *s=buf;
        strtok(s,":");
        printf("%s\n",s);
        char tmp;
        cnt++;
        sscanf(s,"%llx-%llx",&node[cnt].be,&node[cnt].en);
    }
	
    int fdmem,fdout;
    fdmem=open("/dev/mem", O_RDWR|O_SYNC);
	fdout=open("memdump.txt",O_CREAT|O_RDWR|O_SYNC);
    if ((fdmem == -1) || (fdout==-1))
    {
		printf("open err\n");
        return -1;
    }
	for(i=1;i<=cnt;i++)
    {
        ll be=node[i].be,en=node[i].en;
        lseek(fdmem,be,SEEK_SET);
        printf("read %llx-%llx\n",be,en);
        while(1)
        {
            if(en-be+1<=max_read)
            {
                read(fdmem,buf,en-be+1);
                printf("read %llx-%llx\n",be,en);
                write(fdout,buf,en-be+1);
                break;

            }
            read(fdmem,buf,max_read);
            printf("read %llx-%llx\n",be,be+max_read-1);
            write(fdout,buf,max_read);
            be+=max_read;
        }
    }
	close(fdmem);
	close(fdout);
	
    return 0;
}

虚拟化笔记

VMM进程地址空间中存储了各个虚拟机具体的硬件环境(如PC值、EAX值等等,PC值指向guestOS的代码),guestOS在运行时(其实就是VMM将真实寄存器等硬件环境改为guestOS的环境,PC改为指向guestOS的代码,这样guestOS的代码就开始运行了),其代码是真正运行在真实cpu上的,由于guestOS是在ring3,所以执行特权指令时触发异常,VMM的异常处理模块截获异常,然后再做安排。

设备模拟

1.guestOS中的驱动程序称为前端(Front-End,FE)设备驱动,而VMM中的驱动程序为后端(Back-End,BE)设备驱动。

硬件辅助虚拟化:硬件本身加入虚拟化功能,就可以截获操作系统对敏感指令的执行或者对敏感资源的访问,从而通过异常的方式报告给VMM,这样就解决了虚拟化的问题。

硬件辅助虚拟化的典型:Intel的VT-x技术。VT-x技术在处理器上引入了一个新的执行模式用于运行虚拟机。当虚拟机执行在这个特殊模式中时,它仍然面对的是一套完整的处理器寄存器集合和执行环境,只是任何特权操作都会被处理器截获并报告给VMM

linux伙伴系统

前段时间由于实验室相关项目的需要+OS课的presentation,看了linux2.6.24内核伙伴系统的源码。写一下总结。

引言
    伙伴系统作为一种古老而历经检验的系统,也被Linux内核所采用。伙伴系统的提出是为了管理和记录内存的分配和使用。在X86架构的Linux内核版本 2.6.24及之后,Linux对原本的伙伴系统做了改进,在原来的基础上加入了反碎片机制,使得内核能够更好的管理内存的外部碎片。
    本文的分析针对X86架构。首先介绍了什么是伙伴系统,以及伙伴系统的相关数据结构。然后分析了X86架构上Linux 2.6.24这个版本对伙伴系统做的改进(加入了反碎片机制)。最后从源代码出发,深入揭示了伙伴系统的内核工作流程。
什么是伙伴系统
    伙伴系统的宗旨就是用最小的内存块来满足内核对于内存的请求。在最初,只有一个块,也就是整个内存,假如为1M大小,而允许的最小块为64K,那么当我们申请一块200K大小的内存时,就要先将1M的块分裂成两等分,各为512K,这两份之间的关系就称为伙伴,然后再将第一个512K的内存块分裂成两等分,各为256K,将第一个256K的内存块分配给内存,这样就是一个分配的过程。下面我们结合示意图来了解伙伴系统分配和回收内存块的过程。
图1 伙伴系统示意图
1. 初始化时,系统拥有1M的连续内存,允许的最小的内存块为64K,图中白色的部分为空闲的内存块,着色的代表分配出去了的内存块。
2. 程序A申请一块大小为34K的内存,对应的order为0,即2^0=1个最小内存块
   2.1 系统中不存在order 0(64K)的内存块,因此order 4(1M)的内存块分裂成两个order 3的内存块(512K)
   2.2 仍然没有order 0的内存块,因此order 3的内存块分裂成两个order 2的内存块(256K)
   2.3 仍然没有order 0的内存块,因此order 2的内存块分裂成两个order 1的内存块(128K)
   2.4 仍然没有order 0的内存块,因此order 1的内存块分裂成两个order 0的内存块(64K)
   2.5 找到了order 0的内存块,将其中的一个分配给程序A,现在伙伴系统的内存为一个order 0的内存块,一个order 1的内存块,一个order 2的内存块以及一个order 3的内存块
3.程序B申请一块大小为66K的内存,对应的order为1,即2^1=2个最小内存块,由于系统中正好存在一个order 1的内存块,所以直接用来分配
4 程序C申请一块大小为35K的内存,对应的order为0,同样由于系统中正好存在一个order 0的内存块,直接用来分配
5 程序D申请一块大小为67K的内存,对应的order为1
   5.1 系统中不存在order 1的内存块,于是将order 2的内存块分裂成两块order 1的内存块
   5.2 找到order 1的内存块,进行分配
6 程序B释放了它申请的内存,即一个order 1的内存块
7 程序D释放了它申请的内存
   7.1 一个order 1的内存块回收到内存当中
   7.2由于该内存块的伙伴也是空闲的,因此两个order 1的内存块合并成一个order 2的内存块
8 程序A释放了它申请的内存,即一个order 0的内存块
9 程序C释放了它申请的内存
   9.1 一个order 0的内存块被释放
   9.2 两个order 0伙伴块都是空闲的,进行合并,生成一个order 1的内存块m
   9.3 两个order 1伙伴块都是空闲的,进行合并,生成一个order 2的内存块
   9.4 两个order 2伙伴块都是空闲的,进行合并,生成一个order 3的内存块
   9.5 两个order 3伙伴块都是空闲的,进行合并,生成一个order 4的内存块
 从上述例子中,我们可以总结出伙伴系统分配内存释放内存的算法:
分配内存
1.寻找大小合适的内存块(大于等于所需大小并且最接近2的幂)
  • 1.1.如果找到了,分配给应用程序
  • 1.2.如果没找到,分出合适的内存块
  • 1.2.1.对半分离出高于所需大小的空闲内存块
  • 1.2.2.如果分到最低限度,分配这个大小
  • 1.2.3.回溯到步骤1
  • 1.2.4.重复该步骤直到一个合适的块
释放内存
1.释放该内存块
  • 1.1.寻找相邻的块,看其是否释放了。
  • 1.2.如果相邻块也释放了,合并这两个块,重复上述步骤直到遇上未释放的相邻块,或者达到最高上限(即所有内存都释放了)
伙伴系统的数据结构
    我们首先来看一下伙伴系统相关的数据结构,首先看一下free_area。
<include/linux/mmzone.h>
struct free_area {
    struct list_head    free_list;
    unsigned long     nr_free;
};
    其中nr_free指定了当前内存区中空闲页块的数目。free_list是用于链接空闲页的链表,页链表包含大小相同的连续内存区。是伙伴系统里非常重要的概念,它描述了内存分配的数量单位,例如2^order,order就是阶,并且其范围从0到MAX_ORDER。order通常设置为11,这意味着一次分配可以请求的页的最大数是2^11=2048。
    free_area[]数组中的各个元素索引也可以理解为索引,第0个链表代表内存管理区里的单页,第1个链表代表内存管理区里的两页。从下图可以看出,free_area[0]每个元素代表单个页帧,free_area[2]的每个元素代表4个页帧。
伙伴系统的反碎片机制
    本文研究的是X86平台Linux2.6.24版本的内核。在该版本中,对于伙伴系统加入了反碎片机制(anti-fragmentation),试图从最初开始就尽可能防止碎片。
    首先我们必须知道,内核将已分配页分为以下三种不同的类型:
  不可移动页(UNMOVABLE): 这些页在内存中有固定的位置,不能够移动。
  可回收页(RECLAIMABLE): 这些页不能移动,但可以删除。内核在回收页占据了太多的内存时或者内存短缺时进行页面回收。
  可移动页(MOVABLE): 这些页可以任意移动,用户空间应用程序使用的页都属于该类别。它们是通过页表映射的。当它们移动到新的位置,页表项也会相应的更新。
  在内存子系统初始化期间,所有的页都被标记为可移动的。在启动期间,核心内核分配的内存是不可移动的。此时内核的策略是分配一个尽可能大的连续内存块,将其从可移动列表转换到不可移动列表。原因如下:
   例如:现有一块可移动的具有16页的连续空闲内存块。当内核需要分配1页不可移动内存页时。分配器选择后8页(而不是一页)转移到不可移动列表,然后从 不可移动列表中选择1页用于分配。如果内核又需要分配1页不可移动内存页则从不可移动列表中选择一页用于分配,下图显示了进行4次分配后内存的分布。
        但如果内核只选择1页用于分配将其加入到不可移动列表,当下次需要分配时又选择一页加入到不可移动列表,下图显示了按照这种方式进行4次分配后内存的分布。
        因此,当没有满足可用于分配的不可移动空闲块时,分配器会在可移动列表中迁移一个尽可能大的连续内存块给不可移动列表。这样避免了启动期间内核分配的内存散列到物理内存各处,从而使其他类型的内存分配免受碎片的干扰。
        内核定义了一些宏来表示不同的迁移类型:
<include/linux/mmzone.h>
    #define MIGRATE_UNMOVABLE     0
    #define MIGRATE_RECLAIMABLE   1
    #define MIGRATE_MOVABLE       2
    #define MIGRATE_RESERVE       3
    #define MIGRATE_ISOLATE       4 /*用于跨越NUMA结点移动物理内存页*/
    #define MIGRATE_TYPES         5
    2.6.24版本对伙伴系统结构的主要调整,是将空闲列表分解成MIGRATE_TYPE个列表,数据结构如下(注意变化的部分):
<include/linux/mmzone.h>
struct free_area {
    struct list_head    free_list[MIGRATE_TYPE];
    unsigned long     nr_free;
};
    也就是说每一个free_area又根据MIGRATE_TYPE分成了5种类型,每种类型里面分别都有一个head_list结构体。
    如果内核无法满足针对某一给定迁移类型的分配请求的话,内核提供了一个备用列表,规定了在指定列表中无法满足分配请求时,接下来应使用哪一种迁移类型:
static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {  
  • [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_RESERVE },  
  • [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_RESERVE },  
  • [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },  
  • [MIGRATE_RESERVE] = { MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE }, 
}; 
    内核想要分配不可移动页时,如果对应链表为空,则后退到可回收链表,接下来到可移动页链表,最后到紧急分配链表。
    在X86架构中存在着三种内存域ZONE_DMA、ZONE_NORMAL、ZONE_HIGHMEM,那么每个内存域都有一个free_area数据结构:
<mm/mmzone.h>
struct zone {
  • struct free_area    free_area[MAX_ORDER];
}
    而如果是在NUMA架构中,可能存在着多块物理内存,其结构可能是如下图所示:
    基于伙伴系统的内存管理专注于某个节点的某个内存域,例如DMA或高端内存域。但所有内存管理区和节点的伙伴系统都通过备用分配列表链接起来。在首选内存 管理区或节点无法满足分配请求时,首先尝试用同一节点的另一个内存管理区分配,反复尝试下一个结点直到满足请求。

页的分配以及源代码剖析
       就伙伴系统的接口而言,NUMA或UMA体系结构是没有差别的,二者的调用语法都是相同的。所有函数的一个共同点是:只能分配2的整数幂个页。

从函数关系图上可以看到,最终的分配任务落在__alloc_pages()上。我们来看这个函数的代码
————————————————————————————待续————————————————-——————

leetcode比较重要的题(always updating)

对leetcode比较重要的题做下记录。
“重要”的条件:
1.没能想到解法的题
2.没能想到最优解的题
3.虽想到最优解,但是面试现场容易出错的题
关于第三点易出错是指完成时间较长,或者对代码修改多次。
注意,建议读者在做题时不要使用编译器编译,而是用肉眼和纸笔进行debug,毕竟面试时不可能让你用编译器。
10 Regular Expression Matching(hard)
这题虽然知道用递归,但是还是没想出来。。

bool isMatch(char* s, char* p) {
    int i,j;
    if(*p==0) return *s==0;//两者都到末尾是递归结束条件
    if(*(p+1)!='*')//根据下一个字符是否是'*'区分
    {
        if(*s!=0 &amp;amp;&amp;amp; (*s==*p || *p=='.'))
            return isMatch(s+1,p+1);
        return 0;
    }
    else
    {
        while(*s!=0 &amp;amp;&amp;amp; (*s==*p || *p=='.'))//如果两者当前字符匹配,则首先看*匹配0个试试,不行则匹配1个
        {
            if(isMatch(s,p+2)) return 1;
            s++;
        }
        return isMatch(s,p+2);//两者当前字符不匹配,那么只能是*匹配0个的情况
    }
}

Find the Duplicate Number
没想到最优解法

http://segmentfault.com/a/1190000003817671

http://blog.csdn.net/wongson/article/details/48979391

int findDuplicate(int* nums, int numsSize) {
    int i,j;
    int n=numsSize;
    int fast=0,slow=0;
    slow=nums[0];
    fast=nums[nums[0]];
    while(slow!=fast)
    {
        slow=nums[slow];
        fast=nums[nums[fast]];
    }
    fast=0;
    while(slow!=fast)
    {
        slow=nums[slow];
        fast=nums[fast];
    }
    return fast;
}

154 Find Minimum in Rotated Sorted Array II
Find Minimum in Rotated Sorted Array的升级版,可能有重复数.如3 3 4 4 6 1 1 2 3 3
关键是对重复数的处理,观察可以知道中间的重复数字对结果不会有影响。而两侧的重复数字,我们只要去除重复就行。这样一般情况是O(lgn)。。
但是这样做最坏情况下是O(n)的。。应该是是有最坏O(lgn)的解法的,但是我不知道怎么改二分的条件。。暂时先这样吧。。
注意如果nums[m]==nums[0]的情况也要l=m+1.因为开始时单独考虑了1 2 3 4这种没有“移动”的情况,所以出现num[m]==nums[0]一定是2(l,m指向这里) 1(r指向这里),这种情况,显然l指针应该右移。

int findMin(int* nums, int numsSize) {
    int n=numsSize;
    if(n==1) return nums[0];
    if(nums[0]&amp;lt;nums[n-1]) return nums[0];
    int l=0,r=n-1;
    while((l+1&amp;lt;n) &amp;amp;&amp;amp; nums[l]==nums[l+1]) l++;
    while((r-1&amp;gt;=0) &amp;amp;&amp;amp; nums[r]==nums[r-1]) r--;
    while(l&amp;lt;r &amp;amp;&amp;amp; (nums[l]==nums[r])) r--;
    if(l==r) return nums[l];
    while(l&amp;lt;=r)
    {
        int m=l+(r-l)/2;
        if(nums[m]&amp;gt;=nums[0]) l=m+1;
        else r=m-1;
    }
    return nums[l];
}

Populating Next Right Pointers in Each Node
要求O(1)空间,我理解上大意了,用了深搜,实际上dfs用了栈,空间复杂度是O(lgn)的。。
其实可以通过next指针实现O(1)空间的bfs.

void connect(struct TreeLinkNode *root) {
    if(!root) return;
    bool is_right=0;
    struct TreeLinkNode *start=root,*now,*next;
    while(start)
    {
        root=start;
        now=start-&amp;gt;left;
        next=start-&amp;gt;right;
        if(!now) break;
        while(1)
        {
            if(!is_right)
            {
                now-&amp;gt;next=next;
                now=next;
                root=root-&amp;gt;next;
                if(!root) break;
                next=root-&amp;gt;left;
                is_right=!is_right;
            }
            else
            {
                now-&amp;gt;next=next;
                now=next;
                next=root-&amp;gt;right;
                is_right=!is_right;
            }
        }
        start=start-&amp;gt;left;
    }
    return;
}

Copy List with Random Pointer
copy一个链表,这个链表有两个指针域,一个next指向下一个结点,random域可以指向链表中任意一个结点。
我觉得自己好笨。。直接暴力O(n^2)做了,不过还是能ac。
O(n)的方法是这样的:
(1)原来链表中每个结点后面复制出一个结点,这个结点和原结点信息完全一样
(2)第一步已经malloc出了新链表的结点,这样就可以依次改正新链表结点的random域
(3)依次改正next域,将原链表与新链表分离。

struct RandomListNode *copyRandomList(struct RandomListNode *head) {
        int i,j;
        if(!head) return NULL;
        struct RandomListNode*ansp=NULL,*p=head,*q;
        while(p)
        {
            q=(struct RandomListNode*)malloc(sizeof(struct RandomListNode));
            q-&amp;gt;label=p-&amp;gt;label;
            q-&amp;gt;next=p-&amp;gt;next;
            q-&amp;gt;random=p-&amp;gt;random;
            p-&amp;gt;next=q;
            p=p-&amp;gt;next-&amp;gt;next;
        }
        p=head;
        while(p)
        {
            p=p-&amp;gt;next;
            if(p-&amp;gt;random)
                p-&amp;gt;random=p-&amp;gt;random-&amp;gt;next;
            p=p-&amp;gt;next;
        }
        p=head;
        q=p-&amp;gt;next;
        ansp=q;
        while(p-&amp;gt;next-&amp;gt;next)
        {
            p-&amp;gt;next=p-&amp;gt;next-&amp;gt;next;
            q-&amp;gt;next=q-&amp;gt;next-&amp;gt;next;
            p=p-&amp;gt;next;
            q=q-&amp;gt;next;
        }
        p-&amp;gt;next=NULL;
        return ansp;
}

Maximum Gap
基数排序

class Solution {
public:
    int maximumGap(vector&amp;lt;int&amp;gt;&amp;amp; nums) {
        vector&amp;lt;int&amp;gt; a[10];
        int i,j,k,t;
        int n=nums.size();
        if(n&amp;lt;=1) return 0;
        if(n==2) return abs(nums[0]-nums[1]);
        int len=0,cnt;
        for(i=0;i&amp;lt;n;i++)
        {
            int tmp=nums[i];
            cnt=0;
            while(tmp) tmp/=10,cnt++;
            if(cnt&amp;gt;len) len=cnt;
        }
        for(i=1;i&amp;lt;=len;i++)
        {
            for(j=0;j&amp;lt;=9;j++) if(!a[j].empty()) a[j].clear();
            for(j=0;j&amp;lt;n;j++)
            {
                int tmp=nums[j],xh=1;
                for(k=1;k&amp;lt;=i;k++) xh*=10;
                tmp=tmp%xh/(xh/10);
                a[tmp].push_back(nums[j]);
            }
            int cc=0;
            for(j=0;j&amp;lt;=9;j++)
                for(t=0;t&amp;lt;a[j].size();t++) nums[cc++]=a[j][t];
        }
        int ans=0;
        for(i=1;i&amp;lt;n;i++) if(abs(nums[i]-nums[i-1])&amp;gt;ans) ans=abs(nums[i]-nums[i-1]);
        return ans;
    }
};

Minimum Window Substring
给出字符串s和t,问s中包含t中全部字符的最小区间,返回这个区间。比如t由2个a,3个b组成,那么s中ababb、aabbb、adfabcbb这样的就符合要求,返回长度最小的答案。要求时间O(n)
没能想到最优解。。(为什么我越来越菜了)
解法如下,设置数组is,is[char]表示char字符是否是t需要的。设置数组need,need[cahr]表示在当前窗口下t数组还需多少个char字符,注意need数组是随窗口变化而变化的,可能为负值(表示当前窗口内含有比t所需更多的char字符)
设置变量cnt表示目前窗口满足了t多少字符。
设置指针begin,end。begin指向窗口起始,end指向窗口结束的后一个。初始化为0.当当前窗口不满足要求时,end后移,扩大窗口。只有当当前窗口满足要求时,begin右移试图减小窗口。

int need[200];
bool is[200];
int begin=0,end=0,cnt=0;
void add(char*s)
{
    if(is[s[end]])
    {
        if(need[s[end]]&amp;gt;0) cnt++;
        need[s[end]]--;
    }
    end++;
    return;
}
void del(char*s)
{
    if(is[s[begin]])
    {
        if(need[s[begin]]&amp;gt;=0) cnt--;
        need[s[begin]]++;
    }
    begin++;
    return;
}
char* minWindow(char* s, char* t) {
    int i,j;
    int ans=0x3f3f3f3f;
    int lens=strlen(s),lent=strlen(t);
    if(!s || !t || lens&amp;lt;lent) return &amp;quot;&amp;quot;;
    memset(need,0,sizeof(need));
    memset(is,0,sizeof(is));
    i=0;
    while(t[i]) is[t[i]]=1,need[t[i++]]++;
    int ansbegin=0,ansend=0;
    begin=0,end=0,cnt=0;
    while(begin&amp;lt;=lens-lent &amp;amp;&amp;amp; end&amp;lt;=lens)
    {
        if(cnt&amp;gt;=lent)
        {
            del(s);
            if(cnt&amp;gt;=lent &amp;amp;&amp;amp; end-begin&amp;lt;ans)
            {
                ans=end-begin;
                ansbegin=begin;ansend=end;
            }
            continue;
        }
        add(s);
        if(cnt&amp;gt;=lent &amp;amp;&amp;amp; end-begin&amp;lt;ans)
        {
            ans=end-begin;
            ansbegin=begin;ansend=end;
        }
    }
    s[ansend]=0;
    return s+ansbegin;
}

Longest Valid Parentheses
这题我虽然想到了最优解法,但是提交的时候发现还是考虑错了一种dp转移情况
题意:给出仅由’(‘、‘)’组成的字符串,问最长合法子串有多长。
这题我是用dp做的。dp[i]表示以s[i]结尾的最长合法串的长度。
那么:
———-(1)s[i]==’(‘,则dp[i]=0;
———-(2)s[i]==’)’
———————-s[i-1]==’(‘,则dp[i]=dp[i-2]+2. s[i-2]存在的情况下
———————-s[i-1]==’)',那么设以s[i-1]为结尾的合法串的起始位置则i-1-dp[i-1]+1为tmp(这里考虑一下为什么不用考虑以s[i-1]为结尾的非最长合法串)
——————————–s[tmp-1]==’)',则dp[i]=0,注意s[tmp-1]的存在性
——————————–s[tmp-1]==’(‘,则dp[i]=dp[i-1]+2+dp[tmp-2],注意s[tmp-1]和s[tmp-2]的存在性.这个情况值得注意。。开始我忘了dp[tmp-2]那一块。。

int dp[1000000];
int longestValidParentheses(char* s) {
    int i;
    int len=strlen(s);
    if(len&amp;lt;=1) return 0;
    if(len==2) return ((s[0]=='(') &amp;amp;&amp;amp; (s[1]==')'))?2:0;
    dp[0]=0;dp[1]=(((s[0]=='(') &amp;amp;&amp;amp; (s[1]==')'))?2:0);
    int ans=dp[1];
    for(i=2;i&amp;lt;len;i++)
    {
        if(s[i]=='(') {dp[i]=0;continue;}
        if(s[i-1]=='(') {dp[i]=dp[i-2]+2;continue;}
        int tmp=i-1-dp[i-1]+1;
        if(tmp==0) {dp[i]=0;continue;}
        if(s[tmp-1]==')') {dp[i]=0;continue;}
        if(tmp-1==0) {dp[i]=dp[i-1]+2;continue;}
        dp[i]=dp[i-1]+2+dp[tmp-2];
    }
    for(i=2;i&amp;lt;len;i++) if(dp[i]&amp;gt;ans) ans=dp[i];
    return ans;
}

Best Time to Buy and Sell Stock IV
这题做出来了,但是花的时间比较长,记录一下。
题意:给出n天时间每天的股票价格,给出k,表示最多交易k(买进卖出算一次)次,同一天只能进行一个操作。问n天后最大收益多少?
题目本身挺简单的,但是要用滚动数组,,已经很久没做这类题了,细节上出了些问题。,调的比较久。
解法:dp[i][j]表示前i天最多交易j次能达到的最大收益.那么dp[i][j]=max(dp[i-1][j-1]+第i天进行交易的收益(可能为负),dp[i-1][j]),上述两种情况分别对应第i天是否进行交易。
是不是很像背包。。
注意:我解法里的交易是指一次买入或一次卖出动作,这和题意里面的交易含义不一样。

int dp[200000];
int max(int a,int b){return a&amp;gt;b?a:b;}
int min(int a,int b){return a&amp;lt;b?a:b;}
int maxProfit(int k, int* prices, int pricesSize) {
    int i,j,t;
    int n=pricesSize;
    if(!k) return 0;
    k*=2;
    for(i=0;i&amp;lt;=n;i++)
        dp[i]=0;
    dp[1]=-prices[0];
    for(i=2;i&amp;lt;=n;i++)
    {
        for(j=min(i,k);j&amp;gt;=1;j--)
        {
            int ans=0;
            int tmp=prices[i-1];
            if(j&amp;amp;1) tmp=-tmp;
            if(i-1&amp;gt;=j) tmp=max(dp[j-1]+tmp,dp[j]);
            else tmp=dp[j-1]+tmp;
            dp[j]=tmp;
        }

    }
    int ans=0;
    for(i=0;i&amp;lt;=min(k,n);i++) if(dp[i]&amp;gt;ans) ans=dp[i];
    return ans;
}

Bitwise AND of Numbers Range
这题比较水,也做出来了。但是感觉挺有意思。
给你一个区间[m,n],问这个区间的整数全部按位与的结果是多少,0<=m<=n<=(1<<31)-1
将区间每次除以2,判断区间中是否有偶数,有的话末位肯定是0
非常精简。自我感觉良好。。

class Solution {
public:
    int dfs(int m,int n)
    {
        if(!n) return 0;
        int ret=dfs(m&amp;gt;&amp;gt;1,n&amp;gt;&amp;gt;1);
        if((n==m) &amp;amp;&amp;amp; (n&amp;amp;1)) return (ret&amp;lt;&amp;lt;1|1);
        return (ret&amp;lt;&amp;lt;1);
    }
    int rangeBitwiseAnd(int m, int n) {
        return dfs(m,n);
    }
};

Convert Sorted List to Binary Search Tree
这题一开始只想到空间O(n),时间O(n)的。
后来发现存在空间O(1),时间O(n)的算法。关键在于递归的写法。
类似中序遍历。先建左子树,再建根结点,最后建右子树。这样可以保证遍历次序是从小到大的。那么每次建立一个结点之后链表指针右移一位就指向了当前将要建立的子树的最左结点

class Solution {
public:
    TreeNode*dfs(ListNode**p,int l,int r)
    {
        if(l&gt;r) return NULL;
        int m=l+(r-l)/2;
        TreeNode*left=dfs(p,l,m-1);
        TreeNode*q=new TreeNode((*p)-&gt;val);
        *p=(*p)-&gt;next;
        TreeNode*right=dfs(p,m+1,r);
        q-&gt;left=left;q-&gt;right=right;
        return q;
    }
    TreeNode* sortedListToBST(ListNode* head) {
        ListNode*p=head;
        int cnt=0;
        while(p)
        {
            cnt++,
            p=p-&gt;next;
        }
        if(!cnt) return NULL;
        return dfs(&amp;head,0,cnt-1);
    }
};

________________________________________
2016.01.24
319. Bulb Switcher
这题其实很有意思。。
问题:给出n盏灯,编号1~n,做n轮操作,第i轮将id能被i整除的灯转换状态(开关)。问最后几盏灯亮着。初始n盏灯都是灭的。
我的思路是这样的:因为一盏灯如果转奇数次那么最后是亮的。而如果一盏灯的id如果有奇数个约数,那么它将转换奇数次,这比较显然。
我开始想到这里,就直接用筛法写了,但是我发现存在一个case n时9999999,也就是说算法只能是O(n)及以下的。
然后这时候再仔细想一下,可以发现一点:一个数的约数是成对出现的(为什么觉得自己好傻逼==)!!!比如12=1*12=2*6=3*4
那么显然如果一个数是完全平方数时,比如9=3*3=1*9,这种情况下约数个数才会是奇数个。所以答案其实就是求n以内的完全平方数个数。
直接return (int)sqrt(n*1.0);即可。
________________________________________
2016.02,25
11. Container With Most Water
题意:这题不难,但是一开始真没想到(==!),从n条与x轴垂直的线中取出两条,连同x轴形成一个杯子,问最大容积。
可以这样做:两个游标,i=0,j=n-1.这是一开始选择的两条线。每次移动的时候都移动短的那个。因为移动长的那个并不会使容积变大,也是因为这点,所以移动短的那个并不会漏掉最优解。
________________________________________
2016.02.26
289. Game of Life
题意:给一个0,1矩阵,如果a[i][j]=1并且和它相邻的八个元素中有两个或三个为1,那么不变,否则a[i][j]=0.如果a[i][j]=0,并且相邻8个元素中恰好有3个元素为1,那么a[i][j]=1,否则不变。注意:对所有元素的变换是同时的,不是先改变一个元素,再在该元素改变后的值得基础上变换相邻元素。
要求原地变换。
不难,但是要想一想。。因为是原地变换,所以我们要想办法记录下一个元素是否应该改变,还要保留原先是几这个信息,因为改变其他元素时会用到。那么我们只要把它加2就行了:0–>2,1–>3 如果a[i][j]>1,就说明它需要改变,而且a[i][j]%2就是原先的值。

int n,m;
bool judge(int x,int y)
{
    if(0&lt;=x &amp;&amp; x&lt;n &amp;&amp; 0&lt;=y &amp;&amp; y&lt;m) return 1;
    return 0;
}
void gameOfLife(int** board, int boardRowSize, int boardColSize) {
    int i,j;
    n=boardRowSize,m=boardColSize;
    for(i=0;i&lt;n;i++)
        for(j=0;j&lt;m;j++)
        {
            int live=0;
            if(judge(i-1,j-1)) live+=board[i-1][j-1]%2;
            if(judge(i-1,j)) live+=board[i-1][j]%2;
            if(judge(i-1,j+1)) live+=board[i-1][j+1]%2;
            if(judge(i,j-1)) live+=board[i][j-1]%2;
            if(judge(i,j+1)) live+=board[i][j+1]%2;
            if(judge(i+1,j-1)) live+=board[i+1][j-1]%2;
            if(judge(i+1,j)) live+=board[i+1][j]%2;
            if(judge(i+1,j+1)) live+=board[i+1][j+1]%2;
            if(board[i][j])
            {
                if((live&lt;2) || (live&gt;3)) board[i][j]+=2;
            }
            else if(live==3) board[i][j]+=2;
        }
    for(i=0;i&lt;n;i++)
        for(j=0;j&lt;m;j++)
            if(board[i][j]&gt;1) board[i][j]=(board[i][j]-1)%2;
    return;
}

343. Integer Break
题意:把一个数分成几个正整数之和,使得这几个正整数之积最大
http://blog.csdn.net/liyuanbhu/article/details/51198124
上面链接讲明了做法,并且进行了证明。
心累,表示没想到最优解,用了O(n^2)的算法

/*
class Solution {
public:
    int dp[1000000];
    int integerBreak(int n) {
        int i,j;
        dp[1]=1;
        for(i=2;i&lt;=n;i++)
        {
            dp[i]=(i/2)*(i-i/2);
            for(j=1;j&lt;=(i/2);j++)
            {
                if(j*dp[i-j]&gt;dp[i]) dp[i]=j*dp[i-j];
                if(dp[j]*dp[i-j]&gt;dp[i]) dp[i]=dp[j]*dp[i-j];
            }
            //printf(&quot;%d:%d\n&quot;,i,dp[i]);
        }
        return dp[n];
    }
};
*/
class Solution {
public:
    int integerBreak(int n) {
        if(n==2) return 1;
        if(n==3) return 2;
        int ans=1;
        while(n&gt;4)
        {
            ans*=3;
            n-=3;
        }
        return ans*n;
    }
};

146. LRU Cache
实现一个lru cache
可以用一个map和一个循环双链表实现。
map中的value是一个指向上述链表的指针。

typedef struct List{
    struct List*pre,*next;
    int key,val;
}List;
class LRUCache{
private:
    List *head;
    int cnt,cap;
    map&lt;int,List*&gt; cache;
public:
    LRUCache(int capacity) {
        cnt=0;
        cap=capacity;
        head=NULL;
        if(!cache.empty()) cache.clear();
    }
    List* new_node(int key,int value)
    {
        List*ret=(List*)malloc(sizeof(List));
        ret-&gt;key=key;ret-&gt;val=value;
        ret-&gt;pre=ret;
        ret-&gt;next=ret;
        return ret;
    }
    void del(List*p)
    {
        p-&gt;pre-&gt;next=p-&gt;next;
        p-&gt;next-&gt;pre=p-&gt;pre;
        if(p==head) head=p-&gt;next;
        cnt--;
        free(p);
        if(!cnt) head=NULL;
        return;
    }
    List* add(List*p,int key,int value)
    {
        List*q=new_node(key,value);
        if(!p) {head=q;cnt++;return q;}
        q-&gt;pre=p;
        q-&gt;next=p-&gt;next;
        p-&gt;next-&gt;pre=q;
        p-&gt;next=q;
        cnt++;
        if(q-&gt;next==head) head=q;
        return q;
    }
    int get(int key) {
        if(cache.find(key)!=cache.end())
        {
            List*p=cache[key];
            int ans=p-&gt;val;
            del(p);
            cache[key]=add(head?head-&gt;pre:head,key,ans);
            return ans;
        }
        return -1;
    }

    void set(int key, int value) {
        if(cache.find(key)!=cache.end())
        {
            List*p=cache[key];
            del(p);
            cache[key]=add(head?head-&gt;pre:head,key,value);
            return;
        }
        cache[key]=add(head?head-&gt;pre:head,key,value);
        if(cnt&gt;cap)
        {
            cache.erase(head-&gt;pre-&gt;key);
            del(head-&gt;pre);
        }
        return;
    }
};

457. Circular Array Loop
题意:一个数组nums[],nums[i]表示下一步跳到j=(i+num[i]+n)%n;j是数组下标,n是数组元素总数。请问该数组是否存在一条链。注:跳跃时必须沿着同一方向
要求:O(n)时间,O(1)空间
我的解法:首先把数组元素的值规整到(-n,n)之间,然后当从某个元素开始跳跃的时候,每跳过一个元素就将该元素值乘上n,如果到达的元素,其值是0,那么说明当前路径失败,如果其值不在(-n,n)范围内,说明遇到了当前路径之前访问的元素,存在环。如果遇到其值符号与出发元素的符号不同,则当前路径失败,将当前路径所有值(不包括最后符号不同的元素)置为0。由于需要回溯,用dfs写比较合适。
注意点:主要是一条路径最后那个符号不同的元素不要置为0,因为它可能是某个未遍历的环中的元素

int abs(int a) {return a&lt;0?-a:a;}
int f(int a){return a/abs(a);}
bool dfs(int *nums,int cur,bool flag,int n)
{
    int j=(cur+nums[cur]/n+n)%n;
    if(!nums[j]) return 0;
    if(f(nums[j])!=flag) return 0;
    if(nums[j]&lt;=-n || nums[j]&gt;=n) return 1;
    nums[j]*=n;
    int ret=dfs(nums,j,flag,n);
    if(!ret) nums[j]=0;
    return ret;
}
bool circularArrayLoop(int* nums, int numsSize) {
    int i,j;
    int n=numsSize;
    for(i=0;i&lt;n;i++)
    {
        nums[i]=f(nums[i])*(abs(nums[i])%n);
    }
    for(i=0;i&lt;n;i++)
    {
        if(!nums[i]) continue;
        int flag=f(nums[i]);
        nums[i]*=n;
        if(dfs(nums,i,flag,n)) return 1;
        nums[i]=0;
    }
    return 0;

}

406. Queue Reconstruction by Height
题意:有一个数组,给出每个元素的值(h)以及在它前面大于等于它的元素的数量(k),求原数组
思路:首先按元素值从小到大排,元素值相等的,按k从大到小排。然后从前往后遍历排序后的数组,对于每个数,从前往后遍历ans数组(初始化为元素都为空),计数空格数量,当空格数量等于k时,从当前位置往后寻找空位插入元素
关键点:考虑元素h的位置时,如果比它小的元素都已经在正确的位置了,那么它所在的位置的前面应该有k个空格(因为x之前有k个数大于等于它,而剩下的数都比它大,所以要正好留k个空格)。第二点是两个数相等的话必须按k从大到小排,这样放h1时不会影响h2

bool cmp(pair&lt;int,int&gt; a,pair&lt;int,int&gt; b){
    if(a.first!=b.first) return a.first&lt;b.first;
    return a.second&gt;b.second;
}
class Solution {
public:
    vector&lt;pair&lt;int, int&gt;&gt; reconstructQueue(vector&lt;pair&lt;int, int&gt;&gt;&amp; people) {
        vector&lt;pair&lt;int,int&gt;&gt; ans;
        if(!ans.empty()) ans.clear();
        int i,j;
        int n=people.size();
        pair&lt;int,int&gt; tmp;tmp.first=-1,tmp.second=-1;
        for(i=0;i&lt;n;i++) ans.push_back(tmp);
        sort(people.begin(),people.end(),cmp);
        for(i=0;i&lt;n;i++)
        {
            int pos=people[i].second;
            int cnt=0;
            for(j=0;j&lt;n;j++)
            {
                if(cnt==pos)
                {
                    int k=j;
                    while(ans[k].first!=-1) k++;
                    ans[k].first=people[i].first;ans[k].second=people[i].second;
                    break;
                }
                if(ans[j].first==-1) cnt++;
            }

        }
        return ans;
    }
};

378. Kth Smallest Element in a Sorted Matrix
题意:在一个横轴纵轴元素值分别都递增的矩阵中找到第k小的元素。
Example:

matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,

return 13.

Note:
You may assume k is always valid, 1 ≤ k ≤ n2

思路:这题挺有意思。首先要知道给出一个值v,通过matrix[0][n-1]一路往下往左,可以O(n)的得到v在这个矩阵所有数中的排名,清楚了这一点,那么接下来只要二分这个v就可以了。总复杂度O(nlgn)
当然如果你没有发现这种矩阵的这个性质,那么可以对每一行/列,二分v的排名,得到v在整个矩阵中的总排名。也是一样的道理。总复杂度O(n*(lgn)^2)

typedef long long ll;
int _rank(vector&lt;vector&lt;int&gt; &gt; &amp; mat,int v,int *pflag)
{
    int n=mat.size();
    int i=0,j=n-1,ret=0;
    while((i&lt;=n-1) &amp;&amp; (j&gt;=0))
    {
        if(mat[i][j]&gt;v) j--;
        else if(mat[i][j]==v) {*pflag=1;j--;}
        else {ret+=(j+1);i++;}

    }
    return ret+1;
}
int bsearch(vector&lt;vector&lt;int&gt; &gt; &amp; mat,ll l,ll r,int k)
{
    ll m;
    while(l&lt;=r)
    {
        //printf(&quot;l:%lld r:%lld\n&quot;,l,r);
        m=(l+r)/2;
        int flag=0;
        int t=_rank(mat,(int)m,&amp;flag);
        //printf(&quot;t:%d m:%d\n&quot;,t,m);
        if(flag &amp;&amp; (t==k)) return m;
        if(t&gt;k) r=(ll)m-1;
        if(t&lt;=k) l=(ll)m+1;
    }
    return (int)r;

}
class Solution {
public:
    int kthSmallest(vector&lt;vector&lt;int&gt;&gt;&amp; matrix, int k) {
        return bsearch(matrix,INT_MIN,INT_MAX,k);
    }
};

452. Minimum Number of Arrows to Burst Balloons
题意:给出一些区间,问最少需要几条竖直线可以将这些区间全部分割
解法:贪心来做。假如一些区间都重合一部分,那么显然在这个公共部分放竖线是最好的(假如不在公共部分放,那么将那条线移到公共部分不会使情况变差)。首先按左端点排序,我们遍历排序后的数组,记录当前重合区间的最小右端点right。如果出现新区间的左端点大于当前最小右端点,那么说明这个新区间需要另一条竖线来分割,同时更新right为这个新区间的右端点值。

bool cmp(pair&lt;int,int&gt; a,pair&lt;int,int&gt; b)
{
    return a.first==b.first?a.second&lt;b.second:a.first&lt;b.first;
}
class Solution {
public:
    int findMinArrowShots(vector&lt;pair&lt;int, int&gt;&gt;&amp; points) {
        if(points.size()==0) return 0;
        sort(points.begin(),points.end(),cmp);
        int n=points.size(),ans=1;
        int right=points[0].second;
        for(int i=0;i&lt;n;i++)
        {
            if(points[i].first&gt;right) {right=points[i].second;ans+=1;}
            else if(points[i].second&lt;right) right=points[i].second;
        }

        return ans;
    }
};

377. Combination Sum IV
题意:数组nums由正整数组成,给出target,求数组元素加起来等于target的方案数。
Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.
j
思路:dp[j]表示把数组元素放入容量为j的背包的方案数。dp[j]=sigma(dp[j-nums[i]]);注意:当j==nums[i]的时候,说明数组中存在j,这时方案数为1,所以dp[0]=1;
写的时候其实就是把传统无限背包的两重循环调换一下内外顺序。

int dp[1000];
class Solution {
public:
    int combinationSum4(vector&lt;int&gt;&amp; nums, int target) {
        int i,j;
        int n=nums.size();
        if(!n) return 0;
        memset(dp,0,sizeof(int)*(target+10));
        dp[0]=1;
        for(j=0;j&lt;=target;j++)
            for(i=0;i&lt;n;i++)
            {
                if(j&lt;nums[i]) continue;
                dp[j]+=dp[j-nums[i]];
            }
        return dp[target];
    }
};

454. 4Sum II
题意:四个数组,每个数组取一个数,问加起来等于0的元组数是多少
思路:A,B数组两两求和得到X数组。C,D数组两两求和得到Y数组。枚举X数组,二分Y数组,注意因为Y中可能出现重复数,所以是每次加上upper_bound-lower_bound

int a[250000+10];
class Solution {
public:
    int fourSumCount(vector&lt;int&gt;&amp; A, vector&lt;int&gt;&amp; B, vector&lt;int&gt;&amp; C, vector&lt;int&gt;&amp; D) {
        int i,j;
        int cnt=0,ans=0;
        for(i=0;i&lt;C.size();i++)
            for(j=0;j&lt;D.size();j++) a[cnt++]=C[i]+D[j];
        sort(a,a+cnt);
        for(i=0;i&lt;A.size();i++)
            for(j=0;j&lt;B.size();j++) ans+=upper_bound(a,a+cnt,-(A[i]+B[j]))-lower_bound(a,a+cnt,-(A[i]+B[j]));
        return ans;
    }
};

421. Maximum XOR of Two Numbers in an Array
题意:给出数组nums[],0<=nums[i] 思路:非常经典的题,字典树

int ch[1000000][2],sz;
int get_bit(int x,int num){return ((x&gt;&gt;num)&amp;1);}
int findMaximumXOR(int* nums, int numsSize) {
    int i,j;
    int n=numsSize;
    sz=1;
    memset(ch,0,sizeof(ch));
    for(i=0;i&lt;n;i++)
    {
        int cur=0;
        for(j=30;j&gt;=0;j--)
        {
            int bit=get_bit(nums[i],j);
            if(!ch[cur][bit]) {ch[cur][bit]=sz++;cur=sz-1;}
            else cur=ch[cur][bit];
        }
    }
    int ans=0;
    for(i=0;i&lt;n;i++)
    {
        int cur=0;
        int tmp=~nums[i];
        int ret=0;
        for(j=30;j&gt;=0;j--)
        {
            int bit=get_bit(tmp,j);
            if(!ch[cur][bit]) {cur=ch[cur][!bit];ret&lt;&lt;=1;}
            else {cur=ch[cur][bit];ret=(ret&lt;&lt;1|1);}

        }
        if(ret&gt;ans) ans=ret;
    }
    return ans;
}

29. Divide Two Integers
题意:int型整数相除,要求不能使用乘除和mod运算
思路:每次减去最大的2的次方。注意:最小的int是(1<<31),最大的int是((1<<31)-1)。所以-(1<<31)除以(-1)会溢出

typedef long long ll;
#define MAX_INT ((1&lt;&lt;31)-1)
ll _abs(ll x){return x&lt;0?-x:x;}
int divide(int dividend, int divisor) {
    int i,j;
    if(!divisor) return MAX_INT;
    int f1=0,f2=0;
    if(dividend&lt;0) f1=-1;
    if(divisor&lt;0) f2=-1;
    ll a=(ll)dividend,b=(ll)divisor;
    a=_abs(a),b=_abs(b);
    if(a&lt;b) return 0;
    int shift=0;
    while(b&lt;=(a&gt;&gt;1))
    {
        b&lt;&lt;=1;shift++;
    }
    ll ret=0;
    while(shift&gt;=0)
    {
        if(a&gt;=b)
        {
            a-=b;
            ret+=(1LL&lt;&lt;shift);
        }
        b&gt;&gt;=1;
        shift--;
    }

    int flag=(((!f1 &amp;&amp; !f2)||(f1 &amp;&amp; f2))?0:-1);
    if(!flag &amp;&amp; ret&gt;(ll)MAX_INT) return MAX_INT;
    //printf(&quot;ret %lld\n&quot;,ret);
    return (int)(!flag?ret:0-ret);
}

435. Non-overlapping Intervals
题意:有一些整数区间,求最少去掉几个区间可以使所有区间都不overlapping,类似[2,4],[4,6]这样的区间不算overlapping
思路:这题是Minimum Number of Arrows to Burst Balloons的翻版,做法也相同。

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
bool cmp(Interval a,Interval b)
{
    if(a.start==b.start) return a.end&lt;b.end;
    return a.start&lt;b.start;
}
class Solution {
public:
    int eraseOverlapIntervals(vector&lt;Interval&gt;&amp; intervals) {
        int i,j,n=intervals.size();
        if(!n) return 0;
        sort(intervals.begin(),intervals.end(),cmp);
        int ans=1;
        int right=intervals[0].end;
        for(int i=0;i&lt;n;i++)
        {
            if(intervals[i].start&gt;=right) {right=intervals[i].end;ans+=1;}
            else if(intervals[i].end&lt;right) right=intervals[i].end;
        }
        return n-ans;

    }
};

330. Patching Array
题意:给出数组nums[],整数n, 问nums[]中最少增加几个数可以使数组中的数自由组合(相加)得到[1,n]范围的数。每个数只能用一次。
思路:先排序。假设现在可以表示[1,x),那么
(1)如果接下来读入的数组元素>x,那么显然必须加入数x(因为x不能由其他数得到)。这时可表示区间变成[1,x<<1)
(2)如果接下来读入的数组元素为k,k<=x,那么可表示区间变成[1,x+k)

typedef long long ll;
class Solution {
public:
    int minPatches(vector&lt;int&gt;&amp; nums, int n) {
        int i=0;
        sort(nums.begin(),nums.end());
        ll max_num=1;
        int ans=0;
        while(max_num&lt;=(ll)n)
        {
            if(i&gt;=nums.size()) {ans++;max_num*=2;continue;}
            if((ll)nums[i]&lt;=max_num) max_num+=(ll)nums[i],i++;
            else {ans++;max_num&lt;&lt;=1;}
        }
        return ans;
    }
};

442. Find All Duplicates in an Array
题意:有个数组a[],共n个数。1<=a[i] 思路:遍历数组,遍历到a[i]的时候,如果a[i]!=i+1且不为0,则记k=a[i]-1,若a[k]==k+1,则把a[i]放入答案并将a[i]清零,否则交换a[i],a[k]

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
void swap(int *a,int *b)
{
    int t;
    t=*a;*a=*b;*b=t;
    return;
}
int* findDuplicates(int* nums, int numsSize, int* returnSize) {
    int i,j;
    int n=numsSize;
    int *ans=(int*)malloc(sizeof(int)*(numsSize+5));
    int cnt=0;
    for(i=0;i&lt;n;i++)
    {
        if(!nums[i]) continue;
        while(nums[i]!=i+1) {
            if(!nums[i]) break;
            if(nums[nums[i]-1]==nums[i]) {ans[cnt++]=nums[i];nums[i]=0;break;}
            else swap(&amp;nums[i],&amp;nums[nums[i]-1]);
        }
    }
    *returnSize=cnt;
    return ans;
}

445. Add Two Numbers II
题意:给出两个链表,每个节点的val是一个数字,表示一个数的一个十进制位。最高位在链表头。对这两个数求和,并以同样的链表形式返回
思路:先翻转两个链表,然后按位相加,注意去除前缀0.
follow up:不能修改数组。
可以使用两个辅助栈

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rev(ListNode* l)
    {
        ListNode* p=l,*head=l,*q=l;
        p=p-&gt;next;
        while(p)
        {
            q-&gt;next=p-&gt;next;
            p-&gt;next=l;l=p;
            p=q-&gt;next;
        }
        head-&gt;next=NULL;
        return l;
    }
    ListNode* new_node()
    {
        ListNode* p=(ListNode*)malloc(sizeof(ListNode));
        p-&gt;next=NULL;
        return p;
    }
    void debug(ListNode* p)
    {
        ListNode* tmp=p;
        while(tmp)
        {
            printf(&quot;%d &quot;,tmp-&gt;val);
            tmp=tmp-&gt;next;
        }
        printf(&quot;\n&quot;);
        return;

    }
    ListNode *remove_z(ListNode* l)
    {
        while(l &amp;&amp; !(l-&gt;val)) l=l-&gt;next;
        return l;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1=rev(l1);l2=rev(l2);
        //debug(l1);debug(l2);
        ListNode* ans=NULL,*p=NULL;
        int c=0;
        while(l1 &amp;&amp; l2)
        {
            int tmp=(l1-&gt;val+l2-&gt;val+c)%10;
            c=(l1-&gt;val+l2-&gt;val+c)/10;
            ListNode *_new=new_node();
            _new-&gt;val=tmp;
            if(!ans) ans=_new,p=_new;
            else {p-&gt;next=_new;p=p-&gt;next;}
            l1=l1-&gt;next;l2=l2-&gt;next;
        }
        while(l1)
        {
            int tmp=(l1-&gt;val+c)%10;
            c=(l1-&gt;val+c)/10;
            ListNode *_new=new_node();
            _new-&gt;val=tmp;
            if(!ans) ans=_new,p=_new;
            else {p-&gt;next=_new;p=p-&gt;next;}
            l1=l1-&gt;next;
        }
        while(l2)
        {
            int tmp=(l2-&gt;val+c)%10;
            c=(l2-&gt;val+c)/10;
            ListNode *_new=new_node();
            _new-&gt;val=tmp;
            if(!ans) ans=_new,p=_new;
            else {p-&gt;next=_new;p=p-&gt;next;}
            l2=l2-&gt;next;
        }
        if(c)
        {
            ListNode *_new=new_node();
            _new-&gt;val=c;
            p-&gt;next=_new;p=p-&gt;next;
        }
        if(ans!=p) {ans=rev(ans);ans=remove_z(ans);}
        return ans;
    }
};

382.Linked List Random Node
当长度很长时,无法预先得到链表的长度。这时可以采用蓄水池抽样法。令ret=链表头(第一个数),cur指向head的下一个数,变量i初始化为1,从[0,,i]中随机选一个数,当选的是0的时候,更新ret=cur。接下来i更新为i+1,继续上述步骤。这样可以保证每个数被取到的概率相同。
证明:
第一个数被取到的概率=1/1*1/2*2/3*……*n-1/n=1/n
第二个数被取到的概率=1*1*1/3*2/4*……*n-1/n=1/n
第k个数被取到的概率=1*1*1*……*1/k*k/k+1*……*n-1/n=1/n
以此类推……
假设被取中的数是k,那么k之前的数有没有被更新到ret不重要,所以前k-1项是1。k之后的项则要保证没更新到ret

follow up:如果是取k个数,那么算法变成:
设置大小为k的ret[]数组,先把前k个数放入,然后第k+1个数以k/k+1的概率选中……第m个数以k/m的概率选中

398. Random Pick Index
这题是蓄水池抽样的一个特例,水池容量为1

#include&lt;stdio.h&gt;
#include&lt;stdlib.h&gt;
#include&lt;time.h&gt;
using namespace std;
class Solution {
private:
    vector&lt;int&gt; num;
public:
    Solution(vector&lt;int&gt; nums) {
        srand((unsigned int)time(0));
        for(int i=0;i&lt;nums.size();i++)
            num.push_back(nums[i]);
    }

    int pick(int target) {
        int cnt=0,ret;
        for(int i=0;i&lt;num.size();i++)
        {
            if(num[i]!=target) continue;
            if(!cnt) {ret=i;cnt++;continue;}
            cnt++;
            ret=rand()%cnt==0?i:ret;
        }
        return ret;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

386. Lexicographical Numbers
题意:给出n,将[1,n]的所有数按字典序从小到大排。例如n=13,则答案为1,10,11,12,13,2,3,4,5,6,7,8,9
思路:这题很有意思。想了很久。。在纸上多写几个例子可以发现这样的规律:假如当前数是cur,那么下一个数应当先试试cur*10,如果*10在范围内,那么下一个数就是cur*10,否则尝试cur+1,然后去除末尾的0得到新的cur。如果此时cur大于n,那么将cur/10-1,作为下一个数。

class Solution {
    vector&lt;int&gt; ans;
public:
    vector&lt;int&gt; lexicalOrder(int n) {
        int i,j;
        int cnt=1;
        ans.push_back(1);
        while(cnt&lt;n)
        {
            int pre=ans[cnt-1];
            if(pre*10&lt;=n) {ans.push_back(pre*10);cnt++;continue;}
            pre+=1;
            while(!(pre%10)) pre/=10;
            if(pre&gt;n) pre=pre/10+1;
            ans.push_back(pre);cnt++;
        }
        return ans;
    }
};

59. Spiral Matrix II
题意:螺旋形将数填入矩阵
常规题,注意矩阵是1*1的情况。这时得到的下一步要走的格子可能不合法,要注意判断,否则会RE
390. Elimination Game
题意:1到n从小到大排列,循环执行以下操作直到只剩一个数:
(1)从左侧开始删除第一个数,然后每隔一个数删除一个数。
(2)从右侧开始删除第一个数,然后每隔一个数删除一个数。
思路:这题还是比较好推理的。设Xn表示n个数最后留下第几个数。先给出递推表达式:Xn=(n/2-Xn/2+1)*2。
Xn/2表示n/2个数排列最后留下第几个数,那么当总数是n时,第二轮是从右侧开始的,所以Xn/2其实是从右侧开始第几个数,n/2-Xn/2+1才是从左侧数第几个数,由于第一轮删掉了一半左右的数,所以要乘2.

int lastRemaining(int n) {
    if(n==1) return 1;
    n/=2;
    return (n-lastRemaining(n)+1)*2;
}

300. Longest Increasing Subsequence
题意:最长子序列,要求时间O(nlgn)
思路:设置数组len[],len[i]表示长度为i的上升子序列末位一个数最小值是什么。由于len是单调递增的所以可以二分更新
注意一点:二分的时候求的是lower_bound
354. Russian Doll Envelopes
题意:给出一些矩形,每个矩形表示为(w,h),两个矩形如果wi 思路:这个是最长递增子序列的变种。分别对其中一个维度排序,然后对另一个维度求LIS即可。
注意一点:对一个维度排序时,如果两个数相等,则按另一个维度从大到小排,这样可以保证对另一个维度做LIS时这两个数中小的那个数会更新掉大的那个数,而不是出现在同一递增序列中。

const int inf=(0x3f3f3f3f)*2;
bool cmp1(pair&lt;int,int&gt; a,pair&lt;int,int&gt; b)
{
    if(a.first==b.first) return a.second&gt;b.second;
    return a.first&lt;b.first;
}
bool cmp2(pair&lt;int,int&gt; a,pair&lt;int,int&gt; b)
{
    if(a.second==b.second) return a.first&gt;b.first;
    return a.second&lt;b.second;
}
class Solution {
public:
    int bs(int* nums,int l,int r,int v)
    {
        while(l&lt;=r)
        {
            int m=(l+r)/2;
            if(v&gt;nums[m]) l=m+1;
            else r=m-1;
        }
        return l;
    }
    int cal(pair&lt;int,int&gt; a,int flag){return flag?a.second:a.first;}
    int lis(vector&lt;pair&lt;int,int&gt; &gt;&amp; a,int flag)
    {
        int i,j,n=a.size();
        int *len=(int*)malloc(sizeof(int)*n);
        for(i=0;i&lt;n;i++) len[i]=inf;
        int ans=0;
        len[0]=cal(a[0],flag);
        for(i=1;i&lt;n;i++)
        {
            int pos=bs(len,0,n,cal(a[i],flag));
            //printf(&quot;pos[%d]:%d\n&quot;,i,pos);
            len[pos]=cal(a[i],flag);
            if(pos&gt;ans) ans=pos;
        }
        return ans+1;
    }

    int max(int a,int b){return a&gt;b?a:b;}
    int maxEnvelopes(vector&lt;pair&lt;int, int&gt;&gt;&amp; envelopes) {
        if(!envelopes.size()) return 0;
        sort(envelopes.begin(),envelopes.end(),cmp1);
        int ans=lis(envelopes,1);
        //printf(&quot;%d\n&quot;,ans);
        sort(envelopes.begin(),envelopes.end(),cmp2);
        //printf(&quot;%d\n&quot;,ans);
        ans=max(ans,lis(envelopes,0));

        return ans;
    }
};

424. Longest Repeating Character Replacement
题意:给出字符串s,s由大写字母组成。可以把s中的任意字符改成其他字符,最多改k个。问改动之后最长的单字符子串有多长。
思路:这题挺有意思。可以这样做。假设这个最长单字符串的字符是26个大写字母中的某一个。维护一个窗口[start,end)。初始化为[0,0)。优先移动end,同时更新当前改动次数(改动时要打上标记,可以改成对应的小写字母,start右移的时候要改回来)和答案。
注意点:在每次大循环(改变假定的最长单字符串字母时,记得先把s所有字符改回大写字母)

class Solution {
public:
    int characterReplacement(string s, int k) {
        int n = s.length();
        int i,j;
        int ans=0;
        char c;
        for(i=0;i&lt;26;i++) {
            c='A'+i;
            int cnt=0;
            int start=0,end=0;
            for(j=0;j&lt;n;j++) if(s[j]&gt;='a') s[j]=s[j]-'a'+'A';
            while(end&lt;n) {
                if(s[end]==c) end++;
                else
                {
                    if(cnt&lt;k)
                    {
                        cnt++;
                        s[end]=s[end]-'A'+'a';end++;
                    }
                    else
                    {
                        if(start==end) {start++;end++;continue;}
                        if(s[start]&gt;='a') {cnt--;s[start]=s[start]-'a'+'A';}
                        start++;
                    }
                }
                //if(c=='B') printf(&quot;cnt:%d start:%d  end:%d\n&quot;,cnt,start,end);
                if(end-start&gt;ans) ans=end-start;
            }
        }
        return ans;
    }
};

69. Sqrt(x)
题意:不用build-in函数实现sqrt().
思路:(1)二分(和判断一个数是否是完全平方数那题一样)(2)牛顿二乘法(待考察)

typedef unsigned long long ull;
class Solution {
public:
    int mySqrt(int x) {
        if(x==0) return 0;
        if(x==1 || x==2 || x==3) return 1;
        if(x&lt;9) return 2;
        ull l=1,r=(ull)x/2;
        while(l&lt;=r)
        {
            ull m=(l+r)/2;
            if(m*m==(ull)x) return m;
            if(m*m&lt;(ull)x) l=m+1;
            else r=m-1;
        }
        if(l*l&gt;(ull)x) l-=1;
        return l;
    }
};

50. Pow(x, n)
思路:这题典型快速幂。但是要注意以下几点:
(1)指数是0的时候,直接返回1
(2)指数是负数的情况!
(3)第(2)点的一个特殊情况,当指数是-2^31时直接变成正数会溢出!所以要用long long。一定要时刻记住int数的正数和负数表示范围不一样,负数大了1

typedef long long ll;
class Solution {
public:
    double myPow(double x, int n) {
        double ans=1,p=x;
        if(!n) return 1.0;
        ll m=(ll)n;
        bool f=0;
        if(m&lt;0) {f=1;m=-m;}
        while(m)
        {
            if(m&amp;1) {ans*=p;m-=1;}
            p*=p;m/=2;
        }
        if(f) ans=1/ans;
        return ans;
    }
};

372. Super Pow
题意:快速幂mod n
注意高精度除法,以前没写过。每次除从high位开始,否则会TLE。。

const int mod=1337;
class Solution {
    int high=0;
public:
    bool odd(vector&lt;int&gt;&amp; num)
    {
        int n=num.size();
        return num[n-1]&amp;1;
    }
    bool zero(vector&lt;int&gt;&amp; num)
    {
        for(int i=high;i&lt;num.size();i++)
            if(num[i]) {high=i;return 0;}
        return 1;
    }
    void sub1(vector&lt;int&gt;&amp; num)
    {
        num[num.size()-1]-=1;
        return;
    }
    void div2(vector&lt;int&gt;&amp; num)
    {
        int i;
        int c=0,n=num.size();
        for(i=high;i&lt;n;i++)
        {
            int tmp=num[i];
            num[i]=(c*10+tmp)&gt;&gt;1;
            c=(c*10+tmp)%2;
        }
        return;
    }
    int superPow(int a, vector&lt;int&gt;&amp; b) {
        int ans=1,p=a%mod;
        while(!zero(b))
        {
            if(odd(b)) {sub1(b);ans=(ans*p)%mod;}
            p=(p*p)%mod;
            div2(b);
        }
        return ans;
    }
};

416. Partition Equal Subset Sum
题意:给出一些positive interger,问能否将这些数分成非空的两个子集,且这两个子集的和相等。
思路:典型的背包0-1背包,dp[j]表示前i个数能否正好放满容量为j的背包。初始化dp[0]=1;表示前0个数可以正好放满容量为0的背包。其他值初始化为0
这题也可以用母函数来做:假设数组为1,2,5.把值作为指数,最终表达式的系数就是方案数。那么计算表达式(1*x^0+1*x^1)*(1*x^0+1*x^2)*(1*x^0+1*x^5)的各项系数,答案即是x^4的系数
其中第一个表达式(1*x^0+1*x^1)表示第一个数可以取也可以不取。
当用母函数解题时如果表达式很长很多,可以考虑用快速傅里叶变换把两个表达式相乘的复杂度从O(n^2)变成O(n)
背包解

class Solution {
    bool dp[10000+10];
public:
    bool canPartition(vector&lt;int&gt;&amp; nums) {
        int i,j;
        int V=0;
        for(i=0;i&lt;nums.size();i++) V+=nums[i];
        if(V&amp;1) return 0;
        V/=2;
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        for(i=1;i&lt;=nums.size();i++)
        {
            for(j=V;j&gt;=0;j--)
            {
                if(j&lt;nums[i-1]) continue;
                dp[j]=dp[j-nums[i-1]]|dp[j];
            }
            //for(j=1;j&lt;=V;j++) printf(&quot;dp[%d]:%d\n&quot;,j,dp[j]);
        }
        return dp[V];

    }
};

母函数:

int c1[20000+10],c2[20000+10];
bool canPartition(int* nums, int numsSize) {
    int i,j,k;
    int n=numsSize;
    int V=0;
    for(i=0;i&lt;n;i++) V+=nums[i];
    if(V&amp;1) return 0;
    V/=2;
    memset(c1,0,sizeof(int)*(2*V+5));
    memset(c2,0,sizeof(int)*(2*V+5));
    c1[0]=1;c1[nums[0]]=1;
    for(i=1;i&lt;n;i++)
    {
        for(j=0;j&lt;=V;j++)
            for(k=0;k&lt;=nums[i] &amp;&amp; k+j&lt;=V;k+=nums[i]) c2[k+j]+=c1[j];
        for(j=0;j&lt;=V;j++) {c1[j]=c2[j];c2[j]=0;}
    }
    return c1[V];
}

375. Guess Number Higher or Lower II
题意:给出范围[1,n],并给出一个数k,让你去猜这个k,每次可以告诉你你说的数比k小还是比k大,直到猜对。每次猜错都要付出对应的金额,例如猜了t,但猜错了,则要付出t元。求参加这个游戏带多少钱才能保证一定能猜到最终的数。
思路:首先要充分理解题意,这题其其实是问在最优的猜数决策之下,找到需要最大花费的数。那么怎样的猜数方法才是最优的呢,其实开始时并不确定,所以遍历所有猜数决策(即每次都枚举猜哪个数),当确定了猜哪个数之后,就去找花费最大的那个数。求出这个最大花费,最后在这些花费中取最小值。
dp[l][r]表示在[l,r]之间猜数至少要带多少钱才能保证猜对。d[i][i+1]=i;

#define inf ((0x3f3f3f3f)*2)
int dp[1010][1010];
int max(int a,int b){return a&gt;b?a:b;}
int min(int a,int b){return a&lt;b?a:b;}
int dfs(int l,int r)
{
    if(l&gt;=r) {dp[l][r]=0;return 0;}
    if(dp[l][r]!=inf) return dp[l][r];
    int i;
    for(i=l+1;i&lt;=r-1;i++) dp[l][r]=min(dp[l][r],i+max(dfs(l,i-1),dfs(i+1,r)));
    dp[l][r]=min(dp[l][r],min(l+dfs(l+1,r),r+dfs(l,r-1)));
    return dp[l][r];
}
int getMoneyAmount(int n) {
    int i,j;
    for(i=1;i&lt;=n;i++)
        for(j=i+1;j&lt;=n;j++) dp[i][j]=inf;
    for(i=1;i&lt;n;i++) dp[i][i+1]=i;
    return dfs(1,n);
}

85. Maximal Rectangle
题意:在一个0-1矩阵中找到最大的全是1的矩形。
思路:这里只说在一个直方图中找到最大矩形(直方图用一个一维数组表示,数组元素表示一个柱子的高度)。解决了这个问题,这道题也就解决了。
其实这个问题我已经是第三次遇到了。。。但还是忘了方法。
从左到右遍历h[]数组,将他们的数组下标压入一个单调递增栈,每当一个元素出栈时计算它向左向右分别可以到达的最远下标,然后以这个出栈元素为高,计算矩形面积

#define maxn 1010
int mat[maxn][maxn];
int st[maxn],top;
int cal(int r,int n)
{
    int i,left,right;
    top=0;
    int ans=0;
    for(i=0;i&lt;=n;i++)
    {
        if(!top) {st[top++]=i;continue;}
        while(top &amp;&amp; (mat[r][st[top-1]]&gt;mat[r][i]))
        {
            int index=st[top-1];
            int lindex=(top==1?0:st[top-2]+1);
            int rindex=i-1;
            int area=mat[r][index]*(rindex-lindex+1);
            if(area&gt;ans) ans=area;
            top--;
        }
        st[top++]=i;
    }
    return ans;
}
int maximalRectangle(char** matrix, int matrixRowSize, int matrixColSize) {
    int i,j;
    int r=matrixRowSize,c=matrixColSize;
    for(i=0;i&lt;r;i++)
    {
        for(j=0;j&lt;c;j++)
        {
            mat[i][j]=matrix[i][j]-'0';
            if(!i) continue;
            if(!mat[i][j]) continue;
            mat[i][j]+=mat[i-1][j];
        }
        mat[i]1=0;
    }
    int ans=0;
    for(i=0;i&lt;r;i++)
    {
        int tmp=cal(i,c);
        if(tmp&gt;ans) ans=tmp;
    }
    return ans;
}

395. Longest Substring with At Least K Repeating Characters
题意:找到最长的子串,使得该子串内每种字符的个数都>=k
思路:递归来做,只要一个字符串内有字符其数量不到k个,那么说明我们要求的子串不能跨越该字符,这样就把原字符串分成了几段,每段字符串都是子问题。

class Solution {
public:
    int dfs(string s,int l,int r,int k)
    {
        if(l&gt;r) return 0;
        int i,j;
        int cnt[256];
        int ans=0;
        for(i='a';i&lt;='z';i++) cnt[i]=0;
        for(i=l;i&lt;=r;i++) cnt[s[i]]++;
        for(i=l;i&lt;=r;i++)
            if(cnt[s[i]]&lt;k) s[i]='A'+s[i]-'a';
        int lsub,rsub;
        i=l;
        while(1)
        {
            while(i&lt;=r &amp;&amp; s[i]&lt;'a') i++;
            if(i&gt;r) break;
            lsub=i;
            while(i&lt;=r &amp;&amp; s[i]&gt;='a') i++;
            rsub=i-1;
            if((lsub==l) &amp;&amp; (rsub==r)) return r-l+1;
            int tmp=dfs(s,lsub,rsub,k);
            if(tmp&gt;ans) ans=tmp;
        }
        return ans;
    }
    int longestSubstring(string s, int k) {
        return dfs(s,0,s.length()-1,k);
    }
};

460. LFU Cache
题意:实现一个LFU,要求有get(key)和set(key,value),当容量到达上限时,删除一个访问频率最小的,如果有多个数访问频率最小,选最近最久未访问的那个。
思路:用一个Node机构表示元素,用一个hash表存储key和指向对应node的指针。用另一个hash表存储所有的访问频率(作为key),每个元素是一个双向循环链表,链表元素就是node。
node的成员一定要有key,因为删除一个node的时候要把表示该node存在的hash表中的对应元素置为NULL。(node[key]=NULL;)
注意点:min_cnt的更新:如果get()使得freq[min_cnt]变为空,则需要min_cnt++。如果set时增加新元素导致容量超过上限,则要删除一个元素,如果删除那个元素导致freq[min_cnt]变为空,则需要min_cnt=1(因为新增加的那个数一定访问频率最小,为1)

struct Node{
    int key,val;
    struct Node*pre,*next;
    struct Node*head;
};
class LFUCache {
private:
    map&lt;int,Node*&gt; node;
    map&lt;int,Node*&gt; freq;
    int cur,cap,min_cnt;
public:
    LFUCache(int capacity) {
        cap=capacity;
        cur=0;
        if(!node.empty()) node.clear();
        if(!freq.empty()) freq.clear();
    }
    Node* _new(int key,int val)
    {
        Node*ret=(Node*)malloc(sizeof(Node));
        ret-&gt;key=key;
        ret-&gt;val=val;
        ret-&gt;next=ret-&gt;pre=ret;
        return ret;
    }
    void list_remove(Node* p)
    {
        p-&gt;pre-&gt;next=p-&gt;next;
        p-&gt;next-&gt;pre=p-&gt;pre;
        return;
    }
    void list_add(Node *pHead,Node *p)
    {
        p-&gt;next=pHead-&gt;next;
        p-&gt;pre=pHead;
        pHead-&gt;next-&gt;pre=p;
        pHead-&gt;next=p;
        return;
    }
    bool empty(Node*head)
    {
        return head-&gt;next==head;
    }
    void move(int key)
    {
        Node* head=node[key]-&gt;head;
        list_remove(node[key]);
        int fre=head-&gt;val;
        if(empty(head) &amp;&amp; (fre==min_cnt)) min_cnt++;
        if(freq.find(fre+1)==freq.end()) freq[fre+1]=_new(0,fre+1);
        list_add(freq[fre+1],node[key]);
        node[key]-&gt;head=freq[fre+1];
        return;
    }
    int get(int key) {
        if((node.find(key)!=node.end()) &amp;&amp; node[key])
        {
            move(key);
            return node[key]-&gt;val;
        }
        return -1;
    }

    void set(int key, int value) {
        if(!cap) return;
        if((node.find(key)!=node.end()) &amp;&amp; node[key])
        {
            node[key]-&gt;val=value;
            move(key);
            return;
        }
        if(cur==cap)
        {
            Node*tmp=freq[min_cnt]-&gt;pre;
            node[tmp-&gt;key]=NULL;
            list_remove(tmp);
            cur--;
        }
        node[key]=_new(key,value);
        if(freq.find(1)==freq.end()) freq[1]=_new(0,1);
        list_add(freq[1],node[key]);
        node[key]-&gt;head=freq[1];
        min_cnt=1;
        cur++;
        return;
    }
    void debug()
    {
        map&lt;int,Node*&gt;::iterator it;
        for(it=freq.begin();it!=freq.end();it++)
        {
            printf(&quot;freq  %d::::&quot;,it-&gt;first);
            Node*head=it-&gt;second;
            Node*p=head-&gt;next;
            while(p!=head)
            {
                printf(&quot;%d &quot;,p-&gt;val);
                p=p-&gt;next;
            }
        }
        printf(&quot;\n___________________\n&quot;);
    }
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.set(key,value);
 */

275. H-Index II
题意:找到一个数x,使得数组中有x个数大于等于x,其他数小于等于x。如果存在多个x,取最大那个

int hIndex(int* citations, int citationsSize) {
        int i;
        int *a=citations;
        int n=citationsSize;
        if(!n) return 0;
        int num;
        for(i=n-1;i&gt;=0;i--)
        {
            num=n-i;
            if(num&gt;=a[i]) break;
        }
        if(i&lt;0) return n;
        return a[i]&gt;=num-1?a[i]:num-1;
}

39. Combination Sum

class Solution {
private:
    vector&lt;int&gt; ret;
    vector&lt; vector&lt;int&gt; &gt; ans;
    int n;
public:
    void dfs(vector&lt;int&gt;&amp; nums,int cur,int target)
    {
        if(cur==n)
        {
            if(!target) ans.push_back(ret);
            return;
        }
        ret.push_back(nums[cur]);
        if(!target)
        {
            ans.push_back(ret);
            ret.pop_back();
            return;
        }
        for(int i=cur;i&lt;=n;i++)
        {
            int tmp=(i==n?target:target-nums[i]);
            if(tmp&lt;0) break;
            dfs(nums,i,tmp);
        }
        ret.pop_back();
        return;
    }
    vector&lt;vector&lt;int&gt;&gt; combinationSum(vector&lt;int&gt;&amp; candidates, int target) {
        int i;
        n=candidates.size();
        sort(candidates.begin(),candidates.end());
        for(i=0;i&lt;=n;i++)
        {
            if(target-candidates[i]&lt;0) continue;
            dfs(candidates,i,target-candidates[i]);
        }
        return ans;
    }
};

474. Ones and Zeroes
题意:给出一些t个字符串,这些字符串都是由'0'和'1'组成。问用m个1和n个0最多可以组成t个字符串中的多少个,注意每个0和1只能用once。
思路:一道挺好的dp题,好久没做dp了。dp[i][j][k]表示前i个字符串,用j个1和k个0最多可以表达多少个。dp方程不难推出:dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-cnt[i][0]][k-cnt[i][1]]+1);
其中cnt[x][0|1]表示第x个字符串由多少个0,多少个1.由dp方程可以发现,可以用滚动数组减少一维空间

class Solution {
    int dp[110][110];
    int cnt[610][2];
public:
    int max(int a,int b){return a&gt;b?a:b;}
    void cal(string a,int x)
    {
        cnt[x][0]=cnt[x][1]=0;
        for(int i=0;i&lt;a.length();i++) cnt[x][a[i]-'0']++;
        return;
    }
    int findMaxForm(vector&lt;string&gt;&amp; strs, int m, int n) {
        int i,j,k;
        int len=strs.size();
        if(!len) return 0;
        for(i=0;i&lt;len;i++) cal(strs[i],i+1);
        for(i=0;i&lt;=len;i++)
        {
            for(j=m;j&gt;=0;j--)
                for(k=n;k&gt;=0;k--)
                {
                    if(!i) {dp[j][k]=0;continue;}
                    if((cnt[i][0]&gt;j) || (cnt[i][1]&gt;k)) continue;
                    dp[j][k]=max(dp[j][k],dp[j-cnt[i][0]][k-cnt[i][1]]+1);
                }
        }
        return dp[m][n];
    }
};

376. Wiggle Subsequence
题意:将一个数组相邻两数分别相减得到一个差数组x1,x2,x3 ……如果x1符号与x2不同,x2符号与x3不同,……则此数组满足要求。现在给出一个数组,问最长的满足要求的子序列是多长。
思路:又是一道dp。类似LIS,但是由于每个数作为结尾有两种情况,即前面那个数比它小,以及前面那个数比它大。更新时如果两种情况的结果一样,那么这两种情况要分别保留,因为无法确定哪种情况对后续求解更优。
dp[i][0]表示以nums[i]为结尾且前一个数比它大的情况下满足要求的最长子序列。
dp[i][1]表示以nums[i]为结尾且前一个数比它小的情况下满足要求的最长子序列。
转移方式和LIS类似,时间复杂度O(n^2)

class Solution {
private:
    int dp[10000][2];
public:
    int wiggleMaxLength(vector&lt;int&gt;&amp; nums) {
        int i,j;
        int n=nums.size();
        int ans=1;
        if(n&lt;=1) return n;
        for(i=0;i&lt;n;i++) dp[i][0]=dp[i][1]=1;
        for(i=1;i&lt;n;i++)
        {
            for(j=0;j&lt;i;j++)
            {
                int tmp=nums[i]-nums[j];
                if(tmp&gt;0 &amp;&amp; dp[j][0]+1&gt;dp[i][1]) dp[i][1]=dp[j][0]+1;
                if(tmp&lt;0 &amp;&amp; dp[j][1]+1&gt;dp[i][0]) dp[i][0]=dp[j][1]+1;
            }
            if(dp[i][0]&gt;ans) ans=dp[i][0];
            if(dp[i][1]&gt;ans) ans=dp[i][1];
        }
        return ans;

    }
};

134. Gas Station
题意:给出n个gas station,绕成一个圈。每个station i有gas[i]的油。一辆车从station i到station i+1消耗cost[i]的油。问能否找到一个station作为起点绕所有station一圈回到起点。
思路:朴素做法是尝试每个加油站作为起点,复杂度O(n^2)。
更好的思路:贪心。最优的起点必然是能够积累出最多油量的station。如果在这种情况下都无法绕一圈,那么其他起点也不行。问题变成了求循环数组的最大连续和(的起点)。
求循环数组的最大连续和的方法:首先求普通数组的最大连续和。然后不要忘了另一种情况:最大连续和那个序列是跨越a[n-1]到a[0]的,这种情况的求法:求出普通数组a[]的最小连续和,用总和减去这个最小连续和即可。

int dp[10000];
int begin[10000];
int max(int a,int b){return a&gt;b?a:b;}
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
    int i;
    int sum=0;
    int n=gasSize;
    for(i=0;i&lt;n;i++)
    {
        gas[i]-=cost[i];
        sum+=gas[i];
    }
    if(sum&lt;0) return -1;
    for(i=0;i&lt;n;i++) {dp[i]=gas[i];begin[i]=i;}
    int max_sum=dp[0],max_begin=0;
    for(i=1;i&lt;n;i++)
    {
        if(dp[i-1]&gt;0) {dp[i]+=dp[i-1];begin[i]=begin[i-1];}
        if(dp[i]&gt;max_sum) {max_sum=dp[i];max_begin=begin[i];}
    }
    for(i=0;i&lt;n;i++) {dp[i]=gas[i];}
    int min_sum=dp[0],min_end=0;
    for(i=1;i&lt;n;i++)
    {
        if(dp[i-1]&lt;0) dp[i]+=dp[i-1];
        if(dp[i]&lt;min_sum) {min_sum=dp[i];min_end=i;}
    }
    max_sum=max(max_sum,sum-min_sum);
    if(max_sum&lt;sum-max_sum) return -1;
    if(max_sum==sum-min_sum) return (min_end+1)%n;
    return max_begin;
}

213. House Robber II
这题简单,但还是记一下
题意:给出一个循环数组,元素是positive数。两个相邻的数不能同时选中。问最大获益是多少。
思路:如果不是循环数组,则dp[i][0]=max(dp[i-1][0],dp[i-1][1]);dp[i][1]=dp[i-1][0]+nums[i];
问题在于数组是循环的,也就是说nums[n-1]和nums[0]是相邻的,不能同时选中。所以要这么做:第一次dp的时候dp[0][0]=dp[0][1]=0。也就是强制我不选第0个元素。第二次dp的时候正常dp,但是只取dp[n-1][0],也就是强制不选第n-1个数
这样就得到了(1)不选第0个数的最优解(2)可选第0个数但是不选第n-1个数的最优解。两者取最优即可

int dp[1010][2];
int max(int a,int b){return a&gt;b?a:b;}
int rob(int* nums, int numsSize) {
    int i;
    int n=numsSize;
    if(!n) return 0;
    if(n==1) return nums[0];
    dp[0][0]=dp[0][1]=0;
    for(i=1;i&lt;n;i++)
    {
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        dp[i][1]=dp[i-1][0]+nums[i];
    }
    int ans=max(dp[n-1][0],dp[n-1][1]);
    dp[0][1]=nums[0];
    for(i=1;i&lt;n;i++)
    {
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        dp[i][1]=dp[i-1][0]+nums[i];
    }
    ans=max(ans,dp[n-1][0]);
    return ans;
}

310. Minimum Height Trees
题意:给出一棵无根树。选定一个节点可以将它转化为有根数。问:以哪些节点为根,可以使树高最小。
思路:这题非常有意思。本质是书树上的最长路问题。记得以前打acm的时候总结过,下面再来详细分析一遍。
树上的最长路指的是树上距离最远的两个点之间的距离。
问题一:一棵树上的最长路有几条?
答:一棵树上的最长路可能有很多条,但是他们必然相交。
问题二:如果最长路有多条,可不可能它们的中心点不同?
答:不会,一棵树上所有最长路的中点只可能有一个(如果最长路为偶数长度,那当然有两个,但他们属于同一条最长路)。
这个问题非常关键。这其实是在证本题答案最多为2个。
反证法:假设一棵树有两条最长路path1,path2,设他们相交那部分为path_share,如果path1的中点在它的独立部分,那么是不是说明path1的独立部分比path_share要长呢。那么是不是path1的独立部分加上path2的独立部分(和path1接壤的部分)这样形成的路更长呢?这样和path1是最长路矛盾,得证。
定理一:要是无根树的树高最小,一定要选最长路上的中点。
证明:假设最长路长度为len,当选择最长路的中点作为树根的时候,树高是len/2。
情况一:如果选的是最长路上不是中点的点,那么它将最长路分割成x,len-x,显然两者之中有一个大于len/2。
情况二:如果选的不是最长路上的点,那么最长路肯定不跨域root节点,也就是最长路被“折叠悬挂在某个节点下”。假设最长路被分割成x,len-x。那么两者中必然有一个数大于等于len/2,这一段再加上“悬挂点”往上一段,必然大于len/2。
由此得证。
定理二:选定无根树的任意一个节点作为root,离root最远的叶子节点一定是最长路的一个端点。
这个定理看定理一的证明就够明白了。
由此我们得到两种解题思路:
思路1:从叶子节点(度为1)bfs,得到每个点的depth值,depth最大的点就是可选的根节点。
思路2:随便选一个点作为root,dfs找到最远的叶子节点,这个叶子节点就是最长路的一个端点。再以这个叶子节点为root,dfs找到最远的叶子节点,这个叶子节点是最长路的另一个端点,这样最长路的两个端点都找到了,接下来就很容易找到最长路的中点了
思路1代码

#define maxn 100000
struct Edge{
    int to;
    int next;
};
class Solution {
    Edge edge[maxn&lt;&lt;1];
    int head[maxn];
    int cnt;
    bool vis[maxn];
    int d[maxn],dep[maxn];
    int q[maxn],iq;
public:
    void add(int u,int v)
    {
        edge[cnt].to=v;edge[cnt].next=head[u];
        head[u]=cnt++;
    }
    vector&lt;int&gt; findMinHeightTrees(int n, vector&lt;pair&lt;int, int&gt;&gt;&amp; edges) {
        int i,j;
        cnt=0;
        vector&lt;int&gt; ans;if(!ans.empty()) ans.clear();
        if(!n) return ans;
        if(n==1) {ans.push_back(0);return ans;}
        memset(head,-1,sizeof(int)*(n+5));
        memset(d,0,sizeof(int)*(n+5));
        memset(vis,0,sizeof(bool)*(n+5));
        memset(dep,0,sizeof(int)*(n+5));
        for(i=0;i&lt;edges.size();i++)
        {
            int u=edges[i].first,v=edges[i].second;
            add(u,v);
            add(v,u);
            d[u]+=1;d[v]+=1;
        }
        iq=0;
        for(i=0;i&lt;n;i++)
            if(d[i]==1) {q[iq++]=i;vis[i]=1;dep[i]=1;}
        for(i=0;i&lt;iq;i++)
        {
            int cur=q[i];
            for(j=head[cur];j!=-1;j=edge[j].next)
            {
                int v=edge[j].to;
                if(vis[v]) continue;
                d[v]-=1;
                if(d[v]==1) {q[iq++]=v;vis[v]=1;dep[v]=dep[cur]+1;}
            }
        }
        int max_dep=1;
        for(i=0;i&lt;n;i++) if(dep[i]&gt;max_dep) max_dep=dep[i];
        for(i=0;i&lt;n;i++) if(dep[i]==max_dep) ans.push_back(i);
        return ans;
    }
};

368. Largest Divisible Subset
辛苦打了那么多字,结果一点更新就没了。。。
题意:
思路:类似LIS的dp

class Solution {
private:
    vector&lt;int&gt; ans;
public:
    vector&lt;int&gt; largestDivisibleSubset(vector&lt;int&gt;&amp; nums) {
        int i,j;
        int n=nums.size();
        if(!n) return ans;
        if(n==1) return nums;
        sort(nums.begin(),nums.end());
        int *dp=(int*)malloc(sizeof(int)*n);
        int *pre=(int*)malloc(sizeof(int)*n);
        dp[0]=1;pre[0]=-1;
        int last=0,max_sub=1;
        for(i=1;i&lt;n;i++)
        {
            dp[i]=1;pre[i]=-1;
            for(j=0;j&lt;i;j++)
            {
                if(nums[i]%nums[j]) continue;
                if(dp[j]+1&gt;dp[i]) {dp[i]=dp[j]+1;pre[i]=j;}
            }
            if(dp[i]&gt;max_sub) {max_sub=dp[i];last=i;}
        }
        while(last!=-1) {ans.push_back(nums[last]);last=pre[last];}
        return ans;
    }
};

321. Create Maximum Number
题意:给出两个数组,元素都是[0,9]的数字。现在从两个数组中总共取出k个数,求能够形成的最大k位数。
思路:从一个数组中取出k个数组成最大的k位数是比较好做的,直接贪心即可,而且因为是求最大,不用考虑最高位取0的问题。两个数组的话只能枚举每个数组分别取几个数了。
注意点:当从数组1取出x个数,从数组2取出k-x个数,形成两个新数组后,使用合并两个数组的方式合并它们,这时如果出现两个数组的当前元素相等,要考虑后面的元素大小来决定先放哪个数。

class Solution {
private:
    vector&lt;int&gt; ret;
public:
    int choose_one(vector&lt;int&gt; a,int start,int end,int &amp;index)
    {
        int ret=-1;
        for(int i=start;i&lt;=end;i++) if(a[i]&gt;ret) {ret=a[i];index=i;}
        return ret;
    }
    vector&lt;int&gt; choose(vector&lt;int&gt; a,int k)
    {
        if(!ret.empty()) ret.clear();
        if(!k) return ret;
        int start=0,end=a.size()-k;
        for(int i=1;i&lt;=k;i++)
        {
            int index;
            int tmp=choose_one(a,start,end,index);
            ret.push_back(tmp);
            start=index+1;end+=1;
        }
        return ret;
    }
    vector&lt;int&gt; merge_vector(vector&lt;int&gt; a,vector&lt;int&gt; b)
    {
        if(!ret.empty()) ret.clear();
        int i=0,j=0;
        while(i&lt;a.size() &amp;&amp; j&lt;b.size())
        {
            if(a[i]&gt;b[j]) ret.push_back(a[i++]);
            else if(a[i]&lt;b[j]) ret.push_back(b[j++]);
            else
            {
                int f=0;
                int k;
                for(k=1;i+k&lt;a.size();k++)
                {
                    if(j+k&gt;=b.size()) break;
                    if(a[i+k]&gt;b[j+k]) break;
                    if(a[i+k]&lt;b[j+k]) {f=1;break;}
                }
                if(i+k==a.size()) f=1;
                if(!f) ret.push_back(a[i++]);
                else ret.push_back(b[j++]);
            }
        }
        while(i&lt;a.size()) ret.push_back(a[i++]);
        while(j&lt;b.size()) ret.push_back(b[j++]);
        return ret;
    }
    bool cal(vector&lt;int&gt; a,vector&lt;int&gt; b)
    {
        for(int i=0;i&lt;a.size();i++)
            if(a[i]&gt;b[i]) return 1;
            else if(a[i]&lt;b[i]) return 0;
        return 0;
    }
    vector&lt;int&gt; maxNumber(vector&lt;int&gt;&amp; nums1, vector&lt;int&gt;&amp; nums2, int k) {
        int i,j;
        vector&lt;int&gt; ans(5);
        for(i=0;i&lt;=k;i++)
        {
            if((i&gt;nums1.size()) || (k-i&gt;nums2.size())) continue;
            vector&lt;int&gt; c1(choose(nums1,i));
            vector&lt;int&gt; c2(choose(nums2,k-i));
            vector&lt;int&gt; c3(merge_vector(c1,c2));
            if(cal(c3,ans)) ans.assign(c3.begin(),c3.end());

        }
        return ans;
    }
};

95. Unique Binary Search Trees II
题意:返回1到n的所有不同形态的BST。
思路:dfs。dfs的时候枚举一值x作为root,然后分别dfs左(1,x-1)右(x+1,n)区间。dfs的返回值是该区间所有可能的BST。当前区间的答案是左子树的所有可能与右子树的所有可能分别对应连接。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector&lt;TreeNode*&gt; dfs(int l,int r)
    {
        int i,j,k;
        vector&lt;TreeNode*&gt; ret;
        if(l&gt;r) {ret.push_back((TreeNode*)NULL);return ret;}
        if(l==r)
        {
            TreeNode* tmp=new TreeNode(l);
            ret.push_back(tmp);
            return ret;
        }
        for(int i=l;i&lt;=r;i++)
        {
            vector&lt;TreeNode*&gt; left=dfs(l,i-1);
            vector&lt;TreeNode*&gt; right=dfs(i+1,r);
            for(j=0;j&lt;left.size();j++)
                for(k=0;k&lt;right.size();k++)
                {
                    TreeNode* root=new TreeNode(i);
                    TreeNode* lnow=left[j],*rnow=right[k];
                    root-&gt;left=lnow;root-&gt;right=rnow;
                    ret.push_back(root);
                }
        }
        return ret;
    }
    vector&lt;TreeNode*&gt; generateTrees(int n) {
        int i,j;
        if(!n) return vector&lt;TreeNode*&gt;();
        return dfs(1,n);

    }
};

335. Self Crossing
题意:给出数组a[],元素都是positive integer。表示从原点(0,0)出发,先向上画长度为a[0]的直线,然后向左画长度为a[1]的直线,然后向下画长度为a[2]的直线,然后向右画长度为a[3]的直线。如此循环往复。问这些线是否相交。要求时间O(n),空间O(1)
思路:仔细分析可以发现线之间相交只有三种情况。(此处缺图一张)

class Solution {
public:
    bool isSelfCrossing(vector&lt;int&gt;&amp; x) {
        int n=x.size();
        if(n&lt;=3) return 0;
        for(int i=3;i&lt;n;i++)
        {
            if((x[i-1]&lt;=x[i-3]) &amp;&amp; (x[i]&gt;=x[i-2])) return 1;
            if((i&gt;=4) &amp;&amp; (x[i-1]==x[i-3]) &amp;&amp; (x[i]+x[i-4]&gt;=x[i-2])) return 1;
            if((i&gt;=5) &amp;&amp; (x[i-2]&gt;x[i-4]) &amp;&amp; (x[i-1]&lt;=x[i-3]) &amp;&amp; (x[i-1]&gt;=x[i-3]-x[i-5]) &amp;&amp; (x[i]&gt;=x[i-2]-x[i-4])) return 1;
        }
        return 0;
    }
};

132. Palindrome Partitioning II
题意:给出字符串s,问最少切几刀可以使分成的所有字符串都是回文串。
思路:先用dp的方式求出所有子串是否是回文串,时间复杂度O(n^2)。然后再次dp。dp[i]表示s[0……i]最少切几刀。更新时先看s[0……i]如果整个是回文串,则直接dp[i]=1。dp[i]=min{dp[j]|1<=j<=i,isp[j][i]=1}+1.

int dp[2010];
int isp[2010][2010];
class Solution {
public:
    int minCut(string s) {
        int i,j;
        int n=s.length();
        if(n&lt;=1) return 0;
        dp[0]=0;
        for(i=0;i&lt;n;i++)
        {
            isp[i][i]=1;
            if(i&lt;n-1) isp[i][i+1]=(s[i]==s[i+1]);
        }
        for(int len=3;len&lt;=n;len++)
            for(i=0;i+len-1&lt;n;i++)
                isp[i][i+len-1]=(s[i]==s[i+len-1]?isp[i+1][i+len-1-1]:0);
        for(i=1;i&lt;n;i++)
        {
            if(isp[0][i]) {dp[i]=0;continue;}
            dp[i]=i;
            for(j=1;j&lt;=i;j++)
                if(isp[j][i] &amp;&amp; (dp[j-1]+1&lt;dp[i])) dp[i]=dp[j-1]+1;
        }
        return dp[n-1];
    }
};

131. Palindrome Partitioning
题意:上题求的是最少划分。这题求的是所有的划分方案。和上题一样,先求出所有子串是否是回文串。然后dfs暴力求解。求得时候枚举s[i……j]的开头回文串,然后递归求接下来的。

int isp[2010][2010];
class Solution {
    vector&lt;vector&lt;string&gt;&gt; ans;
    vector&lt;string&gt; ret;
    int n;
public:
    void dfs(string s,int cur)
    {
        if(cur==n)
        {
            ans.push_back(ret);
            return;
        }
        for(int i=cur;i&lt;n;i++)
        {
            if(!isp[cur][i]) continue;
            string tmp=s.substr(cur,i-cur+1);
            ret.push_back(tmp);
            dfs(s,i+1);
            ret.pop_back();
        }
        return;
    }
    vector&lt;vector&lt;string&gt;&gt; partition(string s) {
        int i,j,len;
        n=s.length();
        if(!n) return ans;
        if(n==1) {ret.push_back(s);ans.push_back(ret);return ans;}
        for(i=0;i&lt;n;i++)
        {
            isp[i][i]=1;
            if(i&lt;n-1) isp[i][i+1]=(s[i]==s[i+1]);
        }
        for(len=3;len&lt;=n;len++)
            for(i=0;i+len-1&lt;n;i++)
                isp[i][i+len-1]=(s[i]==s[i+len-1]?isp[i+1][i+len-1-1]:0);
        for(i=0;i&lt;n;i++)
        {
            if(!isp[0][i]) continue;
            string tmp=s.substr(0,i+1);
            ret.push_back(tmp);
            dfs(s,i+1);
            ret.pop_back();
        }
        return ans;
    }
};

473. Matchsticks to Square
题意:给出一些整数长度的火柴。火柴不能折断,但可以拼接。问能否使用每根火柴恰好一次,拼接成一个正方形。
思路:以前在hdoj上做过一道差不多的题。我感觉这种题其实已经算搜索中有点难度的了,可见leetcode的一些题其实是有一定难度的。
注意点:
(1)若某一条边选的火柴不适当,会导致无法拼好剩下几条边,所以要枚举一条边的所有可能组合
(2)dfs的时候要记录当前已经拼好了几条边,cnt。当回溯的时候如果当前火柴是上一次拼好的边的最后一根,则cnt也要回退。
(3)在dfs之前先预处理出边长。这样,如果dfs出cnt==4,也就是找到了四条边,则此时一定正好用尽所有火柴有且仅有一次。

const int maxn=1000+10;
class Solution {
    bool vis[maxn];
    int n,target;
    int cnt;
    int f=0;
public:
    void dfs(vector&lt;int&gt;&amp; nums,int cur,int sum)
    {
        vis[cur]=1;
        if(sum&gt;target) {vis[cur]=0;return;}
        if(sum==target)
        {
            cnt++;
            if(cnt==4) {f=1;return;}
            for(int i=0;i&lt;n;i++)
            {
                if(f) break;
                if(vis[i]) continue;
                dfs(nums,i,nums[i]);
            }
            vis[cur]=0;
            cnt-=1;
        }
        for(int i=cur+1;i&lt;n;i++)
        {
            if(f) break;
            if(vis[i]) continue;
            dfs(nums,i,sum+nums[i]);
        }
        vis[cur]=0;
        return;
    }
    bool cal(vector&lt;int&gt; nums)
    {
        f=0;cnt=0;
        for(int i=0;i&lt;n;i++)
        {
            if(f) break;
            if(vis[i]) continue;
            dfs(nums,i,nums[i]);
        }
        return f;
    }
    bool makesquare(vector&lt;int&gt;&amp; nums) {
        int i;
        n=nums.size();
        memset(vis,0,sizeof(bool)*(n+5));
        target=0;
        for(i=0;i&lt;n;i++) target+=nums[i];
        if(target%4) return 0;
        target/=4;
        return cal(nums);
    }
};

352.Data Stream as Disjoint Intervals
题意:每次给出整数x,表示插入区间[x,x],如果与现有区间连接,那么要合并区间。操作有两种add(x)表示插入一个数,get()输出当前所有区间。注意只考虑整数[1,2],2,[3,5]这三个区间是连续的,要合并
思路:用平衡树实现名次树和求第k小值。我用的是treap,可以lgn删除,增加元素,求kth(),rank()。add一个数时注意细节,几种不同情况。

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
struct Node{
    Node *ch[2];
    int r;
    int v;
    int right;
    int s;
    int cc;
    Node(int v,int right):v(v),right(right) {ch[0]=ch[1]=NULL;r=rand()%100007;s=1;cc=1;}
    bool operator <(const Node& rhs) const
    {
        return r<rhs.r;
    }
    int cmp(int x) const
    {
        if(x==v) return -1;
        return x<v?0:1;
    }
    void maintain()
    {
        s=cc;
        if(ch[0]!=NULL) s+=ch[0]->s;
        if(ch[1]!=NULL) s+=ch[1]->s;
    }
};

class SummaryRanges {
private:
    Node* root;
    vector<Interval> ans;
public:
    /** Initialize your data structure here. */
    SummaryRanges() {
        srand((unsigned int)time(NULL));
        root=NULL;
    }
    void rotate(Node* &o,int d)
{
    Node*k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
    o->maintain();k->maintain();o=k;
    return;
}
void insert(Node* &o,int x,int right)
{
    if(o==NULL) o=new Node(x,right);
    else
    {
        int d=o->cmp(x);
        if(d==-1) o->cc++;
        else
        {
            insert(o->ch[d],x,right);
            if(*(o)<*(o->ch[d])) rotate(o,d^1);
        }
    }
    o->maintain();
    return;
}
void _remove(Node* &o,int x)
{
    int d=o->cmp(x);
    if(d==-1 && o->cc>1)
        o->cc--;
    else if(d==-1)
    {
        Node*u=o;
        if(o->ch[0]!=NULL && o->ch[1]!=NULL)
        {
            int d2=(*(o->ch[1])<*(o->ch[0])?1:0);
            rotate(o,d2);_remove(o->ch[d2],x);
        }
        else
        {
            if(o->ch[0]==NULL) o=o->ch[1];
            else o=o->ch[0];
            delete u;
        }
    }
    else _remove(o->ch[d],x);
    if(o!=NULL) o->maintain();
}
int find(Node* o,int x)//treap中是否存在元素x
{
    while(o!=NULL)
    {
        int d=o->cmp(x);
        if(d==-1) return 1;
        else o=o->ch[d];
    }
    return 0;
}
Node* kth(Node* o,int k)//第k大数
{
    if(o==NULL || k<=0 || k>o->s) return NULL;//k不合法时返回0
    int s=(o->ch[0]==NULL?0:o->ch[0]->s);
    if(s+1<=k && k<=s+o->cc) return o;
    else if(k<=s) return kth(o->ch[0],k);
    else return kth(o->ch[1],k-s-o->cc);
}
int rank(Node* o,int x)
{
    int cnt=0;
    while(o!=NULL)
    {
        int d=o->cmp(x);
        if(d==-1)
        {
            if(o->ch[0]!=NULL) cnt+=o->ch[0]->s;
            return cnt+1;
        }
        if(d==1)
        {
            cnt+=o->cc;
            if(o->ch[0]!=NULL) cnt+=(o->ch[0]->s);
            o=o->ch[1];
        }
        else o=o->ch[0];
    }
    return cnt+1;
}
    void addNum(int val) {
        if(!root) {insert(root,val,val);return;}
        if(find(root,val)) return;
        int mingci=rank(root,val);
        if(mingci==1)
        {
            Node* next=kth(root,mingci);
            int left=next->v,right=next->right;
            if(left==val+1)
            {
                _remove(root,left);
                insert(root,val,right);
            }
            else
                insert(root,val,val);
            return;
        }
        if(mingci==(root->s+1))
        {
            Node* pre=kth(root,mingci-1);
            int left=pre->v,right=pre->right;
            if(right>=val) return;
            if(right==val-1)
            {
                _remove(root,left);
                insert(root,left,val);
            }
            else
                insert(root,val,val);
            return;
        }
        Node* pre=kth(root,mingci-1),*next=kth(root,mingci);
        int l1=pre->v,r1=pre->right,l2=next->v,r2=next->right;
        if(val<=r1) return;
        if((val==r1+1) && (val==l2-1))
        {
            _remove(root,l1);_remove(root,l2);
            insert(root,l1,r2);
            return;
        }
        if(val==r1+1)
        {
            _remove(root,l1);insert(root,l1,val);return;
        }
        if(val==l2-1)
        {
            _remove(root,l2);insert(root,val,r2);return;
        }
        insert(root,val,val);
        return;
    }
    void dfs(Node* cur)
    {
        Interval now(cur->v,cur->right);
        if(cur->ch[0]) dfs(cur->ch[0]);
        ans.push_back(now);
        if(cur->ch[1]) dfs(cur->ch[1]);
        return;
    }
    vector<Interval> getIntervals() {
        if(!ans.empty()) ans.clear();
        dfs(root);
        return ans;
    }
};

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges obj = new SummaryRanges();
 * obj.addNum(val);
 * vector<Interval> param_2 = obj.getIntervals();
 */

331. Verify Preorder Serialization of a Binary Tree
题意:给出一个字符串,问是否是一棵二叉树的先序遍历序列。'#'表示空指针。
思路:先序遍历去验证即可。

class Solution {
public:
    bool dfs(string s,int &p)
    {
        if(p>=s.length()) return 0;
        if(s[p]=='#') {p+=2;return 1;}
        while(s[p]>='0' && s[p]<='9') p++;
        p+=1;
        return (dfs(s,p) & dfs(s,p));
    }
    bool isValidSerialization(string preorder) {
        int p=0;
        int ans=dfs(preorder,p);
        return p<preorder.length()?0:ans;
    }
};

80. Remove Duplicates from Sorted Array II
题意:一个排好序的数组,每个元素只允许出现两次。把多余元素放到后面去。比如:1,1,1,2,2,3。返回5,并且返回时,数组变成1,1,2,2,3.后面如何排列不重要
思路:两个指针i,j,j指向垃圾区的开始位置。i遍历所有元素。如果nums[i]当前是出现两次及以内,则交换到垃圾区的开头,j++。否则只是i++

class Solution {
public:
    void swap(int& a,int& b){a^=b;b^=a;a^=b;}
    int removeDuplicates(vector<int>& nums) {
        int i,j;
        int n=nums.size();
        if(n<=2) return n;
        int cnt=0,cur=nums[0];k
        for(j=0;j<n;j++)
        {
            if(nums[j]==cur)
            {
                cnt++;
                if(cnt==3) break;
            }
            else {cur=nums[j];cnt=1;}

        }
        for(i=j+1;i<n;i++)
        {
            if(nums[i]==cur)
            {
                cnt++;
                if(cnt<=2) swap(nums[j++],nums[i]);
            }
            else
            {
                cur=nums[i];cnt=1;
                swap(nums[j++],nums[i]);
            }
        }
        return j;
    }
};

45. Jump Game II
我在leetcode的 discussion 里面写了一篇题解,渣英文.
地址:https://discuss.leetcode.com/topic/74602/a-dp-solution-with-humdrum-stack-o-n-with-a-small-constant
思路是dp加单调栈优化

const int inf=0x3f3f3f3f;
const int maxn=100000;
int dp[maxn];
int st[maxn],top;
class Solution {
public:
    int min(int a,int b){return a<b?a:b;}
    int bs(int l,int r,int v)
    {
        while(l<=r)
        {
            int m=l+(r-l)/2;
            if(v>=st[m]) r=m-1;
            else l=m+1;
        }
        return l;
    }
    int jump(vector<int>& nums) {
        int i,j;
        top=0;
        int n=nums.size();
        if(n<=1) return 0;
        dp[n-1]=0;
        st[top++]=n-1;
        for(i=n-2;i>=0;i--)
        {
            int index=i+nums[i];
            j=bs(0,top-1,index);
            if(j>=top)
            {
                dp[i]=inf;
                st[top++]=i;
                continue;
            }
            dp[i]=dp[st[j]]+1;
            st[j+1]=i;
            top=j+2;
        }
        return dp[0];
    }
};

407. Trapping Rain Water II
题意:给出一个矩阵,每个元素表示高度,问,该矩阵总共可以接多少水
思路:这题想不出来啊。。思路真心巧妙。用优先队列表存边界的所有高度。每次pop出最小元素。然后bfs。如果周围未访问的元素比他高,则入队,否则它和当前元素的差就是这块上面可以接的雨水,之后把雨水高度加上,然后入队。

struct Node{
    int x,y;
    int h;
    friend bool operator < (Node a,Node b)
    {
        return a.h>b.h;
    }
    Node(int x,int y,int h):x(x),y(y),h(h)
    {}
    Node(const Node &a)
    {
        x=a.x;y=a.y;h=a.h;
    }
};
class Solution {
private:
    int r,c;
    bool vis[115][115];
public:
    int max(int a,int b){return a>b?a:b;}
    bool judge(int x,int y)
    {
        return !((x<0) || (x>=r) || (y<0) || (y>=c));
    }
    int trapRainWater(vector<vector<int>>& mat) {
        int i,j;
        int ans=0;
        r=mat.size();
        if(!r) return 0;
        c=mat[0].size();
        if(!c) return 0;
        memset(vis,0,sizeof(vis));
        priority_queue<Node> q;
        while(!q.empty()) q.pop();
        for(i=0;i<r;i++)
        {
            Node tmp1(i,0,mat[i][0]);
            Node tmp2(i,c-1,mat[i]1);
            q.push(tmp1);vis[i][0]=1;
            q.push(tmp2);vis[i]1=1;
        }
        for(j=1;j<c-1;j++)
        {
            Node tmp1(0,j,mat[0][j]);
            Node tmp2(r-1,j,mat[r-1][j]);
            q.push(tmp1);vis[0][j]=1;
            q.push(tmp2);vis[r-1][j]=1;
        }
        int dirx[]={0,-1,1,0,0};
        int diry[]={0,0,0,-1,1};
        while(!q.empty())
        {
            Node cur=q.top();q.pop();
            int x=cur.x,y=cur.y,h=cur.h;
            for(i=1;i<=4;i++)
            {
                int xx=x+dirx[i],yy=y+diry[i];
                if(!judge(xx,yy) || vis[xx][yy]) continue;
                ans+=(h-mat[xx][yy]>0?h-mat[xx][yy]:0);
                Node tmp(xx,yy,max(mat[xx][yy],h));
                q.push(tmp);
                vis[xx][yy]=1;
            }
        }
        return ans;
    }
};

373. Find K Pairs with Smallest Sums
题意:给出两个升序数组,返回前k小的2sum。
思路:设置id[nums1.size()],id[i]表示nums1[i]对应的nums2[]中的下标。表示之前已经试过nums1[i]+nums2[0……id[i]-1]。那么只要遍历一遍nums1[]数组就能选出一个最小的sum,选前k个的复杂度是O(k*n)

const int inf=0x3f3f3f3f;
class Solution {
public:
    int min(int a,int b){return a<b?a:b;}
    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        int i;
        int n=nums1.size(),m=nums2.size();
        vector<pair<int,int>> ans;
        if(!k || !n || !m) return ans;
        vector<int> id(n);
        k=min(k,n*m);
        while(k--)
        {
            int _min=inf,min_id;
            for(i=0;i<n;i++)
            {

                if(id[i]<m && nums1[i]+nums2[id[i]]<_min)
                {
                    _min=nums1[i]+nums2[id[i]];
                    min_id=i;
                }
            }
            ans.push_back({nums1[min_id],nums2[id[min_id]]});
            id[min_id]++;
        }
        return ans;
    }
};

239. Sliding Window Maximum
题意:给出一个整形数组,窗口大小为k,窗口从左往右滑动。计算每次窗口中的最大值。要求O(n)时间
思路:典型的单调队列题

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int q[100000],id[100000];
int start,end;
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
    int i,j;
    int n=numsSize;
    int *ans=(int*)malloc(sizeof(int)*(n-k+1));
    *returnSize=0;
    if(!k) return ans;
    start=end=0;
    int cnt=0;
    for(i=0;i<k-1;i++)
    {
        while((end>start) && (nums[i]>q[end-1])) end--;
        q[end]=nums[i];id[end++]=i;
    }
    for(i=k-1;i<n;i++)
    {
        while((end>start) && (nums[i]>q[end-1])) end--;
        q[end]=nums[i];id[end++]=i;
        //printf("%d %d\n",start,end);
        while((end>start) && (id[start]<i-k+1)) start++;
        ans[(*returnSize)++]=q[start];

    }
    return ans;
}

140. Word Break II
题意:给出一个字符串,给出一个字符串字典,在原字符串中加空格来分割字符串,使得每部分都是字典中的单词。求出所有方案
思路:这题我写的比较烦,因为这样可以有效剪枝。首先原字符串尾部开始dp.dp[i]表示以s[i]结尾的字符串能否有效分割。转移的时候就是在字典中查找所有单词与dp[i]代表的那个字符串的后缀匹配。
比如:dp[i]的那个字符串的后缀是"abc",而"abc"是字典中的单词。那么如果dp[i-3]=1,则dp[i]=1。这时我们连一条边(i,i-3)。最后我们在这张图上从源字符串的最后一个字符,即点n(从1开始计数)开始dfs所有路径即可。
注意:dfs时候先生成更深层dfs产生的子字符串列表。然后在后面加空格和当前字符串。注意若干细节。
先生成图再dfs和直接从尾部dfs相比,相当于剪枝。因为如果直接dfs,可能陷入到很多“不能分割到起始点的分支”中。

const int maxe=10000+10;
const int maxn=10000+10;
struct Edge{
    int v;
    int next;
    string s;
};
class Solution {
private:
    Edge edge[maxe];
    int head[maxn],cnt;
public:
    void add(int u,int v,string s)
    {
        edge[cnt].v=v;edge[cnt].s=s;edge[cnt].next=head[u];
        head[u]=cnt++;
        return;
    }
    vector<string> dfs(int cur)
    {
        int i,j;
        vector<string> ret;
        if(!cur) {ret.push_back("");return ret;}
        for(i=head[cur];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            string now=edge[i].s;
            //cout<<cur<<"  "<<v<<"  "<<now<<endl;
            vector<string> pre=dfs(v);
            for(int j=0;j<pre.size();j++)
            {
                if(pre[j]!="") pre[j]+=" "+now;
                else pre[j]+=now;
            }
            ret.insert(ret.end(),pre.begin(),pre.end());
        }
        return ret;

    }
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        int i,j;
        cnt=0;memset(head,-1,sizeof(head));
        int n=s.length();
        if(!n || !wordDict.size()) return vector<string>();
        bool *dp=(bool *)malloc((n+5)*sizeof(bool));
        dp[0]=1;for(i=1;i<=n;i++) dp[i]=0;
        for(i=1;i<=n;i++)
        {
            for(j=0;j<wordDict.size();j++)
            {
                string tmp=wordDict[j];
                int len=tmp.length();
                if((i-len>=0) && (s.substr(i-len,len)==tmp) && dp[i-len])
                {
                    add(i,i-len,tmp);
                    dp[i]=1;
                }
            }
        }
        return dfs(n);
    }
};

166. Fraction to Recurring Decimal
题意:把整数除法的结果用字符串表示,如果是循环小数,只需将循环节加括号表示
注意点:
1.注意int型数,INT_MIN和INT_MAX是不一样的。INT_MIN的绝对值要比INT_MAX大1。这点很重要,凡是整数除法,一定要想到这一点。
2.注意结果是负的情况
3.找循环节的时候不要弄错长度

typedef long long ll;
class Solution {
private:
    unordered_map<ll,int> mod;
public:
    string dfs(ll x)
    {
        string ret;
        if(!x) return ret;
        if(x) ret=dfs(x/10);
        char tmp='0'+x%10;
        return ret+tmp;
    }
    string fractionToDecimal(int xx, int yy) {
        string ans;
        if(xx==0) {ans+='0';return ans;}
        int f=0;
        ll x=xx,y=yy;
        if((xx<0 && yy>0) || (xx>0 && yy<0)) f=1;
        if(f) {x=abs(x);y=abs(y);}
        if(f) ans+="-";
        ll tmp=x/y;
        if(!tmp) ans+='0';
        else ans+=dfs(tmp);
        if(!(x%y)) return ans;
        else ans+='.';
        ll c=x-tmp*y,pre;
        int loop=0;
        if(!mod.empty()) mod.clear();
        while(c)
        {
            mod1=ans.length();
            pre=c;
            c*=10;
            char t='0'+c/y;
            ans+=t;
            c-=c/y*y;
            if(mod.find(c)!=mod.end())
            {
                loop=mod1;break;
            }
        }
        if(!loop) return ans;
        string last=ans.substr(loop,ans.length()-loop);
        ans[loop]='(';ans.resize(loop+1);
        return ans+last+")";
    }
};

143. Reorder List
题意:这题是把链表后一半倒序插入到前面一半之间。
思路:先把后面一半逆置,然后两个指针遍历一下。注意细节。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
int get_len(struct ListNode* head)
{
    int cnt=0;
    while(head) {cnt++;head=head->next;}
    return cnt;
}
void reverse(struct ListNode* head)
{
    struct ListNode* p=head->next,*q=p->next;
    if(!q) return;
    while(q)
    {
        p->next=q->next;
        q->next=head->next;
        head->next=q;
        q=p->next;
    }
    return;
}
void reorderList(struct ListNode* head) {
    int i,j;
    int len=get_len(head);
    if(len<=2) return;
    int pre=len-len/2;
    struct ListNode* p=head;
    int cnt=1;
    while(cnt<pre) {p=p->next;cnt++;}
    reverse(p);
    struct ListNode*l1=head,*l2=p->next;
    while(l1!=p)
    {
        p->next=l2->next;
        l2->next=l1->next;
        l1->next=l2;
        l1=l1->next->next;
        l2=p->next;
    }
    return;

}

49. Group Anagrams
题意:给出一些字符串,将它们归类。归类方法是:出现字母及次数相同的为一类。
思路:一个字符串排序后作为hash table的key。复杂度O(nklgk)。n是字符串个数,k是字符串的平均长度。
有种方法可以防止每次对字符串进行排序:对每个字母映射一个prime。将一个字符串对应的所有prime相乘作为key。这样虽然复杂度是O(nk),但是可能溢出。作为一个不错的思路,我放在这里。
105. Construct Binary Tree from Preorder and Inorder Traversal

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    vector<int> pre,in;
public:
    int cal(int l,int r,int v)
    {
        int i;
        for(i=l;i<=r;i++)
            if(in[i]==v) break;
        return i;
    }
    TreeNode* dfs(int pl,int pr,int il,int ir)
    {
        if(pl>pr || il>ir) return NULL;
        TreeNode* root=new TreeNode(pre1);
        int mid=cal(il,ir,pre1);
        int left_len=mid-il,right_len=ir-mid;
        root->left=dfs(pl+1,pl+1+left_len-1,il,mid-1);
        root->right=dfs(pl+1+left_len,pr,mid+1,ir);
        return root;
    }
    TreeNode* buildTree(vector<int>& preo, vector<int>& ino) {
        int i,j;
        pre=preo;in=ino;
        int n=pre.size();
        return dfs(0,n-1,0,n-1);
    }
};

324. Wiggle Sort II
题意:给出数组nums[],排序使得nums[0]nums[2]……。
思路:先升序排序。然后将前面一半和后面一半倒序交叉放入新数组。比如1,2,3,4,5。变成3,5,2,4,1
为什么这样做一定可行,在保证有解的情况下。
首先,如果同一个数出现次数超过一半(对于总数是偶数的情况),或者超过一半+1(对于总数是奇数的情况)。那么一定不存在解。因为必定存在相邻两数相等的情况。
除了上述情况,还有类似4,5,5,5,5,5,7,8,9这种情况没有解。其他情况下,排序后的nums[i]和与它相距n/2的数nums[i+n/2]一定不相等。所以可以用上述方法求解。
注意点:为什么要倒序放前后两部分?考虑1,5,5,6的情况,如果顺序放,则先放1,5再放5,6,最后序列是1,5,5,6.不符合要求,原因是这样放使中间的数距离近了。
同样的,1,2,3,4,5的时候,要先放3,5 而不是先放2,4。前者3会在最后,后者1会在最后。也是上述道理

此题有时间O(n),空间O(1)的做法。暂时还没理解

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int i,j;
        sort(nums.begin(),nums.end());
        int n=nums.size();
        vector<int> tmp(n);
        int cnt=0;
        if(n%2==0)
        {
            for(i=(n-1)/2;i>=0;i--) tmp[cnt++]=nums[i],tmp[cnt++]=nums[i+n/2];
        }
        else
        {
            for(i=n/2;i>=1;i--)
            {
                tmp[cnt++]=nums[i];tmp[cnt++]=nums[i+n/2];
            }
            tmp[cnt++]=nums[0];
        }
        for(i=0;i<n;i++) nums[i]=tmp[i];
    }
};

87. Scramble String
题意:给出两个字符串,能否通过以下操作将s1变成s2.
对一个字符串可以实行的操作:操作1,是选择一个分割点,将字符串分成两个子串。操作2,对1中得到的子串,可以交换他们的位置。
思路:dp。dp[i][j][k]表示s1的起始下标为i长度为k的字符串能否由s2的下标为j长度为k的字符串得到。
初始化:dp[i][j][1]=(s1[i]==s2[j])

class Solution {
private:
    int dp[100][100][100];
    string str1,str2;
public:
    bool dfs(int l1,int l2,int len)
    {
        int i;
        if(dp[l1][l2][len]!=-1) return dp[l1][l2][len];
        string tmp1=str1.substr(l1,len),tmp2=str2.substr(l2,len);
        sort(tmp1.begin(),tmp1.end());
        sort(tmp2.begin(),tmp2.end());
        for(i=0;i<len;i++) if(tmp1[i]!=tmp2[i]) return 0;
        for(i=1;i<len;i++)
        {
            if(dfs(l1,l2,i) && dfs(l1+i,l2+i,len-i)) return 1;
            if(dfs(l1,l2+len-i,i) && dfs(l1+i,l2,len-i)) return 1;
        }
        return 0;
    }
    bool isScramble(string s1, string s2) {
        int i,j,k;
        int len1=s1.length(),len2=s2.length();
        if(len1!=len2) return 0;
        str1=s1,str2=s2;
        memset(dp,-1,sizeof(dp));
        for(i=0;i<len1;i++)
            for(j=0;j<len1;j++)
            {
                dp[i][j][1]=(s1[i]==s2[j]);
            }
        return dfs(0,0,len1);
    }
};

467. Unique Substrings in Wraparound String
题意:
思路:


const int maxn=100000;
class Solution {
private:
    int ch[26];
public:
    int findSubstringInWraproundString(string p) {
        int i,j;
        int n=p.length();
        if(n<=1) return n;
        memset(ch,0,sizeof(ch));
        int dpi=1;ch[p[0]-'a']=1;
        int ans=1;
        for(i=1;i<n;i++)
        {
            if(((p[i]=='a') && (p[i-1]=='z')) || (p[i]==p[i-1]+1)) dpi++;
            else dpi=1;
            if(dpi<=ch[p[i]-'a']) continue;
            ans+=dpi-ch[p[i]-'a'];
            ch[p[i]-'a']=dpi;
        }
        return ans;
    }
};

410. Split Array Largest Sum
题意:把一个int数组分成m块,使得每块之和的最大值最小
思路:经典dp

typedef long long ll;
const int maxn=1010;
const ll inf=10000000000000000LL;
class Solution {
private:
    ll dp[maxn][55];
    ll sum[maxn];
public:
    ll min(ll a,ll b){return a<b?a:b;}
    ll max(ll a,ll b){return a>b?a:b;}
    ll DP(int x,int k)
    {
        if(dp[x][k]!=-1) return dp[x][k];
        if(k==1) {dp[x][k]=sum[x];return dp[x][k];}
        dp[x][k]=inf;
        for(int len=1;len<x;len++)
        {
            dp[x][k]=min(dp[x][k],max(DP(x-len,k-1),sum[x]-sum[x-len]));
        }
        return dp[x][k];
    }
    int splitArray(vector<int>& nums, int m) {
        int i,j;
        int n=nums.size();
        if(!n) return 0;
        if(n==1) return nums[0];
        memset(dp,-1,sizeof(dp));
        sum[0]=0;
        for(i=1;i<=n;i++) sum[i]=sum[i-1]+nums[i-1];
        return DP(n,m);
    }
};

212. Word Search II
题意:给出一个字典,一个字母矩阵。要求返回那些出现在矩阵中的单词。矩阵中的单词是由相邻的字母组成的。注意不能交叉形成环
思路:将字典中的单词插入Trie中,然后将矩阵的每个元素作为单词起点进行dfs。Trie用来剪枝,记得用hash表防止结果数组的元素重复。

const int maxn=100000;
int ch[maxn][26],sz;
int val[maxn];
void init()
{
    memset(ch,0,sizeof(ch));
    memset(val,0,sizeof(val));
    sz=0;
}
void insert(string s)
{
    int cur=0,i;
    int len=s.length();
    for(i=0;i<len;i++)
    {
        int tmp=s[i]-'a';
        if(!ch[cur][tmp]) ch[cur][tmp]=++sz;
        cur=ch[cur][tmp];
    }
    val[cur]=1;
    return;
}
int dirx[]={0,0,0,-1,1};
int diry[]={0,-1,1,0,0};

class Solution {
private:
    int r,c;
    unordered_map<string,bool> _hash;
    vector<vector<char>> mat;
    vector<string> ans;
    bool vis[110][110];
public:
    bool judge(int x,int y)
    {
        return !((x<0) || (x>=r) || (y<0) || (y>=c));
    }
    void dfs(int x,int y,int p,string pre)
    {
        int i;
        vis[x][y]=1;
        int index=mat[x][y]-'a';
        string str=pre+mat[x][y];
        int node=ch[p][index];
        if(!node) {vis[x][y]=0;return;}
        if(val[node] && _hash.find(str)==_hash.end())
        {
            ans.push_back(str);
            _hash[str]=1;
        }
        for(i=1;i<=4;i++)
        {
            int xx=x+dirx[i],yy=y+diry[i];
            if(!judge(xx,yy) || vis[xx][yy]) continue;
            dfs(xx,yy,node,str);
        }
        vis[x][y]=0;
        return;
    }
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        int i,j;
        r=board.size();
        if(!r) return ans;
        c=board[0].size();
        if(!c) return ans;
        mat=board;
        init();
        for(i=0;i<words.size();i++) insert(words[i]);
        if(!_hash.empty()) _hash.clear();
        for(i=0;i<r;i++)
            for(j=0;j<c;j++)
            {
                memset(vis,0,sizeof(vis));
                dfs(i,j,0,"");
            }
        return ans;
    }
};

224. Basic Calculator
题意:给出一个由空格、非负int、+、-、括号组成的合法数学表达式。求其值
思路:递归求解。注意tmp=tmp*10+s[i]-'0'有可能导致溢出!!。因为先计算了tmp*10+s[i]。所以要这样写:tmp=s[i]-'0'+tmp。
每次递归时,表达式的括号位置要重新用栈求出。每个string求解时末尾手工加上+号。因为我是每次遇到+号或-号才会计算上一步运算。

class Solution {
public:
    int cal(string str)
    {
        if(str=="") return 0;
        int i,n=str.length();
        stack<int> q;
        unordered_map<int,int> p;
        while(!q.empty()) q.pop();
        if(!p.empty()) p.clear();
        for(i=0;i<n;i++)
        {
            if((str[i]!='(') && (str[i]!=')')) continue;
            if(str[i]=='(') {q.push(i);continue;}
            if(!q.empty() && (str[q.top()]=='('))
            {
                p[q.top()]=i;
                q.pop();
            }
        }
        int ans=0,tmp=0;
        int op=1;
        for(i=0;i<str.length();)
        {
            if(str[i]==' ') {i++;continue;}
            if(str[i]>='0' && str[i]<='9') {tmp=str[i]-'0'+tmp*10;i++;continue;}
            if((str[i]=='+') || (str[i]=='-'))
            {
                if(op==1) ans+=tmp;
                if(op==2) ans-=tmp;
                tmp=0;
                op=(str[i]=='+'?1:2);
                i++;
                continue;
            }
            tmp=cal(str.substr(i+1,p[i]-i-1)+'+');
            i=p[i]+1;
        }
        return ans;
    }
    int calculate(string s) {
        return cal(s+"+");

    }
};

481. Magical String

const int maxn=1000000+10;
int a[maxn];
int b[maxn];
class Solution {
public:
    int magicalString(int n) {
        n--;
        int i,cnt1=2,cnt2=1;
        int start1=2,start2=2;
        a[0]=1;a[1]=2;a[2]=2;
        b[0]=1;b[1]=2;
        int ans=0;
        while((cnt1<=n) && (cnt2<=n))
        {
            for(i=start1;i<=cnt1;i++)
            {
                b[++cnt2]=a[i];
            }
            start1=cnt1+1;
            for(i=start2;i<=cnt2;i++)
            {
                if(b[i]==1) {a[cnt1+1]=3-a[cnt1];cnt1++;}
                if(b[i]==2) {a[cnt1+1]=a[cnt1+2]=3-a[cnt1];cnt1+=2;}
            }
            start2=cnt2+1;
        }
        if(cnt1>=n) for(i=0;i<=n;i++) ans+=abs(a[i]-2);
        else for(i=0;i<=n;i++) ans+=abs(b[i]-2);
        return ans;
    }
};

301. Remove Invalid Parentheses
题意:给出一个由括号和字母组成的表达式。去除最少的括号使得表达式合法。返回所有去除方案。
思路:bfs。初始把原字符串入队。它的后继就是尝试去除一个括号的结果。当第一次得到合法表达式时记录此时删掉几个字符。
注意:判断括号表达式合法的充要条件是:从前往后边路字符串,每一时刻保证右括号数量<=左括号数量,且最后左右括号数相等。

class Solution {
public:
    bool cal(string s)
    {
        int i,cnt=0;
        int n=s.length();
        for(i=0;i<n;i++)
        {
            if(s[i]=='(') {cnt++;continue;}
            if((s[i]==')') && (cnt--==0)) return 0;
        }
        return cnt==0;
    }
    vector<string> removeInvalidParentheses(string s) {
        int i;
        unordered_map<string,int> _hash;
        queue<string> q;
        vector<string> ans;
        int rem=0;
        if(cal(s)) {ans.push_back(s);return ans;}
        q.push(s);
        while(!q.empty())
        {
            string cur=q.front();q.pop();
            for(i=0;i<cur.length();i++)
            {
                if((s[i]=='(') || (s[i]==')'))
                {
                    string tmp=cur.substr(0,i)+cur.substr(i+1);
                    if(_hash.find(tmp)!=_hash.end()) continue;
                    _hash[tmp]=1;
                    int del=s.length()-tmp.length();
                    if(cal(tmp))
                    {
                        if(!rem || (del==rem)) {ans.push_back(tmp);rem=del;}
                        continue;
                    }
                    if(rem && (del>rem)) continue;
                    q.push(tmp);
                }
            }
        }
        return ans;
    }
};

147. Insertion Sort List

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    ListNode* target;
public:
    ListNode* insertionSortList(ListNode* head) {
        if(!head) return head;
        ListNode* p=head;
        if(!p->next) return head;
        p=p->next;
        target=head;target->next=NULL;

        while(p)
        {
            ListNode*cur=target,*pre=target;
            while(cur && (cur->val<p->val))
            {
                pre=cur;cur=cur->next;
            }
            ListNode* q=p->next;
            if(pre==cur)
            {

                p->next=target;
                target=p;
                p=q;
                continue;
            }
            p->next=pre->next;
            pre->next=p;
            p=q;
        }
        return target;
    }
};

72. Edit Distance
题意:给出两个字符串s1,s2。对一个字符串可以做的操作有:
1.删除一个字符
2.插入一个字符
3.改变一个字符
问s1最少经过多少步可以变成s2
思路:dp[i][j]表示s1的前i个字符变成s2的前j个字符最少需要多少步。dp[i][j]=min{dp[i][j-1]+1,1+dp[i-1][j],dp[i-1][j-1]+(s1[i]==s2[j]?0:1)}

int dp[1000][1000];
class Solution {
public:
    int min(int a,int b){return a<b?a:b;}
    int minDistance(string word1, string word2) {
        int i,j;
        int n1=word1.size(),n2=word2.size();
        dp[0][0]=0;
        for(i=0;i<=n1;i++)
            for(j=0;j<=n2;j++)
            {
                if(i==0) {dp[0][j]=j;continue;}
                if(j==0) {dp[i][0]=i;continue;}
                dp[i][j]=min(dp[i][j-1]+1,1+dp[i-1][j]);
                dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(word1[i-1]==word2[j-1]?0:1));
            }
        return dp[n1][n2];
    }
};

215. Kth Largest Element in an Array
题意:找第k大数
思路零:排序 空间O(1) 时间O(nlgn)
思路一:维护大小为k+1的最小堆,每次替换掉堆顶元素 空间O(n),时间O(nlg(k+1))
思路二:类似快排partition的分治算法 空间平均O(lgn) 最坏O(n),时间 平均O(nlgn) 最坏O(n^2)
算法导论里将思路二进行了优化,可以达到空间最坏O(lgn),时间最坏O(nlgn)
下面给出思路二的代码

class Solution {
public:
    void swap(vector<int>& nums,int a,int b)//it's possible that swap(nums[t],nums[t]),so xor method isn't ok here
    {
        int t=nums[a];
        nums[a]=nums[b];
        nums[b]=t;
    }
    int findk(vector<int>& nums,int k,int l,int r)
    {
        if(l>=r) return nums[l];
        int i=l,j=l+1;
        int x=nums[l];
        while(j<=r)
        {
            if(nums[j]>x) swap(nums,++i,j);
            j++;
        }
        swap(nums,l,i);
        int rank=i-l+1;
        if(rank==k) return nums[i];
        if(rank<k) return findk(nums,k-rank,i+1,r);
        return findk(nums,k,l,i-1);
    }
    int findKthLargest(vector<int>& nums, int k) {
        return findk(nums,k,0,nums.size()-1);
    }
};

297. Serialize and Deserialize Binary Tree
题意:给出一种serialize和deserialize的方法可以将一棵二叉树序列化成string和从string reconstruct这棵树。
这题主要学到了istringstream和ostringstream的用法。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
private:
    void serialize(TreeNode*root,ostringstream& out)
    {
        out<<root->val<<' ';
        if(root->left) serialize(root->left,out);
        else out<<"# ";
        if(root->right) serialize(root->right,out);
        else out<<"# ";
        return;
    }
    TreeNode* deserialize(istringstream& in)
    {
        string val;
        in>>val;
        if(val=="#") return NULL;
        TreeNode* cur=new TreeNode(stoi(val));
        cur->left=deserialize(in);
        cur->right=deserialize(in);
        return cur;
    }
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root) return "";
        ostringstream out;
        serialize(root,out);
        return out.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data=="") return NULL;
        istringstream in(data);
        return deserialize(in);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

30. Substring with Concatenation of All Words
题意:给出一个字符串s,给出一些单词。求所有的index,满足s[idnex……]正好是单词列表中所有单词的排列组合串,且中间没有多余字符。
思路:对以0<=i

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int i,j;
        int n=s.length(),total=words.size();
        vector<int> ans;
        if(!n || !total) return ans;
        unordered_map<string,int> dic;
        for(i=0;i<total;i++) dic[words[i]]++;
        int len=words[0].length();
        for(i=0;i<len;i++)
        {
            unordered_map<string,int> cnt;
            int left=i;
            int count=0;
            for(j=i;j<=n-len;j+=len)
            {
                string tmp=s.substr(j,len);
                if(dic.find(tmp)==dic.end())
                {
                   cnt.clear();
                   left=j+len;
                   count=0;
                   continue;
                }
                cnt[tmp]+=1;count++;
                while((left<=j) && (cnt[tmp]>dic[tmp]))
                {
                    cnt[s.substr(left,len)]--;count--;
                    left+=len;
                }
                if(count==total) ans.push_back(left);
            }
        }
        return ans;
        
    }
};

Shortest Palindrome

leetcode的一道题
题意:给出一个字符串,只能在首部加上字符使其成为回文串,求所加字符数最少的方案。
这题以前搞acm的时候碰到过,如果是以前,就直接上KMP了。但是前面有道题是用manacher算法求字符串的最长回文子串。突然发现这题也可以用manacher来做,时间复杂度也是O(n)。
manacher确实是一种思路巧妙,代码简短的算法。
https://leetcode.com/problems/shortest-palindrome/

char str[1000010],ans[1000010];
int r[1000010];
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
char* shortestPalindrome(char* s) {
    int i,j,k,cnt;
    int len=strlen(s);
    if(len<=1)  return s;
    r[0]=0;
    str[0]='?';
    for(i=0;i<=len;i++)
    {
        str[(i<<1)+1]=s[i];
        str[(i<<1)+2]='*';
    }
    str[len<<1]='#';str[(len<<1)+1]='\0';
    i=1;j=0;
    while(i<=(len<<1))
    {
        while(str[i-j-1]==str[i+j+1]) j++;
        r[i]=j;
        for(k=1;k<=j;k++)
            if(r[i]-k!=r[i-k]) r[i+k]=min(r[i]-k,r[i-k]);
            else break;
        j=max(0,r[i]-k);
        i+=k;
    }
    for(i=(len<<1);i>=1;i--)
    {
        if(i-r[i]==1) break;
    }
    i=(i+r[i])/2;
    cnt=0;
    for(j=len-1;j>=i+1;j--) ans[cnt++]=s[j];
    for(j=0;j<=len-1;j++) ans[cnt++]=s[j];
    ans[cnt++]='\0';
    return ans;
}

pmfs+nvm与ext4+pmbd+nvm性能比较

这周开始做nvm相关的一个性能测试。nvm是非易失性内存,是一类比较新的存储硬件的总称,其读写速率比DRAM慢,比ssd快。之前看了一些相关的论文,nvm的应用大概分这么几种:

1.用来完全替代DRAM作为主存.(并用DRAM做cache)

2.和DRAM一起构成一个混合的内存模型

3.作为块设备。

4.作为其他块设备的cache(如ssd)

这里把nvm作为块设备。

实验用dram模拟nvm,试验机总共8g内存,前4g仍作为dram使用,后4g作为nvm。

现在存在两种方案来使用它。

一是用新的filesystem来管理,这里使用pmfs这个文件系统.

pmfs项目的github:https://github.com/linux-pmfs/pmfs

二是在现有filesystem的基础上加上一层转换层,使得能够用现有的filesystem,如ext4来管理nvm。

这个中间层在这里是pmbd:https://github.com/linux-pmbd/pmbd

这两种方案下的体系结构图大概如下:

pmbd是作为内核模块启动的,可以按照README进行

pmfs对内核改动比较大,因此github给出的是修改后的整个内核。需要下载后重新编译内核。

注意不要下载zip文件然后解压,会导致文件不全。请用git clone到试验机。

对内核进行编译,请参照:http://zjuedward.blog.51cto.com/1445231/461376

make menuconfig时记得选上File sytems->Miscellaneous filesystems->Persistent and Protected PM file system support

这里声明一点:由于pmfs是基于内核3.11,而pmbd只能运行在3.2.1的内核上,所以我们只能在不同的内核下进行测验,但是内核版本的不同对实验结果影响不大,内存那块的差异非常小。

 
实验主要测试io带宽。使用的benchmark是fio-2.1.10
由于需要多次测试取平均值,并且生成的结果需要以特定格式导入到excel中生成图表,所以我写了个脚本来进行测试(只列举了针对pmbd的测试,pmfs的测试时类似的),如下:

import commands
io_type=["read","write","randread","randwrite"];
blocksize=["1KB","2KB","4KB","8KB"];
job_num=["1","2","4","8"];
result='type-job';
for num in range(1,4):
	for i in blocksize:
		result+="	"+i;
	result+="\n";
	for iotype in io_type:
		for job in job_num:
			result+=iotype+'-'+job;
			for bs in blocksize:
#				commands.getstatusoutput('touch /mnt/1.txt');
				cmd='fio -filename=/dev/pma -direct=1 -iodepth 1 -thread -rw='+iotype+' -ioengine=psync -bs='+bs+' -size=8G -numjobs='+job+' -runtime=30 -group_reporting -name=mytest';
				print str(iotype)+"  "+str(bs)+"  "+str(job)+"  begin\n";
				(status,output)=commands.getstatusoutput(cmd);
				word=output.split();
				bw_val=0.0;
				for i in word:
					if i.startswith('bw='):
						i=i.lstrip('bw=');
						if i.endswith('KB/s,'):
							bw_val=float(i.rstrip('KB/s,'))/1024.0;
							bw_val=float('%0.3f' %bw_val);
							bw_val=str(bw_val);
						else:bw_val=i.rstrip('MB/s,');
						break;
				result+="	"+str(bw_val);
				print str(iotype)+"  "+str(bs)+"  "+str(job)+"\t"+str(bw_val)+"  end\n";
				tmp_result=str(iotype)+"  "+str(bs)+"  "+str(job)+"\t"+str(bw_val)+"  end\n";
				ret1="echo '"+tmp_result+"' >>tmp_fio_log.txt";
				commands.getstatusoutput(ret1);
			result+="\n";
	ret="echo '"+result+"' >>resultlog.txt";
	commands.getstatusoutput(ret);
	result='type-job';

最终得到如下性能:


注意两个图纵坐标的不同,初步的比较可知使用pmfs对nvm进行管理的性能更好。
job=4比job=8性能更好是因为实验机为四核,用8个线程去跑反而增加切换的开销。
顺序读比随机读性能稍好可能是因为预取和cache的原因,我们的nvm实际上是DRAM模拟的,所以cache对其是有影响的
顺序写比随机写性能稍好也可能是cache的原因。
目前进行的是没有虚拟化的情况下的性能比较,后期还要加入kvm,在kvm下进行性能测试,io栈大致如下:

bestcoder#64 div1

还是做出两题。。
1001(hdu5586) Sum
题意:给出n个数,给出函数f(x),现在可以对连续的一段区间的数使用f(x)转换,也可以不用。问最后这n个数之和最大是多少.
简单dp。可以先对这n个数都使用f(x)得到新的数组b(设原数组为a),b[]-a[],得到数组c。对c[]求最大子串和,这个最大子串和就是对某一段数施加f(x)之后可以达到的最大增益。如果是负的,那么显然不应该进行f(x)的转换。a数组的和加上这个增益就是答案。

#include<stdio.h>
#include<string.h>
int n;
int a[100010],dp[100010];
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        int sum=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
            a[i]=(1890*a[i]+143)%10007-a[i];
        }
        dp[1]=a[1];
        int ans=dp[1];
        for(i=2;i<=n;i++)
        {
            dp[i]=(dp[i-1]>0?dp[i-1]+a[i]:a[i]);
            if(dp[i]>ans) ans=dp[i];
        }
        if(ans>0) sum+=ans;
        printf("%d\n",sum);
    }


    return 0;
}

1002(hdu5587) Array
题意:第一次操作,数列为{1}。总共做一百次操作,每次都是在原先数列末尾增加一个0,并复制原数列增加在0后面。再将新增加的数全部加1.
给出一系列的m,表示求前m个数之和。m<=10^16
第一次:1
第二次:1 1 2
第三次:1 1 2 1 2 2 3
……
解法:因为题意是递推的,比较容易想到用递归去解。对于给定的m,我们可以二分求出最少几次操作可以使数列长度达到m,设为num.设num次操作得到的数列长度为c[num],数列和为s[num].那么前c[num-1]个数的和就是s[num-1],剩余x-c[num-1]个数可以递归解决(设剩余tmp个数,那么转化为求前(tmp-1)个数的和+tmp-1+1)

#include<stdio.h>
#include<string.h>
typedef long long ll;
int t;
ll m;
ll c[110],s[110];
int bs(ll x)
{
    int l=1,r=63;
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(c[m]==x) return m;
        if(x>c[m]) l=m+1;
        else r=m-1;
    }
    return l;
}
ll f(ll x)
{
    int num=bs(x);
    //printf("num:%d\n",num);
    if(num==1) return 1;
    if(c[num]==x) return s[num];
    ll tmp=x-c[num-1];
    if(tmp==1) return s[num-1]+1;
    return s[num-1]+1+f(tmp-1)+tmp-1;
}
int main()
{
    int i,j;
    c[1]=1;
    for(i=2;i<=100;i++) c[i]=2*c[i-1]+1;
    s[1]=1;
    for(i=2;i<=100;i++) s[i]=2*s[i-1]+1+c[i-1];
    //for(i=1;i<=100;i++) printf("c[%d]:%I64d\n",i,c[i]);
    //printf("\n");
    //for(i=1;i<=100;i++) printf("s[%d]:%I64d\n",i,s[i]);
    //printf("\n");
    scanf("%d",&t);
    while(t–)
    {
        scanf("%I64d",&m);
        ll ans=f(m);
        printf("%I64d\n",ans);


    }
    return 0;
}

bestcoder#63 div1

第一次做div1,解出两道题,能做的也只有两道。但是第一题罚时有点厉害,一直不太相信需要高精度(因为output里写了integer。。)
1001(hdu5568) sequence2
一个整数序列有多少种长度为k的不同的递增子序列,两个子序列只要有一个元素对应位置不同就算不同。
如1 2 2有两个长度为2的不同子序列1 2和1 2(这两个2位置不同)
简单的dp题。dp[i][j]表示前i个数组成的序列中有多少个长度为j的不同子序列。
dp[i][j]=sigma(dp[t][j-1]),其中a[i]>a[t]。

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXN 9999
#define MAXSIZE 1000
#define DLEN 4
using namespace std;
class BigNum;
istream& operator>>(istream&,  BigNum&);
ostream& operator<<(ostream&,  BigNum&);
class BigNum
{
public:
	int a[MAXSIZE];
	int len;
public:
	BigNum(){len = 1;memset(a,0,sizeof(a));}
	BigNum(const int);
	friend ostream& operator<<(ostream&,  BigNum&);
	BigNum operator+(const BigNum &) const;
};
ostream& operator<<(ostream& out,  BigNum& b)
{
	int i;
	cout << b.a[b.len - 1];
	for(i = b.len - 2 ; i >= 0 ; i--)
	{
		cout.width(DLEN);
		cout.fill('0');
		cout << b.a[i];
	}
	return out;
}
BigNum::BigNum(const int b)
{
	int c,d = b;
	len = 0;
	memset(a,0,sizeof(a));
	while(d > MAXN)
	{
		c = d - (d / (MAXN + 1)) * (MAXN + 1);
		d = d / (MAXN + 1);  a[len++] = c;
	}
	a[len++] = d;
}
BigNum BigNum::operator+(const BigNum & T) const
{
	BigNum t(*this);
	int i,big;
	big = T.len > len ? T.len : len;
	for(i = 0 ; i < big ; i++)
	{
		t.a[i] +=T.a[i];
		if(t.a[i] > MAXN)
		{
			t.a[i + 1]++;
			t.a[i] -=MAXN+1;
		}
	}
	if(t.a[big] != 0) t.len = big + 1;
	else t.len = big;
	return t;
}

int n,k;
BigNum dp[110][110];
int a[110];
int main()
{
    int i,j,t;
    while(~scanf("%d%d",&n,&k))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++) dp[i][1]=1;
        for(j=2;j<=k;j++)
            for(i=1;i<=n;i++)
                for(t=1;t<=i-1;t++)
                    if(a[i]>a[t]) dp[i][j]=dp[i][j]+dp[t][j-1];
        BigNum ans=0;
        for(i=1;i<=n;i++) ans=ans+dp[i][k];
        cout<<ans<<endl;


    }
    return 0;
}

1002(hdu5569) matrix
也是比较简单的dp题,转移方程容易想到,具体见代码。

#include<stdio.h>
#include<string.h>
typedef long long ll;
int n,m;
int a[1010][1010];
int dp[1010][1010];
const int inf=0x3f3f3f3f;
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m) return 1;
    return 0;

}
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]);
                dp[i][j]=0;
            }
        dp[1][2]=a[1][1]*a[1][2];
        dp[2][1]=a[1][1]*a[2][1];

        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                if((i==1) && (j==2)) continue;
                if((i==2) && (j==1)) continue;
                if((i+j)%2==0) continue;
                int tmp1=-1,tmp2=-1,tmp=0;
                if(judge(i,j-1))
                {
                    tmp1=a[i][j]*a[i][j-1];
                    tmp=inf;
                    if(judge(i,j-2)) tmp=dp[i][j-2];
                    if(judge(i-1,j-1)) tmp=min(tmp,dp[i-1][j-1]);
                    tmp1+=tmp;
                }
                if(judge(i-1,j))
                {
                    tmp2=a[i][j]*a[i-1][j];
                    tmp=inf;
                    if(judge(i-2,j)) tmp=dp[i-2][j];
                    if(judge(i-1,j-1)) tmp=min(tmp,dp[i-1][j-1]);
                    tmp2+=tmp;
                }
                if((tmp1==-1) || (tmp2==-1)) dp[i][j]=max(tmp1,tmp2);
                else dp[i][j]=min(tmp1,tmp2);
            }
        printf("%d\n",dp[n][m]);

    }


    return 0;
}

1003 balls
做不出来,看了题解还没完全清楚。。

bestcoder#61 div2

1001(hdu5522) Numbers
签到题



#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[110];
bool judge(int x,int y,int z)
{
    if((x+y==z) || (x+z==y) || (y+z==x)) return 1;
    return 0;
}
int main()
{
    int i,j,k;
    int t;
    int n;
    while(~scanf("%d",&n))
    {
        bool flag=0;
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(i=1;i<=n;i++)
        {
            for(j=i+1;j<=n;j++)
            {
                for(k=j+1;k<=n;k++)
                {
                    if(judge(a[i],a[j],a[k])) {flag=1;break;}
                }
                if(flag) break;
            }
            if(flag) break;
        }
        printf("%s\n",flag?"YES":"NO");
    }


    return 0;
}

1002(hdu5523) Game
简单题,考虑s和t的位置,分情况讨论即可



#include<stdio.h>
#include<string.h>
int main()
{
    int i,j;
    int n,s,t;
    while(~scanf("%d%d%d",&n,&s,&t))
    {
        if((s==t) && n>1){printf("-1\n");continue;}
        if(((s==1) && (t==n))||((s==n) && (t==1))){printf("0\n");continue;}
        if(((s==1)||(s==n)) && t!=1 && t!=n)
        {
            printf("1\n");continue;
        }
        if(((t==1)||(t==n)) && s!=1 && s!=n)
        {
            if((s-t==1) || (t-s==1)) {printf("1\n");continue;}
            printf("2\n");continue;
        }
        if((s-t==1) || (t-s==1))
            printf("1\n");
        else
            printf("2\n");
    }


    return 0;
}

1003(hdu5524) Subtrees
我看了下别人的代码,似乎有很简单的做法。。但是我还没研究。我说下自己的解法
问题是问n个结点的完全二叉树有多少种结点个数不同的子树。n是long long 范围
可以递归来做,由于是完全二叉树,所以以根结点的两个儿子为根的两棵子树一定有一棵是满二叉树,而满二叉树有log2(结点总数)种结点数不同的子树,对于另一棵子树,我们递归求解。
这样。递归次数是树高h(=log2(n)),每次递归都要往结果set中加log2(n)个数据,set加一次数据复杂度log2级别,由于set中数据总数很少,所以看成常数。所以复杂度大概O(lg(n)^2)
易错点:算树高h的时候,浮点函数log()精度不够,要用二分去求树高。。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<set>
using namespace std;
typedef long long ll;
set<ll> num;
ll pow2(ll k)
{
    ll ans=1,p=2;
    while(k)
    {
        if(k%2)
        {
            k--;
            ans*=p;
            continue;
        }
        else
        {
            k/=2;
            p*=p;
        }
    }
    return ans;
}
ll bs(ll n)
{
    if(!n) return 0;
    ll l=0,r=63;
    while(l<=r)
    {
        ll m=l+((r-l)>>1);
        if((pow2(m)-1>=n) && (pow2(m-1)<n)) return m;
        if(pow2(m)-1<n) l=m+1;
        else r=m-1;
    }
    return l;
}
void f(ll n)
{
    ll i;
    if(!n) return;
    if(n==1) {num.insert(1);return;}
    ll l,r;
    ll h=bs(n);
    ll non_ye=pow2(h-1)-1;
    ll ye=n-non_ye;
    ll xh=pow2(h-2);
    num.insert(n);
    if(ye<=xh)
    {
        l=(non_ye-1)/2+ye;
        r=(non_ye-1)/2;
        ll hr=bs(r);
        for(i=1;i<=hr;i++)
            num.insert(pow2(i)-1);
        f(l);
    }
    else
    {
        l=(non_ye-1)/2+xh;
        r=n-1-l;
        ll hl=bs(l);
        for(i=1;i<=hl;i++)
            num.insert(pow2(i)-1);
        f(r);

    }
    return;
}
int main()
{
    int i,j;
    ll n;
    while(~scanf("%I64d",&n))
    {
        if(!num.empty()) num.clear();
        f(n);
        printf("%I64d\n",(ll)num.size());
    }


    return 0;
}

1004(hdu5525) Product
不知道为什么TLE,按道理不应该啊。。看了下官方解答,基本思路相同,只是我没用费马小定理。有时间再回来改~
待修改

#include<stdio.h>
#include<string.h>
typedef long long ll;
const ll N=100010;
const ll mod=1000000007LL;
ll pr[N],p[N/10];
ll pi[N][20],ki[N][20];
ll cnt,lp;
void gp()
{
	for(int i=2;i<N;i++)
	{
		if(!pr[i])
			p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0)break;
		}
	}
	return;
}
void fenjie(ll n)
{
	cnt=0;
	ll num=n;
	memset(ki[num],0,sizeof(ki[num]));
	while(n!=1)
	{
		ll t=pr[n];
        pi[num][++cnt]=t;
        ki[num][cnt]=0;
        while(n%t==0)
        {
            n/=t;
            ki[num][cnt]++;
        }
	}
	pi[num][0]=cnt;
	return;
}
ll ret;
ll pow(ll p,ll k)
{
    ll ans=1;
    while(k)
    {
        if(k%2) {k--;ans=(ans*p)%mod;}
        k/=2;
        p=(p*p)%mod;
    }
    return ans;
}
ll n,a[100000+10],b[100000+10];
ll zyz[20],cc[20];
void scan(ll &num)    //对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}
int main()
{
    ll i,j;
    gp();
    for(i=2;i<=100000;i++) fenjie(i);
    /*debug
    for(i=2;i<=100000;i++)
    {
        printf("%d的约数为:",i);
        for(j=1;j<=pi[i][0];j++) printf("%d ",pi[i][j]);
        printf("\n");
        printf("%d的次数为:",i);
        for(j=1;j<=pi[i][0];j++) printf("%d ",ki[i][j]);
        printf("\n");
    }
    */
    while(~scanf("%I64d",&n))
    {
        for(i=1;i<=n;i++) scan(a[i]);
        memset(b,0,sizeof(ll)*(n+2));
        ret=1;
        for(i=2;i<=n;i++)
        {
            for(j=1;j<=pi[i][0];j++)
                b[pi[i][j]]+=ki[i][j]*a[i];
        }
        ll cn=0;
        for(i=2;i<=n;i++)
        {
            if(!b[i]) continue;
            zyz[++cn]=i;
            cc[cn]=b[i];
        }
        for(i=1;i<=cn;i++)
        {
            ll tmp=pow(zyz[i],cc[i]*(cc[i]+1)/2);
            for(j=1;j<=cn;j++)
            {
                if(i==j) continue;
                tmp=pow(tmp,1+cc[j]);
            }
            ret=(ret*tmp)%mod;
        }
        printf("%I64d\n",ret);



    }
    return 0;
}

bestcoder#59 div2

1001 SDOI
简单模拟

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m;
typedef struct Node{
    char name[30];
    int sex;
    double s1,s2;
}Node;
Node node[110];
bool cmp(Node a,Node b)
{
    return a.s1>b.s1;
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        char s[10];
        int s1,s2;
        bool flag=0;
        double max1=0,max2=0;
        for(i=1;i<=n;i++)
        {
            scanf("%s%s%lf%lf",node[i].name,s,&node[i].s1,&node[i].s2);
            if(node[i].s1>max1) max1=node[i].s1;
            if(node[i].s2>max2) max2=node[i].s2;
            if(!strcmp(s,"male")) node[i].sex=1;
            else {node[i].sex=0;flag=1;}
        }
        for(i=1;i<=n;i++)
        {
            node[i].s1=node[i].s1*(300*1.0/max1)*0.3+node[i].s2*(300*1.0/max2)*0.7;
        }
        sort(node+1,node+1+n,cmp);
        printf("The member list of Shandong team is as follows:\n");
        if(!flag)
        {
            for(i=1;i<=m;i++)
                printf("%s\n",node[i].name);
            continue;
        }
        int male=0,total=0;
        for(i=1;i<=n;i++)
        {
            int sex=node[i].sex;
            if(total<m)
            {
                if(sex)
                {
                    if(male<m-1)
                    {
                        printf("%s\n",node[i].name);
                        male++;
                        total++;
                    }
                }
                else
                {
                        printf("%s\n",node[i].name);
                        total++;
                }
            }
        }
    }
    return 0;
}

1002 Reorder the Books
题意:给出1-n的一个乱序排列,每次操作只能抽出一个放到开头,请问最少操作几次可以使序列有序。
这题想通了很简单。
我们可以得到以下两个简单结论:
1.抽出数字x放到开头不会改变数字a和数字b的相对顺序(a、b不同于x)
2.当抽出数字x放到开头时显然以后一定要把比x小的数字1,2,3,……,x-1抽出放到开头一次(基于第一点,他们的相对顺序是错误的,但是移动其他元素不能改变他们的相对顺序)。
那么显然我们希望这个x越小越好。
由于从最大数字n为结尾的相对顺序正确的几个数不需要移动,所以x其实就是从n开始往回看的第一个顺序错误的数。
考虑以下情况:3,1,4,2,5
由于3,4,5三个数字相对顺序是正确的,所以x就是2,我们第一次将2放到开头,第二次将1放到开头就行。(显然上面的第二点指出比2小的数字一定至少移动一次,然后,我们可以发现,它们事实上只需要移动一次就可以使未被移动的那些数字连续且有序)
我发现有些想法大脑里过一遍是是快速而跳跃的,但是要通俗易懂地写出来且在逻辑上很严格会很麻烦。。。

#include<stdio.h>
#include<string.h>
int a[30],pos[30];
int main()
{
    int i,j;
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            pos[a[i]]=i;
        }
        int ans=1;
        for(i=n;i>=2;i--)
        {
            if(pos[i]>pos[i-1]) ans++;
            else break;

        }
        printf("%d\n",n-ans);
    }

    return 0;
}

1003 The Highest Mark
这题比赛时没做出来,特么为什么我现在这么菜!(好吧,其实以前也很菜)
题意:n个题目原始分数ai,每分钟减少bi(从比赛开始算起),完成需要ci,问t分钟最多可以得到几分(从中选择一些题目做)
n<=1000,t<=3000
如果没有bi这个量,那么这题就是一个0/1背包。
假设现在顺序已经确定,那么

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef struct Node{
    int a,b,c;
}Node;
Node node[1010];
int n,m;
int t;
bool cmp(Node x,Node y)
{
    return (ll)x.b*(ll)y.c>(ll)y.b*(ll)x.c;
}
inline int max(int a,int b){return a>b?a:b;}
int dp[3010];
int main()
{
    int i,j,T;
    scanf("%d",&t);
    while(t–)
    {
        scanf("%d%d",&n,&T);
        for(i=1;i<=n;i++)
            scanf("%d%d%d",&node[i].a,&node[i].b,&node[i].c);
        sort(node+1,node+1+n,cmp);
        //for(i=1;i<=n;i++)
            //printf("%d  %d  %d\n",node[i].a,node[i].b,node[i].c);
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
            for(j=T;j>=0;j–)
            {
                if(node[i].c>j) continue;
                dp[j]=max(dp[j],dp[j-node[i].c]+node[i].a-node[i].b*j);
            }
        int ans=0;
        for(j=1;j<=T;j++) ans=max(ans,dp[j]);
        printf("%d\n",ans);

    }
    return 0;
}

1004 Candy Game