LeetCode-算法学习（入门篇）

开一个新坑，学习数据结构与算法，也是为了明年秋招做储备（非科班表现很慌QAQ）
跟随B站左神重新开始学习，现在看完了入门篇，写写笔记和自我明白，是一个备忘录的同时也是归纳总结。如有明白不对的地方也请各位大佬见教~
一、二进制与位运算

1.以整数为例，对于n位无符号整数，其大小范围为0~

-1，对于有符号整数，其第一位是符号位则大小范围是-

~

-1，个数都是

个。
2.计算机中如何对一个正数取相反数？b = (~a)+1与b=-a在计算机中是一个意思，但是在计算机中-

是无法取相反数的，因为最大的正数是

-1，其相反数还是自己
3.位运算，|,&,^(异或，相同为0不同为1),~,<<,>>,>>>。>>是右移后左边用符号位补位，>>>是右移后左边用0补位，以是对于非负数两个符号没有区别，对于负数有区别
4.二进制打印函数中用移位和与操纵实现，对每一位用代码a判断，而不能用代码b。如果与操纵第3位的效果是0b1000，那么此时该数不即是1而即是8，用b代码判断效果就是0，而a代码判断效果就是1。

1. a) num&(1<<i)==0?'0':'1'   b) num&(1<<i)==1?'1':'0'

复制代码

5.计算机不会判断是否会溢出，在进行运算时需要自己保证运算的效果不会溢出，包括中间变量,a,b代码的理论运算效果是一样的，但是a+b大概会存在溢出，以是b)代码更好

1. a) m=(a+b)/2                   b) m= b + (a-b)/2

复制代码

6. 为什么在二进制中负数计划的这么反人类，是为了加法逻辑是一套逻辑没有条件转移，计算机底层只有加法运算。
好比 3+1->0011+0001=0100=4， -5+7->1011+0111=0010=2
二、选择、冒泡、插入排序

1.选择排序：i~n-1范围上，找到最小值并放在i位置上，然后i+1~n-1范围上继续

1. def SelectSort(arr):
2.     length = len(arr)
3.     for i in range(length):
4.         mindex = i
5.         for j in range(i + 1, length):
6.             if arr[j] < arr[mindex]:
7.                 mindex = j
8.         swap(arr, mindex, i)
9.     return arr

复制代码

2.冒泡排序：0~i范围上，相邻位置较大的数滚下去，最大值最终来到i位置，然后0~i-1范围上继续

1. def BubbleSort(arr):
2.     length = len(arr)
3.     for i in range(length - 1, -1, -1):
4.         for j in range(i):
5.             if arr[j] > arr[j + 1]:
6.                 swap(arr, j, j + 1)
7.     return arr

复制代码

3.插入排序：0~i范围上已经有序，新来的数从右到左滑到不再小的位置插入，然后继续

1. def InsertSort(arr):
2.     length = len(arr)
3.     for i in range(1, length):
4.         for j in range(i - 1, -1, -1):
5.             if arr[j] > arr[j + 1]:
6.                 swap(arr, j, j + 1)
7.     return arr

复制代码

其中swap函数是交换数组中两个数字位置

1. def swap(arr, i, j):
2.     temp = arr[i]
3.     arr[i] = arr[j]
4.     arr[j] = temp

复制代码

只能说概念好明白，代码还真不一定能一次写对(⊙﹏⊙)，常看常新吧
三、对数器

这个感觉就有点难了，自己想出两种不同的思路去解题。在leetcode中的标题我们可以通过提交看报错一步一步改，但是现实中面经啊，大概别人说的口试题就没这个条件了，所有我们需要想一个暴力解，能解出来但是毫无美感，另一个是渴望的最优解，然后不绝的生成随机输入测试我们的最优解，和暴力解的答案对比，不停修改最优解，直到两个方法的解完全一样，此时最优解就优化完成。前提是暴力解得保证是对的。
四、二分搜索

