big-yellow的算法工程师进阶之路-编程思维

Big-Yellow的算法工程师进阶之路 一、基础算法 二、基础数据结构 2.1 链表[1] 2.1.1 基础理论 链表是一种以链的形式来存储数据的数据结构。链表的结构:每一个数据都与其后一个数据相连(有时候也与前一个数据相连)。链表中的每个元素都被称为一个结点, 在形状上链表就像自行车链条一样 一节接着一节 链表的优点 1、因为链表是一个链式的数据结构,你可以快速地添加和移除其中的元素。并且

算法学习:堆排序-编程思维

一、关于二叉树和堆的基本概念 1、二叉树 每个节点,最多有2个子树的数结构。 左右子树,也是最多有2个子节点。 2、满二叉树 除最后一层外,每个节点都有2个子节点。   3、完全二叉树 存在的节点,和满二叉树的节点完全对应。   4、堆: Max Heap:最大的元素永远在根节点 任一非终端节点数据均不小于其左、右孩子节点。   Min Heap: 最小的元素永远在根节点 任一非终端节点数据均

算法学习:归并排序-编程思维

1、概念 归并排序使用了二分法,归根到底的思想还是分而治之。 拿到一个长数组,将其不停的分为左边和右边两份,然后以此递归分下去。 将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合 并成一个有序表,称为二路归并。 归并排序是一种稳定的排序方法。   2、举例 1)合并两个有序数组,伪代码 arr_a = [1,4,5,6] a

算法学习:快速排序-编程思维

1、基本思想 取待排序数组第一个数作为参照数,建立left和right数组,left存储小于参照数的数组集合,right存储大于参照数的数组集合,然后分别对left和right进行递归调用排序。   2、举例 [11,2,3,43,23,5,6,9,10] 取任意的一个数为基准数 temp = arr[0] 遍历数组,将比temp小的元素放在temp的左边,比temp大的元素放在temp的右

算法学习:基数排序-编程思维

1、基数排序的应用场景 把一系列单词,按照英文字典的顺序排序,如 a,alice,bob .... 基数排序不具有普适性。   2、定义 基数排序(radix sort)属于“分配式排序”(distribution sort),又称“筒子法”(bucket sort)或bin sort。 顾名思义,它是通过键值的部分资讯,将要排序的元素分配至某些“桶”中,以此达到排序的作用。 基数排序法是稳定

算法学习:汉诺塔算法-编程思维

汉诺塔问题 背景 3根柱子(x,y,z轴),64个盘子(在x轴上)从下至上盘子是从大到小的。 将盘子从x轴搬到z轴有2个条件: 第一:1次只能挪动1个盘子 第二:大的盘子不能放到小的盘子上面 思路 1.对于问题N,如果问题N-1已经解决了,那么N就很容易解决 2.问题点转换为了如何求解 N-1 过程 汉诺塔的解决过程: 假如要挪动6个盘子,那么要做以下三步: 第一步:将第 2 - 6个盘子

算法学习:简单选择排序-编程思维

题目:给定一个数组 [3,2,11,-9,0,12],如何将这个数组进行排序,得到一个有序序列 排序过程:   1.选择数组中最小元素的索引(从0到length-1),和第一个元素(索引为0) 的两个值交换位置:[-9,2,11,3,0,12]   2.选择数组中最小元素的索引(从1到length-1),和第一个元素(索引为0) 的两个值交换位置:[-9,0,11,3,2,12]   3.选择

算法学习:直接插入排序-编程思维

