New Leetcode Track[Easy]-蒲公英云

I am a new research guy with a hard time in reading papers.
So there has little time for me to coding.
In order to master Python and keep coding, I try leetcode again.
I am trainning my English, so this blog wouldn’t show any Chinese.
Let’s begin and pythonic, it’s hard to start with everything.

9.3 7. Reverse Integer

First post a very amazing version, it’s really awsome!!!

def reverse(self, x):
   s=cmp(x,0);r=int(`s*x`[::-1]);return(r<2**31)*s*r

This is my first version. Because forgot the rule of leetcode, I used print rather than return.

flag, stack, tail = True, [], -1
if x < 0: flag, x = False, -x
while x > 0:
    stack.append(x % 10)
    tail += 1
    x //= 10
if flag is False: 
    print("-", end="")
if tail == -1: 
    print("0", end="")
for i in range(0, tail+1):
    print(stack[i], end="")
print("")

I try how to print without new line in Python.
print("", end="")

This is my final version, please check the Description

If reversing x x x causes the value to go outside the signed 32-bit integer range [ − 2 31 , 2 31 − 1 ] [-2^{31}, 2^{31} - 1] [−231,231−1], then return 0 0 0.

class Solution:
    def reverse(self, x: int) -> int:
        flag, stack, tail = True, [], -1
        if x < 0: flag, x = False, -x
        while x > 0:
            stack.append(x % 10)
            tail += 1
            x //= 10
        ans, mul = 0, 1
        for i in reversed(stack):
            ans += i*mul
            mul *= 10
        ans = 0 if abs(ans) > (2**31) else ans
        return ans if flag else -ans

9.9 9. Palindrome Number

long time not to code ACM problem
When I watch the describition, I always want to use a data struction figuring out the problem.
But I forgot it is a simple level question. Please let me be simple.

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0: return False
        origin, reverse = x, 0
        while x > 0:
            reverse = reverse * 10 + (x % 10)
            x = x // 10
        return origin == reverse

And there is a pythonic version:

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x<2**31-1 and x>-2**31 :
            if str(x) == str(x)[::-1]:
                return 1
            else:
                return 0
        else:
            return 0

reverse the string and determine equality

9.9 13. Roman to Integer

When I watch the Roman number, I want to use the map, but when I am coding I decided to use string directly. So my code is long.

class Solution:
    def romanToInt(self, s: str) -> int:
        n = len(s)
        roman = { 'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
        # for i, symbol in enumerate(s[::-1]):
        tail, ans = n - 1, 0
        while(tail > -1):
            if s[tail] == 'I':
                ans += 1
                tail -= 1
            if s[tail] == 'V' or s[tail] == 'X':
                temp = 5 if s[tail] == 'V' else 10
                while(tail > 0 and s[tail-1] == 'I'):
                    temp -= 1
                    tail -= 1
                ans += temp
                tail -= 1
            if s[tail] == 'L' or s[tail] == 'C':
                temp = 50 if s[tail] == 'L' else 100
                while(tail > 0 and s[tail-1] == 'X'):
                    temp -= 10
                    tail -= 1
                ans += temp
                tail -= 1
            if s[tail] == 'D' or s[tail] == 'M':
                temp = 500 if s[tail] == 'D' else 1000
                while(tail > 0 and s[tail-1] == 'C'):
                    temp -= 100
                    tail -= 1
                ans += temp
                tail -= 1
            pass
        return ans

The fastest version in leetcode submissions. Record the previous char is a useful method.

class Solution:
    def romanToInt(self, s: str) -> int:
        convert = { 'M': 1000, 'D': 500, 'C': 100, 'L': 50, 'X' : 10, 'V': 5, 'I': 1}
        prevChar = 'I'
        answer = 0
        for char in s[::-1]:
            if convert[char] >= convert[prevChar]:
                answer += convert[char]
                prevChar = char
            else:
                answer -= convert[char]
        return answer

9.13 14. Longest Common Prefix

Note the boundary conditions!!!

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # n = len(strs)
        if len(strs) == 1: return strs[0]
        minn = 1e7
        for i in strs:
            minn = min(len(i),minn)
        ans = ""
        for i in range(minn):
            now = strs[0][:i+1]
            flag = 1
            for s in strs:
                if now != s[:i+1]:
                    flag = 0
                    break
            if flag == 1:
                ans = now
            else: break
        return ans

The fastest version, use the set to count the number of the different alpha in the same position. If the number equal one, the alpha is the same.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        minLength = min([len(s) for s in strs])
        prefix = ''
        for n in range(minLength):
            c = list(set([strs[i][n] for i in range(len(strs))]))
            if len(c) == 1:
                prefix += c[0]
            else:
                break
        return(prefix)

9.14 20. Valid Parentheses

stack please think twice before submit

class Solution:
    def isValid(self, s: str) -> bool:
        stack, tail = [], -1
        for c in s:
            if tail == -1:
                stack.append(c)
                tail += 1
            elif stack[tail] == '(' and c == ')':
                stack = stack[:tail]
                tail -= 1
            elif stack[tail] == '{' and c == '}':
                stack = stack[:tail]
                tail -= 1
            elif stack[tail] == '[' and c == ']':
                stack = stack[:tail]
                tail -= 1
            elif c == '(' or c == '{' or c == '[':
                stack.append(c)
                tail += 1
            else: return False
        return True if tail == -1 else False

The fastest version:

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for i in s:
            if i in ['[' , '{' , '('] :
                stack.append(i)
            elif stack :
                if i == ']' and stack[-1] == '[':
                    stack.pop()
                elif i == ')' and stack[-1] == '(':
                    stack.pop()
                elif i == '}' and stack[-1] == '{':
                    stack.pop()
                else:
                    return False
            else:
                return False
        if stack:
            return False
        else:
            return True