New Leetcode Track[Easy]

深藏阁楼爱情的钟 2022-09-10 02:17 123阅读 0赞

> 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
> 
> so list can pop() and can use
> 
>     if i in ['[', '{', '(']:
> 
> to judge

[7. Reverse Integer]: https://leetcode.com/problems/reverse-integer/
[9. Palindrome Number]: https://leetcode.com/problems/palindrome-number/
[13. Roman to Integer]: https://leetcode.com/problems/roman-to-integer/
[14. Longest Common Prefix]: https://leetcode.com/problems/longest-common-prefix/
[20. Valid Parentheses]: https://leetcode.com/problems/valid-parentheses/