LeetCode Solution(Easy.53-56)

c/c++,python,for work

Posted by elmagnifico on December 14, 2015

53.Add Binary

Given two binary strings, return their sum (also a binary string).

For example

a = "11"
b = "1"

Return “100”.

53.Add Binary-Analysis

给二进制的string 然后求和 还能更简单吗?

方法一把string的二进制直接转化成数的二进制,然后求和,之后再把int类型转化为string的二进制(但是如果string非常长,超过int范围就有可能出错)

方法二 直接用string来做二进制求和。

53.Add Binary-Solution-C/C++

c++用方法二来实现的,除了代码很长以外,没什么难度。

class Solution 
{
public:
    string addBinary(string a, string b) 
    {
        stringstream sum;
        string s;
        int i=0,alen=a.length(),blen=b.length();
        int min=alen>blen?blen:alen;
        int max=alen>blen?alen:blen;
        int c=0;
        for(i=0;i<min;i++)
        {
            if(a[alen-1-i]=='1'&&b[blen-1-i]=='1')
            {
                if(c==1)
                {
                    sum<<'1';
                    c=1;
                }
                else
                {
                    sum<<'0';
                    c=1;
                }
            }
            else if((a[alen-1-i]=='1' && b[blen-1-i]=='0')||(a[alen-1-i]=='0' && b[blen-1-i]=='1'))
            {
                if(c==1)
                {
                    sum<<'0';
                    c=1;
                }
                else
                {
                    sum<<'1';
                }
            }
            else
            {
                if(c==1)
                {
                    sum<<'1';
                    c=0;
                }
                else
                {
                    sum<<'0';
                }
            }
            
        }
        s=alen>blen?a:b;
        int dif=max-min;
        for(i=0;i<dif;i++)
        {
            if(s[dif-1-i]=='1')
            {
                if(c==1)
                {
                    sum<<'0';
                    c=1;
                }
                else
                {
                    sum<<'1';
                    c=0;
                }
            }
            else
            {
                if(c==1)
                {
                    sum<<'1';
                    c=0;
                }
                else
                {
                    sum<<'0';
                }
            }
        }
        if(c==1)
            sum<<'1';
        string ret=sum.str();
        string nn(ret.rbegin(),ret.rend());
        return nn;
    }
};

53.Add Binary-Solution-Python

python的string不支持list的操作,真是很麻烦的一个问题啊

还好可以使用

	sum.reverse()
    ret=''.join(sum)
	或
	''.join(sum[::-1])
	进行list到string,而string到list也只用强制转换就行了

下面是具体的程序

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        c=0
        aa=list(a)
        bb=list(b)
        sum=[]
        for i in range(min(len(aa),len(bb))):
            if aa[-1]=='1' and bb[-1]=='1':
                if c==1:
                    sum.append('1')
                    c=1
                else:
                    sum.append('0')
                    c=1
            elif (aa[-1]=='0' and bb[-1]=='0'):
                if c==1:
                    sum.append('1')
                    c=0
                else:
                    sum.append('0')
                    c=0
            else:
                if c==1:
                    sum.append('0')
                    c=1
                else:
                    sum.append('1')
                    c=0
            del aa[-1]
            del bb[-1]
        if aa==[]:
            s=bb
        else:
            s=aa
        for i in range(len(s)):
            if s[-1]=='1':
                if c==1:
                    sum.append('0')
                    c=1
                else:
                    sum.append('1')
                    c=0
            else:
                if c==1:
                    sum.append('1')
                    c=0
                else:
                    sum.append('0')
            del s[-1]
        if c==1:
            sum.append('1')
        sum.reverse()
        ret=''.join(sum)
        return ret        

54.Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up: Could you do it in O(n) time and O(1) space?

54.Palindrome Linked List-Analysis

判断一个单链表是不是回文???要求时间是 O(n) 空间是O(1)

由于有空间的要求,所以要应用之前使用的一个办法,逆序。

只是这次也需要先找到链表的中间部分,然后从中间部分开始逆序

把后半截逆序之后,再跟前半截相比较,得到最后的结果。

但其实这样的话时间不是完美的 O(n) 而是 O(n/2+n/2+n/2)

还有一个递归的方式,直接递归到尾部,然后有一个全局变量记录头,

尾部和头部相比较,如果二者相等,返回,如果不等,返回false

但是如果用递归其实有一个隐藏空间的存在,就是函数保存时用的stack。

两种方法都会写一次

54.Palindrome Linked List-Solution-C/C++

迭代

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool isPalindrome(struct ListNode* head) 
{
    //找到链表的中间位置
    if(!head||!head->next)
        return true;
    struct ListNode* mid=head;
    struct ListNode* temp=head;
    while(mid->next&&mid->next->next)
    {
        temp=temp->next;
        mid=mid->next->next;
    }
    mid=temp->next;//成为另一半节点的头节点
    temp->next=NULL;
    //开始翻转节点
    struct ListNode* pre=NULL;
    struct ListNode* cur=mid;
    struct ListNode* next=cur->next;
    while(next)
    {
            cur->next=pre;
            pre=cur;
            cur=next;
            next=next->next;
    }
    cur->next=pre;
    mid=cur;
    //开始对比
    while(mid->val==head->val)
    {
        if(head->next==NULL||mid->next==NULL||mid==head)
            return true;
        mid=mid->next;
        head=head->next;
    }
    return false;
}

