基本思想 每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。 算法思路 如果由n个数进行排序，只需将n-1个数归位，也就是进行n-1趟操作。 “每一趟”都需要从第一位开始进行相邻两个数的比较，将较小的一个数放在后面 比较完毕后挪一位继续比较下面两个相邻数的大小 重复此步骤，直到最后一个尚未归位的数 算法 # s为数组 def sort(s):   length = len(s)-1 if length < 1: return []  &nb...

题目描述 给定一个数组由一些非负整数组成，现需要将他们进行排列并拼接，使得最后的结果最大，返回值需要是string类型 否则可能会溢出 解题思路 1. 先对列表进行降序排序 2.将列表中的值分别转换成string类型 3.对比当前元素和下一个相邻元素两两交换位置的合并值 ，如果相邻的元素在前可以使数更大，则交换两个元素的位置，以此类推，依此比较数组中的元素，如下图所示： 4.最后直到将所有元素排好序，循环结束。 5.需要注意的是，如果排序好的数组的第一个元素是0，则直接...

主要思想：     1.采用邻接表存储图结构     2.求最短路径 采用队列存储BFS遍历结果     3.首先入队 第一个结点，再遍历所有与第一个结点相连的所有结点并入队，与此同时，更新当前点到其他点的路径长度 变量说明：     1.用来表达邻接表的数组          h[n*2] 存放图的所有结点      &n...

import numpy as np from queue import Queue def main():     global g, q, d,n,m     n = int(input("请输入n值："))     m = int(input("请输入m值："))   &...

题目描述 给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。 请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。 重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。 思路： 1.除去重心后的连通块包括两类，一类为重心节点子树若干连通块，一类是除去重心节点及其子树的连通块 2.第一类的求法：通过DFS计算每个节点子树连通块的最大值 2.第二类的求法：通过树节点总数n 减去 重心节点所有子树和 即 n - size4 关键...

深度优先遍历(Depth First Search)的主要思想是： 思想：不撞南墙不回头 1、首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点； 2、当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直至所有的顶点都被访问过。 邻接表表示： 在这里我们采用数组+链表（头插法）表示邻接表 # a和b存在一条边 def add(a,b):     e[idx]&nb...

n皇后是指将n个皇后放在n-n的国际象棋棋盘上，使皇后不能相互攻击到，即任意两个皇后不能再同一行、同一列或同一斜线上。 算法基本思路： 1.当N个皇后摆放好，依次输出 2.对每行U的0-N列遍历，比较第U个皇后是否会发生冲突（横、竖、对角线） 3.放置好后对该皇后、横、竖、斜对角线做标记，下一次放置 则不会出现在以上地方 需要变量： q[n][n] 棋盘，不放置为‘.’,放置则为‘Q’ col[n]  bool的列标记，标记为True则该列不能再放皇后 dg[n+u-i]、udg[u+i] 对角线、反对角线bool标记 ...

用回溯法解决全排列问题 回溯搜索是深度优先搜索（DFS）的一种，回溯法通俗的将其采用的思想是“一直向下走，走不通就掉头”，类似于树的先序遍历。 dfs和回溯法其主要的区别是：回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。 为了减少存储空间，在深度优先搜索中，用标志的方法记录访问过的状态，这种处理方法使得深度优先搜索法与回溯法没什么区别了。 由于回溯法花费时间较长，所以对于没有明确的动态规划（DP）和递归解法的或问题要求满足某种性质（约束条件）的所有解或最优解时，才考虑使用回溯法。 # 核心代码 def main(): &n...

二叉树是最简单、常用的堆，是一颗符合堆性质的完全二叉树 它可以在O(logn)地插入或删除某个值，在O(1)地查询最大（最小值） 关于节点存储： 作为一棵完全二叉树，二叉堆完全可以用一个1-index的数组来存储， 对于节点p，p2即为左儿子，p2+1即为右节点。 同时，用size记录当前二叉堆中节点的个数。 以大根堆为例： 在数组中存储方式： 关于堆的操作： 现在我们考虑如何保证二叉堆的性质不被破坏。实际上，对于一个破坏堆性质的节点，我们可以使其上浮或下沉，因为最差也不过是上浮到顶或是下沉到底，所以只需要O(logn)的时间就可以使其不再破坏性质。 上浮操作 ...

并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作： 合并（Union）：把两个不相交的集合合并为一个集合。主要思想是路径压缩，把沿途的每个节点的父节点都设为根节点 查询（Find）：查询两个元素是否在同一个集合中。 合并（路径压缩）示意图： #核心代码 import numpy as np # 初始化数组 存放父节点 def init(n)：     glob...

又称单词查找树，是一种树形结构，是一种哈希树的变种。 典型应用： 1.统计 2.排序 3.保持大量字符串（不仅限于字符串） 经常被搜索引擎用于文本词频统计 优点： 利用字符串的公共前缀来减少查询时间，最大限度地减少无谓字符串的比较，查询效率比哈希树高 算法思路：            1.创建存储儿子节点的数组son[][26]         由于存储字母，最多只有26钟可能，故列为26 &nbsp...

def main(): p = "abab" s = "acbababa" print(kmp(p,s)) #求 next 数组 def buildNex(p): x=1 now=0 nex = [] nex.append(0) while x<len(p): # 如果相等 都加1 if p[now] == p[x]: x += 1 now += 1 nex.append(now)...