leetcode 刷题篇_f[0][0]=1; for(int i=1;i<=h;i++) { for(int s1=0;s1

1.https://leetcode-cn.com/problems/01-matrix/

第一题0-1矩阵

解法1：BFS

解法2：DP。dp的做法思路较巧妙，关键点在于二次遍历。

2.https://leetcode-cn.com/problems/132-pattern

解法：最小栈。

以2,4,2,3,5为例。

从后往前遍历，构建最小栈。

5入栈

3入栈

2入栈

然后遇到4，2出栈，3出栈。3即是4右边小于3的最大值。

再遇到2，比3小得到最后结果。遍历结束。

3.https://leetcode-cn.com/problems/2-keys-keyboard/submissions/

动态规划。递推关系式： if(i%j==0) dp[i]=min(dp[i],dp[j]+i/j)。

4.https://leetcode-cn.com/problems/3sum-closest/

数之和问题的变形。

5.https://leetcode-cn.com/problems/3sum-with-multiplicity

三数之和问题的变形。

6.https://leetcode-cn.com/problems/4sum

三数之和问题的变形

7.https://leetcode-cn.com/problems/4sum-ii/

四数之和问题（II)

暴力解法的时间复杂度是四次方。

通过排序可一定程度的优化，复杂度不变。

最优解法是采用哈希表，把四重循环拆分成两个二重循环，时间复杂度仅二次方。

8.https://leetcode-cn.com/problems/accounts-merge/

合并账户和朋友圈有相似之处。

有相同邮箱的结点相连，把它们合并为一个结点即可。这样转化以后就成了朋友圈问题。

有三种解法：bfs，dfs和并查集。

9.https://leetcode-cn.com/problems/zigzag-conversion

Z字变换，找规律的问题。

10.https://leetcode.com/problems/container-with-most-water/

盛水最多的容器。贪心策略，双指针法。（一开始两根指针分别指向数组的头和尾，基于贪心策略去移动这两根指针）。这两根指针哪根指针指向的数小，便移动哪根指针。

11.https://leetcode-cn.com/problems/integer-to-roman/

输入是整数，输出是该数的罗马数字表示。

很简单，只需要把该数从大到小一直减即可，减的过程中加上被减数的罗马表示。

12.https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

给定一个数字串，输出是可能的英文字母组合。数字和字母之间的对应关系按照电话上的来。

这题不难，但写出来还是有点耗时。

递归写法即可。

13.https://leetcode-cn.com/problems/divide-two-integers/

用位运算和减法来做除法。

如果只用减法来模拟除法的话会超时。

14.https://leetcode-cn.com/problems/validate-binary-search-tree/

易错解法：

 bool isValidBST(TreeNode* root) 
    {
     if(root==NULL)   return true;
     if(root->left)
     {
         if(root->left->val>=root->val) return false;
     }
     if(root->right)
     {
         if(root->right->val<=root->val) return false;
     } 
    return isValidBST(root->left)&&isValidBST(root->right);
    }

分析这个例子即可发现上述代码的错误之处[10,5,15,null,null,6,20]。

正确的解法应该是中序遍历，若是递增序列则返回true，反之返回false。

15.https://leetcode-cn.com/problems/decode-ways/

动态规划。

16.https://leetcode-cn.com/problems/divisor-game/

动态规划解法：

  bool divisorGame(int N) 
    {
     vector<int>dp(N,0);
     dp[0]=0;
     for(int i=1;i<N;i++)
     {  
         for(int j=0;j<i;j++)
         {
             if(dp[j]==0&&(i+1)%(i-j)==0)
             {dp[i]=1;
              break;
             }
         }
         
    }
        return dp[N-1];
    }

 更简单的解法是判断N是奇数还是偶数。

分析如下：

假设当n<=N时满足奇数输偶数赢。

当n=N+1时，若N是奇数，则n是偶数。只要第一个数选择1，就赢了。

当n=N+1时，若N是偶数，则n是奇数。爱丽丝第一个数只能选择奇数，那么给鲍勃的数就是偶数。则爱丽丝输了，鲍勃赢。

17.https://leetcode-cn.com/problems/fraction-to-recurring-decimal/

本题的关键点

1.考虑正负。要把int类型转换为long long 类型。

2.找到循环的起点。

例 0.142857 又得到1 则开始循环了。

因此只要找到重复的数字就可以。

18.https://leetcode-cn.com/problems/contains-duplicate-iii/submissions/

滑动窗口。

这题是用set来维护这个滑动窗口。可以使复杂度降到。

19.https://leetcode-cn.com/problems/additive-number/submissions/

深搜。找到一条合法路径便返回。

20.https://leetcode-cn.com/problems/remove-k-digits/comments/

这题深搜会超时。19题用深搜可以剪枝，而20题无法剪枝要比较所有的情况，所以会超时。

深搜代码：

  string removeKdigits(string num,int k)
{
	string ans=removeKdigits_help(num,k);
	ans=nofrontzero(ans);
    if(ans=="") return "0";
	return ans;
}
string removeKdigits_help(string num, int k) 
{
    
	int len=num.size();
    if(len==k) return "";
    if(k==0) return num;
    string s1=removeKdigits_help(num.substr(1,len-1),k-1);
	string s2;
    
	s2=num[0]+removeKdigits_help(num.substr(1,len-1),k);
	
    
    if(comparestring(s1,s2)) return s2;
    return s1;
}
string nofrontzero(string s)
{
    int len=s.size();
    int i;
    for(i=0;i<len;i++)
    {
    if(s[i]!='0') break;
    }
    s=s.substr(i,len-i);
	return s;
}
bool comparestring(string a,string b)
{
     a=nofrontzero(a);
	 b=nofrontzero(b);
	 if(a.size()<b.size())  return false;
     if(a.size()>b.size())  return true;
     if(a.size()==b.size()) 
     {
         int len=a.size();
         for(int i=0;i<len;i++)
         {
          if(a[i]<b[i]) return false;
          if(a[i]>b[i]) return true;
         }
    
     }
       return true; 
}

本题用贪心法求解：

每一步删除一个数字，执行k步就得到最终结果。

21.https://leetcode-cn.com/problems/integer-replacement/

本题用动态规划做会超时。因为动态规划做了很多无用计算。相同的思想改成递归代码即可通过。

若n为偶数，则n除以2即可。

若n为奇数，则考虑n到底是应该+1，还是-1。

此时n+1和n-1是相邻的偶数，则n+1和n-1除以2以后必然有一个是偶数，一个是奇数。

相邻的奇数和偶数之间必然有奇数的步数不小于偶数的步数。

因此选择+1或者-1后除以2仍然是偶数的那个。

22.https://leetcode-cn.com/problems/water-and-jug-problem/

水壶问题。这一题本质是个数学问题。

z<=x+y,且z是x，y的最大公约数的倍数，或者z=0满足题意。

23.https://leetcode-cn.com/problems/circular-array-loop/

环形数据循环问题。

先贴自己的代码：

bool circularArrayLoop(vector<int>& nums) 
    {
      int len=nums.size();
      vector<int>visited(len,0);
      for(int i=0;i<len;i++)
      {     int start=i;
            vector<int>s;
            bool positive=nums[start]>0;
            
          while(1)
          {
             auto iter=find(s.begin(),s.end(),start);
             if(iter==s.end()) 
             {
                 
                 s.push_back(start);
             }
             else if(s.end()-iter==1) break;
             else return true;
             if((positive&&nums[start]>0)||(!positive&&nums[start]<0)&&visited[start]==0)
             {
             visited[start]=1; 
             start+=nums[start] ;
             
             while(start>=len)
             start=start-len;
             while(start<0)
             start=start+len;
             }
             else break;
             
            
          }
      }
      return false;
    }

代码的思路其实已经和答案基本上是一样的。但是这段代码仍然超时了。

答案没有用vector来保存每次走的路径，而是用visited 数组+color变量来记录每次走的路径。

用时差别在find函数上。

24.https://leetcode-cn.com/problems/can-i-win

我能赢吗？这一题是典型的递归+map记录中间结果的例子。

先贴自己的代码：

 bool canIWin(int maxChoosableInteger, int desiredTotal) 
    {
      vector<int>v;
        for(int i=1;i<=maxChoosableInteger;i++)
        {
            v.push_back(i);
        }
        map<vector<int>,bool>m;
        return dfs(v,desiredTotal,m);
    }
    bool dfs(vector<int>v,int desiredTotal,map<vector<int>,bool>&m)
    {
        vector<int>vec=v;
        sort(vec.begin(),vec.end());
        if(m.count(vec)) return m[vec];
        if(desiredTotal<0) return false;
        if(desiredTotal==0) return true;
        int len=v.size()   ;
        for(int i=len-1;i>=0;i--)
        {
            int temp=v[i];
            auto iter=find(v.begin(),v.end(),temp);
            iter=v.erase(iter);
            if(temp>=desiredTotal||!dfs(v,desiredTotal-temp,m)) 
            {  
             m[vec]=true;
            return true;
            }
            v.insert(iter,temp);
        }
        m[vec]=false;
        return false;
    }

使用dfs+map记录中间结果仍然超时了。

可以优化的地方：

对vec的排序可以略掉。用一个整数来表示这个vec。

优化的代码如下：

bool canIWin(int maxChoosableInteger, int desiredTotal) 
    {
       if (maxChoosableInteger >= desiredTotal) return true;
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 == desiredTotal) 
            return maxChoosableInteger%2;
 
        vector<int>v;
        for(int i=1;i<=maxChoosableInteger;i++)
        {
            v.push_back(i);
        }
        
        map<int,bool>m;
        return dfs(v,desiredTotal,m);
    }
    bool dfs(vector<int>v,int desiredTotal,map<int,bool>&m)
    {   int vec=0;
        for(auto it:v)
          vec+=1<<(it-1);  
        if(m.count(vec)) 
          return m[vec];
        if(desiredTotal<0) return false;
        if(desiredTotal==0) return true;
        int len=v.size()   ;
        for(int i=len-1;i>=0;i--)
        {
            int temp=v[i];
            auto iter=find(v.begin(),v.end(),temp);
            iter=v.erase(iter);
            if(temp>=desiredTotal||!dfs(v,desiredTotal-temp,m)) 
            {  
             m[vec]=true;
            return true;
            }
            v.insert(iter,temp);
        }
        m[vec]=false;
        return false;
    }