在有序数组中确定num是否存在。二分搜索的思路很简朴，找数组中间的谁人数，num比这个数大那就往右边找，否则往左边找，每次都可以在将搜索范围减半，时间复杂度就只有O(logN)
对于非有序数组（任何两个相邻的值不相称）也可以做一些工作，好比寻找峰值问题，假设数组num中num[-1]=num[n]=无穷小，类似于高数中的极小值和极大值一样，好比num[1]>num[0]，num[n-2]>num[n-1]那么中间一定有至少一个峰值。
思路就是，先判断0大概n-1位是不是峰值，如果不是，二分数组看中间的数是不是峰值，否则对左侧大概右侧进行二分，以此循环。

1. def findPeakElement(self, nums: List[int]) -> int:
2.         length = len(nums)
3.         if length == 1:
4.             return 0
5.         if nums[0] > nums [1]:
6.             return 0
7.         if nums[length-1] > nums[length -2]:
8.             return length-1
9.         l = 1
10.         r = length -2
11.         while l<=r:
12.             mid = l + ((r-l)>>1)
13.             if nums[mid-1]<nums[mid] and nums[mid] > nums[mid+1]:
14.                 return mid
15.             else:
16.                 if nums[mid-1] >nums[mid]:
17.                     r = mid -1
18.                 elif nums[mid+1]>nums[mid]:
19.                     l = mid +1

复制代码

五、时间复杂度和空间复杂度

建议直接看视频，后续再增补。。。
六、算法和数据结构简介

左神将算法分为了硬计算类算法、软计算类算法。

硬计算类算法：精确求解。但是某些问题利用硬计算类的算法，大概会让计算的复杂度较高。大厂算法和数据结构笔试、口试题、acm比赛大概和acm形式类似的比赛，观察的都是硬计算类算法。软计算类算法：更注重逼近办理问题，而不是精确求解。计算时间可控好比：模糊逻辑、神经网络、进化计算、概率理论、混沌理论、支持向量机、群体智能

硬计算类算法是所有程序员岗位都会考、任何写代码的工作都会用到的。前端、后端、架构、算法所有岗位都要用到。但是算法工程师除了掌握硬计算类的算法之外，还需要掌握软计算类的算法。

学就完事了！

七、单双链表及其反转-堆栈诠释

1）按值传递与按引用传递。在C++中应该很有了解，f(a)与f(&a)的区别，前者并不会改变输入a的值，后者会改变输入a的值。计算机中只有访问该变量内存中的地点并修改值才会改变该值，否则就是新创建一个变量，修改创建变量的值。
2）单双链表，就是链表节点有没有存储上一个节点的地点。
3）反转链表：单链表反转由1->2变成1<-2

1. def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
2.         next = None
3.         pre = None
4.         while head!=None:
5.             next = head.next
6.             head.next = pre
7.             pre = head
8.             head = next
9.         return pre

复制代码

八、链表入门标题-合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。
思路：先判断是否有空链表，如果没有先判断哪个链表的头小，小的为新链表的头，注意链表的头后续不再改变。通过cur1与cur2索引后续的节点，选择较小的与上一个节点pre连接，最后当一个链表遍历完之后，将另一个链表的剩余部门全部接上。

1. def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
2.         if list1==None or list2==None:
3.             if list1==None:
4.                 return list2
5.             else:
6.                 return list1
7.         
8.         if list1.val<=list2.val:
9.             head = list1
10.             cur1 = head.next
11.             cur2 = list2
12.         else:
13.             head = list2
14.             cur1 = head.next
15.             cur2 = list1
16.         
17.         pre = head
19.         while cur1!=None and cur2!=None:
20.             if cur1.val <=cur2.val:
21.                 pre.next = cur1
22.                 cur1 = cur1.next
23.             else:
24.                 pre.next = cur2
25.                 cur2 = cur2.next
26.             pre = pre.next
27.         
28.         if cur1==None:
29.             pre.next = cur2
30.         else:
31.             pre.next = cur1
32.         
33.         return head

