目录1 问题描述2 解决方案 1 问题描述 输入一个正整数N (1样例输入12样例输出6样例说明 12的约数包括：1,2,3,4,6,12。共6个 2 解决方案 具体代码如下：import java.util.Scanner;publicclass Main {publicstaticvoid main(String[] args) {int count = 0;Scanner in = new Scanner(System.in);int n = in.nextInt();for(int i = 1;i <= n;i++) {if(n % i == 0)count++;}System.out.println(count);} } 原文：http://www.cnblo...
好菜啊，现在才学三分。三分：查找凸形（凹形）函数的极大值（极小值）。模板1：double three_divide() {double l=0,r=1000;double mid=(l+r)/2;double mm=(l+mid)/2; while(r-l>=eps){if(F(mid)>F(mm))r=mid;else l=mm;mid=(l+r)/2;mm=(l+mid)/2;}return F(mid); } 模板2： double three_divide() {double l=0,r=1000;double m1=(l+l+r)/3;double m2=(l+r+r)/3; while(r-l>=eps){if(F(m2)>F(m1))r=m2;else l=m1;m1=(l+l+r)/3;m2=(...
目录1 问题描述2 解决方案 1 问题描述问题描述给定带权无向图，求出一颗方差最小的生成树。输入格式输入多组测试数据。第一行为N,M，依次是点数和边数。接下来M行，每行三个整数U,V,W，代表连接U,V的边，和权值W。保证图连通。n=m=0标志着测试文件的结束。输出格式对于每组数据，输出最小方差，四舍五入到0.01。输出格式按照样例。样例输入4 51 2 12 3 23 4 24 1 12 4 34 61 2 12 3 23 4 34 1 12 4 31 3 30 0样例输出Case 1: 0.22C...
1029 旧键盘 （20 分)旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。输入格式：输入在 2 行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过 80 个字符的串，由字母 A-Z（包括大、小写）、数字 0-9、以及下划线 _（代表空格）组成。题目保证 2 个字符串均非空。输出格式：按照发现顺序，在一行中输出坏掉的...
一、穷举法 思想：在没有很好的算法进行运算的情况下，可以尝试穷举所有情况。 EX：顺序找K值二、回溯、搜索 回溯的思想：能进则进，不能进则换，不能再后退的过程。 EX：八皇后、树和图遍历三、递归分治 思想：通过统一的方法，对整体中的部分进行循环调用，最终实现对整体的处理。 EX：二分找K值、快速排序、归并排序四、贪心法 思想：每次求解的时候都去看当前的最佳解，每次贪心求最佳最后得到的总体的结...
目录1 问题描述2 解决方案2.1 动态规划法 1 问题描述现需找零金额为n，则最少需要用多少面值为d1 < d2 < d3 < ... < dm的硬币？（PS：假设这m种面值d1 < d2 < d3 < ... < dm的硬币，其中d1 = 1，且每种硬币数量无限可得） 2 解决方案2.1 动态规划法本文编码思想参考自《算法设计与分析基础》第三版，具体讲解如下： 具体代码如下：package com.liuzhen.chapter8;publicclass ChangeMaking {publicvoid getChangeMakingN(int[] coi...
目录1 问题描述2 解决方案 1 问题描述问题描述 自己实现一个比较字符串大小的函数，也即实现strcmp函数。函数：int myStrcmp(char *s1,char *s2) 按照ASCII顺序比较字符串s1与s2。若s1与s2相等返回0，s1>s2返回1，s1<s2返回-1。具体来说，两个字符串自左向右逐个字符相比（按ASCII值大小相比较），直到出现不同的字符或遇‘\0‘为止（注意‘\0‘值为0，小于任意ASCII字符）。如： "A"<"B" "a">"A" "computer">"compare...
单调队列：队列中元素单调递增或递减，可以用双端队列实现（deque），队列的前面和后面都可以入队出队。单调队列优化dp：问题引入：dp[i] = min( a[j] ) ，i-m < j <= i普通的做法是O(nlogn)，但是当n很大是，这个复杂度就不行了，考虑用单调队列优化来达到O(n)。单调队列优化dp时维护的一般都是两个值{ id（下表），value（值）}，且它们都保持单调。对于这个问题，我们维护一个两个值都单调递增的序列。查询：队首不断删除，直到...
参考资料《算法（第4版）》 — — Robert Sedgewick， Kevin Wayne 归并排序的概念归并排序的实现我是这样来描述的：先对少数几个元素通过两两合并的方式进行排序，形成一个长度稍大一些的有序序列。然后在此基础上，对两个长度稍大一些的有序序列再进行两两合并，形成一个长度更大的有序序列，有序序列的的长度不断增长，直到覆盖整个数组的大小为止，归并排序就完成了。 归并排序的两种实现方式：递归和循环归并排序有两...
数据结构与算法笔记 - 绪论 1. 什么是计算2. 评判DSA优劣的参照(直尺)3. 度量DSA性能的尺度(刻度)4. DSA的性能度量的方法5. DSA性能的设计及其优化x1. 理论模型与实际性能的差异x2. DSA优化的极限(下界) 计算机与算法计算机科学（computer science）的核心在于研究计算方法与过程的规律，而不仅仅是作为计算工具的计算机本身，因此E. Dijkstra及其追随者更倾向于将这门科学称作计算科学（computing science）。计算 = 信息处理计算...
分治动态规划贪心回溯分支界定几大算法的适用范围对比 一、分治分治，就是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。分治法常常跟递归一起使用，借助递归，我们可以方便地将问题分解再将结果合并。分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；递归：若子问题规模较小而容易被解决则直接解，否则递归...
二分查找 对于递增序列，顺序查找的时间复杂度为O(n)，如果序列太大，就很难承受在有序序列中，利用二分查找可以有效减少时间复杂度，其时间复杂度为O(logn)对于递增数列，二分查找如下：#include<cstdio> int binarySearch(int myArray[], int left, int right, int x){while(left <= right){int mid = (left + right) / 2;if(myArray[mid] == x)return mid;else if(myArray[mid] < x){left = mid + 1;}elseright = mid - 1;}retu...
上一章的算法笔记，并不算一个算法系列的一个合适的開始。而本章将会介绍一种产生随机全排列的方法，下一章開始，就正式開始我们的排序算法了。在我们的排序算法演示器中，我们须要一组随机的数据来作为排序的開始，而本章，就会产生这么一组随机数据。（一）实现分析我们须要一组随机的数据，并且似乎产生的方法不会太难。我们仅仅须要通过rand()函数获得一个随机数，让其对count（排序的规模）取模，结果作为数组的索引，其值是当...
/// <summary>/// 步骤:/// 1.记录当前待排元素/// 2.标记顺序表有序查找区域下界和上界/// 3.在顺序表有序查找区域中折半查找等待排序元素的位置/// 4.把顺序表有序查找区域的某些元素后移一位，以空出位置给等待排序的元素/// 5.在空出的位置填写当前排序元素/// </summary>/// <param name="elements"></param>staticvoid SqListSort(int[] elements) {int low; // 有序区域下界int mid; // 有序区域中界int high;// 有序...
pair的常见用法pair是一个很实用的“小玩意”，当想要将两个元素绑在一起作为一个合成元素、又不想要因此定义结构体时，使用pair可以很方便地作为一个代替品。也就是说，pair实际上可以看作一个内部有 两个元素的结构体，且这两个元素的类型是可以指定的，如下面的短代码所示：struct pair{typeName1 first;typeName2 second; } pair的定义头文件#include<utility> using namespace std; 因为实现map时候已经使用了pair，所以...