这并不是最优的解法。最优的解法参见答案。

25.https://leetcode-cn.com/problems/next-greater-element-iii/

下一个更大元素。这题比较简单。但是感觉题意表示不清。32位指的是比特位。

位数是个十百千位的位。

这种题注意要用long long 类型，不然会溢出。

26.https://leetcode-cn.com/problems/valid-parenthesis-string/

有效的括号字符串。

这题用暴力解法会超时。

最优解法是：考虑两种极端情况。一种是把所有的*号变成左括号，判断这个时候右括号有没有过多。

一种是把使用的*号变成右括号，判断左括号有没有过多。只要这两种极端情况满足，那么返回true，反之返回false。

27.https://leetcode-cn.com/problems/remove-comments/

删除注释。这一题其实不难，把输入转成string再处理就变简单了。一开始是直接对原始输入做处理，结果很复杂。

下面贴代码：

  vector<string> removeComments(vector<string>& source) 
{
     vector<string>ans;
     int len=source.size();
     string sources="";
     string temp="";
     for(int i=0;i<len;i++)
     {
       sources+=source[i]+"\n";
     }
   
     len=sources.size();
     bool lineflag=false;
     bool commentstartflag=false;
     for(int i=0;i<len;i++)
     {
      if(i+1<len&&sources[i]=='/'&&sources[i+1]=='/'&&!lineflag&&!commentstartflag)
      {
      i++;
      lineflag=true;
      continue;
      }
      if(i+1<len&&!lineflag&&sources[i]=='/'&&sources[i+1]=='*'&&!commentstartflag)
      {
        i++;
        commentstartflag=true;
        continue;
      }
      if(lineflag&&sources[i]=='\n')
      {
        lineflag=false;
      }
      if(i+1<len&&commentstartflag&&!lineflag&&sources[i]=='*'&&sources[i+1]=='/')
      {
       commentstartflag=false;
       i++;
       continue;
      }
 
      if(!lineflag&&!commentstartflag) temp+=sources[i];
      
     }
     int start=0;
     for(int i=0;i<temp.size();i++)
     {
     if(temp[i]=='\n') 
     {
     string s=temp.substr(start,i-start); 
     start=i+1;
     if(s!="") ans.push_back(s);
     }
     }
    return ans;
     
}

