LeetCode Solution(Easy.21-24)

c/c++,python,for work

Views:  times Posted by elmagnifico on December 10, 2015

21.Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

21.Climbing Stairs-Analysis

一步两步,我的滑板鞋…摩擦摩擦,又摩擦….

什么鬼, 走一步两步,一共走n步,求多少种方法

首先 最多走2步, 而走的这2步,可以拆成1+1 但这强行限制了1连着1的情况

所以最小分析单位应该扩大一些 3步 =1+2=2+1=1+1+1 这样就是最小单位了

那么3步有几种方法呢 3种 那就看n中有多少个3 然后3的x次幂*剩余步数的情况 应该就是最后所有的可能

好吧 事实证明上面的想法不对

那找规律看看吧

步数 1 2 3 4 5 6  7
方法 1 2 3 5 8 13 21

好吧竟然是个类斐波那契数列

21.Climbing Stairs-Solution-C/C++

迭代

int climbStairs(int n)
{
    int i=0,temp;
    int pre=0,cur=1;
    for(i=0;i<n;i++)
    {
        temp=cur;
        cur=cur+pre;
        pre=temp;
    }
    return cur;
}

递归

虽然递归是正确的,但是莫名其妙在输入42以后都会提示超时的问题 基本就是超过2s才能有答案,所以判定超时吧

int climbStairs(int n)
{
    if(n==1||n==0)
        return 1;
    return climbStairs(n-1)+climbStairs(n-2);
}

21.Climbing Stairs-Solution-Python

迭代

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        temp=n
        cur=1
        pre=0
        i=0
        for i in range(0,n):
            temp=cur
            cur=cur+pre
            pre=temp
        return cur

递归

问题同上,只不过python的运行效率更差在33往后就 直接超时了

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if(n==1 or n==0):
            return 1
        return self.climbStairs(n-1)+self.climbStairs(n-2)

22.Power of Two

Given an integer, write a function to determine if it is a power of two.

22.Power of Two-Analysis

判断一个数是不是2的x次方,这里其实可以取巧,直接看位就可以了。

如果32位中只有一位置1 那么就是2的幂次 否则不是

当然这里用来计算1的个数可以用上一次提到的hammingweight的方法,可以提高一倍的速度

22.Power of Two-Solution-C/C++

bool isPowerOfTwo(int n) 
{
    int i=0,temp=0;
    if(n<=0)
        return false;
    for(i=0;i<32;i++)
    {
        temp=temp+((n>>i)&1);
        if(temp==2)
            return false;
    }
    return true;
}

22.Power of Two-Solution-Python

class Solution(object):
    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n<=0:
            return False
        temp=0
        i=0
        for i in range(0,32):
            temp=temp+((n>>i)&1)
            if temp==2:
                return False
        return True

23.Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

23.Balanced Binary Tree-Analysis

判断一个平衡二叉树是否是高度平衡的,左右子树结点数之差不超过1

明显这种用递归比较简单,迭代也会写

首先就需要求解左右子树的度

23.Balanced Binary Tree-Solution-C/C++

递归

在C的代码中

代码单独测试[2,1,3]是正确的,但是只要一提交就会说输出错误

单独测试其他的情况也正确,但是就是不能提交,见了鬼。

如果改成C++ 就一点错都没有了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int balance=0;
int BBTdepth (struct TreeNode* root)
{
    if(root==NULL||balance==1)
        return 0;
    int depthleft=BBTdepth(root->left);
    int depthright=BBTdepth(root->right);
    if(depthleft-depthright>1||depthleft-depthright<-1)
    {
        balance=1;
        printf("123");
        return -1;
    }
    return depthleft>=depthright?depthleft+1:depthright+1;
}
bool isBalanced(struct TreeNode* root) 
{
    BBTdepth(root);
    if(balance==1)
        return false;
    else
        return true;
       
}

