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 && (*s==*p || *p=='.'))
            return isMatch(s+1,p+1);
        return 0;
    }
    else
    {
        while(*s!=0 && (*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]<nums[n-1]) return nums[0];
    int l=0,r=n-1;
    while((l+1<n) && nums[l]==nums[l+1]) l++;
    while((r-1>=0) && nums[r]==nums[r-1]) r--;
    while(l<r && (nums[l]==nums[r])) r--;
    if(l==r) return nums[l];
    while(l<=r)
    {
        int m=l+(r-l)/2;
        if(nums[m]>=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->left;
        next=start->right;
        if(!now) break;
        while(1)
        {
            if(!is_right)
            {
                now->next=next;
                now=next;
                root=root->next;
                if(!root) break;
                next=root->left;
                is_right=!is_right;
            }
            else
            {
                now->next=next;
                now=next;
                next=root->right;
                is_right=!is_right;
            }
        }
        start=start->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->label=p->label;
            q->next=p->next;
            q->random=p->random;
            p->next=q;
            p=p->next->next;
        }
        p=head;
        while(p)
        {
            p=p->next;
            if(p->random)
                p->random=p->random->next;
            p=p->next;
        }
        p=head;
        q=p->next;
        ansp=q;
        while(p->next->next)
        {
            p->next=p->next->next;
            q->next=q->next->next;
            p=p->next;
            q=q->next;
        }
        p->next=NULL;
        return ansp;
}

Maximum Gap
基数排序

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        vector<int> a[10];
        int i,j,k,t;
        int n=nums.size();
        if(n<=1) return 0;
        if(n==2) return abs(nums[0]-nums[1]);
        int len=0,cnt;
        for(i=0;i<n;i++)
        {
            int tmp=nums[i];
            cnt=0;
            while(tmp) tmp/=10,cnt++;
            if(cnt>len) len=cnt;
        }
        for(i=1;i<=len;i++)
        {
            for(j=0;j<=9;j++) if(!a[j].empty()) a[j].clear();
            for(j=0;j<n;j++)
            {
                int tmp=nums[j],xh=1;
                for(k=1;k<=i;k++) xh*=10;
                tmp=tmp%xh/(xh/10);
                a[tmp].push_back(nums[j]);
            }
            int cc=0;
            for(j=0;j<=9;j++)
                for(t=0;t<a[j].size();t++) nums[cc++]=a[j][t];
        }
        int ans=0;
        for(i=1;i<n;i++) if(abs(nums[i]-nums[i-1])>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]]>0) cnt++;
        need[s[end]]--;
    }
    end++;
    return;
}
void del(char*s)
{
    if(is[s[begin]])
    {
        if(need[s[begin]]>=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<lent) return "";
    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<=lens-lent && end<=lens)
    {
        if(cnt>=lent)
        {
            del(s);
            if(cnt>=lent && end-begin<ans)
            {
                ans=end-begin;
                ansbegin=begin;ansend=end;
            }
            continue;
        }
        add(s);
        if(cnt>=lent && end-begin<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<=1) return 0;
    if(len==2) return ((s[0]=='(') && (s[1]==')'))?2:0;
    dp[0]=0;dp[1]=(((s[0]=='(') && (s[1]==')'))?2:0);
    int ans=dp[1];
    for(i=2;i<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<len;i++) if(dp[i]>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>b?a:b;}
int min(int a,int b){return a<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<=n;i++)
        dp[i]=0;
    dp[1]=-prices[0];
    for(i=2;i<=n;i++)
    {
        for(j=min(i,k);j>=1;j--)
        {
            int ans=0;
            int tmp=prices[i-1];
            if(j&1) tmp=-tmp;
            if(i-1>=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<=min(k,n);i++) if(dp[i]>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;
        
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>