28.https://leetcode-cn.com/problems/swap-adjacent-in-lr-string/

在LR字符串中交换相邻字符。本题是找规律题。

即L字符串只能左移，R字符串只能右移。利用这个规律来解本题。

用常规的思路：bfs会超时。

29.https://leetcode-cn.com/problems/valid-tic-tac-toe-state/

有效的井字游戏。

找规律题。

1.X的数量比O的数量多1或者是相等。

2.不可能同时X和O有 3 个相同（且非空）的字符填充任何行、列或对角线。

3.若是O有 3 个相同（且非空）的字符填充任何行、列或对角线,则X和O的数量相等。

4.若是X有 3 个相同（且非空）的字符填充任何行、列或对角线,则X比O多一个。

30.https://leetcode-cn.com/problems/friends-of-appropriate-ages/

适龄的朋友。

这一题用最常规的解法做会超时。

1 <= ages.length <= 20000.

1 <= ages[i] <= 120.

这个是本题的突破点，age的大小在2W左右，处理起来非常麻烦。如果我们把所有年龄相同的人统计起来，这最多只有120情况，因此我们可以计算 每一个年龄发送给另一个年龄的好友请求数，然后求和。这样就大大的降低了时间复杂度。

31.https://leetcode-cn.com/problems/new-21-game/

