- 博客(70)
- 资源 (2)
- 收藏
- 关注
RSS订阅
原创 排序算法小结
最近刚好有空，所以打算全面的看一遍排序，故先总结一下之前和最近看的一些排序算法。排序的基本概念和排序方法概述一、排序的基本概念1.排序 首先来看一下排序的基本概念，排序(Sorting)是按关键字的非递减或非递增顺序对一组记录重新进行排列的操作。2.排序的稳定性 这是一个重要的性质，当排序排序记录中的关键字Ki(i=1,2,...,n)都不相同时，则任
2015-12-15 23:29:42
628
原创 指针数组和数组指针的区别
指针数组和数组指针的区别 经常遇到的问题，又容易混淆，所以做个总结。 指针数组和数组指针分别是什么意思？这个用中文来讲不太好明了，但是英语的表达就清晰多了。 指针数组：array of pointers，即用于存储指针的数组，也就是数组元素都是指针 数组指针：a pointer to an array，即指向数组的指针。 还要注意他们的用法区别 例如
2015-12-30 18:19:46
528
1
原创 【算法导论】最优二叉搜索树
最优二叉搜索树 假定设定一个程序，实现英语文本到法语的翻译。对英语文本中出现的灭个单词，我们需要查找对应的法语单词。为了实现这些查找槽，我们可以创建一棵二搜索叉树，将n个英语单词作为关键词，对应的法语单词作为关联数据。由于文本中的每个单词都要进行搜索，我们希望花费在搜索上的总时间尽量减少。通过红黑树或其他平衡搜索树结构，我们可以假定每次搜索时间为O(lgn)，但是，单词出现的频率是不
2015-12-29 21:55:26
17532
7
原创 【动态规划】最长公共子序列
最长公共子序列问题 最长公共子序列问题(longest-common-subsequence problem)给定两个序列X=和Y=,求X和Y长度最小的公共子序列(可以不连续)。接下来将展示如何用动态规划方法高效地求解LCS问题。步骤1：刻画最长公共子序列的特征 如果用暴力搜索方法求解LCS问题，就要穷举X的所有子序列，对每个子序列检查它是否也是Y的子序列，记录找到的最长
2015-12-29 13:06:31
738
原创 【动态规划】原理
动态规划原理 虽然我们已经用动态规划方法解决了两个问题，但你可能还是弄不清应该在何时使用动态规划。接下来，我们关注适合应用动态规划方法求解的最优化问题应该具备的两个要素：最优子结构和子问题重叠。以及再次讨论备忘方法，更深入地讨论在自顶向下方法中如何借助备忘机制来充分利用子问题重叠特性。最优子结构 用动态规划方法求解最优化问题的第一步就是刻画最优解的结构。如果一个问题的最优解
2015-12-28 11:34:44
1509
原创 【动态规划】矩阵链乘法
矩阵链乘法 求解矩阵链相乘问题时动态规划算法的另一个例子。给定一个n个矩阵的序列（矩阵链），我们希望计算它们的乘积 A1A2...An 为了计算表达式，我们可以先用括号明确计算次序，然后利用标准的矩阵相乘算法进行计算。完全括号化(fully parenthesized)：它是单一矩阵，或者是两个完全括号化的矩阵乘积链的积。 例如如果有矩阵链为,则共有5种完全括号化的矩阵乘
2015-12-27 14:35:39
39910
4
原创 【序列型动态规划】拦截导弹
1044 拦截导弹 1999年NOIP全国联赛提高组题目描述 Description 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入描述 Input D
2015-12-26 14:47:51
1919
原创 【动态规划】钢条切割
花了几天的时间钻研算法导论里的动态规划，做个总结。首先，算法导论真是经典，可惜水平有限，于是乎忽略了一些推理与数学理论，留着有机会再深入，其次可能自己的理解不是很到位，有错误的地方欢迎提出，谢谢。 动态规划（dynamic programming）与分治算法相似，都是通过组合子问题的解来求解原问题(在这里，“programming”指的是一种表格法，并非编写计算机程序)。 一、与分
2015-12-26 14:01:34
945
原创 【蓝桥第七周】守望者的逃离
守望者的逃离题目描述 Description恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。到那时，岛上的所有人都会遇难。守望者的跑步速度为17m/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m，不
2015-12-21 14:43:24
763
原创 【蓝桥第七周】城市游戏
城市游戏题目描述 Description鲍勃是一个战略游戏编程专家。在他的新城市建设游戏游戏环境如下:一个城市建立了地区,有街道、树木,工厂和建筑物。在该地区仍然有一些空间是空置的。他游戏的战略任务是赢得尽可能多的房租钱从这些免费空间。赢得房租钱你必须建造建筑,只能是长方形的,长和宽。鲍勃正试图找到一种方法来建造尽可能最大的在每个区域。但他遇到一些问题——他是不允许破坏已经存在
2015-12-21 14:19:26
478
原创 【蓝桥第七周】安排会议室
安排会议室题目描述 Description在大公司里，会议是很多的，开会得有场子，要场子你得先在电子流里预订。如果你是项目组新来的小弟，那么恭喜你，每天抢订会议室的任务就光荣的分给你了。老大要求你尽可能多的订会议室，但是这些会议室之间不能有时间冲突。输入描述 Input DescriptionN(1 ≤ N ≤ 500)，第一行表示会议室的数目。接下来每行会有2个数字，
2015-12-21 13:44:53
476
原创 【蓝桥第七周】M苹果N盘子
POJ 1664 求m个苹果放入n个盘子的不同放法数目 题目描述 Description 把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。输入描述 Input Description第一行是测试数据的数目t（0 输出描述 Output Description对输入的每组数据M和N，用
2015-12-21 13:16:32
590
原创 【蓝桥第六周】排列
排列题目描述 Description 给出数字n以及x和y，请输出数字1~n的所有排列，但要求排列中x必须在y的左边方向，其它的数位置随意。输入描述 Input Description 读入整数n、x和y ( 1输出描述 Output Description 每行n个用空格隔开的数，表示一个符合条件的排列。并且所有排列按字典序输出。样例输入 S
2015-12-21 12:44:17
376
原创 【蓝桥第六周】奥运火炬登珠峰
RQNQJ PID202 / 奥运火炬登珠峰题目描述 Description 5月8日，在世界人民的共同关注下，象征着和平、友谊、圣洁的奥运火炬终于来到了世界之巅——珠穆朗玛峰……登上珠峰可不是所有人都能办得了的，火炬手们为了登山要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让火炬手需要各种的数量的氧和氮。火炬手有一定数量的气缸。每个气缸都有重量和气体容量。火炬
2015-12-20 22:31:27
564
原创 【蓝桥第五周】小小故事
小小故事题目描述 Description在天朝的鱼C总基地，大厅的墙壁上有N盏灯，分别按顺序从1到N编号。每盏灯都可以每打开或关上。在每一秒钟，如果第I+1盏灯是亮的，那么第I盏灯在下一秒会变化它的状态；特别的，如果第1盏灯是亮的，那么第N盏灯在下一秒会变化它的状态。小甲鱼老师给你某一时刻所有灯的状态，希望你能求出它们在M秒之后的状态。输入描述 Input Description
2015-12-20 21:56:43
580
原创 【蓝桥第四周】ThreeSum
ThreeSum题目描述 Description假设n个整数数组S, a、b、c均为数组S中的元素，要求找出不重复的序列，其中a + b + c = 0，并且要求为非递减序列(即a输入描述 Input Description第一行输入一个数n，第二行依次输入n个元素。输出描述 Output Description每一行输出一个不重复且满足a+b+c=0的序列。样例输入
2015-12-20 20:50:16
394
原创 【蓝桥第三周】汉诺塔
汉诺塔问题题目描述 Description（1）有三根柱子A、B、C。A柱上有n个圆盘，最大的一个在底下，其余一个比一个小，依次叠上去。（2）每次移动一个圆盘，小盘只能叠在大盘上面。（3）把所有圆盘从A柱全部移到C柱。试解出n个圆盘从A柱全部到C柱上的移动次数，并展示n个圆盘的移动过程。输入描述 Input Description圆盘个数n输出描述 Output
2015-12-20 20:37:54
498
原创 【蓝桥第二周】01背包问题
01背包问题题目描述 Description 有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大。输入描述 Input Description 第一行两个整数分别是N件物品与背包容量V接下来分别是N行，每行两个数分别是当前物品的重量w与价值v;输出描述 Output Desc
2015-12-19 23:21:45
487
原创 【蓝桥第二周】矩阵最大和
矩阵最大和[问题描述]给定一个由整数组成二维矩阵（r*c），现在需要找出它的一个子矩阵，使得这个子矩阵内的所有元素之和最大，并把这个子矩阵称为最大子矩阵。 例子：0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 其最大子矩阵为：9 2 -4 1 -1 8 其元素总和为15。 输入第一行有两个的整数r，c（0
2015-12-19 22:20:27
420
原创 【蓝桥第三周】老鼠走迷宫
老鼠走迷宫问题描述老鼠走迷宫是递回求解的基本题型，试以程式求出由入口至出口的路径，入口为左上角，出口为右下角。迷宫图7×7墙的表示：█ 路径的表示：◇INPUT（无）OUTPUT显示迷宫：显示路径：解法一[解题思路]深度搜索，在题的基础上考虑了多种路径到达终点的状况，输出最短路径，需要注意的是a[index].an
2015-12-19 16:18:03
770
原创 【蓝桥第三周】排队购票问题
排队购票问题问题描述 一场球赛开始前，售票工作紧张进行。每张球票50元，现有很多人排队购票，其中m个人手持50元钞票，n个人手持100元钞票。假设售票处没有零钱，求这些人购票时，售票处不至于找不开钱的不同排队总数。（约定：拿同样面值钞票的人兑换位置也视为同一种排队。）输入描述：输入m和n输出描述：排队总数输入样例：（多组测试数据）15 1220 10输
2015-12-19 15:11:34
1975
原创 【蓝桥第一周】最少硬币问题
最少硬币问题问题描述 设有n 种不同面值的硬币，各硬币的面值存于数组T［1:n］中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins［1:n］中。对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。编程任务：对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0≤m≤20001，编程计算找钱m的最少硬币数
2015-12-19 13:39:07
559
原创 常用类型的取值范围
以vs2012(编译器)里的定义，对一些常用类型的取值范围做个小结。int类型#define INT_MIN (-2147483647 - 1) /* minimum (signed) int value */#define INT_MAX 2147483647 /* maximum (signed) int value */#define
2015-12-19 11:34:06
875
原创 1014 装箱问题
1014 装箱问题 2001年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold题目描述 Description有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。输入描述 Inpu
2015-12-18 19:19:34
349
原创 【基数排序】
基数排序(Radix Sorting) 基数排序是和前面所述各类排序方法完全不相同的一种排序方法。前述各类排序方法都是建立在关键字比较的基础上，而基数排序不比较关键字的大小，它是根据关键字中各位的值，通过对待排序记录进行若干趟“分配”与“收集”来实现排序的，是一种借助于多关键字排序的思想对单关键字排序的方法。一、多关键字的排序先看一个具体例子。已知扑克牌中52张牌的次序关系为
2015-12-16 18:52:07
701
原创 【选择排序】堆排序
堆排序(Heap Sort) 从简单选择排序可见，选择排序的主要操作是进行关键字间的比较，因此改进简单选择排序应从如何减少“比较”出发考虑。显然，在n个关键字中选出最小值，至少进行n-1次比较，然而，进行在剩余的n-1个关键字中选择次小值并一定要进行n-2次比较，若能利用前n-1次比较所得信息，则可减少以后各趟排序中所用的比较次数。 堆排序就是基于这种思想，对简单选择排序进行了
2015-12-16 16:08:09
2745
原创 【选择排序】简单选择排序
选择排序的基本思想是：每一趟从待排序的记录选出关键字最小的记录，按顺序放在已排序的记录序列的最后，直到全部排完为止。 简单选择排序(Simple Selection Sort)也称作直接选择排序。[算法思想]1)设待排序的记录存放在数组r[1..n]中。第一趟从r[1]开始，通过n-1次比较，从n个记录中选出关键字最小的记录，记为r[k]，交换r[1]和r[k]。2)第二趟从
2015-12-16 13:35:31
1175
原创 【交换排序】冒泡排序
冒泡排序(Bubble Sort) 冒泡排序是基于交换排序的一种排序，交换排序的基本思想，是两两比较待排序记录的关键字，一旦发现两个记录不满足次序要求时则进行交换，直到整个序列全部满足要求为止。冒泡排序是一种最简单的交换排序方法，它通过两两比较相邻记录的关键字，如果发生逆序，则进行交换，从而使关键字小的记录如气泡一般逐渐往上“漂浮”(左移)，或者使关键字大的记录如石块一样逐渐向下“坠落
2015-12-15 18:01:06
727
原创 【插入排序】希尔排序
希尔排序(Shell’s Sort) 希尔排序又称“缩小增量排序”(Diminishing Incerment Sort)，是插入排序的一种，因D.L.Shell于1959年提出而得名。直接插入排序当待排序的记录个数较少且待排序序列的关键字基本有序时，效率较高。希尔排序基于以上两点，从“减少记录个数”和“序列基本有序”两个方面对直接插入排序进行了改进。[算法思想]
2015-12-15 14:31:11
879
原创 【插入排序】折半插入排序
折半插入排序(Binary Insertion Sort) 直接插入排序采用顺序查找法查找当前记录在已排好序的序列中插入位置，这个“查找”操作可利用“折半查找”来实现，由此进行的插入排序称之为折半插入排序(Binary Insertion Sort)。[算法思想]1)将待排序的记录存放在数组r[1..n]中，r[1]是一个有序序列。2)循环n-1次，每次使用折半查找法，查找
2015-12-15 12:54:10
894
原创 【插入排序】直接插入排序
直接插入排序(Straight Insertion Sort)[算法思想]1)设待排序的记录存放在数组r[1..n]中，r[1]是一个有序序列.2)循环n-1次，每次使用顺序查找法，查找r[i](i=2, ... ,n)在已排好序的序列r[1..i-1]中的插入位置，然后将r[i]插入表长为i-1的有序序列r[1..i-1]，直到将r[n]插入表长为n-1的有序序列r[1..n
2015-12-15 00:00:34
715
原创 next_permutation(全排列算法)
STL提供了两个用来计算排列组合关系的算法，分别是next_permutation和prev_permutation。首先我们必须了解什么是“下一个”排列组合，什么是“前一个”排列组合。考虑三个字符所组成的序列{a,b,c}。这个序列有六个可能的排列组合：abc，acb，bac，bca，cab，cba。这些排列组合根据less-than操作符做字典顺序(lexicographical)的排序。也就
2015-12-14 22:07:36
28869
6
原创 链表的基本功能实现
前言 ： 链表的实现，查询，插入，删除，这些简单的操作。在平时的学习中，经常会遇见，故以单链表为例做个总结。链表的优缺点，以及适用情况在前面的一篇文中(http://blog.csdn.net/c18219227162/article/details/50274243)就提到过，就不作介绍了。一、链表的定义单链表存储结构typedef struct LNode{
2015-12-12 19:48:48
690
原创 数组与链表的区别
数组 数组，即线性表的顺序表示，指的是用一组地址连续的存储单元依次存储线性表的数据元素，其特点是逻辑上相邻的数据元素，其物理次序也是相邻的。假设线性表的每个元素需占用k个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储起始位置。线性表中第i+1个元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系 LOC(ai+1)=LOC(ai)
2015-12-12 13:18:29
340
原创 STL-泛型算法(前篇)
泛型算法(generic algorithm) 前言:在网上找了一堆C++泛型算法的资料,总感觉看起来很没有条理,于是乎搬出书架上的.重温并且全面的总结一下知识点. 来自第十章 泛型算法。 称它们为"算法", 是因为它们实现了一些经典算法的公共接口, 如排序和搜索; 称它们为"泛型的", 是因为它们可以用于不用类型的元素和多种容器类型(不仅包括标准库类型
2015-12-10 22:46:57
440
原创 【散列表】哈希表
散列表(hash table) 散列表，也叫哈希表，是实现字典操作的一种有效数据结构。尽管最坏情况下，散列表中查找一个元素的时间与链表中查找的时间相同，达到O(n)，然而实际应用中，散列查找的性能是极好的。在一些合理的假设下，在散列表中查找一个元素的平均时间是O(1)。是普通数组概念的推广，在散列表中不是直接把关键字key作为数组下标，而是根据关键字计算出相应下标。在构造散列函
2015-12-10 13:25:05
1074
原创 【蓝桥第二周】和尚挑水
和尚挑水问题 [问题描述]某寺庙里7个和尚:轮流挑水，为了和其他任务不能冲突，各人将有空天数列出如下表：和尚1: 星期二,四;和尚2: 星期一,六;和尚3: 星期三,日;和尚4: 星期五;和尚5: 星期一,四,六;和尚6: 星期二,五;和尚7: 星期三,六,日;请将所有合理的挑水时间安排表 【程序输入输出】input:请输入和尚1的空闲时
2015-12-09 23:44:17
608
1
原创 【蓝桥第一周】计数的梦
一、RQNOJPID11 / 计数的梦题目描述 Bessie 处于半梦半醒的状态。过了一会儿，她意识到她好像在数羊，不能入睡。Bessie的大脑反应灵敏，仿佛真实地看到了她数过的一个又一个数。她开始注意每一个数码：每一个数码在计数的过程中出现过多少次？ 给出两个整数 M 和 N (1 例如考虑序列 129..137: 129, 130, 131,
2015-12-09 20:24:33
422
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人