要问错误的原因是什么,我终于找到了 leetcode中其他语言都是面向对象的,在函数外定义的对象也是类之中的,所以作为类成员是没问题,用来传递这个balance。但是在唯一的面向过程的C中这就不一样了。在调试的时候这全局变量是被认可的,所以测试的结果都是正确的。但是当去submit的时候,这个全局变量会自动被leetcode后台给释放掉了,就最后结果永远是true 怎么提交都不对,但是单独测又是正确的

经过修改,把balance作为指针传递进去,避免使用全局变量,从而通过submit

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int MaxDepth(struct TreeNode* root,bool* balance)
{
    if (root == NULL||*balance==false)
        return 0;
    int leftdepth = MaxDepth(root->left,balance);
    int rigtdepth = MaxDepth(root->right,balance);
    if (abs(leftdepth - rigtdepth) > 1)
    {
        *balance = false;
        return -1;
    }
    else if (leftdepth < rigtdepth)
        return rigtdepth + 1;
    else
        return leftdepth + 1;   
}
bool isBalanced(struct TreeNode *root)
{
    bool balance=true;
    MaxDepth(root,&balance);
    return balance;
}

迭代

我先尝试把上面的递归改成迭代,发现好麻烦啊,于是想一想有没有其他的简单一些的方法可以用呢

于是我发现如果构造一个带度节点,并且按照层的顺序压入栈中,压栈的时候如果发现了两个不满的层 那就说明是不平衡的了呗 (等我写完下面的程序才发现,我思路错了,这个想法可以用判断是否满,而不能判断是否是平衡二叉树,平衡二叉树只看左右子树,不相邻的就算差了1也是没事的,一个概念理解错了,直接全写错了)

迭代的思路就放弃了,等以后想出来了再来。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 class Solution
 {
public:
struct DTN 
{
    int degree;
    struct TreeNode *root;
};

bool isBalanced(struct TreeNode *root)
{
    int leftdepth=0,rightdepth=0;
    queue<DTN> store;
    DTN temp;
    DTN temp1;
    if(!root)
        return true;
    temp.degree=0;
    temp.root=root;
    store.push(temp);
    int i=0,j=0,count=0;
    int left=0,right=0;
    for(i=0;i<100;i++)
    {
        while(count<pow(2,i))
        {
            
            temp=store.front();
            store.pop();
            printf("%d-",temp.degree);
            if(temp.degree!=i)
                return false;
            if(temp.root->left)
            {
                left++;
                temp1.degree=i+1;
                temp1.root=temp.root->left;
                store.push(temp1);
            }
            if(temp.root->right)
            {
                right++;
                temp1.degree=i+1;
                temp1.root=temp.root->right;
                store.push(temp1);
            }
            if(store.empty())
                break;
            count++;
        }
        count=0;
        if(store.empty())
            return true;
    }
}
};

23.Balanced Binary Tree-Solution-Python

python也用递归的方式来完成

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    balance=True
    def maxdepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if(root==None or self.balance==False):
            return 0
        leftpath=self.maxdepth(root.left)
        rightpath=self.maxdepth(root.right)
        if(leftpath-rightpath<-1 or leftpath-rightpath>1):
            self.balance=False
            return 0
        if leftpath>rightpath:
            return leftpath+1
        else: 
            return rightpath+1
            
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        self.maxdepth(root)
        return self.balance

24.Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note: Bonus points if you could solve it both recursively and iteratively.

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization: The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.

说白了#就等于之前null嘛

24.Symmetric Tree-Analysis

判断一棵树是不是对称的。

那实际上用之前写过的判读两棵树是不是相等就可以做到了。

还是有一点不同,在于对称的问题,也就是判等的时候要左和右相等而不是左等于左

24.Symmetric Tree-Solution-C/C++

递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 
bool isSame(struct TreeNode* root1,struct TreeNode* root2)
{
    if(root1==NULL&&root2==NULL)
        return true;    
    if((root1!=NULL&&root2==NULL)||(root1==NULL&&root2!=NULL)||(root1->val!=root2->val))
        return false;
    return isSame(root1->left,root2->right)&&isSame(root1->right,root2->left);
}
bool isSymmetric(struct TreeNode* root)
{
    if(!root)
        return true;
    return isSame(root->left,root->right);
}

