袁家小少爷

分类

Idea(1) Java基础(1) Maven(2) Mybatis(2) Spring(2) SpringBoot(1) SpringMVC(1) 数据库(1) 未归档(26) 算法(27) 经验分享(2) 记Java开发的坑点(2)

/ 注册

全部文章（共68篇）

《算法设计与分析》--最长公共子序列随笔

1.定义一个给定序列的子序列是在该序列中删去若干元素后得到的序列。例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列，相应的递增下标序列为{2,3,5,7}。给定两个序列X和Y，当另一个序列Z既是X的子序列又是Y的子序列时候，称Z是序列X和Y的公共子序列。 ...

最长公共子序列

2019-07-04

0 537

《算法设计与分析》--循环赛日程表

1、概述：其实现在分治法用的地方非常的多，分而治之，递归解决可以帮助我们提升解决问题的效率 2、例子: 设有n=2的k次方个运动员要进行网球的循环赛，现在需要射击一个满足以下要求的比赛日程表: (1)每个选手必须与其他n-1个选手各赛一次; (2)每个选手一天只能赛次: (...

循环赛日程表

2019-07-03

0 926

《算法设计与分析》--最接近点对问题

1、最接近点对问题的定义给定平面上面的n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。 2、最接近点的分析事实上，最接近点的对数有可能是多余一对的，其实按照简单来说我们可以只找到其中的一对点来进行求解问题足矣。其实只要将每一点和其他n-1个点...

2019-07-03

0 881

《算法设计与分析》--线性时间选择随笔

定义：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素。（1）在某些特殊情况下，很容易设计出解选择问题的线性时间算法。如：当要选择最大元素或最小元素时，显然可以在O(n)时间完成。（一趟比较即可）（2）一般的选择问题，特别是中位数的选择问题似乎比最小（大）元素...

线性时间选择

2019-07-03

0 1445

《算法设计与分析》--快速排序随笔

快速排序:快排是一种基于分治策略的一个排序算法，其基本的思想是对于输入的子数组a[p:r]可以按照分解、递归求解、合并进行解决。分解:以a[p]为基准的元素将a[p:r]切分成3段，a[p:q-1],a[q]和a[q+1:r],这样就可以使得 a[p:q-1]中任何元素小于a[q],a[q+1]...

快速排序排序

2019-07-03

0 564

《算法设计与分析》--合并排序随笔

合并排序：合并排序其实也叫做归并排序，只是叫法不一样罢了，本质还是使用分治的思想实现对n个元素进行排序的算法，其基本思想是:将待排序的元素分解为大致相同的两个子数组，分别对两个子集合进行排序，最终将排好序的字数组进行合并，最终达到整个数组有序的过程。程序代码如下: //递归拆分排序 publ...

归并排序合并排序算法设计与分析

2019-07-03

0 639

《算法设计与分析》--棋盘覆盖问题随笔

棋盘覆盖问题概念:在一个2^k * 2^k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。显然，特殊方格在棋盘上面出现的位置有4的k次方种可能。棋盘覆盖问题是指，要用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨...

棋盘覆盖

2019-07-03

0 651

《算法设计与分析》--矩阵乘法随笔

矩阵乘法:矩阵乘法是线性代数中最常见的问题，在数值计算中应用的非常的广泛，设A和B为两个2个n*n的矩阵，它们的乘积同样是n*n的矩阵。并且矩阵乘法使用的还是大整数的那种分治法的思想。矩阵相乘最重要的方法是一般矩阵乘积。它只有在第一个矩阵的列数（column）和第二个矩阵的行数（row）相同时才...

矩阵乘法

2019-07-03

0 1018

《算法设计与分析》--大整数随笔

大整数算法：使用分治法的思想，就是把一些大的位数的整数进行一定程度的拆分，然后分别求解，最后合并为原问题的乘积。这里我们假设有两个大整数X、Y，分别设X=1234、Y=5678。现在要求X*Y的乘积，那我们可以采用分治的算法，将X、Y分别拆分为A与B、C与D，如下图: （1）首先将X...

2019-07-03

0 441

《算法设计与分析》--分治法的理解

就个人而言，本身我觉得这个问题都属于人们经过了大量的经验所总结出来的，所以其实我们在分解子问题的时候最好把问题的规模设计为大小都差不多的，通俗的来说：就是把一个问题分解成为大小相同的k个子问题是比较不错的。（事实上这种使子问题大致相同的做法是一种自平衡子问题的思想）。定义...

二分搜索查找算法分治法

2019-07-03

0 672