1.两数之和
输入:nums = [2,7,11,15], target = 9 输出:[0,1] #输出nums中两数之和为target的下标
我自己想到的解法算是暴力解法:
- 记录nums中一个值为a1,a2=target-a1
- 遍历除a1以外的值,判断是否与a2相等
- 获取a1和a2的下标值并输出
有两点注意:
- 第二个for循环的范围是从i之后开始的,这样保证不会出现相同下标值
- 若获得a1、a2后则跳出循环(break),否则开始下一循环(continue)
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
out=[0,0]
lens=len(nums)
for i in range(lens):
a2=target-nums[i]
for j in range(i+1, lens):
if nums[j]==a2:
out[1]=j
out[0]=i
break
elif nums[j] != a2:
continue
return out
优化方法是使用哈希查找降低时间复杂度:
def twoSum(nums, target):
hashmap={} #创建一个hashmap
for index,value in enumerate(nums):
#判断hashmap中有a2这个值
if hashmap.get(target - value) is not None:
return [index,hashmap.get(target - value)]
#没有a2时就将nums和其下标存储到hashmap中
hashmap[value] = index
2.两数相加
知识点:
链表:每个节点有两个属性data和next,在创建ListNode类时包含着两个属性。每调用一次ListNode()就向该对象中添加了一个节点Node。
node1 = ListNode(2)
node2 = ListNode(4)
node3 = ListNode(3)
更改链表值时,涉及到指针的概念,这里我的理解是,定义两个空链表,一个用来在循环时赋值和移动指针到下一位置,这样才能改变链表的内容,最后遍历结束后指针指向链表的尾部。另一个链表用来最后return值,因为这个链表的指针指向链表头,调用next属性时才能输出内容。
解题思路:
- 利用l1.val获得节点的值,
- 将l1和l2每个节点值和flag相加,得到sum
- 设置flag的值为sum取整(判断是否进位)
- 将sum赋值给节点,将指针指向循环变量L 下一节点
- 判断l1、l2是否遍历结束,未结束时将指针指向下一节点
# Definition for singly-linked list.
# 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
"""
lis = L = ListNode(0) #初始化两个链表,一个用来return,一个用来循环遍历
flag = 0 #定义一个进位项
while (l1 or l2 or flag):
# x = l1.val if l1 else 0
if l1:
x = l1.val
else:
x=0
# y = l2.val if l2 else 0
if l2:
y = l2.val
else:
y=0
sum = flag+x+y
flag = sum//10 #清空flag
L.next=ListNode(sum%10) #生成一个节点
L = L.next #指针指向下一个节点
if(l1!=None):l1 = l1.next #以防l1和l2指针长度不一样导致相加错误
if(l2!=None):l2 = l2.next
if (flag>0):
L.next=ListNode(1) #判断最高位是否需要进位
return lis.next
sum的值可以简化为一句代码得到:
sum += (l1.val if l1 else 0) + (l2.val if l2 else 0)
本文含有隐藏内容,请 开通VIP 后查看