以下是为您整理出来关于【算法笔记】合集内容，如果觉得还不错，请帮忙转发推荐。
目录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...