Letcode刷题入门篇
开始准备刷Letcode的题目，入门基础题，从简单的题目开始做，先考虑用python解题
一、两数之和
使用最简单的暴力解法，复杂度为O(n^2)，时间复杂度更低的解法，借用List 的相关函数求解，或使用hash求解，参考博客.
hashmap = {}
for id,num in enumerate(nums):
hashmap[num] = id
for i in range(len(nums)):
j = hashmap.get(target-nums[i])
if j!=None and j!=i:
return [i,j]
- 一遍循环完成，对于遍历到的位置i的数据，每次找其位置之前的数据
hashmap = {}
for i,num in enumerate(nums):
j = hashmap.get(target-num)
if j!= None: return [i,j]
hashmap[num] = i
二、整数反转
int32的数值取值范围为“-2147483648”到“2147483647”；而int64的数值取值范围为“-9223372036854775808”到“9223372036854775808”
三、回文数
自解法，整数转成list,头尾对比，参考后和上一题整数反转有类似求解整数反转的方法：
n,num = 0,x
while (x>0):
n = n * 10 + x % 10
x = x / 10
四、罗马数字转整数
知识拓展，罗马数字的表示:
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
特别的： IV 4、IX 9、XL 40、XC 90、CD 400、CM 900
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
mapping = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}
num = 0
for _ in s:
num = num + mapping[_]
#IV 4、IX 9、XL 40、XC 90、CD 400、CM 900
if "IV" in s or "IX" in s:
num = num - 2
if "XL" in s or "XC" in s:
num = num - 20
if "CD" in s or "CM" in s:
num = num - 200
return num
五、最长公共前缀
模拟字符串对比求最长前缀即可,或对所有字符串按字典排序，比较第一个和最后一个字符串的最长公共前缀
#字符串排序
def longestCommonPrefix(self, strs):
strs = sorted(strs)
com = ""
for i in range(len(strs[0])):
if strs[0][i] == strs[-1][i]: com += strs[0][i]
else: break
return com
六、有效的括号
括号匹配问题，每次遇到右括号，找最近的左括号匹配，判断输出，刚开始忽略了有多余的左括号或多余的右括号的情况，参考其他解法，用栈模拟字符串匹配。
#非栈模拟，开销大，运行速度慢
mapping = {"]":"[","}":"{",")":"("}
left = []
for i in range(len(s)):
if s[i] in ["]","}",")"]:
if len(left) <= 0 : return False #判断右括号溢出
if s[left[-1]]==mapping[s[i]]:
left.pop()
else: return False
else: left.append(i)
return len(left)==0 #判断左括号溢出
#栈模拟
stack = ["$"] #加栈顶，防越界访问
mapping = {"]":"[","}":"{",")":"("}
for _ in s:
if _ in ["(","{","["]:
stack.append(_)
else:
if stack[-1] == mapping[_]:
stack.pop()
else: return False
return len(stack)==1
七、合并两个有序链表
递归求解，对链表连接相关不太熟悉，基本思路就是判断两个链接值小的加入主链表，最后链接剩下非空的链表，参考求解：
if l1 and l2:
if l1.val > l2.val: l1, l2 = l2, l1
l1.next = self.mergeTwoLists(l1.next, l2)
return l1 or l2
Note：要复习数据结构方面知识，数据结构方面的题目需要多练
删除有序数组中的重复项
模拟下标移动，i，j 两个下标移动
def removeDuplicates(self, nums: List[int]) -> int:
i,j = 1,0
while i < len(nums):
if nums[i] == nums[j]:
i += 1
else:
j = j + 1
nums[j] = nums[i]
return j + 1
八、移除数组
求解方法类似上题，修改移动的判断条件即可：
def removeElement(self, nums: List[int], val: int) -> int:
i,j = 0,0
while i < len(nums):
#print(i,j)
if nums[i] == val:
i += 1
else:
nums[j] = nums[i]
j = j + 1
i = i + 1
return j
九、最大子序合
贪心法求解，如果和为负则重新计算：
def maxSubArray(self, nums: List[int]) -> int:
sum = 0
result = -inf
for _ in nums:
sum += _
result = max(sum,result)
if sum<0:
sum = 0
return result
十、合并有序数组（递减）
通过下标模拟访问数组即可，考虑到求递减的序列，考虑倒序填数组：
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
#i:nums1 j:nums2
i,j,k = m-1,n-1,m+n-1
while i>=0 and j>=0:
if nums1[i] > nums2[j] :
nums1[k] = nums1[i]
i = i - 1
k = k - 1
else:
nums1[k] = nums2[j]
j = j - 1
k = k - 1
while i >=0 :
nums1[k] = nums1[i]
i = i - 1
k = k -1
while j >= 0 :
nums1[k] = nums2[j]
j = j - 1
k = k - 1
return nums1