复制代码

九、链表入门标题-两个链表相加

首先该问题不能将链表数字转换成int/long类型相加完之后再写成链表，因为有大概溢出。链表是可以无穷长的，但是整数是有位数限制的。以是老老实实按照链表做。
链表中头节点是个位，按位相加时要考虑两个问题，第一对应位上是否有数字可加，第二进位问题。无论该位有没有数字可以相加都要考虑前一位的进位，三位数+四位数可以即是五位数。对着代码还是很轻易明白的。

1. def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
2.         ans = None
3.         pre = None
4.         cur1 = l1
5.         cur2 = l2
7.         carry = 0
8.         while cur1!= None or cur2 != None:
9.             sum = 0
10.             if cur1 == None:
11.                 sum += cur2.val+ carry
12.                 cur2 = cur2.next
13.             elif cur2== None:
14.                 sum += cur1.val+ carry
15.                 cur1 = cur1.next
16.             else:
17.                 sum = cur1.val + cur2.val + carry
18.                 cur1 = cur1.next
19.                 cur2 = cur2.next
20.             value = sum%10
21.             carry = int(sum/10)
23.             if ans==None:
24.                 ans = ListNode(value)
25.                 pre = ans
26.             else:
27.                 temp = ListNode(value)
28.                 pre.next = temp
29.                 pre = pre.next
31.         
32.         if carry == 1:
33.             temp = ListNode(1)
34.             pre.next = temp
35.         return ans

复制代码

十、链表入门标题-划分链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或即是 x 的节点之前。你应当 保存 两个分区中每个节点的初始相对位置。
将链表分成两个区域，<x与>=x，在这两个区域中，节点的相对位置不变。
思路：遍历链表之后尾插。我们可以假设有两个链表一个是<x一个是>=x，每个链表有头尾节点，重新遍历输入的链表，按照要求尾插入假设的两个链表，最后将小链表的尾与大链表的头相连即可。

1. def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
2.         bigHead = None
3.         bigTail = None
4.         smallHead = None
5.         smallTail = None
6.         while head !=None:
7.             next = head.next
8.             head.next = None
9.             if head.val < x:
10.                 if smallHead==None:
11.                     smallHead = head
12.                 else:
13.                     smallTail.next = head
14.                 smallTail = head
15.             if head.val >= x:
16.                 if bigHead==None:
17.                     bigHead = head
18.                 else:
19.                     bigTail.next = head
20.                 bigTail = head
21.             head = next
22.         if smallHead == None:
23.             return bigHead
24.         else:
25.             smallTail.next = bigHead
26.             return smallHead

复制代码

十一、队列和栈-链表、数组实现

1.队列，先进先出，尾部参加头部弹出。队列的链表实现比力简朴，数据参加只能参加到链表的尾部，弹出只能弹出头部，再将链表的头向后移一个。队列的数组实现，用l和r指示数组的最左边和最右边，l<r有数，l==r就是空，参加就是放到数组r位置r++，弹出就是取出数组l位置，l++。
2.栈，先进后出，尾部参加尾部弹出。栈的数组实现，用size表现数组大小，size==0数组栈为空，参加就是放到数组的size位置，size++，弹出就是弹出size-1位置，size--。
3.环形队列的数组实现。环形队列就是头尾的位置(l/r)可以动态变化，用size管理头尾，队列的大小不能超过n。当size<n时，参加数据放到r处，r++，size++，当r==n-1时，参加数据后r=0，当size>0时，弹出l处的数据，l++，size--，当l==n-1时，弹出数据后l=0。

