kruskal算法的一点就是不能形成环路,而且是从排列好的边集合依次选出最小的边,每次选出的顶点都要放在同一个边集合中,之后在顶点集合选两个顶点的边,要求这两个顶点不能在边集合中,这样才能保障不形成环路。 一、链表表示 #include<stdio.h> #include<stdlib.h> /* kruskal,最小生成树,利用链表,并查集的知识 */ typedef struct{ int bef; int aft; int weight; }pic_node;//图中点的结构体 typedef struct find_set{ int data; struct find_set *next; }NODE;//点集合的节点 typedef struct set_head{ NODE *head; NODE *tail; int flag; }HEAD;//点集合的头 HEAD set[20];//点集合 pic_node arr[20];//开始时候数据 int edge 继续阅读 >>


陈文浩 18/01/15 15:08:38
算法训练 Lift and Throw 问题描述   给定一条标有整点(1, 2, 3, …)的射线. 定义两个点之间的距离为其下标之差的绝对值.   Laharl, Etna, Flonne一开始在这条射线上不同的三个点, 他们希望其中某个人能够到达下标最大的点.   每个角色只能进行下面的3种操作, 且每种操作不能每人不能进行超过一次.   1.移动一定的距离   2.把另一个角色高举过头   3.将举在头上的角色扔出一段距离   每个角色有一个movement range参数, 他们只能移动到没有人的位置, 并且起点和终点的距离不超过movement range.   如果角色A和另一个角色B距离为1, 并且角色B没有被别的角色举起, 那么A就能举起B. 同时, B会移动到A的位置,B原来所占的位置变为没有人的位置. 被举起的角色不能进行任何操作, 举起别人的角色不能移动.同时, 每个角色还有一个throwing range参数, 即他能把举起的角色扔出的最远的距离. 注意, 一个角色只能被扔到没有别的角色占据的位置. 我们认为一个角色 继续阅读 >>


陈文浩 17/12/10 15:59:37
Leetcode 1: Two Sum 问题描述 给定一个整数数组和一个目标数,返回两个下标,使数组中这两个下标所代表的数字之和等于目标数。 你可以认为每组输入有且仅有一个正解,除此之外,两个下标不应当相等。 例子: 给定一数组nums = [2, 7, 11, 15],目标数target = 9 因为nums[0] + nums[1] = 2 + 7 = 9 = target,所以最后返回[0, 1]。 解题思路 显然的,本题最直接明了的方式就是暴力循环两个数组,依次算出所有和,并判定它是否与目标数相等,可以写出: class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> ret { 0, 1 }; for (int i = 0; i < nums.size(); i++) { 继续阅读 >>


娄泽豪 17/12/04 22:47:03
什么是模式匹配? 给定一个子串,要求在某个字符串中找出与该子串相同的所有子串,这就是模式匹配。也就是我们平常在记事本中的“查找选项”所运用的算法,其实说白了就是让我们编程实现:在一个大的字符串中找到一个小的字符串并返回其第一个匹配字符的下标 BF算法 时间复杂度为O(m×n),m和n分别是模式串与主串的长度。 思路:将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果 代码实现: #include<stdio.h> #include<string.h> #include<iostream> #define MAX 255 using namespace std ; typedef struct { int count ; char str[MAX]; }PP ; int BF(PP S ,PP T, int pos ) { int i 继续阅读 >>


刘生玺 17/11/26 15:07:00
#include<stdio.h> #include<stdlib.h> #include<time.h> int RANDOMIZED_SELECT(int a[],int p,int r,int i); int RANDOMIZED_PARTITION(int a[],int p,int r); int PARTITION(int a[],int p,int r); void swap(int *a,int *b); int RANDOM(int p,int q); int main() { int a[] = {10,9,8,7,6,5,4,3,2,1}; int i = 3; printf("第%d小:%d\n",i,RANDOMIZED_SELECT(a,0,9,i)); return 0; } void swap(int *a,int *b) { int temp; temp = *a; *a = *b; *b = temp; } int RAND 继续阅读 >>


陈文浩 17/10/26 22:52:27
import java.util.Scanner; public class Hex2Dec { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.println("Enter a hex number"); String hex = input.nextLine(); System.out.println("The decimal value for hex number"+ hex + "is " + hexToDecimal(hex.toUpperCase()));//全部转换成了大写字母 } public static int hexToDecimal(String hex) { int decimalValue = 0; for(int i = 0;i < hex.leng 继续阅读 >>


陈文浩 17/09/26 22:56:39
int pmatch(char *string,char *pat) { int i=0,j=0; int lens=strlen(string);//主字符串 int lenp=strlen(pat);//需要匹配的字符串 while(i < lens && j < lenp) { if(string[i]==pat[j])//如果顺利匹配,下标都移动 { i++; j++; } else if(j==0)//如果需要匹配的字符串首字母都不匹配,主串移动下标 i++; else //都不是的情况 j=failure[j-1]+1; } return ((j==lenp) ? (i-lenp):-1);//返回的是主串匹配的首元素下标 } void fail(char *pat) { int n 继续阅读 >>


陈文浩 17/09/09 11:42:37
#include<stdio.h> void perm(char *list,int i,int n); void swap(char *a,char *b); int main() { char a[5]={'a','b','c','\0'}; perm(a,0,2); } void perm(char *list,int i,int n) { int j; if(i==n)//满足长度就输出 { for(j=0;j<=n;j++) printf("%c",list[j]); printf("\n"); } else { for(j=i;j<=n;j++) { swap(&list[i],&list[j]);//每次进行交换,然后不断递归就可以得到新结果 perm(list,i 继续阅读 >>


陈文浩 17/09/09 11:07:27
1. Find The Multiple ( POJ 1426) Description Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits. Input The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input. Ou 继续阅读 >>


王良 17/07/30 20:43:04
DFS(深度优先搜索) 深度优先搜索算法(英语:Depth-First-Search,简称DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。(Wiki) (直到走不下去才往回走) 基本模板 int check(参数) { if(满足条件) return 1; return 0; } void dfs(int step) { 判断边界 { 相应操作 } 尝试每一种可能 { 满足check条件 标记 继续下一步dfs(step+1) 恢复初始状态(回溯的时候要用到) 继续阅读 >>


李猛 17/07/29 15:01:09