ACOOLAcer

算法基础

/ 注册

全部文章 / 算法基础（共13篇）

排序——快速排序

基本思想确定数字序列的基准数，使用两个指针，分别指向一头一尾，分别与基准数进行对比，直到指针相遇，基准数与序列的第一个数交换，然后分而治之，采用递归，进行新一轮比较。算法 # tinput为数组 &nbs...

2021-06-08

0 333

排序——冒泡排序

基本思想每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。算法思路如果由n个数进行排序，只需将n-1个数归位，也就是进行n-1趟操作。 “每一趟”都需要从第一位开始进行相邻两个数的比较，将较小的一个数放在后面比较完毕后挪一位继续比较下面两个相邻数的大小...

2021-06-07

0 358

排序——最大数

题目描述给定一个数组由一些非负整数组成，现需要将他们进行排列并拼接，使得最后的结果最大，返回值需要是string类型否则可能会溢出解题思路 1. 先对列表进行降序排序 2.将列表中的值分别转换成string类型 3.对比...

2021-03-20

0 477

数据结构——BFS广度优先遍历之图的最短路径

主要思想： 1.采用邻接表存储图结构 2.求最短路径采用队列存储BFS遍历结果 3.首先入队第一个结点，再遍历所有与第一个结点相连的所有结点并入队，与此同时，更新当前点到其他点的路径长度 ...

2021-02-26

0 426

数据结构——BFS广度优先遍历之走迷宫

import numpy as np from queue import Queue def main(): global g, q, d,n,m &n...

2021-02-25

0 393

数据结构——DFS深度优先遍历之树的重心

题目描述给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。思路：...

2021-02-23

1 487

数据结构——DFS深度优先遍历

深度优先遍历(Depth First Search)的主要思想是：思想：不撞南墙不回头 1、首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点； 2、当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直至所有...

2021-02-23

0 418

数据结构——DFS深度优先遍历之n皇后问题

n皇后是指将n个皇后放在n-n的国际象棋棋盘上，使皇后不能相互攻击到，即任意两个皇后不能再同一行、同一列或同一斜线上。算法基本思路： 1.当N个皇后摆放好，依次输出 2.对每行U的0-N列遍历，比较第U个皇后是否会发生冲突（横、竖、对角线） 3.放置好后对该皇后、横...

2021-02-23

0 559

数据结构——DFS深度优先遍历之全排列

用回溯法解决全排列问题回溯搜索是深度优先搜索（DFS）的一种，回溯法通俗的将其采用的思想是“一直向下走，走不通就掉头”，类似于树的先序遍历。 dfs和回溯法其主要的区别是：回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。为了减少存储空间，在深度优先搜索中，用...

2021-02-22

0 653

数据结构——堆排列

二叉树是最简单、常用的堆，是一颗符合堆性质的完全二叉树它可以在O(logn)地插入或删除某个值，在O(1)地查询最大（最小值）关于节点存储：作为一棵完全二叉树，二叉堆完全可以用一个1-index的数组来存储，对于节点p，p2即为左儿子，p2+1即为右节点。同时，用size记录当前二叉...

2021-02-21

0 458