从零开始用python刷leetcode,随手记录一些tips
1.哈希表(leetcode第一题两数之和)
哈希表也叫作散列表,数据结构提供了键(key)和值(value)的映射关系,具有高效快速查找的特点,其查找时间复杂度为O(1)。
在python语言中,哈希表对应的集合叫做字典(dict)。
哈希表也是一个特殊的数组,哈希表示将键key经过哈希函数处理得到数组的下标,从而键值对在数组内的位置,根据键key可以直接求得键值对在数组上的位置,所以在哈希表上查找O(1)比在数组中查找O(n)有很好的实时性。
在使用时,要将需要查找的值作为哈希表中键值对的键key,才能发挥出哈希表的性能特点。
(特殊情况:当发生哈希冲突时哈希表会拓展为一个数组+链表,或者一个数组+二叉树的形式,哈希冲突是不同的键经过哈希函数后获得相同的索引,所以通过开放寻址法或者链表法来解决)
第一题
暴力列表双循环解法
哈希表循环
2.链表
python中没有链表数据结构,一般在题目中会给定义链表类
如单向链表:
class ListNode:
def __init__(self,val=0,next=None):
self.val=val
self.next=next
一般首先定义一个头节点,其默认值为0:
head=ListNode()
链表list与链表节点listnode有不同
返回链表只需要头指针,所以将链表赋值头指针的地址,通过head.next
head = curnode = ListNode() #定义头链节点
curnode.next = ListNode(a) #定义下一个节点,需要再用ListNode类
curnode=curnode.next #将节点指针向后挪
return head.next #返回头结点,通过.next得到整个链表
两数之和(迭代法)这里cur和result变量名与含义不对应,不太妥当:
# 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
"""
cur = result = ListNode()
more = 0
while l1 != None or l2 != None:
x=l1.val if l1 else 0
y=l2.val if l2 else 0
total = x + y + more
more=total // 10
result.next = ListNode(total % 10)
if l1: l1=l1.next
if l2: l2=l2.next
result=result.next
if more != 0: #当两数最高位仍需进位时,要添加一个节点
result.next=ListNode(more)
return cur.next
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)