1、插入排序核心思想   插入排序的核心思想是将数组中所有的元素和前面已经排序好的元素相比较。   如果后面选择的元素比排序的元素小,则交换位置,直到比较完成。   2、插入排序过程举例   arr = [1,22,-1,9,23,5]   思路,将一个数字插入到有序部分,对比;找到插入位置;插入。      1)将数组分成两部分     -有序部分 [1]     -无序部分 [22,-1

算法学习:希尔排序(插入排序)-编程思维

1、插入排序有两种,直接插入排序和希尔排序 2、希尔排序核心思想 希尔排序本质也是一种插入排序,但是是根据简单插入排序进行优化有的一种更加高效的版本,别称是缩小增量排序。 希尔排序的核心思想是将排序数组按照增量进行分组,然后对分组的元素进行直接插入排序,循环缩小分组增量,最后当增量长度为1是排序结束。 3、举例:给不同身高的人进行排序 第一步:分组,找一个间隔分组,间隔取4。间隔通常是总长度

算法学习:冒泡排序-编程思维

1、思路 对于数组s:   每一轮,遍历数组,比较相邻的两个数,交换位置,大的放后面;   第一轮,得到最大的数,比较len(s) - 1 次   第二轮,得到第二大的数。。。。   第len(s)-1轮,得到第2小和最小的数。   所以要比较len(s)-1 轮。   2、举例 原始数组:[9,5,4,3,2] 第一轮   • 第一次:9>5==>[5,9,4,3,2]   •

高精度算法-编程思维

高精度加法第三次学习...内容自己理解吧 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 #define MAXLEN 110 6 int main(){ 7 char a1[MAXLEN],b1[MAXLEN];/

算法学习——递推之杨辉三角_stars-one-编程思维

算法描述 杨辉三角 算法思路 将杨辉三角看成一个二维数组,开头和末尾都为1 第一行和第二行已经被前面的1给赋值了,所以我们直接从第三行开始赋值,a[2][1]开始,因为下标是从0开始的,a[2][1] = a[1][0]+a[1][1],也就是等于2,依次递推下去 打印(for循环),每打印出一行则换一行,System.out.println 我的打印处理没有处理好,如果数组

算法学习——回溯之伯努利装错信封问题_stars-one-编程思维

算法描述 某人给6个朋友每个人都写了一封信,同时写了这6个朋友地址的信封,有多少种投放信笺的方法,使得每封信与信封上的收信人都不相符? 算法思路 6封信可能出现的结果: 所有的信都是在对应的信封中,也就是所有的信都放对了信封,这种情况只有一种 部分信放错了信封 全部信都放错了信封 题目要求的就是求最后一种情况,也就是全部新都放错了信封 定义一个数组a[i],a[1

算法学习——动态规划之装载问题_stars-one-编程思维

算法描述 两艘船各自可装载重量为c1,c2,n个集装箱,各自的重量为w[n],设计一个可以装载的方案,使得两艘船装下全部集装箱 算法思路 将第一艘船尽量装满(第一艘船放的集装箱的重量之和接近c1),剩余的集装箱放入第二艘船,若剩余的集装箱重量之和大于第二艘船,则无解 定义一个一维数组,a[n] 存放对应的集装箱的重量 定义一个数组,m[i][j]表示第一艘船还可装载的重量j,可取

算法学习——动态规划之点数值三角形的最小路径_stars-one-编程思维

算法描述 在一个n行的点数值三角形中,寻找从顶点开始每一步可沿着左斜或者右斜向下直到到达底端,使得每个点上的数值之和为最小 右图为一个4行的点数值三角形 算法思路 接收用户输入行数n 使用一个二维数组a[n+1][n+1]来存放各个点上的数值,数值可以由用户输入或者是随机生成 定义一个二维数组(用来存放方向)direction[n+1][n+1],存放1或0,1代表右,0代表左

算法学习——递归之快速排序_stars-one-编程思维

算法描述 快速排序 算法思路 快速排序算法的基本思路为从数组中选择一个数为基准数,之后,将比基准数小的数放在左边,比基准数大的数放在右边(分为了两个区),之后将左边(小于基准数)与右边(大于基准数)再次进行上述操作,一直重复直到无法再分为止 用户输入n,使用随机数产生n个数放入到数组a中 调用递归方法sort() PS:下面的数组a是全局变量 算法实现 System.out

算法学习——贪心算法之可拆背包_stars-one-编程思维

算法描述 已知道n种物品和一个可容纳c重量的背包,第i种物品的重量为wi,价值为pi,装包的时候可以把物品拆开(即可只装每种物品的一部分),设计如何装包,使装包所得整体的价值最高? 算法思路 首先,我们要知道,n种物品以及他们对应的价值,都是由用户输入的 我们使用贪心算法,每一步取最大效益的物品放入背包之中(及单位价值为最高的物品 单位价值=pi/wi) 由以上思路,我们可以定义

算法学习——递推之摆动数列_stars-one-编程思维

算法描述 已知递推数列: a(1)=1 a(2i)=a(i)+1 a(2i+1)=a(i)+a(i+1) (i为正整数) 求该数列的第n项,以及前n项中的最大值为多少,其n为多少? 算法思路 采用递推的方法,使用一维数组,从2开始递推,一直递推到n a(i)=a(i/2)+1(n为偶数) a(i)=a((i+1)/2)+((i-1)/2) (n为奇数) 我们只需要使用一个