本文最后更新于:3 years ago
两数之和
题目:给定一个整数数组 nums
和一个目标值 target
,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum
暴力解法
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(len(nums)):
if (j==i):
break
else:
if target - nums[i] == nums[j]:
return [i,j]
时间复杂度O(n)解法
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {} #key:num value:index
for index,num in enumerate(nums):
another_num = target - nums[index]
if another_num in hashmap:
return [hashmap[another_num],index]
hashmap[num] = index
return None
两数相加
题目:给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/add-two-numbers
我的解法
首先将l1
和l2
字符串话,接着将每个字符串逆转然后转成int
类型,再加sl1
和sl2
相加,然后将相加的结果num
转成字符串并逆转。创建一个首节点,然后赋值给r
因为r
节点需要一直变换,将num
迭代并使用enumerate
获取索引,将迭代的num
的int
值赋值给r
节点的val
,判断是不是最后一个索引是的话就退出,不是的话将r.next
创建一个节点,再将它赋值给r
,进行之后的迭代
# Definition for singly-linked list
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
sl1 = ''
sl2 = ''
while l1:
sl1 += str(l1.val)
l1 = l1.next
while l2:
sl2 += str(l2.val)
l2 = l2.next
num = str(int(sl1[::-1]) + int(sl2[::-1]))[::-1]
first = ListNode()
r = first
for index,i in enumerate(num):
r.val = int(i)
if (index == len(num)-1): break
r.next = ListNode()
r = r.next
return first
'''迭代做法'''
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
sl1 = ''
sl2 = ''
while l1:
sl1 += str(l1.val)
l1 = l1.next
while l2:
sl2 += str(l2.val)
l2 = l2.next
num = iter(str(int(sl1[::-1]) + int(sl2[::-1]))[::-1])
first = ListNode(int(next(num)))
r = first
while 1:
try:
r.next = ListNode(int(next(num)))
r = r.next
except:
break
return first
无重复字符的最长子串
题目:给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
解法
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
hashmap = {}
repeat_index, ans = -1,0
for index,i in enumerate(s):
if i in hashmap:
repeat_index = max(hashmap[i],repeat_index)
ans = max(ans,index - repeat_index)
hashmap[i] = index
return ans;
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!