我需要学习算法，我要开始重新认真

哈希表（12.3）

本质：就是找到一个可以一一对应的表格关系，节省下寻找的时间

（通常是：字典，列表，数组之类可一一对应的）

python:

1
2
3
4
5
6
7
8
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtext = dict()
        for i,num in enumerate(nums):
            if (target - num) in hashtext:
                return [hashtext[target - num],i]   #直接根据目标数找到对应的下标
            #这里key是数，value是下标
            hashtext[nums[i]] = i
for i, num in enumerate(nums)：遍历数组（同时拿下标和值）
  • enumerate(nums) 是 Python 内置函数，遍历数组时会同时返回「元素的下标 i」和「元素的值 num」。
  • 比如 nums = [2,7,11,15]，遍历第一次得到 (0,2)，第二次 (1,7)，以此类推。
  • 不用 for i in range(len(nums)) + num = nums[i]，是因为 enumerate 更简洁高效。

在python中创建链表：

1
2
3
4
class Lianbiao:
    def __init__(self,vale=0,next=None)：		#这里是给初始赋值
    	self.vale = vale	#让vale/next能接受外来变量的同时，也能给他初始赋值
        self.next = next

具体实现：

赋值：

1
2
3
test_1 = Lianbiao(1)
test_2 = Lianbiao(2)
test_1.next = test_2

遍历：

1
print()

两数相加：

递归法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 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: Optional[ListNode], l2: Optional[ListNode],carry=0) -> Optional[ListNode]:			#新增了一个输入carry，用于更加方便添加进位
        #递归出口
        if carry == 0 and not l1 and not l2:			#写递归就要把终止条件写在前面
            return None

        s = carry		
        if l1:
            s += l1.val
            l1 = l1.next

        if l2:
            s += l2.val
            l2 = l2.next

        return ListNode(s%10,self.addTwoNumbers(l1,l2,s//10))   
    	#必须加self，不然找不到
        #s//10是清除s的原本值
    	#s//10只能是 0/1，用于计算进位
        #s%10是拿来计算个位的，也就是当前该放哪一个进入

迭代：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
       if l1.val + l2.val >=10:         #别少了最初给i的赋值
        temp = 1
       else:
        temp = 0
       node_1 = ListNode((l1.val + l2.val)%10)
       mid_1 = node_1
       if l1.val != None and l2.val != None:
        while l1.next and l2.next:
            mid_1.next = ListNode((l1.next.val + l2.next.val + temp)%10)      
            
            #应该用l1.next.val，少了next
            
            if (l1.next.val + l2.next.val + temp) >= 10:          
                temp = 1
            else:
                temp = 0
            l1 = l1.next
            l2 = l2.next
            mid_1 = mid_1.next 
        if l1.next != None:
            while l1.next:
                mid_1.next = ListNode((l1.next.val + temp)%10)
                if (l1.next.val + temp) >= 10:
                    temp = 1
                else:
                    temp = 0
                l1 = l1.next
                mid_1 = mid_1.next
        if l2.next != None:
            while l2.next:
                mid_1.next = ListNode((l2.next.val + temp)%10)
                if (l2.next.val + temp) >= 10:
                    temp = 1
                else:
                    temp = 0   
                l2 = l2.next
                mid_1 = mid_1.next
        if temp == 1:
            mid_1.next = ListNode(1)
        return node_1           #要输出node_1（头节点），而不是mid_1

注意点：

1
1.记得用在写完开头后，后面的循环要写上next
backtop