好得很程序员自学网

<tfoot draggable='sEl'></tfoot>

leetcode刷题笔录

leetcode刷题笔录

leetcode刷题笔录-4

不同的子序列 给定字符串 S 和 T ，计算 T 作为 S 的不同子序列的个数（不同，指子序列每个元素在原序列中的位置）。比如，给出 S="rabbbit" 和 T="rabbit" ，应当返回 3 ，应为有这样 3 种不同的子序列：" rabb b it "，" rab b bit "，" ra b bbit "。 思路：动态规划。T(1...n) 作为 S(1...m) 的不同子序列的数量（问题），就等于： 如果 T[n]!=S[m] ，为：T(1...n) 作为 S(1...m-1) 的不同子序列的数量（子问题）。 如果 T[n]=S[m]，为：T(1...n-1) 作为 S(1...m-1) 的不同子序列的数量，加上T(1...n) 作为 S(1...m-1) 的不同子序列的数量。这是因为，S 中与 T 一致的子序列，可以分为两种：即最后一个元素在 S[m] 上的和最后一个元素不在 S[m] 上的。 这样，我们需要维护一个二维数组域 N(1...n)(1...m) ，N[i][j] 表示 T[1...i] 作为 S[1...j] 的不同子序列的数量。再适当考虑边界条件就行了。 实现：

 class   Solution {
  public  :
      int  numDistinct( string  S,  string   T) {
        vector <vector< int >>  n;
        
        vector < int >  tmp0;
          if (S.size()== 0  || T.size()== 0  ){
              return   0  ;
        }        
          else  {
            tmp0.push_back(S[  0 ]==T[ 0 ] ?  1  :  0  );
        }
          for ( int  j= 1 ; j<S.size(); j++ ){
            tmp0.push_back(S[j] ==T[ 0 ] ? tmp0[j- 1 ]+ 1  : tmp0[j- 1  ]);
        }
        n.push_back(tmp0);
        
          for ( int  i= 1 ; i<T.size(); i++ ){
            vector < int >  tmp;
            tmp.push_back(  0  );
              for ( int  j= 1 ; j<S.size(); j++ ){
                tmp.push_back(S[j] ==T[i] ? n[i- 1 ][j- 1 ]+tmp[j- 1 ] : tmp[j- 1  ]);
            }
            n.push_back(tmp);
        }
        
          return  n[T.size()- 1 ][S.size()- 1  ];
    }
};

将二叉树转化为单链表 给出一棵二叉树，将其转化为单链表（利用右节点指针）。比如，给出：

          1 
        /           2     5 
      /  \          3     4     6

应当返回：

    1  
           2  
               3  
                   4  
                       5  
                           6

单链表的顺序应该是前序遍历的顺序。

思路：递归，对某一个二叉树，现将其左子树排成前序遍历的链表并指定后一个节点是右子树的第一个节点（如果有），然后将右子树也排成前序遍历的链表并指定后一个节点为本树的后一个节点（如果有）。再完善一下边界条件。 实现： 

 /*  *
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
   */ 
 class   Solution {
  public  :
      void  flatten(TreeNode * root) {
          if (root== NULL){
              return  ;
        }
        _flatten(root, NULL);
    }
    
      void  _flatten(TreeNode *root, TreeNode * next){
        
          if (root->left !=  NULL){
              if (root->right !=  NULL){
                _flatten(root ->left, root-> right);
                _flatten(root -> right, next);    
            }
              else {  //   root->right == NULL 
                _flatten(root-> left, next);
            }
            root ->right = root-> left;
            root ->left =  NULL;
        }
          else {  //   root->left == NULL 
             if (root->right !=  NULL){
                _flatten(root -> right, next);
            }
              else {  //   root->right == NULL 
                root->right =  next;
            }
        }
    }
};   

路径节点和 给出一棵二叉树和一个数值 sum，判断二叉树中是否存在一条从跟到叶子节点的路径，使路径上节点的加和等于这个数值。比如，给出如下一棵二叉树和值22：

               5 
             /                4     8 
           /   /              11    13    4 
         /   \                7      2        1

应当返回 true ，因为路径 5-4-11-2 的路径节点和为 22。 思路：很简单，对某棵二叉树，如果有任意一棵子树的路径节点和为sum-val ，那么就存在这么一条路径。 实现：

 /*  *
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
   */ 
 class   Solution {
  public  :
      bool  hasPathSum(TreeNode *root,  int   sum) {
          if (root ==  NULL){
              return   false  ;
        }
          if (root->left == NULL && root->right ==  NULL){
              return  sum==root->val ?  true  :  false  ;
        }
          bool  hasPath =  false  ;
          if (root->left !=  NULL){
            hasPath  = hasPath || hasPathSum(root->left, sum-root-> val);
        }
          if (root->right !=  NULL){
            hasPath  = hasPath || hasPathSum(root->right, sum-root-> val);
        }
          return   hasPath;
    }
};   

 路径节点和2： 给出一棵二叉树和一个数值 sum，找出所有路径节点和为 sum 的路径并输出。比如给出这样一棵二叉树和 sum 值 22：

               5 
             /                4     8 
           /   /              11    13    4 
         /  \    /            7      2    5     1

应当返回：

 [
   [  5 , 4 , 11 , 2  ],
   [  5 , 8 , 4 , 5  ]
]

