地址:https://nanti.jisuanke.com/t/31716 思路:手算出n=4,5的结果可以发现 答案就是 2^(n-1) ,但是这里的 n<=10^100000就算用快速幂也会超时,因此需要用费马小定理: a^(p-1)=1 (mod p) ,将 n对(MOD-1)取模后-1 ,然后再用快速幂即可 Code :  ...

排序算法之归并排序 归并排序的主要思想为:分治法 即将问题分解为本质相同的若干个分问题,通过对分问题的求解,达到对总问题求解的目的。中间会用到编程中的一个重要思想—递归思想。 现在假设给定一个无序的长度为n的数组 我们可以取数组的中间值mid 然后我们可以得到两个数组,那么相似的,我们也可以把对这两个数组排序的问题看做同对原数组排序一样的分问题。 假定我们已经利用递归思想对上述两个数组...

最近遇到个挺有意思的算法题,题目不是很难,主要考察的是递归,题目是这样的: 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例: 输入:“23” 输出:[“ad”, “ae”, “af”, “bd&...

一、利用python实现单向链表 在程序中,经常需要将一组(通常是同为某个类型的)数据元素作为整体管理和使用,需要创建这种元素组,用变量记录它们,传进传出函数等。一组数据中包含的元素个数可能发生变化(可以增加或删除元素)。 对于这种需求,最简单的解决方案便是将这样一组元素看成一个序列,用元素在序列里的位置和顺序,表示实际应用中的某种有意义的信息,或者表示数据之间的某种关系。 这样的一组序列元素的组...

十大常用排序算法(java实现) 【前言】最近在重新研究算法,此篇博文供自己复习使用也为方便广大程序员同学!此文代码均为自己实现,通过对比经典解法校验,若有错请读者及时提出! - 【对比分析图】首先,我们先来对比分析一下这十大排序算法的特点: (一).冒泡排序(优化) 【题目】对于一个int数组,请编写一个冒泡排序算法,对数组元素排序。  给定一个int数组A及数组的大小n,请返回排序后...

题目描述 输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。 分析:首先需要判断n是不是负数,当n为负数的时候,直接用while循环判断会导致死循环,因为负数向左移位的话最高位补1 。 针对这种情况,要不就是对正数和负数的操作应该分开处理,要不就是找到一个对正数和负数都可以处理的方法。 如果是第二种方法可以把int型转成二进制的string类型,再统计string类型中1的...

题目: 实现一个特殊的栈,在实现栈功能基础上,并实现返回栈的最小值 要求: pop,push,getMin方法的时间复杂度O(1) 设计的栈类型可以使用现成的栈结构 Java的Stack类 Java的Stack类: 1. boolean empty()——测试堆栈是否为空。 2. Object peek( )——查看堆栈顶部的对象,但不从堆栈中移除它...

地址:http://acm.hdu.edu.cn/showproblem.php?pid=6446 思路:首先对a[1->n]的全排序分析,可以发现 ai->aj(就是排列中ai与aj相邻,ai在左边,aj在右)的次数为(n-1)的阶乘 (n-1)! (相当于将ai,aj当成一个数,n-1个数的全排列),也就是说任意两点的走的次数有 (n-1)! 次。 在对于树分析,对于一条边 t ,...

地址:http://codeforces.com/contest/620/problem/D 思路:对于交换0可以直接判断,1次可以将b[]保留下标并按值由小到大排序,在二分查找,即a[],b[]的总和差值ss,对b[]查找a[i]-ss/2的值即可,而对于2次交换,可以将b[]的所有组合情况保存在二分即可 Code :  ...

交换类排序、 1、冒泡排序算法 冒泡排序在众多排序算法中算比较简单的一个,基本思想是重复的进行整个数列的排序,一次比较两个元素(两两排序),如果它们顺序不符合就交换,重复这样直到数列没有再需要交换的数为止(结束条件)。就好像气泡一样,轻的气泡会往上漂浮,在不断漂浮的过程中,发生了两两交换过程,所以叫冒泡排序。 2、快速排序 1.概念 快速排序,听这个名字就能想到它排序速度快,它是一种原地排序(只需...

地址:http://codeforces.com/contest/1028/problem/C 思路:求n个区域中n-1个区域的交点,那么说明只有一个错误区域要排除掉,那么可以从头开始和从尾开始各自遍历一遍,找其有公共点的区域个数并不断缩小公共区域范围即可,这样总会有一次能够将错误区域排除掉,例如当从头开始遍历将错误区域也算在里面,导致后面的区域没有公共点时,那么从尾开始遍历就会先求后面的区域从而...

贪婪算法

算法

  

2019-06-16 20:22:26

本文参考书籍《图解算法》 一、在了解贪婪算法之前,首先需要了解一下 NP完全问题 NP完全问题(NP-C问题),是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题,即多项式复杂程度的非确定性问题。简单的写法是 NP=P?,问题就在这个问号上,到底是NP等于P,还是NP不等于P。。。。。。。 具体的详细描述可以参考百度百科,不过其中解释实在晦涩难...

算法分析

算法

  

2019-06-19 02:40:47

一般而言,需要考虑的因素有以下四点:  1.待排序的记录数目n的大小;  2.记录本身数据量的大小,也就是记录中除关键字外的其他信息量的大小;  3.关键字的结构及其分布情况;  4.对排序稳定性的要求。       设待排序元素的个数为n 1)当n量级为万到十万级:若内存有限,不要求稳定性:快速排序。若内存空间允许,且要求稳定...

POJ-2513-Colored Sticks

算法

  

2019-06-19 19:39:02

地址:http://poj.org/problem?id=2513 思路:可以用map将所有颜色编号并记录每种颜色的个数,由欧拉回路知,每个颜色个数为奇数的个数>2时就不成立,再利用并查集判断是否在同一个集合即可。 Code :  ...