1. class MyCircularQueue:
3.     def __init__(self, k: int):
4.         self.arr = [None for _ in range(k)]
5.         self.l = 0
6.         self.r = 0
7.         self.k=k
8.         self.size = 0
10.     def enQueue(self, value: int) -> bool:
11.         if self.isFull():
12.             return False
13.         self.arr[self.r] = value
14.         if self.r == self.k-1:
15.             self.r=0
16.         else:
17.             self.r+=1
18.         self.size+=1
19.         return True
21.     def deQueue(self) -> bool:
22.         if self.isEmpty():
23.             return False
24.         if self.l==self.k-1:
25.             self.l = 0
26.         else:
27.             self.l +=1
28.         self.size-=1
29.         return True
31.     def Front(self) -> int:
32.         if self.isEmpty():
33.             return -1
34.         return self.arr[self.l]
36.     def Rear(self) -> int:
37.         if self.isEmpty():
38.             return -1
39.         if self.r==0:
40.             return self.arr[self.k-1]
41.         else:
42.             return self.arr[self.r-1]
44.     def isEmpty(self) -> bool:
45.         return self.size ==0
48.     def isFull(self) -> bool:
49.         return self.size == self.k

复制代码

十二、队列和栈入门标题-栈和队列相互实现

1.用栈实现队列：我们用两个栈实现队列，因为栈是先进后出，那么将in栈的数据倒入到out栈中，则可以实现次序颠倒，进而实现先进先出。首先所有的数据都是先进入in栈，之后在倒入到out栈中必须保证两点：（1）out栈必须是空的；（2）in栈必须全部倒入out栈。这两点保证out栈弹出的次序不会改变。所有数据的都是in栈进入，out栈弹出。

1. class MyQueue:
3.     def __init__(self):
4.         self.in_stack = []
5.         self.out_stack = []
8.     def push(self, x: int) -> None:
9.         self.in_stack.append(x)
10.         self.in2out()
12.     def pop(self) -> int:
13.         if self.empty():
14.             return None
15.         self.in2out()
16.         temp = self.out_stack.pop()
17.         return temp
19.     def peek(self) -> int:
20.         if self.empty():
21.             return None
22.         self.in2out()
23.         temp = self.out_stack[-1]
24.         return temp
26.     def empty(self) -> bool:
27.         if len(self.in_stack) + len(self.out_stack)==0:
28.             return True
29.         else:
30.             return False
32.     def in2out(self):
33.         if len(self.out_stack)==0 and len(self.in_stack)!=0:
34.             for i in range(len(self.in_stack)):
35.                 self.out_stack.append(self.in_stack.pop())

复制代码

2.用队列实现栈。标题要求用两个队列实现，左神的思路用一个队列即可，并且十分巧妙。焦点为：后来的数据把队列中现有的数据一个一个挤出去再重新入队，如许就可以保证新进来的数在队列的头部，可以重新部顺利弹出。（队列只能尾进头出）队列中有几个数字该过程就重复几次。

1. class MyStack:
3.     def __init__(self):
4.         self.list=[]
7.     def push(self, x: int) -> None:
8.         length = len(self.list)
9.         self.list.append(x)
10.         for i in range(length):
11.             temp = self.list.pop(0)
12.             self.list.append(temp)
15.     def pop(self) -> int:
16.         if self.empty():
17.             return None
18.         return self.list.pop(0)
21.     def top(self) -> int:
22.         if self.empty():
23.             return None
24.         return self.list[0]
27.     def empty(self) -> bool:
28.         if len(self.list)==0:
29.             return True
30.         else:
31.             return False

复制代码

十三、栈的入门标题-最小栈

计划一个支持 push ，pop ，top 操纵，并能在常数时间内检索到最小元素的栈。该题的焦点是在栈进行push和pop操纵后仍可以快速检索到最小元素。最开始想的是在压入的时候记录最小值，但是如果最小值弹出了就无法更新了。左神的思路是：用两个栈实现，一个是data栈存储压入的数据，一个是min栈记录压入第i个元素时最小值，min栈第一个元素和data栈一样，从第二个开始进行比力，如果压入的元素比当前min栈元素小则压入，否则压如当前min栈的元素，在弹出数值时两个栈同时弹出。以是在检索最小元素时只需要检索min栈顶元素即可。

