算法思想
一、前言
从考研结束就一直学习算法和数据结构。经过几个月的学习是时候写一些总结了。程序是由数据结构和算法组成的，数据结构的介绍在另一篇文章上，这里不再过多的赘述。这篇文章主要进行算法思想的总结。算法思想主要包括：分而治之、贪婪算法、动态规划、回溯、哈希表等等。为了便于说明这些思想，这篇文章举例相关的题目进行解说。
二、排序
排序有多种方法，常见的有冒泡排序、选择排序、插入排序、快速排序、堆排序等。
（1）冒泡排序
冒泡排序是最基本的一种排序方法，思路：比较相邻的两个元素，做比较大小，将大的元素向后移动（如果是升序排序，降序排序反之。），循环一次，此时已经将最大的元素排列到最后。重复上述循环直到排序完成。
冒泡排序的实现
#python实现
def bubSort(self,nums:list)->list:
count = len(nums)
#[1,2,3,4,5]
for i in range(count):
for j in range(count-i-1):
if nums[j]>nums[j+1]:
nums[j+1],nums[j] = nums[j],nums[j+1]
return nums//使用java实现
public void pubSotd(int [] nums) {
int count = nums.length;
int temp = 0;
for(int i=0;i<count;i++) {
for (int j=0;j<count-i-1;j++) {
if(nums[j]>nums[j+1]) {
temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
}(2)快速排序
由于冒泡排序的思想和插入排序以及选择排序的思想都差不多，在这只实现冒泡排序。采用分而治之的思想实现的快速排序。
算法思路：随机抽取一个元素（假设为n），遍历该数组，将大于n的元素放在n后面（如果是升序排列采用该方法，降序排列反之），小于n的元素放在后面。在递归执行分好组的其他没有分组的元素。直到实现排序。
#python实现
class Solution:
#现实快速排序
#这个函数是切割函数
def cut(self,nums:list):
#抽取第一个
priot = nums[0]
i = 0
j = len(nums) - 1
while i<=j:
if nums[i] > priot:
nums[i],nums[j] = nums[j],nums[i]
j-=1
else:
i+=1
nums[0],nums[i-1] = nums[i-1],nums[0]
return i-1
def quickSort(self,nums:list):
if len(nums) == 1:
return nums
elif len(nums)==0:
return []
else:
t = self.cut(nums)
#print(nums)
l = self.quickSort(nums[:t+1])
r = self.quickSort(nums[t+1:])
l.extend(r)
return l(3)归并排序
归并排序的思想主要是把大问题划分为小问题，然后解决所有的小问题就可以解决当前的大问题。归并排序利用递归，多次递归将大的排序问题分成多个子问题，同样利用调用归并排序算法。
可以如下图所示：
#使用python实现归并排序算法
class Solution:
#归并排序
def m(self,nums1:list,nums2:list)->list:
i = 0
j = 0
n = []
while i<len(nums1) and j<len(nums2):
if nums1[i]<nums2[j]:
n.append(nums1[i])
i+=1
else:
n.append(nums2[j])
j+=1
while i<len(nums1):
n.append(nums1[i])
i+=1
while j<len(nums2):
n.append(nums2[j])
j+=1
return n
def mergeSort(self,nums:list)->list:
if len(nums)==1:
return nums
if len(nums)==0:
return []
long = len(nums)
mid = long//2
pre = self.mergeSort(nums[:mid])
last = self.mergeSort(nums[mid:])
return self.m(pre,last)（4）堆排序
堆是一种数据结构。它类似二叉树结构，堆的特点是父节点要大于子节点的值，如果是倒堆父节点要小于子节点的值。由于堆类似于二叉树，因此，堆它符合一些二叉树的性质。假设堆有一个节点i,该i的值为二叉树层次排序的值（所谓二叉树层次排序的值为：第一层第一个为1，第二层第一个为2，第二层第二个为3，第三层第一个为4，第三层第二个为5，依次类推）。则该i节点的父节点值就为((i+1)/2)-1,该i节点的左孩子为2(i+1)-1,该i节点的右孩子为2(i+1)。根据这个性质我们就可以用数组去构造一个堆。
利用下标作为i值，就可以确定他们的父子关系。
在进行堆排序的时候应该需要将数组构造成堆。构成堆的思路为：遍历整个数组判断子节点和父节点的大小，如果不符合大堆的性质就交换。
#python的代码实现
class Heap:
def parent(self, i: int) -> int:
return int((i + 1) / 2) - 1
def left(self, i: int) -> int:
return 2 * (i + 1) - 1
def right(self, i: int) -> int:
return 2 * (i + 1)
def BuildHeap(self, nums: list) -> list:
if len(nums) <= 1:
return nums
k = 1
while k < len(nums):
i = k
while self.parent(i) >= 0:
if nums[self.parent(i)] < nums[i]:
nums[self.parent(i)], nums[i] = nums[i], nums[self.parent(i)]
i = self.parent(i)
else:
break
k += 1此时要是实现堆排序的第一步构造堆已经实现了，在构造这个堆的时候我们已经发现，该堆的堆顶就是数组中最大值。要实现堆排序，接下来就是取出堆顶，重新构造堆，重复步骤就可以实现排序。由于我们构造的是一个大堆，我们只要把堆顶的元素于数组的最后一个元素交换即可。对于这个操作我们面临着一个操作是交换之后如何重构n-1个元素的堆。
堆为
首先交换堆顶于最后一个元素的位置，并且要实现最后一个元素于堆的联系
#python的实现
class Heap:
def parent(self, i: int) -> int:
return int((i + 1) / 2) - 1
def left(self, i: int) -> int:
return 2 * (i + 1) - 1
def right(self, i: int) -> int:
return 2 * (i + 1)
def BuildHeap(self, nums: list) -> list:
if len(nums) <= 1:
return nums
k = 1
while k < len(nums):
i = k
while self.parent(i) >= 0:
if nums[self.parent(i)] < nums[i]:
nums[self.parent(i)], nums[i] = nums[i], nums[self.parent(i)]
i = self.parent(i)
else:
break
k += 1
return nums
def maxifyHeap(self, heap: list, size: int):
parent = 0
while self.left(parent) < size or self.right(parent) < size:
maxVal = heap[parent]
child = parent
if self.left(parent) < size and heap[self.left(parent)] > maxVal:
maxVal = heap[self.left(parent)]
child = self.left(parent)
if self.right(parent) < size and heap[self.right(parent)] > maxVal:
maxVal = heap[self.right(parent)]
child = self.right(parent)
if child == parent:
return
heap[parent], heap[child] = heap[child], heap[parent]
parent = child
def heapSort(self, nums: list) -> list:
nums = self.BuildHeap(nums)
heapSize = len(nums)
while heapSize > 1:
nums[0], nums[heapSize - 1] = nums[heapSize - 1], nums[0]
heapSize -= 1
self.maxifyHeap(nums, heapSize)
return nums三、分而治之思想
现实生活中有很多的问题看似很难，但是却可以分解成多个不难解决的小问题，当解决这些小问题的时候，这些小问题组成的当前较难的大问题也就解决了，这就是分而治之的基本思想。分而治之一般都与递归有关系，当前要解决的问题分解各个小问题一般他们都具有相同的解决方案，这样通过递归调用就可以进行解决。为了说明这个思想我们可以举一个具体的实例。
假如有个大小为n的数组，我们要从这个数组中找到一个与原数组顺序相同的子数组，使这个子数组的和为最大。讨论这个问题我们首先分析最大和的数组所在的位置。可以用暴力的解法遍历包含每个元素的子数组，但是效率太低，我们利用分而治之的思想去思考，先把当前的数组进行分割，分割成两个大小相当的数组。这时解决问题变成了解决了这两个分割数组中的最大子数组。
在解决这个问题时出现了三种情况：
此时我们只需要思考第三种情况，其他两种情况和我们的大问题是属于一样性质的问题，我们已经把它规模通过分而治之的思想转化为了较小规模的小问题。
现在只需要把左侧数组从尾巴处索引进行向左累加确定左侧最大值，同理，右侧相同的处理，只不过要从开头处向右累加确定右侧最大值。比较中间的值和左右两侧的值进行判断取留那个子数组。
根据上述分析我们可以画出程序流程图：
我们着手实现我们的思想：
#python代码
class Solution:
# 该方法是将一个数组进行分割，然后去中间最大值的子数组
def find_max_crossing_subarray(self, array: list, mid: int):
# lift = array[:mid]
# right = array[mid:]
index_lift = mid
index_right = mid+1
# 统计左侧数组最大值
lift_max = -sys.maxsize - 1
# 求和
temp = 0
# 记录当前索引
li = 0
while index_lift >= 0:
temp += array[index_lift]
if lift_max < temp:
lift_max = temp
li = index_lift
index_lift -= 1
t = lift_max
lift_max = -sys.maxsize - 1
# 记录右边的索引
temp = 0
ri = 0
while index_right < len(array):
temp += array[index_right]
if lift_max < temp:
lift_max = temp
ri = index_right
index_right += 1
return array[li:ri + 1], t + lift_max
def find_max_subarray(self, array: list):
if len(array) <= 1:
return array, array[0]
mid = len(array) // 2
array_lift, m_lift = self.find_max_subarray(array[:mid])
array_right, m_right = self.find_max_subarray(array[mid:])
# 再调用find_max_crossing_subarray函数，求中间最大值
array_mid, m_mid = self.find_max_crossing_subarray(array, mid)
if m_lift > m_right:
if m_lift > m_mid:
return array_lift, m_lift
else:
return array_mid, m_mid
else:
if m_right > m_mid:
return array_right, m_right
else:
return array_mid, m_mid四、图论之并查集思想
并查集思想是解决图论相关问题。并查集大致可以分为三个步骤，第一步是节点的初始化（一般是利用与节点数量相同的数组，该数组的索引就代表节点，初始化数组为该索引值代表指向自己为根节点，也就是说数组元素存储的值为这个节点的父节点），第二步是构造查找根节点函数，该函数可以使用递归调用实现，也可以利用循环实现。查找根节点主要是查找当前这个节点所在的连通量的根节点。第三步是构建合并函数，根据查找根节点函数判断两个节点是否相同的根节点，如果是相同的根节点则不能合并，不是相同的根节点就可以合并。
背景：假设有一个树形的数据结构，如图所示
根据该图我们可以将树形结构抽象为一个无向图[[1,2],[2,3],[3,4],[1,4],[1,5]]
我们怎么利用并查集去判断树形图是否有环。
首先初始化一个数组parent,此数组的大小为节点数量的大小，初始各个节点的父节点为自己，parent = [0,1,2,3,4,5]
定义一个查找根节点的函数，该函数的思路为，判断parent[index]是否相等index,如果相等则是父节点，如果不是将index赋值为parent[index]循环该步骤，直到parent[index]相等index。返回parent[index]的值
定义合并函数，根据判断查找根节点函数的返回值，如果相同的根节点就合并成功返回true，不同直接返回false。
#python实现
class Solution:
def find(self, parent: list, index: int) -> int:
while parent[index] != index:
index = parent[index]
return parent[index]
def union(self, parent: list, index1: int, index2: int) -> int:
a = self.find(parent,index1)
b = self.find(parent,index2)
if a != b:
parent[a] = self.find(parent, b)
return 1
else:
return 0
def findRedundantConnection(self, edges: list) -> list:
parent = list(range(len(edges) + 1))
for i, j in edges:
if self.union(parent, i, j):
continue
else:
return [i, j]五、二分查找法
1.简述：二分查找法是在一个已经排序完成的数组中使用的查找方法，它的基本思路是：（1）前提：设置前后两个指针指向数组的头节点（low）和尾节点(hight)，并且定义中间节点(mid=(low+hight)/2)。(2)步骤：将要查询的节点值与中间节点进行比较，比较情况有三种：①若比中间值大，则调整low=mid+1,mid=(low+hight)/2。②若与中间值相等，则查找完成。③若比中间值小，则调整hight=mid-1,mid=(low+hight)/2。
2.算法框架和分析
以python为例
#以python为例
def twodiv(arr:list,target:int):
low = 0
hight = len(arr)
mid = (low+hight)//2
while low<hight:
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
mid = (low+hight) // 2
else:
hight = mid - 1
mid = (low+hight) // 2
六、动态规划
1.简述：动态规划思想就是拒绝重复，也可以说是根据之前搜寻子问题的结果去解决父问题。用动态规划解决问题，该问题就应该有一下特征：①最优子结构②重叠的子问题③状态的转移④边界条件。
最优的子问题也就是说该问题可以划分多个最优的子问题，通过一定的条件进行叠加最优子问题就可以解决该问题。
重叠的子问题：一般能用动态规划解决的问题，都重复进行解决子问题，动态规划其中的一个优点就是可以记录子问题，降低时间复杂度。
状态转移：通过解决子问题，必须通过一定的方法进行迁移，一般是能找到迁移公式，将子问题的结果迁移到父问题，逐步解决了父问题。
边界条件：在进行状态转移的时候会有边界条件需要考虑。
2.动态规划的案例
（1）斐波那契数列问题
分析：当解决斐波那契数列的第n个值，可以把先解决斐波那契数列的第n-1个值和第n-2个值，该问题的转移方程可以很容易的发现f(n) = f(n-1) + f(n-2)，它的边界可以是1，1开头。因此该问题可以用动态规划进行解决。
def fei(self, n: int):
if n <= 0:
return 0
if n == 1 or n == 2:
return 1
pre1 = 1
pre2 = 1
nownumber = 0
for i in range(3, n + 1):
nownumber = pre1 + pre2
pre1 = pre2
pre2 = nownumber
return nownumber
（2）基础背包问题
题目描述：有n个物品，他们有各自的质量和价值。现有给定容量的背包，求如何能让背包里装入的物品具有最大的价值总和，并输出最大价值总和的值。
示例：
#物品重量 weight = [1,3,2,5] #物品价值 value = [20,24,14,15] #背包重量 max_weight = 5
分析：背包重量最大承重是5，首先解决背包容量为1的时候可以存放最大价值的物品，再考虑容量为2的时候。依次递推。边界可以以零容量开始。为了更好的分析可以使用二维数组表格进行分析。如图：
定义一个二维表格，首先更新第i行(从1行开始因为初始0行为零)，i行代表考虑前i个物品，j列考虑的是装下总共为j重量的物品。当j重量大于value[i]的时候就考虑装下该物品，否则不考虑，按照i-1行j列进行。
更新规则是：
①当j<weight[i]时 d[i][j] = d[i-1][j]
②当j>=weight[i]时 d[i][j] = max(d[i-1][j],value[i]+d[i-1][j-weight[i]])
七、深度优先搜索
1.简述：
深度优先搜索(DFS)是一种常见的遍历方式，DFS的基本思想是沿着当前查找路径深层遍历，直到结束当前路径的查询，然后返回到之前的位置继续进行没有查找的节点或元素。与DFS思想类似的思想是回溯，递归。DFS的实现是靠栈进行实现的。虽然在一些深度优先搜索的案例中的实现是使用递归进行实现，其实递归就是系统调用的隐形栈。
2.深度优先搜索的实现
深度优先搜索的实现可以与回溯算法类似，与回溯算法不同是回溯算法需要进行搜索之后恢复原来状态，例如我们在一个树种搜索想要的节点，则必须递归和标记，递归则是让DFS进行下去，标记则是减少重复的计算。
深度优先搜索的模板可以用以下伪代码：
#搜索回溯算法模板
def (x :int):
if 到达目的地:
输出解
return
for i in range(方案数):
if 方案可行:
保存路径
if dfs(x+1)：
return
return
3.深度优先搜索的案例
(1)岛屿的数量:给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
示例： 输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出：1
本题的解决思路可以使用深度优先搜索，利用深度优先搜索可以将岛屿连续找到相连的岛屿，并且标记成'0'(或是其他标记)，进行统计执行了几次深度优先遍历，就可以统计出来有多少个岛屿。
#python
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
number = 0#统计岛屿个数
def dfs(grid, i ,j):#定义递归函数
if i >= len(grid) or j>=len(grid[0]) or i<0 or j<0:#排除条件
return
if grid[i][j] == '0':
return
if grid[i][j] == '1':#进行递归
grid[i][j] = '0'
dfs(grid,i-1,j)
dfs(grid,i+1,j)
dfs(grid,i,j-1)
dfs(grid,i,j+1)
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
dfs(grid,i,j)
number += 1
else:
continue
return number（2）克隆图：有一个无向图，请克隆该无向图。
京公网安备 11010502036488号