Array And Strings
2020-01-18 本文已影响0人
inspiredhss
- Two Sum
# 1. Two Sum
# array of integers,specific target ==> return indices
class Solution:
def twoSum(self, num, target):
map = {}
for i in range(len(num)):
if num[i] not in map: # 对于{}，用in, 用map[key]
map[target - num[i]] = i
else:
return map[num[i]], i # 返回的是位置，字典通过“数值”查询“位置”
return -1, -1 #循环所有都没有
- Valid Palindrome
# Valid Palindrome
# only alphanumeric characters and ignoring cases.
# Input: "A man, a plan, a canal: Panama"=>Output: true
class Solution:
def isPalindrome(self, s: str) -> bool:
l, r = 0, len(s)-1 # 左右两头向内比较
while l < r:
while l < r and not s[l].isalnum(): #一直移动直至是字母或数字
l += 1
while l <r and not s[r].isalnum(): #一直移动直至是字母或数字
r -= 1 # 左右各自滤除非字母数字
if s[l].lower() != s[r].lower():
return False #有不同 则退出
l +=1; r -= 1 #相同则继续
return True #全部相同则正解
- String to Integer(atoi)
# String to Integer (atoi)
# converts a string to an integer.
# discards until the first non-whitespace character
# initial plus or minus sign
class Solution:
def myAtoi(self, s):
ls = list(s.strip())
if len(ls) == 0 : return 0 #
sign = -1 if ls[0] == '-' else 1 #正负问题
if ls[0] in ['-','+'] : del ls[0] #正负问题
ret, i = 0, 0 #遍历及其结果
while i < len(ls) and ls[i].isdigit():
ret = ret*10 + ord(ls[i]) - ord('0') #逐字符拼入数字
i += 1
return max(-2**31, min(sign * ret,2**31-1))#长度范围内
- Reverse String
# Reverse String
# Input: ["h","e","l","l","o"]
# Output: ["o","l","l","e","h"]
class Solution:
def reverseString(self, s):
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left, right = left + 1, right - 1
- Reverse Words in String
# 151. Reverse Words in a String
# Input: " hello world! "
# Output: "world! hello"
class Solution:
def reverseWords(self, s: str) -> str:
return " ".join(s.split()[::-1])
- Reverse Words in a String II
# Reverse Words in a String II
# Input: ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
# Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
class Solution:
def reverseWords(self, s: List[str]) -> None:
self.reverse(s, 0, len(s) - 1)
beg = 0
for i in range(len(s)):
if s[i] == ' ':
self.reverse(s, beg, i-1)
beg = i + 1
elif i == len(s) -1:
self.reverse(s, beg, i)
def reverse(self, s, start, end):
while start < end:
s[start], s[end] = s[end], s[start]
start += 1
end -= 1
- Valid Parentheses
# 20. Valid Parentheses
# string containing just the characters '(', ')', '{', '}', '[' and ']'
# determine if the input string is valid.
# correct order&same type
class Solution:
def isValid(self, s: str) -> bool:
stack = []
dict = {"]":"[", "}":"{", ")":"("}
for char in s:
if char in dict.values():
stack.append(char)
elif char in dict.keys():
if stack == [] or dict[char] != stack.pop():
return False
else:
return False
return stack == []
- Longest Palindromic Substring
# 5. Longest Palindromic Substring
class Solution:
def longestPalindrome(self, s: str) -> str:
res = ""
for i in range(len(s)):
# odd case, like "aba"
tmp = self.helper(s, i, i)
if len(tmp) > len(res):
res = tmp
# even case, like "abba"
tmp = self.helper(s, i, i+1)
if len(tmp) > len(res):
res = tmp
return res
# get the longest palindrome, l, r are the middle indexes
# from inner to outer
def helper(self, s, l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return s[l+1:r]
- Group Anagrams
# 49. Group Anagrams
# Given an array of strings, group anagrams together.
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = {}
for w in sorted(strs):
key = tuple(sorted(w))
d[key] = d.get(key, []) + [w]
return d.values()
- Trapping Rain Water
# # Trapping Rain Water
# # elecation map; width 1; trap??
# # ==>300T/60=>5h
# 输入：height_List；
# 挖掘边界 最外层==>l_index&r_index
# 挖掘固定参考边界 固定一侧 内层&&l_max&r_max&&ans
# 挖掘具体移动l+=或边界更新 及取值ans+= &&height[l]&height[r]&ans
class Solution:
def trap(self, height: List[int]) -> int:
# 结果&边界点&边界值
ans = 0
l,r = 0 , len(height) -1
l_max, r_max = 0,0
# 边界点内；
while l < r:
# 右侧高点
if height[l] < height[r]:
# 左侧高点置换
if height[l] >= l_max:
l_max = height[l]
# 至左侧积水
else:
ans += l_max - height[l]
l += 1
# 左侧高点
else:
# 右侧高点置换
if height[r] >= r_max:
r_max = height[r]
else:
ans += r_max - height[r]
r -= 1
return ans
- Set Matrix Zeroes
# Set Matrix Zeroes
# Given a m x n matrix,
# element is 0, set its entire row and column to 0.
# Do it in-place.
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
# First row has zero?
m, n, firstRowHasZero = len(matrix), len(matrix[0]), not all(matrix[0])
# Use first row/column as marker, scan the matrix
for i in range(1, m):
for j in range(n):
if matrix[i][j] == 0:
matrix[0][j] = matrix[i][0] = 0
# Set the zeros
for i in range(1, m):
for j in range(n - 1, -1, -1):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# Set the zeros for the first row
if firstRowHasZero:
matrix[0] = [0] * n
- Rotate Image
# Rotate Image
# Given an n x n 2D matrix representing an image.
# Rotate the image by 90 degrees (clockwise).
class Solution:
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
n = len(matrix[0])
for i in range(n // 2 + n % 2):
for j in range(n // 2):
tmp = matrix[n - 1 - j][i]
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - j - 1]
matrix[n - 1 - i][n - j - 1] = matrix[j][n - 1 -i]
matrix[j][n - 1 - i] = matrix[i][j]
matrix[i][j] = tmp
13.Spiral Matrix
# Spiral Matrix
# Given a matrix of m x n elements (m rows, n columns),
# Return all elements of the matrix in spiral order.
class Solution:
def spiralOrder(self, matrix):
if not matrix or not matrix[0]:
return []
ans = []
m, n = len(matrix), len(matrix[0])
u, d, l, r = 0, m - 1, 0, n - 1
while l < r and u < d:
ans.extend([matrix[u][j] for j in range(l, r)])
ans.extend([matrix[i][r] for i in range(u, d)])
ans.extend([matrix[d][j] for j in range(r, l, -1)])
ans.extend([matrix[i][l] for i in range(d, u, -1)])
u, d, l, r = u + 1, d - 1, l + 1, r - 1
if l == r:
ans.extend([matrix[i][r] for i in range(u, d + 1)])
elif u == d:
ans.extend([matrix[u][j] for j in range(l, r + 1)])
return ans