新21点

典型的动态规划问题。

dp[i]表示得分为i的概率。

递推关系式：

sum(dp[i] + dp[i - 1] + dp[i - 2] + ... + dp[i - min(i, W)]) / W。

不要用循环去求上面的和，用一个变量去记录即可。

32.https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence/

将数组拆成斐波那契数列。

这一题是累加数的进阶版。累加数只判断能不能分割成斐波那契数列，而本题是返回可行的路径。若不可行，则返回空。

33.https://leetcode-cn.com/problems/longest-mountain-in-array/

数组中的最长山脉

常规的解法是。

优化解法是：

借用辅助数组left和right。

其中left[i]表示i的左边有多少个连续小于num[i]的元素。right[i]表示i的右边有多少个连续小于num[i]的元素。4

这样子可以把时间复杂度降到。

34.https://leetcode-cn.com/problems/prime-palindrome/

回文素数。

这一题要用到两个数学性质。

1.除 11 外的偶数位回文数，都能被 11 整除

2.除 2 和 3 外，所有的素数一定在 6 的两侧

利用这两条性质可以跳过很多数字，就不会超时了。

如遇到13，则可以马上跳到101.

如遇到25，下一个可以跳到29.

35.https://leetcode-cn.com/problems/exam-room/

考场就座问题。

第一个版本答案：

class ExamRoom {
public:
    ExamRoom(int N) {
    vec.resize(N);
    for(int i=0;i<N;i++)
        vec[i]=-1;
    }
    int seat() {
    int N=vec.size();
    vector<int>temp;
    for(int i=0;i<N;i++)
    {
        if(vec[i]==i) temp.push_back(i);
    }
    if(temp.size()==0) {
        vec[0]=0;
        return 0;}
    if(temp.size()==1) 
    { if(temp[0]<N/2)  
      {vec[N-1]=N-1;
      return N-1;
      }
    else
    {
       vec[0]=0;
       return 0;
    }
    }
    if(temp.size()==N) return -1;
    int dis=0;
    int ans=-1;
    for(int i=0;i<temp.size()-1;i++)
    {
        if((temp[i+1]-temp[i])/2>dis) 
        {dis=(temp[i+1]-temp[i])/2;
        ans=(temp[i+1]+temp[i])/2;
        }
    }
    if(vec[0]==-1&&(dis>=temp[0]/2||ans==-1))
    {
        vec[0]=0;
        return 0;
    }
    else if(vec[N-1]==-1&&ans==-1)
    {
        vec[N-1]=N-1;
        return N-1;
    }
    else    
    {
       vec[ans]=ans;
       return ans;
    }
    }
    void leave(int p) {
     vec[p]=-1;
    }
    vector<int>vec;
};

