公司和企业的区别,免费关键词排名优化,什么叫网站定位,wordpress 图片懒加载1、有序数组查找 假设一个数组#xff0c;事先在你未知的情况下#xff0c;以某一点分段有序排列。比如#xff1a;#xff08;0,0,0,1,2,2,3 变成 0,0,1,2,2,3,0#xff0c;定需要查找的数#xff0c;在当前数组中查找#xff0c;存在#xff0c;返回ture#xff0c;… 1、有序数组查找 假设一个数组事先在你未知的情况下以某一点分段有序排列。比如0,0,0,1,2,2,3 变成 0,0,1,2,2,3,0定需要查找的数在当前数组中查找存在返回ture不存在返回false。注意这次数组中有重复的数字哦 格式 第一行输入数字n接下来一行输入数组A[n],数组A[n]满足题目描述的条件即分段有序。如(2, 2, 0, 0, 1, 1)第三行输入要查找的target值。接下来一行输出true或者false。 样例输入 7
1 2 2 2 0 1 1
0 样例输出 true #includeiostream
#includealgorithm
using namespace std;
int main()
{int n;cinn;int a[n];for(int i0;in;i)cina[i]; int target,mid;cintarget;sort(a,an);//对输入的数组排序int l0, rn-1;//二分查找while(rl){mid(lr)/2;/*if(targeta[mid]){couttrueendl;return 0;}*/if(targeta[mid]) lmid1;else if(targeta[mid]) rmid-1;else {couttrueendl;return 0;} }coutfalseendl;return 0;
} 2、特殊质数 7331是一个特殊的质数因为我们去掉个位得到的733是一个质数再次去掉个位得到的73又是一个质数再去掉个位后得到的7依然是一个质数。对于形似这种的质数我们称呼它为特殊质数。 写一个程序对给定的待求特殊质数的位数 N (1≤N≤8)求出所有对应位数的特殊质数注意数字1不被看作一个质数。 输入包括一个整数为待求特殊质数的位数 N。 输出长度为N的特殊质数列表每行一个。 #includeiostream
using namespace std;
int n;
bool IsPrime(int a){for(int i2;i*ia;i){if(a%i0)return false;}return true;
}
void dfs(int sum,int cur){if(curn)coutsumendl;for(int i1;i9;i){if(i%20)continue;int asumsum*10i;if(IsPrime(asum)){dfs(asum,cur1);}}
}
int main(){while(cinn){dfs(2,1);dfs(3,1);dfs(5,1);dfs(7,1);}return 0;
} 3、颜色排序 给定由n个图案图案是红色白色或者蓝色其中的一种开始的时候他们的顺序是混乱的。请你设计一种排序算法使得相同颜色的图案紧挨着并且顺序为红白蓝。 为了方便这里我们用0, 1, 2分别代替红白蓝三种颜色请将他们排序出来 看这个例子如2 2 1 0 1 2 0排序后变成0 0 1 1 2 2 2 注意你不能使用库函数里面的排序算法哦 要求时间复杂度 O(n),空间复杂度 O(1) 格式 第一行输入数字n第二行输入A[n], 其中数组里面只包含0, 1, 2三个数。第三行输出排好序的A[n] 样例输入 8 1 2 1 2 0 0 0 2 样例输出 0 0 0 1 1 2 2 2 void SortByN(int a[], int length)
{if (a NULL || length 0){return;}//重新申请一个数组const int N 200;int b[N];//把新申请的数组全部初始化为0for (int i 0; i N; i){b[i] 0;}//遍历a数组for (int i 0; i length; i){//例如a[0] 10;那么b[key] b[10] 1;表示有一个10 a[4] 10;//那么b[key] b[10] 11 2,表示此时有两个10int key a[i];b[key];//意思就是b数组里面存放的是a数组中某个元素的个数b[10]表示在a数//组当中10出现的次数b[0]表示0在a数组当中出现的次数}int index 0;for (int i 0; i N; i){//如果b[0] 0;表示a数组当中没有0那么不执行这个循环例如这里a是一个年龄数组假设最小的年龄是18//那么b[0] -- b[17]都是等于0那么第二个循环都不执行第一个循环执行i加到了18b[18]2//那么a数组当中有两个18而且这两个18就是最小的数字那么a[0] 18; a[1] 18;for (int j 0; j b[i];j){a[index] i;index;}}
} 4、单独的数字 一个整型数组中有一个元素只出现一次其它元素都出现两次。求出只出现一次的元素。要求线性时间复杂度不能使用额外空间。聪明的你能搞定吗格式第一行输入数字n代表有n个数根据题意很明显n是奇数第二行输入数组A[i], i从0n-1.最后输出单独的数字。样例1输入71 3 2 0 3 2 1输出0 /*那么这个题的突破口在哪里呢注意这个数组的特殊性其它数字都出现了两次只有一个数出现了一次。可以想到运用异或运算任何一个数字异或它自己都等于0。如果我们从头到尾依次异或数组中的每一个数那么最终的结果就是那个只出现一次的数字因为其他出现两次的数字全部在异或中被抵消为0了异或运算遵循交换分配率。举个栗子2 3 4 2 3所有数字依次异或运算2 xor 3 xor 4 xor 2 xor 3 (2 xor 2) xor (3 xor 3) xor 4 0 xor 0 xor 4 4最终结果4就是我们要找的那个只出现一次的数字。*/
#includeiostream
using namespace std;
int main(){int num;int f(int a[],int n,int num);int n;cinn;int a[n];for(int i0;in;i){cina[i];}coutf(a,n,num)endl;return 0;
}
int f(int a[],int n,int num){for(int i0;in;i)num^a[i];return num;
} 5、第一个没有出现的正数 给定一个数组从 11 到 nn找出数组中第一个没出现的正数。 例如 给定[1,2,0]则返回 33。 给定[3,4,-1,1]则返回 22。 注意 算法需要 \mathcal{O}(n)O(n) 的时间复杂度以及线性的空间复杂度。 #includeiostream
using namespace std;
int main()
{int n;cinn;int a[1000001]{0};int tmp;for(int i0;in;i){cintmp;if(tmp0) a[tmp];}for(int i1;in;i){if(a[i]0){couti;return 0;}}
} 转载于:https://www.cnblogs.com/geziyu/p/9665777.html
