Ywc's blog

LeetCode的一些记录

Word count: 1.2k / Reading time: 5 min
2020/11/28 Share

一组数数组的动态和

给你一个数组 nums 。数组「动态和」的计算公式为:runningSum[i] = sum(nums[0]…nums[i]) 。
请返回 nums 的动态和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 1:

输入:nums = [1,2,3,4]
输出:[1,3,6,10]
解释:动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。
示例 2:

输入:nums = [1,1,1,1,1]
输出:[1,2,3,4,5]
解释:动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。
示例 3:

输入:nums = [3,1,2,10,1]
输出:[3,4,6,16,17]
1
2
3
4
5
6
7
class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
if not nums:
return []
for i in range(1,len(nums)):
nums[i]=nums[i]+nums[i-1]
return nums

寻找数组的中心索引

解题思路:先求出所有数的总和,然后遍历数组,如果遍历数的左边*2 + 遍历数 == 总和 , 那这个数就一定是中心索引。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
S=sum(nums)
leftnums=0
for i in range(len(nums)):
if leftnums *2 + nums[i] == S:
return i
else:
leftnums += nums[i]
else:
return -1

sum() 方法对序列进行求和计算

Reference: https://www.pythonheidong.com/blog/article/249069/53202e9ddbc9740732b4/

两数之和

方法一:使用最容易理解的遍历数组进行查找

1
2
3
4
5
6
7
8
9
10
def solution(nums,target):
#如果列表长度小于2,则直接结束
if len(nums) < 2:
return
#两次循环列表,分别对列表中的所有可能的数字进行相加
#循环两次列表对应的时间复杂度为O(n²)
for i in range(0, len(nums) - 1):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]

方法二:使用哈希表,通过以空间换取速度的方式,可以将查找时间从 O(n)降低到 O(1)。在python中列表字典的即为哈希类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(nums,target):
#新建立一个空字典用来保存数值及其在列表中对应的索引
dict1 = {}
#遍历一遍列表对应的时间复杂度为O(n)
for i in range(0, len(nums)):
#相减得到另一个数值
num = target - nums[i]
#如果另一个数值不在字典中,则将第一个数值及其的索引报错在字典中
#因为在字典中查找的时间复杂度为O(1),因此总时间复杂度为O(n)
if num not in dict1:
dict1[nums[i]] = i
#如果在字典中则返回
else:
return [dict1[num], i]

整数反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def reverse(self, x: int) -> int:
if x == 0:
return 0
if x > 0:
x = str(x)
x = x[::-1]
else:
x = str(x)
x = x[1:] #为了删除负号
x = x[::-1]
x = '-' + x
x = int(x)
if -2**31 < x < 2**31-1: #为了不超出32位整数
return x
else:
return 0

利用R = X[::-1]这种方法对X(X必须是字符串)进行一个反转复制的操作
python 中的[::-1]
彻底搞懂切片操作

回文数

1
2
3
4
5
6
7
8
9
10
11

class Solution:
def isPalindrome(self, x: int) -> bool:
if x<0:
return False
x=str(x)
y=x[::-1]
if x==y:
return True
else:
return False

罗马数字转整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def romanToInt(self, s: str) -> int:
d = {'I': 1, 'IV': 4, 'V': 5, 'IX': 9, 'X': 10, 'XL': 40, 'L': 50, 'XC': 90, 'C': 100, 'CD': 400, 'D': 500, 'CM': 900, 'M': 1000}
result = 0
i = 0
while i < len(s):
#查看当前位和下一位的字符
str1 = s[i:i+2]
#如果当前位置是特殊情况,那么返回其在字典中对应值,并且下一次从特殊字符之后一位开始索引
if str1 in d:
result += d.get(str1)
i += 2
#如果当前位不是特殊情况,那么只返回当前位的数值
else:
result += d[s[i]]
i += 1
return result

最长公共前缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs: #边界条件判断,若字符串为空,则返回空
return ""
short_word=min(strs,key=len) #筛选出长度最短的单词然后进行遍历
for i,e in enumerate(short_word): #遍历长度最短的单词
for others in strs: #遍历列表中的其他字符串
if others[i]!=e: #一旦出现非公共字符,返回公共字符
return short_word[:i]
return short_word #遍历结束后依然没匹配到非公共字符,则返回整个字符

enumerate
enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列,同时列出数据和数据下标,一般用在 for 循环当中。

Reference

原文作者: Ywc

原文链接: https://yinwc.github.io/2020/11/28/leetcodepractice/

发表日期: November 28th 2020, 10:15:40 am

版权声明:

CATALOG
  1. 1. 一组数数组的动态和
  2. 2. 寻找数组的中心索引
  3. 3. 两数之和
  4. 4. 整数反转
  5. 5. 回文数
  6. 6. 罗马数字转整数
  7. 7. 最长公共前缀
  8. 8. Reference