但是超时了。

优化：

由于每次调seat函数时，都要重新找哪些位置是已经有人了的，有很多重复的计算。这个部分可以优化。

优化后的代码如下：

class ExamRoom {
public:
    ExamRoom(int N) {
    n=N;
    }
    int seat() {
   if(temp.size()==0) {
    temp.insert(0);
    return 0;}
    if(temp.size()==1) 
    { if(*temp.begin()<n/2)  
      {
       temp.insert(n-1);
      return n-1;
      }
    else
    { temp.insert(0);
       return 0;
    }
    }
    if(temp.size()==n) return -1;
    int dis=0;
    int ans=-1;
    auto iter=temp.begin();
   while(iter!=temp.end())
    {
      auto it=iter;
    if(++it!=temp.end())
    {  int first=*iter;
      int second=*(++iter);
        if((second-first)/2>dis)
       {
        dis= (second-first)/2;
        ans= (second+first)/2;
       }
    }
    else
    {
       break;
    }
    
    }
    if(temp.find(0)==temp.end()&&(dis>=*temp.begin()/2||ans==-1))
    {
    temp.insert(0);
    return 0;    
    }
    else if(temp.find(n-1)==temp.end()&&ans==-1)
    {
       
        temp.insert(n-1);
        return n-1;
    }
     else    
    {
      
       temp.insert(ans);
       return ans;
    }
    }
    void leave(int p) {
    
    temp.erase(p);
     
    }
    int n;
    set<int>temp;
};

36.https://leetcode-cn.com/problems/decoded-string-at-index/

若把完整的字符串存储下来会内存超出。

优化解法如下：

 string decodeAtIndex(string S, int K) 
    {
      int len=S.size();
      long long int size=0;
      for(int i=0;i<len;i++)
      {
        if(isdigit(S[i]))
            size=size*(S[i]-'0');
        else size++;
      }
     for(int i=len-1;i>=0;i--)
     {
        if((K==size||K==0)&&!isdigit(S[i]))  return string("")+S[i];;
         if(isdigit(S[i]))
         {
             size=size/(S[i]-'0');
             K=K%size;
         }
         else
            size--;
     }
        return string("");
    }

先求出下来字符串的长度，再反向遍历求出第K个字符。

37.https://leetcode-cn.com/problems/bitwise-ors-of-subarrays/

这一题直接二重循环会超时。优化的思路是消去重复计算。

38.https://leetcode-cn.com/problems/sum-of-subarray-minimums

res = sum(A[i] * f(i))
where f(i) is the number of subarrays,
in which A[i] is the minimum.

难点就在于求f(i)，为了求f(i)需要求left[i]和right[i]。

left[i]：A[i]左边严格大于A[i]的个数

right[i]：A[i]右边大于等于A[i]的个数

f(i) = (left[i] + 1) * (right[i] + 1)，其实就是一个排列组合，左边取一个可能，那么可以从右边取right[i] + 1种来进行组合。

这里需要特别注意的一点是：首先本问题是允许重复的子数组的，这里的重复是指数字上相等，但是是不允许完全一致的区间，因此左边必须是严格大于，否则会出现重复的情况。计算left，right数组可以使用Stack在O(n)时间复杂度完成求解，最后的res计算也是线性时间，因此总的时间复杂度为O(n)。

利用单调栈来求left和right数组。

39.https://leetcode-cn.com/problems/maximum-sum-circular-subarray/

环形子数组的最大和。这一题是子数组的最大和的进阶版。

分两种情况讨论：一种是最大和没有循环。这种情况按子数组的最大和求解即可。

