作者：mobiledu2502931987 | 来源：互联网 | 2023-01-22 11:58
由于之前对算法题接触不多,因此暂时只做easy和medium难度的题.1.TwoSum时间复杂度:O(n),python中的字典其实就是哈希表的应用,所以我们通过字典用哈希表来降低查找的时间复杂
由于之前对算法题接触不多,因此暂时只做easy和medium难度的题.
1.Two Sum
时间复杂度:O(n),python中的字典其实就是哈希表的应用,所以我们通过字典用哈希表来降低查找的时间复杂度
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
d = {}
for i, n in enumerate(nums):
m = target - n
if m in d:
return [d[m], i]
else:
d[n] = i
Two Sum
2.Add Two Numbers
思路非常简单,先将两个单链表中的数字分别提取出来求和,然后将求得的和存入一个单链表,实际上相加这一步也可以直接在原链表中完成,只需要添加判断条件while(l1 or l2 or carry)即可.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
node1 = l1
node2 = l2
l3 = ListNode(0)
l3.next = ListNode(0)#[0],[0]的特殊情况
node3 = l3
sum1 = 0
coe = 1
while not node1 is None:
sum1 += node1.val * coe
coe *= 10
node1 = node1.next
sum2 = 0
coe =1
while not node2 is None:
sum2 += node2.val * coe
coe *= 10
node2 = node2.next
sum = sum1 + sum2
while sum > 0:
node3.next = ListNode(sum % 10)
node3 = node3.next
sum //= 10
return l3.next
Add Two Numbers
3.Longest Substring Without Repeating Characters
一开始没有想到用字典,而是直接用str来存储字串,时间复杂度是O(n^2),后来用字典将时间复杂度降到了O(n).注意到仅当字典中出现重复值且该重复值在strat区段里时才移动start.另外用了Sliding Window的思想,每次将strat移动到重复值的下一位置.
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
start = 0
max_length = 0
substring = {}
for i, c in enumerate(s):
if c in substring and start <= substring[c]:#只有当重复值是在start后面出现时才移动start
start = substring[c] + 1#Slding Window的思想
else:
max_length = max(max_length, i - start + 1)
substring[c] = i
return max_length
Longest Substring Without Repeating Characters
5.Longest Palindromic Substring
最长回文子串问题,一开始我的思路如下:回文子串的特点是首尾字母相同,所以我对每一个字母都找到位于它后面的相同字母,利用切片判断这一段是否为回文子串(str[i:j]==str[i:j][::-1]).虽然AC了但是时间复杂度很高,主要是因为str.find操作非常耗时.
后来看了Solution发现这是一道可以用动态规划解决的问题,思路是若s是回文字串,令s'=s加上s左右两侧的两个字母,如果这两个字母相同则s'也是回文字串.重写代码如下:
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
max = 0
palindromic = '' if len(s) == 0 else s[0]
for i in range(len(s)):
length = 1
while i - length >=0 and i + length and s[i-length] == s[i+length]:
tmp = s[i-length:i+length+1]
if len(tmp) > max:
max = len(tmp)
palindromic = tmp
length += 1
length = 1
while i - length + 1 >=0 and i + length and s[i-length+1] == s[i+length]:
tmp = s[i-length+1:i+length+1]
if len(tmp) > max:
max = len(tmp)
palindromic = tmp
length += 1
return palindromic
Longest Palindromic Substring
这道题还有经典的Manacher算法,可以看这篇文章.Discuss里的算法实现在这里.
另外在Discuss里发现了另一种做法,思路是一段回文字符串的后面新增了一个字母,如果新字符串仍是回文字符串的话只有两种可能:形如bb+b,也就是多了一个字母,或形如a(bb)+a,算上原回文字符串的前一个字母共多了两个字母.基于这个思路可以写出代码.因为用到了切片,在题例上运行的速度甚至比Manacher算法还快.
6.ZigZag Conversion
一道将字符串做之字形排列的题目.我们用n表示行数,将排列后得到的字符串分为完整竖列和折线两部分.每个完整竖列有n个数,每两个完整竖列之间的折线有n-2列,每列一个数,因此每两个完整竖列中同一行的数的间隔是n+n-2=2n-2.同时我们发现,除了第一行和最后一行之外的第i行都有折线,第i行的第一个折线是第2n-i个数.于是可以遍历输出每一行,判定条件是这一行我们要输出的数字是否超出了字符串的长度.
class Solution:
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
zigzag = ''
if numRows == 1 or numRows == 0 or numRows >= len(s):
return s
space = 2 * numRows - 2
for i in range(1,numRows+1):
n = 0
if i == 1 or i == numRows:
while i + n * space <= len(s):
zigzag += s[i+n*space-1]
n += 1
else:
while i + n * space <= len(s):
zigzag += s[i+n*space-1]
if (2 * numRows - i) + (n * space) <= len(s):
zigzag += s[(2*numRows-i)+(n*space)-1]
n += 1
return zigzag
ZigZag Conversion
ZigZag Conversion
7.Reverse Integer
非常简单的一道题
class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
tmp = abs(x)
sum = 0
while tmp > 0:
sum = sum * 10 + tmp % 10
tmp = tmp // 10
sum = sum if x >= 0 else -sum
return sum if sum <2**31 and sum > -2**31 else 0
Reverse Integer
8.String to Integer(atoi)
我的思路是设定标志位start=0和符号位sign,遍历字符串,当start=0时遇到空格则continue,遇到+则记录sign=1,遇到-则记录sign=-1,遇到数字则记录数字;当strat=1时代表已经找到了第一个数字或符号位,此时遇到除数字之外的字符都break,遇到数字则继续记录数字.注意我们得到的整数值不能超过INT_MAX和INT_MIN.后来发现其实用str.strip()函数来去除字符串头尾的空格会更方便.
class Solution(object):
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
ans = 0
start = 0
sign = 0
if str.isspace() is True:
print(0)
for i in str:
if start == 0:
if i.isspace() is True:
continue
if i == '+':
sign = 1
elif i == '-':
sign = -1
elif i.isdigit() is True:
sign = 1
ans = ans * 10 + int(i)
else:
break
start = 1
else:
if i.isdigit() is True:
ans = ans * 10 + int(i)
else:
break
ans = sign * ans
if ans >= 2147483647:
return 2147483647
elif ans <= -2147483648:
return -2147483648
else:
return ans
String to Integer(atoi)
9.Palindrome Number
题目要求不能用额外的空间,否则可以利用python的字符串切片轻松解决.我的思路是求出该整数的位数,判断第一位数和最后一位数是否相同,如果相同则将位数/100,然后将原数字的首尾两个数删除,最后如果位数<1说明是回文数.
class Solution(object):
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x < 0:
return False
high = 1
while x / high >= 10:
high *= 10
while x // high == x % 10:
x = x % high // 10
high /= 100
if high <1:
return True
return False
Palindrome Number
11.Container With Most Water
这到题用到了双指针的思想.我们在数轴的两端分别放置一个left指针和right指针,因为容器容量=较短边*两边位置之差,所以如果移动较大的那个指针,那么容量必定在减小.因此我们不断往中间移动较小的指针才有可能使容量变大,直到两指针相遇为止.
对于算法合理性的逻辑推理:我们假设在best_left和best_right位置取到最大容量,那么left指针到达best_left位置或right指针到达best_right位置至少有一种会发生.不妨令left指针到达best_left位置,此时right指针的位置有三种可能:
- 位于best_right位置左侧.这说明best_right位置已经被计算过,成立.
- 位于best_right位置,同上.
- 位于best_right位置右侧.因为left指针移动的条件是right指针所在边大于left指针所在边,如果符合此条件,且right指针在best_right右侧,那么当前容量一定大于假设中的最大容量,与假设矛盾.所以left指针必定会一路移动至best_right位置.
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
left = 0
right = len(height) - 1
most = 0
while left != right:
h = min(height[left], height[right])
most = max(most, h * (right - left))
if height[left] < height[right]:
left += 1
else:
right -=1
return most
Container With Most Water
12.Integer to Roman
比较简单的一道题.我的思路是判断当前位数,改变代表1/5/10的字符然后逐位输出.也可以直接将每位上的各种字符表示存在列表里,然后直接取出.
class Solution(object):
def intToRoman(self, num):
"""
:type num: int
:rtype: str
"""
carry = 1
roman = ''
while num != 0:
n = num % 10
num //= 10
if carry == 1:
numeral_1 = 'I'
numeral_5 = 'V'
numeral_10 = 'X'
elif carry == 10:
numeral_1 = 'X'
numeral_5 = 'L'
numeral_10 = 'C'
elif carry == 100:
numeral_1 = 'C'
numeral_5 = 'D'
numeral_10 = 'M'
else:
numeral_1 = 'M'
numeral_5 = ''
numeral_10 = ''
if 1 <= n <= 3:
roman = numeral_1 * n + roman
elif n == 4:
roman = numeral_1 + numeral_5 + roman
elif 5 <= n <= 8:
roman = numeral_5 + numeral_1 * (n - 5) + roman
elif n == 9:
roman = numeral_1 + numeral_10 + roman
carry *= 10
return roman
Integer to Roman
13.Roman to Integer
非常无聊的一道题.比较简单的方法是写非常多的if语句来判断,或者将罗马数字与对应的十进制数字存入字典来转换.下面是我在discuss里看到的一个方案,巧妙利用了罗马数字"大数前面的小数用来减,大数后面的小数用来加"这个特点.
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
roman_map = {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000,
}
result = 0
last_num = None
for char in s:
current_num = roman_map[char]
if last_num is None or last_num >= current_num:
result += current_num
elif last_num < current_num:
result += current_num - 2 * last_num
last_num = current_num
return result
Roman to Integer
京公网安备 11010802041100号