I'am GongQi.
GongQi · 共 32 篇文章
找出数组中两个只出现一次的数字
转载,原文地址 http://blog.csdn.net/tulun/article/details/6792860 一个整型数组里除了两个数字之外,其它的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是o(n),空间复杂度是o(1)。 要求:首先阐述主要思路,然后编写代码实现。 (盛大笔试题) 考虑过程: 首先我们考虑这个问题的一个简单版本:一个数组里除了一个数字之外,其他的数字都出现了两次。请写程序找出这个只出现一次的数字。 这个题目的突破口在哪里?题目为什么要强调有一个数字出现一次,其他的出现两次?我们想到了异或运算的性质:任何一个数字异或它自己都等于0 。也就是…
2012-06-13 21:50 · 算法 · 评论(0)
随机数范围扩展方法总结
转载,原文地址 http://blog.csdn.net/hackbuteer1/article/details/7486704 题目: 已知有个rand7()的函数,返回1到7随机自然数,让利用这个rand7()构造rand10() 随机1~10。 分析:要保证rand10()在整数1-10的均匀分布,可以构造一个1-10 n的均匀分布的随机整数区间(n为任何正整数)。假设x是这个1-10 n区间上的一个随机整数,那么x%10+1就是均匀分布在1-10区间上的整数。由于(rand7()-1)*7+rand7()可以构造出均匀分布在1-49的随机数(原因见下面的说明),可以将41~49这样的…
2012-06-13 21:04 · 算法 · 评论(0)
求链表倒数第k个结点
题目描述: 输入一个单向链表,输出该链表中倒数第k个结点, 链表的倒数第0个结点为链表的尾指针。 第一反应是先遍历一遍链表,获得产度l,再遍历链表至l-k处,得到需求节点,这种做法不是最优 应该设置两个指针p、q,让p和q之间相距k个节点,然后让p、q同步向链表后走至链表尾节点,此时p指向的就是倒数第k个节点。 struct Node{ char data; Node* next; } Node *p,*q; Node* fun(Node *head,int k){ assert(k>=0);//有效性检验 p=q=head; for(;k>0&&q!=NULL;k--) q=q->next…
2012-06-12 21:17 · 算法 · 评论(0)
求亲和数算法
转载自 http://blog.csdn.net/v_JULY_v/article/details/6441279 题目描述: 求10000以内的所有亲和数 如果两个数a和b,a的所有真因数之和等于b,b的所有真因数之和等于a,则称a,b是一对亲和数。 例如220和284,1184和1210,2620和2924。 //求解亲和数问题 //第一个for和第二个for循环是logn(调和级数)*N次遍历,第三个for循环扫描O(N)。 //所以总的时间复杂度为 O(n*logn)+O(n)=O(N*logN)(其中logN为调和级数)。 //关于第一个for和第二个for寻找中,调和级数的说明:…
2012-06-11 19:18 · 算法 · 评论(0)
2011年搜狗在线测评笔试题
根据encode方法写出对应的decode方法。最后运行程序输出的结果就是要求的答案 在iteye上早有人讨论过这题了,写下来给自己备忘下。 解题思路是按照encode的顺序去decode 如对byte a进行了3次加密操作 1.^seed 2.>>>5 3.&0x7 对byte b进行了4次加密 1.<<16 2.^seed 3.>>>14 4.&0xf8 所以在解密时候,对a也要进行3次解密,对b进行4次解密,同时要保证顺序正确 完成对byte a,b的初步解密后,因为0x7的二进制形式为 0000 0111,0xf8为1111 1000, 同样应用相反的方式去解密,此时应该用 1110…
2012-06-08 11:08 · 算法 · 评论(0)
n阶Hanoi塔问题
int c=0; void move(char x,int n,char z){ printf("%d. Move disk %d from %c to %c \n",++c,n,x,z); } void hanoi(int n,char x,char y,char z){ if(n==1) move(x,1,z);//将编号1的圆盘从x移到z else{ hanoi(n-1,x,z,y);//将x上编号1--n-1的圆盘移到y,z做辅助 move(x,n,z);//将编号为n的圆盘从x移到z hanoi(n-1,y,x,z);//将y上编号为1--n-1的圆盘移到z,x做辅助 } } vo…
2012-05-17 16:58 · 算法 · 评论(0)
C语言位运算--将整数转换成二进制串以及反转整数后N位
// c primer plus上的内容,位运算 #include <stdio.h> char * itobs (int n,char * ps); void show_bstr(const char *); int invert_end(int num,int bits); int main(void){ char bin_str[8*sizeof(int)+1]; int number; puts("Enter integers and see them in binary."); puts("Non-numberic input terminates program."); whil…
2012-05-13 19:49 · 算法 · 评论(0)
单向扫描快排,双向扫描快排与非递归快排
import java.util.Stack; public class QuickSort { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int unsort[]={4,3,5,6,2,1},i; quickSort3(unsort,0,5); for(i=0;i<6;i++) System.out.print(unsort[i]+","); } //单向扫描快排 static void quickSort(int p[],int left…
2012-05-12 22:22 · 算法 · 评论(0)
C语言栈的简易实现,包含O(1)时间复杂度的min方法
#include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<string.h> //定义栈的初始分配空间 #define STACK_INIT_SIZE 100 //栈的分配增量 #define STACKINCRENMENT 10 typedef struct { char *top;//栈顶 char *base;//栈底 char min; int stacksize;//当前栈的大小 }stack; //栈的初始化 stack *initStack(stack *s) { s->base=(char*)malloc…
2012-05-12 21:44 · 算法 · 评论(0)
两个单向链表的第一个公共结点
转载,原文 http://blog.csdn.net/wcyoot/article/details/6426436 题目:两个单向链表,找出它们的第一个公共结点。 如果两个单向链表有公共的结点,也就是说两个链表从某一结点开始,它们的m_pNext都指向同一个结点。但由于是单向链表的结点,每个结点只有一个m_pNext,因此从第一个公共结点开始,之后它们所有结点都是重合的,不可能再出现分叉。所以,两个有公共结点而部分重合的链表,拓扑形状看起来像一个Y,而不可能像X。 看到这个题目,第一反应就是蛮力法:在第一链表上顺序遍历每个结点。每遍历一个结点的时候,在第二个链表上顺序遍历每个结点。如果此时两…
2012-05-08 20:33 · 算法 · 评论(0)
空间复杂度O(1)的归并问题
最近百度实习生笔试题里考了这个,要求归并算法里空间复杂度为O(1),不能设置辅助数组 # include <stdio.h> # define N 10 int binarySearch(int m,int* unsort ,int low,int high){ int mid; while(low<=high){ mid=(low+high)/2; if(unsort[mid]>m) high=mid-1; else if(unsort[mid]<m) low=mid+1; else return mid; } return low; } void merge(int * unsort,i…
2012-05-08 17:29 · 算法 · 评论(0)
字符串最大公共子序列以及最大公共子串问题
最大公共子序列 import java.util.Random; public class LCS { public static void main(String[] args){ //设置字符串长度 int substringLength1 = 20; int substringLength2 = 20; //具体大小可自行设置 // 随机生成字符串 String x = GetRandomStrings(substringLength1); String y = GetRandomStrings(substringLength2); // 构造二维数组记录子问题x[i]和y[i]的LC…
2012-05-08 15:30 · 算法 · 评论(0)
输入两个整数 n 和 m,从数列1,2,3.......n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来
转载的文章,原链接 http://www.cnblogs.com/pippo0725/articles/2046366.html #include <iostream> using namespace std; int length; void PrintSolutions(int *flag) { for (int i=0; i<length; i++) { if (flag[i] == 1) { cout << i+1 << " "; } } cout << endl; } void BagProblem(int m, int n, int *flag) { if(n<1 || m<1)…
2012-05-02 13:51 · 算法 · 评论(0)
数组最大上升子序列解法
#include <stdio.h> #define N 9 //O(nlogn) /**该方法可求最大上升子序列同时,可求最大不下降子序列 如{2,1,1,4}这种连续两个元素相等的序列,最大不下降子序列为{1,1,4} */ void lis1(int *a){ int i,j=0,temp,b[n],low,mid,high; b[0]=a[0]; for(i=1;i<N;i++) { if(a[i]>=b[j]){ b[++j]=a[i]; }else{ low=0;high=j; while(low<=high){ mid=(low+high)/2; if(a[i]>b[mid])…
2012-04-24 15:53 · 算法 · 评论(0)
支持正负数的大数乘法
#include <stdio.h> #include <string.h> #define N 1000//最大1000位 int input(char n[]){ char s[n],temp; int i,j,positive; scanf("%s",s); j=strlen(s); for(i=0;i<N;i++){ n[i]=0; } if(s[0]=='-'){ positive=-1; for(i=0;i<j-1;i++){ temp=s[i];s[i]=s[i+1];s[i+1]=temp; } j=j-1; }else{ positive=1; } for(i=0;i<j;…
2012-04-23 15:18 · 算法 · 评论(0)