一种是最大和有循环。这种情况按子数组的最小和求解，再用整个数组的和减去这个最小和。

40.https://leetcode-cn.com/problems/delete-columns-to-make-sorted-ii/

贪心算法: 从前往后比较字符串上的字符, 通过删除那些破坏顺序的列来逐步构建顺序.

(S1). 用一个向量来记录当前不确定是否排好顺序的那些字符串: 让j记录当前研究的列, 若 A[i] 和 A[i+1] 的前j列完全一样, 那个 i 就包含在 vec 里. 初始化时, vec={0, 1,2,...,A.size()-2};

(S2).若 j 列破坏了之前的顺序, 那么删除 j 列, 结果加1; 若 j 列没破坏之前排序, 那么不删除, 但是新增加的 j 列可能会区分开之前不能区分的字符串 A[i][0:j-1] 和 A[i+1][0:j-1], 因此要更新 vec；

(S3).若 vec 是空的, 就说明已经排好序了, 不需要再继续了, 返回结果, 否则继续检查下一列 j+1 列.

贴代码：

int minDeletionSize(vector<string>& A) 
 {
      int rows=A.size();
      if(rows==0) return 0;
      int cols=A[0].size();
      vector<int>s;
      for(int i=0;i<rows-1;i++)
       s.push_back(i);
      int ans=0;
     for(int i=0;i<cols;i++)
      { bool flag=true;
        for(auto iter=s.begin();iter!=s.end();iter++)
        { if(A[*iter+1][i]<A[*iter][i])
             {
               ans++;
               flag=false;
               break; 
             }
            else
               continue;
         }
         if(flag)
         {
          for(auto iter=s.begin();iter!=s.end();iter++)
          {
              if(A[*iter+1][i]>A[*iter][i])
             {
               iter=s.erase(iter);
               iter--;
             }
          }
         }
         if(s.size()==0) return ans;
        }
  return ans;
 }

40.https://leetcode-cn.com/problems/smallest-range-ii/

最小差值II

思路：较小的数加上K，较大的数减去K。

遍历去确定这个分割点，即可得到结果。

41.https://leetcode-cn.com/problems/online-election/

在线选举，用vector存下每个时刻是由哪个选举者主导的。

然后二分法查找即可。

42.https://leetcode-cn.com/problems/time-based-key-value-store/

这题对时间的要求非常苛刻。

class TimeMap {
public:
    /** Initialize your data structure here. */
    TimeMap() {
        
    }
    
    void set(string key, string value, int timestamp) {
   
     m[key].push_back(make_pair(value,timestamp));
     
    }
    
    string get(string key, int timestamp) {
      
      if(m.find(key)==m.end()) return "";
      auto& vec=m[key];//这个地方必须要有引用，否则会超时。
      int len=vec.size();
      int low=0;
      int high=len-1;
      int mid=(low+high)/2;
      while(low<=high)
      {
       if(vec[mid].second==timestamp) return vec[mid].first;
       else if (vec[mid].second<timestamp) low=mid+1;
       else high=mid-1;
       mid=(low+high)/2;
      }
      return high==-1? "":vec[high].first;
     }
    unordered_map<string,vector<pair<string,int>>>m;
};
 
/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap* obj = new TimeMap();
 * obj->set(key,value,timestamp);
 * string param_2 = obj->get(key,timestamp);
 */

43.数独问题，深搜的典型问题。

版本一：

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) 
    {
      int count=0;
      vector<pair<int,int>>vec;
      for(int i=0;i<9;i++)
          for(int j=0;j<9;j++)
          {
              if(board[i][j]=='.') 
              {
               vec.push_back(make_pair(i,j));
              }
          }
      for(int num=1;num<=9;num++)
      {
          if(dfs(board,vec,num,count)) break;;
       
      }
      return;
    }