思路：避免采用循环遍历二叉树的方法就是在递归中访问函数外的变量（此处是类的成员）。递归地形式保证了递归地次序，即前序遍历，在递归时维护一个栈，栈中的所有元素即使从根节点到当前正在递归地节点的路径，进入一棵子树时，向栈中压入一个子树的根节点的值，退出该子树时弹出一个元素。检测到叶子节点的值就是给定的值（侦测到一个满足的路径），就将当前的栈复制一份并加入到结果列表中。 实现： 

 class   Solution {
  public  :
    vector <vector< int > > pathSum(TreeNode *root,  int   sum) {
        paths  = vector<vector< int >> ();
        path  = vector< int > ();        
        _pathSum(root, sum);
          return   paths;        
    }
    
      void  _pathSum(TreeNode *root,  int   sum){
          if (root ==  NULL){
              return  ;
        }
        
        path.push_back(root -> val);        
          if (root->left == NULL && root->right ==  NULL){
              if (sum == root-> val){
                paths.push_back(vector < int > (path));
            }
        }        
        _pathSum(root ->left, sum-root-> val);
        _pathSum(root ->right, sum-root-> val);
        path.pop_back();
    }
    
    vector <vector< int >>  paths;
    vector < int >  path;
};   

二叉树的最小深度 给出一棵二叉树，求其最小深度（即，最短的从根节点到叶节点的路径的长度）。 思路：在递归外维护一个变量，进入一棵子树时+1，离开一棵子树时-1，则该变量就记录当前节点的深度。每到达一个叶节点时，该变量就记录了一条路径的长度，将其与现有最短路径的长度比较，如果当前路径更短，则更新最短路径长度。 实现：

 /*  *
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
   */ 
 class   Solution {
  public  :
      int  minDepth(TreeNode * root) {
        depth  =  0  ;
        min  =  INT_MAX;
        
          if (root ==  NULL){
              return   0  ;            
        }
          else  {
            _minDepth(root);
              return   min;
        }
    }
    
      void  _minDepth(TreeNode * root){
          if (root ==  NULL){
              return  ;
        }
        
        depth ++ ;
        
          if (root->left == NULL && root->right ==  NULL){
            min  = min<depth ?  min : depth;
        }
        _minDepth(root -> left);
        _minDepth(root -> right);
        depth -- ;
    }
    
      int   depth;
      int   min;
};

平衡二叉树 给出一棵二叉树，判断其是否是平衡的。一棵平衡的二叉树应该是这样的：二叉树的每一个节点，其左子树的高度和右子树的高度差小于等于1。 思路：直接递归，大小集合就都通过了。如果维护另一颗二叉树，记录每个节点为根的子树的高度，性能肯定会更好一些。 实现：

 /*  *
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
   */ 
 class   Solution {
  public  :
      bool  isBalanced(TreeNode * root) {
          if (root ==  NULL){
              return   true  ;
        }
          else   if (isBalanced(root->left) && isBalanced(root-> right)){
              int  dif = getDepth(root->left) - getDepth(root-> right);
              if (dif <= 1  && dif >= - 1  ){
                  return   true  ;
            }
        }
          return   false  ;        
    }
    
      int  getDepth(TreeNode * root){
          if (root ==  NULL){
              return   0  ;
        }
          else  {
              int  left = getDepth(root-> left);
              int  right = getDepth(root-> right);
              return  left>right ? left+ 1  : right+ 1  ;
        }
    }
};

作者： 一叶斋主人
出处： www.cnblogs.com/yiyezhai
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

 

分类:  leetcode 刷题笔录

leetcode 刷题笔录

 

leetcode刷题笔录-4

摘要: leetCode刷题笔录-4，不同的子序列数量，二叉树原地转单链表，二叉树路径节点之和1&2，二叉树最小深度，平衡二叉树 阅读全文

posted @  2013-04-19 08:59  一叶斋主人 阅读(113) |  评论 (0)   编辑

 

leetcode刷题笔录-3

摘要: leetcode刷题笔录3：三角形，帕斯卡三角形1&2，二叉树中的next节点1&2 阅读全文

posted @  2013-04-02 09:08  一叶斋主人 阅读(693) |  评论 (0)   编辑

 

leetcode刷题笔录-2

摘要: leetCode刷题笔录-2 字梯游戏1&2、回文验证、二叉树最大路径和、股价问题1&2&3 阅读全文

posted @  2013-03-27 16:51  一叶斋主人 阅读(694) |  评论 (7)   编辑

 

leetcode刷题笔录-1

摘要: leetcode OJ 听说难度适中，适合我这种还没毕业的菜鸟吧。回文分割1&2，围棋，“根-叶”数之和，最长连续序列。 阅读全文

posted @  2013-03-19 15:51  一叶斋主人 阅读(791) |  评论 (0)   编辑

公告

 

非计算机专业出身的计算机爱好者，中科院某所硕士研究生在读。理想是做一名一流的游戏设计师，目前正在广泛涉猎中。

个人博客：   www.xieguanglei.com 我的邮箱：   xieguanglei@hotmail.com 我的QQ：   280138635

 

随笔分类 (39) leetcode 刷题笔录(4) Three.js Demo 源码笔记(1) Three.js 教程翻译(6) Three.js 源码笔记(4) WebGL 原生 API 笔记(4) 编程语言笔记(5) 计算机图形学笔记 开发环境和开发工具 算法导论笔记(13) 我的 Demo(2)

积分与排名 积分 - 27068 排名 - 4776

 

 

作者： Leo_wl

　　　　

出处： http://www.cnblogs.com/Leo_wl/

　　　　

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

版权信息

查看更多关于leetcode刷题笔录的详细内容...

声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did46077

  阅读：40次

上一篇： .NET 4.5 压缩

下一篇：Vim常用命令

相关资讯