注:标题即题目链接
1. 两数之和
我采取了暴力的遍历方法:
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
answer = [-1,-1]
size = len(nums)
for key in range(size):
for key2 in range(key+1,size):
if nums[key] + nums[key2] == target:
answer[0] = key
answer[1] = key2
return answer
难点以及解决方法:
暂无。
做这题的时候我一个语法点搞错了,整数列表是不能用for key,vale in nums
来进行索引的。
2. 两数相加
下面这段程序是带了测试样例的,大家拿去跑的时候可以进行修改测试:
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
answer = ListNode()
answer_out = answer
add_flag = 0
final_val = 0
while l1.next != None or l2.next != None:
if (l1.next == None):
l1.__init__(l1.val, ListNode())
elif (l2.next == None) :
l2.__init__(l2.val, ListNode())
temp = l1.val + l2.val
final_val = (temp + add_flag) % 10
answer.__init__((final_val), ListNode())
answer = answer.next
add_flag = (temp + add_flag) // 10
print("final_val", final_val)
l1 = l1.next
l2 = l2.next
answer.val = (l1.val + l2.val + add_flag) % 10
add_flag = (l1.val + l2.val + add_flag) // 10
if add_flag != 0:
temp = ListNode(add_flag, None)
answer.next = temp
return answer_out
if __name__ == '__main__':
ret = Solution()
a = [9, 9, 9, 9, 9, 9, 9]
b = [9,9,9,9]
l1 = ListNode()
l2 = ListNode()
temp1 = l1
temp2 = l2
for i in range(len(a)):
if i == len(a)-1:
l1.val = a[i]
l1.next = None
else:
l1.__init__(a[i], ListNode())
l1 = l1.next
for i in range(len(b)):
if i == len(b)-1:
l2.val = b[i]
l2.next = None
else:
l2.__init__(b[i], ListNode())
l2 = l2.next
answer = ret.addTwoNumbers(temp1, temp2)
while answer.next != None:
print(answer.val)
answer = answer.next
print(answer.val)
图解:
难点以及解决方法:
1:进位;进位我设置了一个数值,每次进行数字相加的时候都会考虑上一位的进位;
2:不等长;我通过将短的链表补长从而完成计算;
3:最后一位的进位;如果最后一位需要进位的话add_flag
是不为0的,因此就在输出链表的最后添加一个新的节点;
4:输入链表的格式;输入链表是没有尾节点的,所以处理不等长链表在链表的最后一位增加节点时注意不要改变输入链表最后一个节点的数值;
3. 无重复字符的最长子串
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
max_len = 0
temp_list = ""
for i in range(len(s)):
temp_list = temp_list + s[i]
for j in s[i+1:]:
if j not in temp_list:
temp_list = temp_list + j
if max_len < len(temp_list):
max_len = len(temp_list)
else:
temp_list = ""
break
if max_len == 0 and len(s) > 0:
max_len = 1
return max_len
if __name__ == '__main__':
ret = Solution()
print(ret.lengthOfLongestSubstring('aaab'))
难点以及解决方法:
暴力解决,不过用了一个trick,当字符串里字符都一样的时候我的算法会输出结果0,因此我就直接判断非空字符串且连续不重复字符串大小为0的时候,直接将输出强制设置成1。
评论(0)
您还未登录,请登录后发表或查看评论