子数组换位问题 设a[0:n-1]是一个有n个元素的数组,k(0<=k<=n-1)是一个非负整数。 试设计一个算法将子数组a[0:k]与a[k+1,n-1]换位。要求算法在最坏情况下耗时O(n),且只用到O(1)的辅助空间。 初步思考:最简单的方法就是循环(n-k-1)次,将a数组的末尾数字插入到a[0]之前。 具体做法: (1) 首先开辟一个额外空间temp用于存放每一次a数组的末尾数据。 (2) temp <- a[n-1] (3) 将a[0: n-2] 每个数据都依次向后移动一位赋值给a[1: n-1]。 (4) a[0] <- temp (5) 循环执行(2) -(4) 步 (n-k+1)次。 代价分析: 时间代价—— O((n-1)*(n-k+1)) 即O(n^2 继续阅读 >>


陈文浩 18/04/03 22:49:49
buddy system简介: buddy system内存管理,努力让内存分配与相邻内存合并能快速进行(对于普通算法来讲,合并内存相当困难),它利用的是计算机擅长处理2的幂运算。 我们创建一系列空闲块列表,每一种都是2的倍数。 举个例子,如果最小分配单元是8字节,整个内存空间有1M。我们创建8字节内存块链表,16字节内存块链表,32字节内存块链表,64,128,256,512,1k,2K, 4K, 8K, 16K, 32K, 64K, 128K, 256K, 512K 和一个1M内存块链表。 除了1M内存块链表有一个可用单元,其余链表初始为空。所有的内存分配都会向上取整到2的倍数—-70K会向上取整到128K,15K会向上取整到16K,等等。 什么是Buddy buddy system允许一个被分配块单元平均拆分成两个大小是原来一半的块单元,这两个块单元互为伙伴。块B的伙伴必须满足大小跟块B一样大,并且内存地址相邻(才可以合并)。 另一个伙伴性质是所有块单元在内存中的地址必须能被它自 继续阅读 >>


楚东方 18/03/03 22:58:13
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] 继续阅读 >>


陈文浩 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 < 继续阅读 >>


娄泽豪 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 , 继续阅读 >>


刘生玺 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 = 继续阅读 >>


陈文浩 17/10/26 22:52:27
KMP算法的实现 假如你急着要跟MM急着约会,抱团取暖,就直接调到下面看吧,我爱啰嗦,全部看完的话,我怕你会忍不住想打我。 kmp算法又称“看毛片”算法,但我作为跟根正苗红的社会主义接班人, 外加吃货属性 ,所以我还是偏向叫它“烤馍片”算法,此算法是一个效率非常高的字符串匹配算法。比之bf暴力其实在某些情况下也没高到哪里去的啦。 KMP是三位大牛:D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的。其中第一位就是《计算机程序设计艺术》的作者!!! 开始不懂的时候,我在网上搜索资料,据说此算法是与红黑树,Manacher,遗传算法。。。等等可以强势提升逼格的牛逼算法之一,虽然很短,但确是属于难想难写的范畴里。 本着geek精神,经过一天的琢磨,凭借着搞不出来就不睡觉的社会主义建设者的拼搏精神终于在昨天的晚上顺利解决。喜迎十九大嘛。 多亏了小组温暖的空调(三十几度)。23333333~~~ 提到KMP绕不开的就是BF暴力 继续阅读 >>


刘嘉辉 17/10/10 18:01:13
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