递归

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution 
{
public:
    ListNode* temp;
    bool ispalindrome(ListNode* head) 
    {
        if(head==NULL)
            return true;
        if(ispalindrome(head->next)==false)
            return false;
        else
        {
            if(head->val==temp->val)
            {
                temp=temp->next;
                return true;
            }
            else
                return false;
        }
        
    }
    bool isPalindrome(ListNode* head) 
    {
        temp=head;
        return ispalindrome(head);
    }
};

54.Palindrome Linked List-Solution-Python

递归

不出所料,python的递归通不过,Memory Limit Exceeded ,也就是递归超界了

所以递归的办法应该不是leetcode想要的

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def __init__(self):
        self.temp=None 
    def ispalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head==None:
            return True
        if self.ispalindrome(head.next)==False:
            return False
        else:
            if head.val==self.temp.val:
                self.temp=self.temp.next
                return True
            else:
                return False
        
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        self.temp=head
        return self.ispalindrome(head)

迭代

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def __init__(self):
        self.temp=None 
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if(not head) or (not head.next):
            return True
        mid=head
        temp=head
        #//查找中间节点
        while mid.next and mid.next.next:
            temp=temp.next
            mid=mid.next.next;
        mid=temp.next
        #//链表逆序
        temp.next=None
        pre=None
        cur=mid
        next=mid.next
        while next:
            cur.next=pre
            pre=cur
            cur=next
            next=next.next
        cur.next=pre
        mid=cur
        #//两个链表对比
        while mid.val==head.val:
            if mid==head or mid.next==None or head.next==None:
                return True
            mid=mid.next
            head=head.next
        return False

55.Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

55.Binary Tree Paths-Analysis

返回根到子叶的路径,这不是前天做过的那个类似吗,返回根到节点的总和。

一样是使用深度遍历,然后挨个存储把左子树和右子树的内容分开存储

55.Binary Tree Paths-Solution-C/C++

/**
 * 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<string> ret;
    void depthsearch(TreeNode* root,string path)
    {
        //cout<<path;
        if(root==NULL)
            return;
        if(root->left==NULL&&root->right==NULL)
        {
            
            //当前节点为叶节点,路径加入返回区
            stringstream sum;
            sum<<path<<root->val;
            path=sum.str();
            ret.push_back(path);
        }        
        if(root->left!=NULL)
        {
            stringstream sum;
            string p;
            sum<<path<<root->val;
            p=sum.str();
            depthsearch(root->left,p+"->");
        }  
        if(root->right!=NULL)
        {
            stringstream sum;
            string p;
            sum<<path<<root->val;
            p=sum.str();            
            depthsearch(root->right,p+"->");
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) 
    {
        if(root==NULL)
            return (vector<string>)0;
        stringstream sum;    
        sum<<root->val;
        string s="";//=sum.str();
        depthsearch(root,s);
        return ret;
    }
};

55.Binary Tree Paths-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 __init__(self):
        self.ret =[]  
    def depthsearch(self, root,path):
        if root==None:
            return
        path=path+str(root.val)
        if root.left==None and root.right==None:
            self.ret.append(path)
        if root.left!=None:
            self.depthsearch(root.left,path+"->")
        if root.right!=None:
            self.depthsearch(root.right,path+"->")
    
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        s=""
        self.depthsearch(root,s)
        return self.ret

56.Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

You may assume that the array does not change.

There are many calls to sumRange function.

56.Range Sum Query - Immutable-Analysis

给定一组数,返回对应下标范围内的数字的总和

但是这个题并不仅仅是到这里而已,他需要你自己写一个类对象,并且完成上面的操作

也就是要自己写一个构造函数,和sumRange的成员函数,感觉很简单啊?

实际上第一次写完以后就不通过,百度了一下,发现题目想要的是什么。

56.Range Sum Query - Immutable-Solution-C/C++

下面的代码,功能上没有问题,但是没通过,Time Limit Exceeded,竟然超时了,也就是说这里需要优化一下。

class NumArray 
{
public:
    vector<int> data;
    NumArray(vector<int> &nums)
    {
        data=nums;
    }

    int sumRange(int i, int j)
    {
        int sum=0;
        for(i;i<=j;i++)
            sum=sum+data[i];
        return sum;
    }
};

所以此题的解决办法就是提前计算好所有数字的和,存到vector中,在最后调用的时候用sum(j)-sum(i-1)就能得到i到j的总和了

class NumArray 
{
public:
    vector<int> data;
    NumArray(vector<int> &nums)
    {
        int sum=0,i=0;
        for(i=0;i<nums.size();i++)
        {
            sum=sum+nums[i];
            data.push_back(sum);
        }
    }

    int sumRange(int i, int j)
    {
        if(i==0)
            return data[j];
        return data[j]-data[i-1];
    }
};

56.Range Sum Query - Immutable-Solution-Python

class NumArray(object):
    def __init__(self, nums):
        """
        initialize your data structure here.
        :type nums: List[int]
        """
        data=0
        self.sum=[]
        for i in range(len(nums)):
            data=data+nums[i]
            self.sum.append(data)
        

    def sumRange(self, i, j):
        """
        sum of elements nums[i..j], inclusive.
        :type i: int
        :type j: int
        :rtype: int
        """
        if i==0:
            return self.sum[j]
        return self.sum[j]-self.sum[i-1]

Quote

http://blog.csdn.net/sunao2002002/article/details/46918645

http://www.bkjia.com/ASPjc/1031678.html

http://www.cnblogs.com/ganganloveu/p/4635328.html

http://my.oschina.net/Tsybius2014/blog/528708