1. class MinStack:
3.     def __init__(self):
4.         self.data=[]
5.         self.min=[]
8.     def push(self, val: int) -> None:
9.         self.data.append(val)
10.         if len(self.min) ==0 or val<= self.min[-1]:
11.             self.min.append(val)
12.         else:
13.             self.min.append(self.min[-1])
16.     def pop(self) -> None:
17.         self.min.pop()
18.         self.data.pop()
21.     def top(self) -> int:
22.         return self.data[-1]
25.     def getMin(self) -> int:
26.         return self.min[-1]

复制代码

十四、双端队列-双链表和固定命组实现

双端队列就是头部和尾部都可以进出数据，如果用双链表实现，注意头尾的指针和新数据一段指向空即可。主要讨论固定命组实现。
固定命组实现时接纳循环队列的思路管理数组大小，用size管理数组现在的大小，因为时固定命组以是size是有最大值k的。我们界说头部指针为l，尾部为r。总结进入队列和弹出队列的逻辑为：
头部进入：l==0时，数据进入k-1位置，l=k-1；l!=0时，数据进入l-1位置，l-=1
头部弹出：弹出[l]位置数据，l=k-1时，令l=0;l!=k-1时，令l+=1
尾部进入：r=k-1时，数据进入0位置，r=0；r!=k-1时，数据进入r+1位置，r+=1
尾部弹出：弹出[r]位置数据，r=0时，令r=k-1；r!=0时，令r-=1

1. class MyCircularDeque:
3.     def __init__(self, k: int):
4.          self.limit = k
5.          self.l=self.r=self.size=0
6.          self.data=[-1]*8001
9.     def insertFront(self, value: int) -> bool:
10.         if self.isFull():
11.             return False
12.         if self.isEmpty():
13.             self.l=self.r=0
14.             self.data[0]=value
15.         else:
16.             if self.l==0:
17.                 self.data[self.limit-1] = value
18.                 self.l = self.limit-1
19.             else:
20.                 self.l -=1
21.                 self.data[self.l] = value
22.         self.size+=1
23.         return True
25.     def insertLast(self, value: int) -> bool:
26.         if self.isFull():
27.             return False
28.         if self.isEmpty():
29.             self.l=self.r=0
30.             self.data[0]=value
31.         else:
32.             if self.r==self.limit-1:
33.                 self.data[0] = value
34.                 self.r = 0
35.             else:
36.                 self.r +=1
37.                 self.data[self.r] = value
38.         self.size+=1
39.         return True
41.     def deleteFront(self) -> bool:
42.         if self.isEmpty():
43.             return False
44.         if self.l == self.limit-1:
45.             self.l=0
46.         else:
47.             self.l+=1
48.         self.size-=1
49.         return True
51.     def deleteLast(self) -> bool:
52.         if self.isEmpty():
53.             return False
54.         if self.r == 0:
55.             self.r = self.limit-1
56.         else:
57.             self.r-=1
58.         self.size-=1
59.         return True
61.     def getFront(self) -> int:
62.         if self.isEmpty():
63.             return -1
64.         return self.data[self.l]
67.     def getRear(self) -> int:
68.         if self.isEmpty():
69.             return -1
70.         return self.data[self.r]
73.     def isEmpty(self) -> bool:
74.         return self.size==0
77.     def isFull(self) -> bool:
78.         return self.size==self.limit

复制代码

十五、二叉树及其三种序的递归实现

二叉树有三种遍历方式先序(中左右)，中序(左中右)，后序(左右中)。利用递归算法实现时，时间复杂度为O(n)，空间复杂度为O(h)，h为树的高度。
我们以下图的树为例: 对于遍历的原则是对于任何一颗子树都要满足该种遍历的次序

先序：1，2，4，5，3，6，7。中序：4，2，5，1，6，3，7。后序：4，5，2，6，7，3，1。
用递归的算法写十分简朴，在不同位置拿数据即可实现不同的遍历方式。

