分类：leetcode

LeetCode第12,13题:Integer to Roman and Roman to Integer总结

2015年11月9日 by JayceeZ·0评论

这两道题明显是一对。。。放一起

题目一 Integer to Roman

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999. 阅读全文

LeetCode第11题:Container With Most Water总结

2015年11月9日 by JayceeZ·0评论

题目

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

大意：有n个非负的整数a1到an，ai每个代表i处的高度，(i,ai)和(i,0)是线段i的两个端点，所有任意两个线段i可以和x轴组成一个容器，找出能装最多水的容器。注意：不能倾斜容器。

思路

这道题所求的容积和容器下边长度（两个线段的横坐标距离）和侧边最小长度有关（类似木桶效应）。
所以容积 = abs(i2 – i1) * min(ai1, ai2)，我们要找出的就是用那两条线段做边界时，这个容器最大，求出这个最大的容积。阅读全文

LeetCode第9题:Palindrome Number总结

2015年11月1日 by JayceeZ·0评论

题目

Determine whether an integer is a palindrome. Do this without extra space.

大意：判断一个整数是不是回文的。。

吐槽：

同第7题：用Python简直就是作弊啊。。。。。

代码

Python

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        x = str(x)
        x = x.strip()
        if x[::1] == x[::-1]:
            return True
        else:
            return False

class Solution(object):

def isPalindrome(self, x):

"""

:type x: int

:rtype: bool

"""

x = str(x)

x = x.strip()

if x[::1] == x[::-1]:

return True

else:

return False

阅读全文

LeetCode第8题:String to Integer (atoi)总结

2015年11月1日 by JayceeZ·0评论

题目：

Implement atoi to convert a string to an integer.

大意：就是手动实现C语言里常用的atoi函数。。。

思路和吐槽：

我最讨厌这种了，完全的信息不对称。。要讨论的情况只有不断提交才知道出题人什么意思，我怎么知道你要求的是什么，况且这是算法题又不是工程题。。。。幸亏这道题比较简单，多试几次也不太费时。

代码

Python

class Solution(object):
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        str = str.strip()
        if not str:
            return 0
        ans = []
        neg = "-"
        pos = "+"
        ch = str[0]
        if  ch == neg:
            c = -1
        elif ch == pos:
            c = 1
        elif ch.isdigit():
            ans.append(ch)
            c = 1
        else:
            return 0
        for ch in str[1:]:
            if ch.isdigit():
                ans.append(ch)
            else:
                break
        ans_str = "".join(ans)
        if ans_str:
            ans =  c * int(ans_str)
            if ans > 2147483647:
                return 2147483647
            elif ans < -2147483648:
                return -2147483648
            else:
                return ans
        else:
            return 0

class Solution(object):

def myAtoi(self, str):

"""

:type str: str

:rtype: int

"""

str = str.strip()

if not str:

return 0

ans = []

neg = "-"

pos = "+"

ch = str[0]

if ch == neg:

c = -1

elif ch == pos:

c = 1

elif ch.isdigit():

ans.append(ch)

c = 1

else:

return 0

for ch in str[1:]:

if ch.isdigit():

ans.append(ch)

else:

break

ans_str = "".join(ans)

if ans_str:

ans = c * int(ans_str)

if ans > 2147483647:

return 2147483647

elif ans < -2147483648:

return -2147483648

else:

return ans

else:

return 0

阅读全文

LeetCode第7题:Reverse Integer总结

2015年11月1日 by JayceeZ·0评论

题目

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

大意：就是把数字倒过来。。。

思路和吐槽

只有吐槽：用Python做简直是太简单了，简直就是在作弊，，，如果我十天之内没用c++再做一遍，我肯定是白做了这道题阅读全文

LeetCode第6题:ZigZag Conversion总结

2015年11月1日 by JayceeZ·0评论

题目

The string “PAYPALISHIRING” is written in a zigzag pattern on a given >number of rows like this: (you may want to display this pattern in a >fixed font for better legibility)

P A H N
A P L S I I G
Y I R
And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a >number of rows:

string convert(string text, int nRows);
convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”. 阅读全文

LeetCode第4题:Median of Two Sorted Arrays总结

2015年10月27日 by JayceeZ·0评论

题目

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

大意

有两个排好序的数组nums1和nums2，分别长m和n.找出两个数列的中值，复杂度应该为O(log (m+n)).

思路

这道题虽然知道应该是分治的思路，我没有做出来，找了一下discuss里面的题解，看了一下，打算把有关的分治书上好好看过之后在回顾之后再更新下这道题。
这里贴出discuss的两个帖子链接，这两个是discuss里面顶的最多了两篇。第一篇思路比较正常，翻译了下。第二篇的思路更是很巧妙的避开了奇偶数的讨论，但不知道是否具有普适性。阅读全文

LeetCode第5题:Longest Palindromic Substring总结

2015年10月27日 by JayceeZ·0评论

题目：

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

大意：就是找出字符串中最大的回文子字符串

吐槽：

这应该是一道经典的算法题，可是我还是没有什么好办法，可见我真的是太菜了。哎。。。用了一个O( n^2 )的解法，妥妥的超时了。。。后来看了网上的有关文章和discuss里面的代码，修改了版本。

暴力超时版Python代码：

（肯定是我自己写的）阅读全文

LeetCode第3题:Longest Substring Without Repeating Characters总结

2015年10月26日 by JayceeZ·0评论

题目：

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

大意：给出一个字符串，找出不包含重复字母的最长字串，输出字符串的长度。

这道题是一个字符串的题，好久不写明显手生，所以一些细节耗费了很多时间去调试，希望自己慢慢熟悉起来。阅读全文

LeetCode第2题:Add Two Numbers总结

2015年10月25日 by JayceeZ·0评论

题目

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

大意：给出两个从低位到高位排列链表形式的多位数，相加后按原格式输出。阅读全文