private:
  bool dfs(vector<vector<char>>& board, vector<pair<int, int>>&vec, int num, int &count)
{
	if (count == vec.size()) return true;
	int i = vec[count].first;
	int j = vec[count].second;
	
	if (isvalid(board, i, j, num) == false) return false;
	board[i][j] = num + '0';
	count++;
	bool flag = false;
	for (int nextnum = 1; nextnum <= 9; nextnum++)
	{
		if (dfs(board, vec, nextnum, count))
		{
			flag = true;
			break;
		}
	}
	if(!flag) board[i][j] = '.';
	count--;
	return flag;
}
    bool isvalid(vector<vector<char>>& board, int i, int j, int num)
   {
	set<int>s;
	for (int k = 0; k < 9; k++)
	{
		if(k!=j) s.insert(board[i][k] - '0');
	}
	
	
	for (int k = 0; k < 9; k++)
	{
		if(k!=i) s.insert(board[k][j] - '0');
	}
 
	for (int m = i / 3 * 3; m <= i / 3 * 3 + 2; m++)
		for (int n = j / 3 * 3; n <= j / 3 * 3 + 2; n++)
		{
			if(m!=i&&n!=j)
			s.insert(board[m][n] - '0');
		}
	if (s.find(num) == s.end()) return true;
	return false;
  }
 
};

结果：超时。

改进：剪枝部分可以优化。用三个数组来标记某个数字是否在某行、某列或者是某个3*3小方格中出现过。

版本二：

class Solution {
public:
   void solveSudoku(vector<vector<char>>& board)
{
	int count = 0;
    vector<vector<bool>>rows(9, vector<bool>(9, false));
    vector<vector<bool>>cols(9, vector<bool>(9, false));
    vector<vector<bool>>blocks(9, vector<bool>(9, false));
	vector<pair<int, int>>vec;
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++)
		{
			if (board[i][j] == '.')
			{
			vec.push_back(make_pair(i, j));
			}
			else
			{
				rows[i][board[i][j] - '1'] = 1;
				cols[j][board[i][j] - '1'] = 1;
				blocks[i / 3 * 3 + j / 3][board[i][j] - '1'] = 1;
			}
		}
	for (int num = 1; num <= 9; num++)
	{
		if (dfs(board, vec, num, count,rows,cols,blocks)) break;
 
	}
	return;
}
private:
    bool dfs(vector<vector<char>>& board, vector<pair<int, int>>&vec, int num, int &count, vector<vector<bool>>&rows, vector<vector<bool>>&cols, vector<vector<bool>>&blocks)
{
	if (count == vec.size()) return true;
	int i = vec[count].first;
	int j = vec[count].second;
	if (rows[i][num - 1] || cols[j][num - 1] || blocks[i / 3 * 3 + j / 3][num - 1]) return false;
	
	board[i][j] = num + '0';
	rows[i][num - 1] = 1;
	cols[j][num - 1] = 1;
	blocks[i / 3 * 3 + j / 3][num - 1] = 1;
	count++;
	bool flag = false;
	for (int nextnum = 1; nextnum <= 9; nextnum++)
	{
		if (dfs(board, vec, nextnum, count,rows,cols,blocks))
		{
			flag = true;
			break;
		}
	}
	if (!flag)
	{
		board[i][j] = '.';
		rows[i][num - 1] = 0;
		cols[j][num - 1] = 0;
		blocks[i / 3 * 3 + j / 3][num - 1] = 0;
	}
	count--;
	return flag;
}
 
};

44.缺失的第一个正数

限制：时间复杂度 O(n)  空间复杂度 常数复杂度

思路:   桶排序 。把i放在下标为i-1的位置上，然后顺序遍历一遍找到第一个不满足的元素即可。

45.有效数字https://leetcode-cn.com/problems/valid-number/

解法：有限状态自动机。

46.https://leetcode-cn.com/problems/minimum-window-substring/

双指针法

47.柱状图中的最大矩形

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

解法:单调非递减栈

48.最大矩形

https://leetcode-cn.com/problems/maximal-rectangle/

解法:转化为上一题.

49.计算右侧小于当前元素的个数

https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/

树状数组.复杂度:O(nlgn)

50.去除重复字母

https://leetcode-cn.com/problems/remove-duplicate-letters/

贪心法.

51.拼接最大数

https://leetcode-cn.com/problems/create-maximum-number/

单调栈得到数组长度为k的最大子序列