1. class Solution:
2.     def __init__(self):
3.         self.result=[]
4.     def anyorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
5.         if root==None:
6.             return []
7.         # 先序遍历则在此压入结果队列
8.         #self.result.append(root.val)
9.         self.anyorderTraversal(root.left)
11.         # 中序遍历则在此压入结果队列
12.         #self.result.append(root.val)
13.         self.anyorderTraversal(root.right)
15.         # 后序遍历则在此压入结果队列
16.         self.result.append(root.val)
18.         return self.result

复制代码

那么我们该如何明白这个递归呢？递归的停止条件是该节点没有左右叶子节点了开始往上一级回溯，以之前的图为例，整个递归序列是1，2，4，4，4，2，5，5，5，2，1，3，6，6，6，3，7，7，7，3，1。每个空节点只会来一次，就return了，回溯到上一个节点了，但是每个非空节点会遍历3次，那么我们的先，中，后序就是第几次遍历该非空节点时弹出数据。第一次碰到该节点就弹出就是先序，第二次中序，第三次后续。从递归序的角度更好明白该递归代码和深层逻辑。
十六、二叉树遍历的非递归实现

递归实现的代码非常简朴逻辑有点绕，但好坏递归的我感觉代码也不简朴逻辑也不简朴QAQ。左神主要保举用一个栈实现二叉树的不同遍历方式。
1.先序遍历：因为栈是先进后出，所有要实现中左右的次序，对于左右节点应该先压入右节点数据再压入左节点数据。大概逻辑就是，先压入根节点到栈，此时栈内有数据，当栈不空时，弹出顶层节点之后先压右节点再压左节点，直到栈空了就是遍历完了。明白就是，在压入左右节点之前栈顶一定是该子树的根节点，如果已经到叶子节点，那么再下一个循环里就会被弹出。并且一定是先弹出上一个根节点的左节点。

1. def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
2.         stack = []
3.         result = []
4.         if root==None:
5.             return []
6.         stack.append(root)
7.         while len(stack) != 0:
8.             head = stack.pop()
9.             result.append(head.val)
10.             if head.right!=None:
11.                 stack.append(head.right)
12.             if head.left!=None:
13.                 stack.append(head.left)
14.             
15.         return result

复制代码

2.中序遍历：中序的是左中右，对于任何一个节点都应该先处置惩罚左树再处置惩罚右树。当栈不空大概该节点还有子树时，先将该子树的左边全部压入栈，之后弹出栈顶元素，再将该弹出节点的右边全部压入，云云循环即可。以上图为例，首先压入1,2,4此时弹出4，4没有右节点继续弹出2，2有右节点压入5，5没有右节点了，弹出5，此时栈里只剩1，弹出，将3，6压入，弹出6，弹出3，压入7，弹出7，此时栈空并且该节点也没有子树了竣事，次序就是4，2，5，1，6，3，7。

1. def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
2.         stack = []
3.         result = []
4.         if root==None:
5.             return result
6.         while len(stack)!=0 or root!=None:
7.             if root!= None:
8.                 stack.append(root)
9.                 root = root.left
10.             else:
11.                 root = stack.pop()
12.                 result.append(root.val)
13.                 root = root.right
14.         return result

复制代码

3. 后序遍历：如果我们用两个栈实现，可以如许。我们前序遍历时中左右，控制左右是先压右再压左，如果我们颠倒这个次序就可以实现中右左，再将这个效果倒入第二栈实现反转就是左右中的后序遍历。
主要还是看一个栈如何实现，我们引入一个新的变量h，h是记录上次弹出的节点位置的变量。当还没有弹出时，h一直在树的根节点，弹出节点x之后，h就到了x的位置。我们主要判断就是该节点左树是否存在并且左树是否被处置惩罚之后判断右树是否存在且右树是否被处置惩罚。感觉有点绕