迭代

这份代码优化了很多,比之前写的判断二叉树是否相等,去掉了很多重复的判断,简洁了一些。

/**
 * 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:
    bool isSymmetric(TreeNode* root) 
    {
        if(!root)
            return true;
        queue<TreeNode*>left;
        queue<TreeNode*>right;
        TreeNode*root1=root->left;
        TreeNode*root2=root->right;
        if(root1==NULL&&root2==NULL)
	        return true;    
	    if((root1!=NULL&&root2==NULL)||(root1==NULL&&root2!=NULL)||(root1->val!=root2->val))
	        return false;        
        while(1)
        {
            
            if(root1==NULL&&root2==NULL)
	        {
	            if(left.empty()&&right.empty())
	                return true;
	            else
	            {
	                root1=left.front();
	                root2=right.front();
	                left.pop();
	                right.pop();
	                continue;
	            }    
	        }
	        if((root1!=NULL&&root2==NULL)||(root1==NULL&&root2!=NULL)||(root1->val!=root2->val))
	            return false;
	        
            //root1和root2不为空的情况下,并且二者相等
            if(root1->left!=NULL)
	        {
	            if(root1->right!=NULL)
	                left.push(root1->right);
	            root1=root1->left;
    	        if(root2->right!=NULL)
    	        {
    	            if(root2->left!=NULL)
    	                right.push(root2->left);
    	            root2=root2->right;
    	        }
    	        else
    	            return false;
	        }
	        else
	        {
	            if(root1->right!=NULL)
	                root1=root1->right;
	            else
	            {
	                root1=NULL;
	            }
	            if(root2->right!=NULL)
    	            return false;
    	        else
    	        {
    	            if(root2->left!=NULL)
    	                root2=root2->left;
    	            else
    	            {
    	                root2=NULL;
    	            }
    	        }
	            
	        }
        }

    }
};

24.Symmetric Tree-Solution-Python

递归

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSame(self, left,right):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if(left==None and right==None):
            return True
        if((left!=None and right==None)or(left==None and right!=None)or(left.val != right.val)):
            return False
        return self.isSame(left.left,right.right)&self.isSame(left.right,right.left)
        
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if(not root):
            return True
        return self.isSame(root.left,root.right)

迭代

在这里发现了一个问题,python对于数据的空的判断要求高,也就是说空的情况下,如果要求返回值 必然会出错。

也就是说必须在程序里确保其自身有内容的情况下才能取值,而不是像c/c++可能要去不够严格,为空的情况下会取到空值什么的。

除此以外还有一个对齐的问题,之前提交的时候,总是提示IndentationError: unexpected indent python

发现是对齐有问题,找了半天没找到,然后重置代码,重新一个一个弄过去,才没有错了。无意间复制的空格什么的都得注意

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if(root==None):
            return True
        left=[]
        right=[]
        root1=root.left
        root2=root.right
        if (root1==None and root2==None):
            return True
        if((root1!=None and root2==None)or(root1==None and root2!=None)or(root1.val != root2.val)):
            return False
        while True:
            if(root1==None and root2==None):
                if (left==[] and right==[]):
                    return True
                elif ((left!=[] and right==[])or(left==[] and right!=[])):
                    return False
                else:
                    root1=left[0]
                    left.remove(left[0])
                    root2=right[0]
                    right.remove(right[0])
            if((root1!=None and root2==None)or(root1==None and root2!=None)or(root1.val!=root2.val)):
                return False

            if root1.left!=None:
                if root1.right!=None:
                    left.append(root1.right)
                root1=root1.left
                
                if root2.right!=None:
                    if root2.left!=None:
                        right.append(root2.left)
                    root2=root2.right
                else:
                    return False
            else:
                if root1.right!=None:
                    root1=root1.right
                else:
                    root1=None;
                    
                if root2.right!=None:
                    return False
                else:
                    if root2.left!=None:
                        root2=root2.left
                    else:
                        root2=None

Quote

http://dikar.iteye.com/blog/308934