问题描述：一个栈stack，具有push和pop操作，其时间复杂度皆为O(1)。设计算法max操作，
求栈中的最大值，该操作的时间复杂度也要求为O(1)。
可以修改栈的存储方式，push，pop的操作，但是要保证O(1)的时间复杂度，空间时间复杂
度无要求。
可以创建一个类，类里有两个栈，一个栈S维持正常的push、pop操作，另一个Sm保存当前的最大值
假设元素以5,4,1,2,3,10,9,8,6,7,15顺序入栈，则两个栈中存储的元素如下图所示：
S 5 4 1 2 3 10 9 8 6 7 15
Sm 5 10 15
struct max_stack{
stack<int> s1;
stack<int> sm;
};
max_stack s;
void my_push(int k) {
if(!s.s1.empty()){
if(k>s.sm.top()) s.sm.push(k);
s.s1.push(k);
} else {
s.s1.push(k); s.sm.push(k);
}
}
void my_pop() {
if(!s.s1.empty()) {
if(s.s1.top()==s.sm.top()) s.sm.pop();
s.s1.pop();
}
}
int my_max() {
if(!s.s1.empty()) {
return s.sm.top();
}
}
二、约瑟夫环问题
瑟夫环问题的原来描述为，设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人
开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止
报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计
算法求n个人出圈的次序。换一种表述如下
问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始
报数。求胜利者的编号。
具体数学上给出通项公式：
f(0)=0
f(n)=(f(n-1)+m)%n , (n>1)
int joseph(int n,int m) {
int *f=new int[n+1];
f[0]=f[1]=0;
for(int i=2;i<n+1;i++)
f[i]=(f[i-1]+m)%i;
int result=f[n];
delete []f;
return result;
}
如果求解原表述的解，只需要将result加1即可。
三、寻找明星
问题描述：有个聚会有N人参加，其中N-1个是群众。1个是明星。其中所有群众都认识明星，
明星不认识任何群众，群众之前是否认识不知道。
假设有个机器人能问问题A是否认识B？时间复杂度为O（1），那么设计一个算法用最小的复
杂度找出明星。
从问题的描述中可以知道，对于任意两个人A、B，如果A认识B那么A一定不是明星；如果A不
认识B，那么B一定不是明星。将所有人存储在数组中，每次比较询问A[0]是否认识A[1]，将一
定不是明星的人放在数组的最后，并且在以后可以不用管了。代码描述如下
int famous(int A[],int n) {
int j=n;
while(j>1) {
if(A[0] knows A[1])
swap(A[0],A[1]);
swap(A[1],A[--j]);
}
return A[0];
}
由于询问和交换的时间复杂度是O(1),while循环进行了n-1次，所以时间复杂度是O(n).
四、最小交流次数
问题描述：有n个战士其中n>4他们手中都有不同的情报，假设每个人通过交流能过得双方所有
的情报。设计一个算法使得用最少的交流次数使得所有的战士都获得全部的情报，给出算法并
给出最小交流次数？
可以建立递推式:
f(4)=4
f(n)=f(n-1)+2 , n>4
假设在战士人数是n-1时需要f(n-1)次交流，则增加一个人时，如下步骤进行：
1、第n个战士和前面任意一个战士交流一次
2、前n-1个战士互相交流，使得前面n-1个战士都有所有战士获得的情报
3、第n个战士和前面任意一个战士交流一次。
这样n个战士都有所有情报了。
五、数星星
问题描述：A和B晚上无聊就开始数星星。每次只能数K个（20<=k<=30）A和B轮流数。最后
谁把星星数完谁就获胜，那么当星星数量为多少时候A必胜？
这是一个博弈的问题，我们可以从胜利条件出发，A必胜，那么最后一次是A数，并且剩下星星
的个数 20<=k<=30 ，那么如何保证呢？最后50颗由B先数，B数m颗，然后A数剩下的50-m
颗。好了，那么第一次A数的话必须保证，第一次A数完之后，剩下的个数是50的倍数。所以
案就明了了,星星的数量应满足
50k+20 <= N <=50K+30 , k是整数
六、求连续子数组的最大和
这是一个动态规划问题递推式为
M(i)=max{M(i-1)+a(i),a(i)},i>0
int max_sub_sum(int *A,int n) {
int thissum=0,maxsum=0;
for(int i=0;i<n;i++) {
thissum+=A[i];
if(thissum>maxsum) maxsum=thissum;
if(thisum<0) thisum=0;
}
return maxsum;
}
七、二分查找
用二分法查找已排序的大小为n的数组A是否存在value，如果存在返回下标，否则返回-1。
int b_search(int *A,int n,int value) {
int low=0,high=n-1;
while(low<=high) {
int mid=(low+high)/2;
if(A[mid]==value) return mid;
else if(A[mid]>value) high=mid-1;
else low=mid+1;
}
return -1;
}
1.从考试成绩中划出及格线
（1）及格线是10的倍数
（2）保证至少有60%的学生及格
（3）如果有所有的学生都高于60分，则及格线为60分。
算法分析：
关键信息点为“保证至少有60%的学生及格”，可将分数线的概念转换为人数，即只需统计每个档次的人数，若60以上档次的人数就是全体人员则分数线为60，否则去寻找（由高分到低分）最先达到60%人数的档次。
java实现如下：
- public class Exam{
- public int findPassLine(int[] scores){
- int num=scores.length;
- int[] record=new int[num+1];//记录每一个档次的人数
- for(int i=0;i<num;i++){
- switch(scores[i]/10){
- case 10:record[10]++;break;
- case 9:record[9]++;break;
- case 8:record[8]++;break;
- case 7:record[7]++;break;
- case 6:record[6]++;break;
- case 5:record[5]++;break;
- case 4:record[4]++;break;
- case 3:record[3]++;break;
- case 2:record[2]++;break;
- case 1:record[1]++;break;
- case 0:record[0]++;break;
- }
- }
- int sumh=0;//记录60分以上所有人数
- int suml=0;//记录60分以下所有人数
- for(int j=record.length-1;j>=0;j--){
- if(j>=6)
- sumh+=record[j];
- }
- suml=10-sumh;
- if(sumh==10){//所有人都在60分以上
- System.out.println("所有人的分数均高于60，分数线为：");
- return 60;
- }
- else{
- //有高分档次向下遍历
- for(int k=record.length-1;k>0;k--){//10~0遍历
- if(record[k]>=6){
- return 10*k;
- }
- else
- record[k-1]+=record[k];//向下累加
- }
- }
- return 0;
- }
- public static void main(String[] args){
- int a[]={99,89,79,69,0,0,4,5,80,50};
- System.out.println(new Exam().findPassLine(a));
- int b[]={100,100,100,100,100,80,0,0,0,0};
- System.out.println(new Exam().findPassLine(b));
- int c[]={100,100,100,100,100,100,0,0,0,0};
- System.out.println(new Exam().findPassLine(c));
- int d[]={100,100,100,100,100,100,60,80,70,90};
- System.out.println(new Exam().findPassLine(d));
- }
- }
public class Exam{ public int findPassLine(int[] scores){ int num=scores.length; int[] record=new int[num+1];//记录每一个档次的人数 for(int i=0;i<num;i++){ switch(scores[i]/10){ case 10:record[10]++;break; case 9:record[9]++;break; case 8:record[8]++;break; case 7:record[7]++;break; case 6:record[6]++;break; case 5:record[5]++;break; case 4:record[4]++;break; case 3:record[3]++;break; case 2:record[2]++;break; case 1:record[1]++;break; case 0:record[0]++;break; } } int sumh=0;//记录60分以上所有人数 int suml=0;//记录60分以下所有人数 for(int j=record.length-1;j>=0;j--){ if(j>=6) sumh+=record[j]; } suml=10-sumh; if(sumh==10){//所有人都在60分以上 System.out.println("所有人的分数均高于60，分数线为："); return 60; } else{ //有高分档次向下遍历 for(int k=record.length-1;k>0;k--){//10~0遍历 if(record[k]>=6){ return 10*k; } else record[k-1]+=record[k];//向下累加 } } return 0; } public static void main(String[] args){ int a[]={99,89,79,69,0,0,4,5,80,50}; System.out.println(new Exam().findPassLine(a)); int b[]={100,100,100,100,100,80,0,0,0,0}; System.out.println(new Exam().findPassLine(b)); int c[]={100,100,100,100,100,100,0,0,0,0}; System.out.println(new Exam().findPassLine(c)); int d[]={100,100,100,100,100,100,60,80,70,90}; System.out.println(new Exam().findPassLine(d)); } }输出：
50
80
100
所有人的分数均高于60，分数线为：
602.亮着电灯的盏数
一条长廊里依次装有n(1 ≤ n ≤ 65535)盏电灯，从头到尾编号1、2、3、…n-1、n。每盏电灯由一个拉线开关控制。开始，电灯全部关着。
有n个学生从长廊穿过。第一个学生把号码凡是1的倍数的电灯的开关拉一下；接着第二个学生把号码凡是2的倍数的电灯的开关拉一下；接着第三个学生把号码凡是3的倍数的电灯的开关拉一下；如此继续下去，最后第n个学生把号码凡是n的倍数的电灯的开关拉一下。n个学生按此规定走完后，长廊里电灯有几盏亮着。
注：电灯数和学生数一致。算法分析：无任何算法可言，只需要按照题目描述实现一边，不知道有啥捷径
java实现如下：
- //import java.lang.StringBuilder;
- public class Light{
- public int lightNum(int[] lights){
- //刚开始默认全部打开，1开，0闭
- int i=1,n=lights.length-1,num=0;
- while(i<=n){
- for(int j=1;j<=n;j++){//遍历1--n栈灯(0号元素忽略)
- if(j%i==0){
- if(lights[j]==1){
- //开着的等被关闭
- lights[j]=0;
- num--;
- }
- else if(lights[j]==0) {
- //关闭的灯被打开
- lights[j]=1;
- num++;
- }
- }
- }
- i++;//第i个人
- }
- return num;
- }
- //打印亮着的编号
- public void printLightsNum(int[] lights){
- StringBuilder sb=new StringBuilder();
- sb.append("它们分别是:");
- for(int i=1;i<=lights.length-1;i++){
- if(lights[i]==1){//开着
- sb.append(" ");
- sb.append(i);
- }
- }
- System.out.println(sb.toString());
- }
- public static void main(String[] args){
- for(int i=10;i<=100;i+=10){
- System.out.println("初始时"+i+"栈灯灭着!");
- int[] lights=new int[i+1];
- Light obj=new Light();
- System.out.println("触动后还剩下"+obj.lightNum(lights)+"栈灯开着！");
- obj.printLightsNum(lights);
- System.out.println("--------------------------------------------------");
- }
- }
- }
//import java.lang.StringBuilder; public class Light{ public int lightNum(int[] lights){ //刚开始默认全部打开，1开，0闭 int i=1,n=lights.length-1,num=0; while(i<=n){ for(int j=1;j<=n;j++){//遍历1--n栈灯(0号元素忽略) if(j%i==0){ if(lights[j]==1){ //开着的等被关闭 lights[j]=0; num--; } else if(lights[j]==0) { //关闭的灯被打开 lights[j]=1; num++; } } } i++;//第i个人 } return num; } //打印亮着的编号 public void printLightsNum(int[] lights){ StringBuilder sb=new StringBuilder(); sb.append("它们分别是:"); for(int i=1;i<=lights.length-1;i++){ if(lights[i]==1){//开着 sb.append(" "); sb.append(i); } } System.out.println(sb.toString()); } public static void main(String[] args){ for(int i=10;i<=100;i+=10){ System.out.println("初始时"+i+"栈灯灭着!"); int[] lights=new int[i+1]; Light obj=new Light(); System.out.println("触动后还剩下"+obj.lightNum(lights)+"栈灯开着！"); obj.printLightsNum(lights); System.out.println("--------------------------------------------------"); } } }
输出：初始时10栈灯灭着!
触动后还剩下3栈灯开着！
它们分别是: 1 4 9
--------------------------------------------------
初始时20栈灯灭着!
触动后还剩下4栈灯开着！
它们分别是: 1 4 9 16
--------------------------------------------------
初始时30栈灯灭着!
触动后还剩下5栈灯开着！
它们分别是: 1 4 9 16 25
--------------------------------------------------
初始时40栈灯灭着!
触动后还剩下6栈灯开着！
它们分别是: 1 4 9 16 25 36
--------------------------------------------------
初始时50栈灯灭着!
触动后还剩下7栈灯开着！
它们分别是: 1 4 9 16 25 36 49
--------------------------------------------------
初始时60栈灯灭着!
触动后还剩下7栈灯开着！
它们分别是: 1 4 9 16 25 36 49
--------------------------------------------------
初始时70栈灯灭着!
触动后还剩下8栈灯开着！
它们分别是: 1 4 9 16 25 36 49 64
--------------------------------------------------
初始时80栈灯灭着!
触动后还剩下8栈灯开着！
它们分别是: 1 4 9 16 25 36 49 64
--------------------------------------------------
初始时90栈灯灭着!
触动后还剩下9栈灯开着！
它们分别是: 1 4 9 16 25 36 49 64 81
--------------------------------------------------
初始时100栈灯灭着!
触动后还剩下10栈灯开着！
它们分别是: 1 4 9 16 25 36 49 64 81 100
--------------------------------------------------
从输出中反推原理：最后亮着灯的编号都是可以开方的数，这时为什么呢？
题中告知所有灯刚开始是关着的，也就说最后想开着，必须触动开关奇数次，即"该灯所对应的编号数，其公约数有奇数个"。那么问题就转化为"什么样的数有奇数个公约数",由于已经知道答案了(完全平方数)，所有只好用反证法。
证： 若对任意实数C具有奇数个公约数，且C不是完全平方数
则有C的任意一对公约数m1!=m2，设C有n对公约数，
则C的公约数总数=n*2+2(可以被自身和1整除)=2*(n+1)为偶数
此结论与已知"C具有奇数个公约数"矛盾，故C是完全平方数。
有了上面的结论，即可以直接去找1--n内的完全平方数即可,复杂度就降为O(n)了，我想这就是华为将此题做为中级难度题目的捷径思路了吧。
3.验证括号是否匹配
输入一串字符串，其中有普通的字符与括号组成（包括‘（’、‘）’、‘[’,']'）,要求验证括号是否匹配，如果匹配则输出0、否则输出1.
Smple input：dfa(sdf)df[dfds(dfd)] Smple outPut:0算法分析：利用栈来实现，所有左括号入栈，遇到右括号就进行出栈，看是否匹配。
java实现：
- import java.util.Scanner;
- import java.util.Stack;
- public class Match{
- public static void main(String[] args){
- Boolean isMatch=true;
- Stack<Character> stack=new Stack<Character>();
- Scanner s=new Scanner(System.in);
- while(true){
- char ch=s.nextLine().charAt(0);
- if(ch=='q')
- break;
- else{
- switch(ch){
- case '{':;
- case '[':;
- case '(':
- stack.push(ch);break;
- case '}':
- if(stack.empty())
- isMatch=false;
- else if(stack.pop()!='{')
- isMatch=false;
- break;
- case ']':
- if(stack.empty())
- isMatch=false;
- else if(stack.pop()!='[')
- isMatch=false;
- break;
- case ')':
- if(stack.empty())
- isMatch=false;
- else if(stack.pop()!=')')
- isMatch=false;
- break;
- }
- }
- }
- if(isMatch)
- System.out.println("匹配！");
- else
- System.out.println("不匹配");
- }
- }
import java.util.Scanner; import java.util.Stack; public class Match{ public static void main(String[] args){ Boolean isMatch=true; Stack<Character> stack=new Stack<Character>(); Scanner s=new Scanner(System.in); while(true){ char ch=s.nextLine().charAt(0); if(ch=='q') break; else{ switch(ch){ case '{':; case '[':; case '(': stack.push(ch);break; case '}': if(stack.empty()) isMatch=false; else if(stack.pop()!='{') isMatch=false; break; case ']': if(stack.empty()) isMatch=false; else if(stack.pop()!='[') isMatch=false; break; case ')': if(stack.empty()) isMatch=false; else if(stack.pop()!=')') isMatch=false; break; } } } if(isMatch) System.out.println("匹配！"); else System.out.println("不匹配"); } }
C/C++:
- void main()
- 13.{//子函数声明
- 14. void InitStack(SqStack &S);//初始化空栈
- 15. int StackEmpty(SqStack S);//判空
- 16. void push(SqStack &S,int e);//进栈
- 17. void pop(SqStack &S,int &e);//出栈
- 18. //主函数开始
- 19. SqStack s;//初始化空栈
- 20. InitStack(s);
- 21. char ch[100],*p;int e;
- 22. p=ch;
- 23. printf("输一个含义有()[]{}的括号表达式:\n");
- 24. gets(ch);
- 25. while(*p)
- 26. {
- 27. switch (*p)
- 28. {
- 29. case '{':
- 30. case '[':
- 31. case '(': push(s,*p++);break;//只要是左括号就入栈
- 32. case '}':
- 33. case ']':
- 34. case ')':pop(s,e);
- 35. if ((e=='{' && *p=='}') ||(e=='[' && *p==']') || (e=='(' && *p==')'))
- 36. p++;
- 37. else
- 38. {printf("括号不匹配!");exit(OVERFLOW);}
- 39. break;
- 40. default :p++;//其他字符就后移
- 41. }
- 42. }
- 43. if (StackEmpty(s))
- 44. printf("括号匹配成功");
- 45. else
- 46. printf("缺少右括号！");
- 47. printf("\n");
- 48.}
void main() 13.{//子函数声明 14. void InitStack(SqStack &S);//初始化空栈 15. int StackEmpty(SqStack S);//判空 16. void push(SqStack &S,int e);//进栈 17. void pop(SqStack &S,int &e);//出栈 18. //主函数开始 19. SqStack s;//初始化空栈 20. InitStack(s); 21. char ch[100],*p;int e; 22. p=ch; 23. printf("输一个含义有()[]{}的括号表达式:\n"); 24. gets(ch); 25. while(*p) 26. { 27. switch (*p) 28. { 29. case '{': 30. case '[': 31. case '(': push(s,*p++);break;//只要是左括号就入栈 32. case '}': 33. case ']': 34. case ')':pop(s,e); 35. if ((e=='{' && *p=='}') ||(e=='[' && *p==']') || (e=='(' && *p==')')) 36. p++; 37. else 38. {printf("括号不匹配!");exit(OVERFLOW);} 39. break; 40. default :p++;//其他字符就后移 41. } 42. } 43. if (StackEmpty(s)) 44. printf("括号匹配成功"); 45. else 46. printf("缺少右括号！"); 47. printf("\n"); 48.}
4.回文数
判断回文数，是返回1
算法分析：既然是对称的，那么从个位开始，逆序反向生成一个数，若该数与原数相同，则是回文数。
- Scanner s=new Scanner(System.in);
- int num=s.nextInt();
- int max=num,min=0;
- while(max>0){
- min=min*10+max%10;//反向生成
- max=max/10;//去除最后一位
- }
- if(min==max)
- System.out.println("Yes");
- else
- System.out.println("No");
Scanner s=new Scanner(System.in); int num=s.nextInt(); int max=num,min=0; while(max>0){ min=min*10+max%10;//反向生成 max=max/10;//去除最后一位 } if(min==max) System.out.println("Yes"); else System.out.println("No");
附：回文数还有一个性质，即数字位数与存在的回文数有如下关系，1位回文数： 9个
2位回文数： 9个
3位回文数： 90个
4位回文数： 90个
5位回文数： 900个
6位回文数： 900个
…
即每增加两位，则存在的回文数为原来的10倍。
5.将整数倒序输出，剔除重复数据
输入一个整数，如12336544，或1750，然后从最后一位开始倒过来输出，最后如果是0，则不输出，输出的数字是不带重复数字的，所以上面的输出是456321和571。如果是负数，比如输入-175，输出-571。
算法分析：将每一位存储，存储时剔除重复元素，而后输出。（注意符号）
- public static void main(String[] args){
- Scanner s=new Scanner(System.in);
- int num=s.nextInt();
- int[] store=new int[]{99,99,99,99,99,99,99,99,99,99,99,99,99};//初始值不要赋个位数，避免和取余后的数等值
- int len=0,tmp=num,last;
- while(true){
- if(tmp==0)
- break;
- else{
- int lastNum= tmp%10;//取余求最后一位
- tmp=tmp/10;
- int flag=1;//待插入数组中是否含有该数
- for(int k=0;k<=len;k++){
- if(store[k]==lastNum){
- flag=0;//重复则不插入
- break;
- }
- }
- if(flag!=0){
- store[len]=lastNum;//需要插入
- len++;
- }
- }
- }
- //len指向待插入位置
- if(num<0)
- System.out.print("-");
- for(int j=0;j<len;j++){
- if(store[j]!=0)
- System.out.print(Math.abs(store[j]));
- }
- }
public static void main(String[] args){ Scanner s=new Scanner(System.in); int num=s.nextInt(); int[] store=new int[]{99,99,99,99,99,99,99,99,99,99,99,99,99};//初始值不要赋个位数，避免和取余后的数等值 int len=0,tmp=num,last; while(true){ if(tmp==0) break; else{ int lastNum= tmp%10;//取余求最后一位 tmp=tmp/10; int flag=1;//待插入数组中是否含有该数 for(int k=0;k<=len;k++){ if(store[k]==lastNum){ flag=0;//重复则不插入 break; } } if(flag!=0){ store[len]=lastNum;//需要插入 len++; } } } //len指向待插入位置 if(num<0) System.out.print("-"); for(int j=0;j<len;j++){ if(store[j]!=0) System.out.print(Math.abs(store[j])); } }
6.大数相减
输入两行字符串正整数，第一行是被减数，第二行是减数，输出第一行减去第二行的结果。备注：1、两个整数都是正整数，被减数大于减数
示例：
输入：1000000000000001
1
输出：1000000000000000
注意大数用char a[] 存储，用%s接收，一位一位的运算。注意a[0]里的正负号
算法描述：一位一位减，最高位无需借位。不仅可以大减小，也可以小减大(大减小取负即可)。
java实现：
- public int[] subtraction(int[] a,int[] b){
- int[] c=new int[a.length];
- //a[0]...a[n]代表高位到低位
- for(int i=c.length-1;i>=0;i--){
- //最高位不借位
- if(i!=0){
- if(a[i]<b[i]){
- a[i-1]-=1;//向高位借位
- a[i]+=10;
- }
- }
- c[i]=a[i]-b[i];//存储对应位的差值
- }
- return c;
- }
public int[] subtraction(int[] a,int[] b){ int[] c=new int[a.length]; //a[0]...a[n]代表高位到低位 for(int i=c.length-1;i>=0;i--){ //最高位不借位 if(i!=0){ if(a[i]<b[i]){ a[i-1]-=1;//向高位借位 a[i]+=10; } } c[i]=a[i]-b[i];//存储对应位的差值 } return c; }
输出：2 7 8 7 1 0 0 2 9 4 0 7 0 8 3 3 8 7 0 6
- 2 5 1 3 7 3 8 8 8 3 1 7 5 2 3 7 3 6 1 2
----------------------------------------------------
0 2 7 3 3 6 1 4 1 0 8 9 5 5 9 6 5 0 9 4
0 8 4 9 2 7 2 5 7 8 4 8 1 3 1 0 6 1 7 9
- 2 0 2 1 6 0 4 9 2 8 8 0 6 3 3 0 2 0 5 8
----------------------------------------------------
-1 1 7 2 3 3 2 3 5 0 3 2 5 0 1 9 5 8 7 9
6 6 5 5 5 1 1 1 5 6 5 5 1 6 2 1 9 7 2 9
- 0 2 8 5 9 7 5 8 9 8 2 8 0 1 8 5 7 3 3 4
----------------------------------------------------
6 3 6 9 5 3 5 2 5 8 2 7 1 4 3 6 2 3 9 5
3 4 7 5 7 1 1 1 9 1 9 2 2 0 0 4 5 2 9 8
- 5 9 5 6 1 5 8 9 8 9 7 1 9 7 1 2 5 0 3 5
----------------------------------------------------
-2 4 8 0 4 4 7 7 9 7 7 9 7 7 0 7 9 7 3 7
5 1 9 0 4 6 1 6 1 6 5 3 1 9 9 3 8 5 9 5
- 4 0 2 2 8 3 3 4 8 0 9 0 3 5 5 8 3 1 5 0
----------------------------------------------------
1 1 6 7 6 2 8 1 3 5 6 2 8 4 3 5 5 4 4 5
完整代码：
- import java.util.Random;
- public class Sub{
- //判别大小
- public Boolean compare(int[] a,int[] b){
- Boolean bool=true;//大于
- for(int i=0;i<a.length;i++){
- //从高位开始遍历
- if(a[i]<b[i]){
- bool=false;
- break;
- }
- else if(a[i]>b[i]){
- bool=true;
- break;
- }
- }
- return bool;
- }
- public int[] subtraction(int[] a,int[] b){
- int[] c=new int[a.length];
- //a[0]...a[n]代表高位到低位
- for(int i=c.length-1;i>=0;i--){
- //最高位不借位
- if(i!=0){
- if(a[i]<b[i]){
- a[i-1]-=1;//向高位借位
- a[i]+=10;
- }
- }
- c[i]=a[i]-b[i];//存储对应位的差值
- }
- return c;
- }
- //输出
- public void print(int[] bt){
- for(int b : bt){
- System.out.print(b+" ");
- }
- }
- public static void main(String[] args){
- Random rand=new Random();
- for(int i=0;i<5;i++){
- Sub sub=new Sub();
- int[] a=new int[20];
- int[] b=new int[20];
- for (int n=0; n<a.length; n++) {
- a[n]=rand.nextInt(10);//随机0--9
- b[n]=rand.nextInt(10);
- }
- System.out.print(" ");
- sub.print(a);
- System.out.println("");
- System.out.print("- ");
- sub.print(b);
- System.out.println("");
- System.out.println("------------------------------------------------");
- if(sub.compare(a,b)){//保证被减数大于减数
- System.out.print(" ");
- sub.print(sub.subtraction(a,b));
- System.out.println("");
- }
- else{
- System.out.print(" -");
- sub.print(sub.subtraction(b,a));
- System.out.println("");
- }
- System.out.println("");
- System.out.println("");
- }
- }
- }
import java.util.Random; public class Sub{ //判别大小 public Boolean compare(int[] a,int[] b){ Boolean bool=true;//大于 for(int i=0;i<a.length;i++){ //从高位开始遍历 if(a[i]<b[i]){ bool=false; break; } else if(a[i]>b[i]){ bool=true; break; } } return bool; } public int[] subtraction(int[] a,int[] b){ int[] c=new int[a.length]; //a[0]...a[n]代表高位到低位 for(int i=c.length-1;i>=0;i--){ //最高位不借位 if(i!=0){ if(a[i]<b[i]){ a[i-1]-=1;//向高位借位 a[i]+=10; } } c[i]=a[i]-b[i];//存储对应位的差值 } return c; } //输出 public void print(int[] bt){ for(int b : bt){ System.out.print(b+" "); } } public static void main(String[] args){ Random rand=new Random(); for(int i=0;i<5;i++){ Sub sub=new Sub(); int[] a=new int[20]; int[] b=new int[20]; for (int n=0; n<a.length; n++) { a[n]=rand.nextInt(10);//随机0--9 b[n]=rand.nextInt(10); } System.out.print(" "); sub.print(a); System.out.println(""); System.out.print("- "); sub.print(b); System.out.println(""); System.out.println("------------------------------------------------"); if(sub.compare(a,b)){//保证被减数大于减数 System.out.print(" "); sub.print(sub.subtraction(a,b)); System.out.println(""); } else{ System.out.print(" -"); sub.print(sub.subtraction(b,a)); System.out.println(""); } System.out.println(""); System.out.println(""); } } }
7.上海华为的一道关于指针方面的编程题
题目：
int A[nSize]，其中隐藏着若干0，其余非0整数，写一个函数int Func(int* A, int nSize)，使A把0移至后面，非0整数移至 数组前面并保持有序，返回值为原数据中第一个元素为0的下标。(尽可能不使用辅助空间且考虑效率及异常问题，注释规范且给出设计思路)
思路：
选择一个排序算法对其进行排序，在排序过程中记录0元素的个数count，即nSize-count为首个0元素的下标；需要注意的是，若排序时需由大到小的排序（题中只说保持有序），不然0元素出现在前半部分又要移动元素。C实现如下：
- #include <stdio.h>
- using namespace std;
- int Func(int *A,int nSize){
- if(A!=0&&nSize>0){
- int count=0;//记录0元素的个数
- //折半插入排序
- int low,high,mid;
- if(*A==0)
- count++;
- for(int i=1;i<nSize;i++){
- low=0;
- high=i-1;
- mid=(low+high)/2;
- while(low<=high){
- if(*(A+i)>*(A+mid))//key>mid
- high=mid-1;//注意此处故意倒序排列
- else
- low=mid+1;
- mid=(low+high)/2;
- }
- //high+1为待插入位置
- int key=*(A+i);
- //后移元素腾出位置
- for(int j=i;j>high+1;j--){
- *(A+j)=*(A+j-1);
- }
- *(A+high+1)=key;//插入
- if(key==0)
- count++;
- }
- return nSize-count;
- }
- else
- return -1;
- }
- void main(){
- int a[]={0,3,0,4,9,1,0,44,2,0,12};
- int index=Func(a,11);
- printf("首个0在 %d 处\n",index);
- for(int i=0;i<11;i++){
- printf("%d ",a[i]);
- }
- }
#include <stdio.h> using namespace std; int Func(int *A,int nSize){ if(A!=0&&nSize>0){ int count=0;//记录0元素的个数 //折半插入排序 int low,high,mid; if(*A==0) count++; for(int i=1;i<nSize;i++){ low=0; high=i-1; mid=(low+high)/2; while(low<=high){ if(*(A+i)>*(A+mid))//key>mid high=mid-1;//注意此处故意倒序排列 else low=mid+1; mid=(low+high)/2; } //high+1为待插入位置 int key=*(A+i); //后移元素腾出位置 for(int j=i;j>high+1;j--){ *(A+j)=*(A+j-1); } *(A+high+1)=key;//插入 if(key==0) count++; } return nSize-count; } else return -1; } void main(){ int a[]={0,3,0,4,9,1,0,44,2,0,12}; int index=Func(a,11); printf("首个0在 %d 处\n",index); for(int i=0;i<11;i++){ printf("%d ",a[i]); } }输出：
首个0在 7 处
44 12 9 4 3 2 1 0 0 0 0 请按任意键继续. . .8.素数问题
题目：
求2~2000的所有素数.有足够的内存,要求尽量快
思路：
查表法，即为2~2000的序列建立对应的表，表大小与序列大小一致(序列需要由小到大排序)，选择最小的素数并将其倍数剔除(在表中记录),在剩余的序列中，继续选择最小的素数并剔除其倍数，直到剔除到第N个。这样的好处在于每次遍历时可以参考上次table中的标记，可以避免许多重复操作。
例如在判断4是否为素数时，由于在剔除2的倍数时在表中已经标记为NONPRIME（不是素数），那就不比调用判断素数的方法，省去许多操作。C实现，为了输出方便，选择10以内的素数
- #include <stdio.h>
- #include <math.h>
- #define TRUE 1
- #define FALSE 0
- #define NULL -1 //未遍历标记
- #define NONPRIME 0//不是素数标记
- #define PRIME 1 //是素数标记
- #define LEN 10+1 //为了让数组下标一致
- using namespace std;
- int isPrime(int num){
- if(num==2)
- return TRUE;
- for(int i=2;i<=sqrt((double)num);i++){
- if(num%i==0)
- return FALSE;
- }
- return TRUE;
- }
- //将num的倍数剔除（num为最小质数）
- void deleNonPrime(int table[], int num){
- table[num]=PRIME;
- for(int i=2*num;i<LEN;i+=num){
- if(table[i]==NULL){//有可能已经被赋值了
- table[i]=NONPRIME;
- }
- }
- }
- void print(int arr[],int size){
- for(int i=2;i<size;i++){
- printf("%d ",arr[i]);
- }
- printf("\n");
- }
- void main(){
- int primes[LEN]={NULL};
- int table[LEN]={NULL};//建立对应的表
- for(int i=2;i<LEN;i++){
- primes[i]=i;
- table[i]=NULL;
- }
- for(int j=2;j<LEN;j++){
- if(j==2){
- deleNonPrime(table,2);
- }
- else{//参考上次表中的标记
- if(table[j]==NULL){//有可能为素数（剔除时有可能已经判断过了，避免重复判断）
- if(isPrime(primes[j])){
- deleNonPrime(table,primes[j]);
- }
- }
- }
- printf("序列：");
- print(primes,LEN);
- printf(" 表：");
- print(table,LEN);
- printf("\n\n");
- }
- for(int i=2;i<LEN;i++){
- if(table[i]==PRIME)
- printf("%d ",i);
- }
- }
#include <stdio.h> #include <math.h> #define TRUE 1 #define FALSE 0 #define NULL -1 //未遍历标记 #define NONPRIME 0//不是素数标记 #define PRIME 1 //是素数标记 #define LEN 10+1 //为了让数组下标一致 using namespace std; int isPrime(int num){ if(num==2) return TRUE; for(int i=2;i<=sqrt((double)num);i++){ if(num%i==0) return FALSE; } return TRUE; } //将num的倍数剔除（num为最小质数） void deleNonPrime(int table[], int num){ table[num]=PRIME; for(int i=2*num;i<LEN;i+=num){ if(table[i]==NULL){//有可能已经被赋值了 table[i]=NONPRIME; } } } void print(int arr[],int size){ for(int i=2;i<size;i++){ printf("%d ",arr[i]); } printf("\n"); } void main(){ int primes[LEN]={NULL}; int table[LEN]={NULL};//建立对应的表 for(int i=2;i<LEN;i++){ primes[i]=i; table[i]=NULL; } for(int j=2;j<LEN;j++){ if(j==2){ deleNonPrime(table,2); } else{//参考上次表中的标记 if(table[j]==NULL){//有可能为素数（剔除时有可能已经判断过了，避免重复判断） if(isPrime(primes[j])){ deleNonPrime(table,primes[j]); } } } printf("序列："); print(primes,LEN); printf(" 表："); print(table,LEN); printf("\n\n"); } for(int i=2;i<LEN;i++){ if(table[i]==PRIME) printf("%d ",i); } }
输出：序列：2 3 4 5 6 7 8 9 10
表：1 -1 0 -1 0 -1 0 -1 0
序列：2 3 4 5 6 7 8 9 10
表：1 1 0 -1 0 -1 0 0 0
序列：2 3 4 5 6 7 8 9 10
表：1 1 0 -1 0 -1 0 0 0
序列：2 3 4 5 6 7 8 9 10
表：1 1 0 1 0 -1 0 0 0
序列：2 3 4 5 6 7 8 9 10
表：1 1 0 1 0 -1 0 0 0
序列：2 3 4 5 6 7 8 9 10
表：1 1 0 1 0 1 0 0 0
序列：2 3 4 5 6 7 8 9 10
表：1 1 0 1 0 1 0 0 0
序列：2 3 4 5 6 7 8 9 10
表：1 1 0 1 0 1 0 0 0
序列：2 3 4 5 6 7 8 9 10
表：1 1 0 1 0 1 0 0 0
2 3 5 7 请按任意键继续. . .注意isPrime函数判断素数时只用判断至sqrt处(素数定理)。
9.操作系统任务调度问题
题目：
操作系统任务分为系统任务和用户任务两种。其中，系统任务的优先级 < 50，用户任务的优先级 >= 50且 <= 255。优 先级大于255的为非法任务，应予以剔除。现有一任务队列task[]，长度为n，task中的元素值表示任务的优先级，数值越小，优先级越高。函数scheduler 实现如下功能，将task[] 中的任务按照系统任务、用户任务依次存放到 system_task[] 数组和 user_task[] 数组中（数组中元素的值是任务在task[] 数 组中的下标），并且优先级高的任务排在前面，数组元素为-1表示结束。
例如：
task[] = {0, 30, 155, 1, 80, 300, 170, 40, 99}
system_task[] = {0, 3, 1, 7, -1}
user_task[] = {4, 8, 2, 6, -1}
函数接口 void scheduler(int task[], int n, int system_task[], int user_task[])思路：
先以50做为关键字对原有序列进行一次快排，返回50的待插入位置location即为系统任务的个数，然后以location做为分界线，左右两边分别进行快排，最后依次将左半部放在system_task[]中，右半部分放在user_task[]（需剔除大于255的）
C/C++实现如下：
- #include <stdio.h>
- using namespace std;
- // 利用一趟快速排序找分界线的位置i,即[low,i)为系统任务，[i,high]为用户任务
- int findLine(int task[],int lowSpace,int highSpace,int key){
- int low=lowSpace,high=highSpace;
- while(low<high){
- while(low<high&&task[high]>key){
- high--;
- }
- if(low<high){
- int tmp=task[high];
- task[high]=task[low];
- task[low]=tmp;
- }
- while(low<high&&task[low]<key){
- low++;
- }
- if(low<high){
- int tmp=task[low];
- task[low]=task[high];
- task[high]=tmp;
- }
- }
- return low;
- }
- void quickSort(int subTask[],int lowSpace,int highSpace){
- if(lowSpace<highSpace){//限制递归
- int low=lowSpace,high=highSpace;
- int insertIndex;//待插入位置
- int key=subTask[lowSpace];//关键字
- while(low<high){
- while(low<high&&subTask[high]>=key){
- high--;
- }
- if(low<high){
- int tmp=subTask[high];
- subTask[high]=subTask[low];
- subTask[low]=tmp;
- }
- while(low<high&&subTask[low]<=key){
- low++;
- }
- if(low<high){
- int tmp=subTask[low];
- subTask[low]=subTask[high];
- subTask[high]=tmp;
- }
- }
- insertIndex=low;
- subTask[insertIndex]=key;
- if(insertIndex==lowSpace)
- quickSort(subTask,insertIndex+1,highSpace);//只用排高区
- else if(insertIndex==highSpace)
- quickSort(subTask,lowSpace,insertIndex-1);//只用排低区
- else {
- quickSort(subTask,lowSpace,insertIndex-1);
- quickSort(subTask,insertIndex+1,highSpace);
- }
- }
- }
- void scheduler(int task[], int n, int system_task[], int user_task[]){
- int index=findLine(task,0,n-1,50);//以50为关键字划分
- //分别排序
- quickSort(task,0,index);
- quickSort(task,index+1,n-1);
- int len=0;//记录用户任务的长度,因为需要剔除大于255的数，所以长度不一定为n-index
- for(int i=0;i<n;i++){
- //系统任务[0,index)
- if(i<=index){
- system_task[i]=i;
- }
- //用户任务[index,n)
- else if(i>index){
- //剔除无效任务
- if(task[i]>=50&&task[i]<=255){
- user_task[i-index-1]=i;
- len++;
- }
- }
- }
- system_task[index+1]=-1;//结束
- user_task[len]=-1;
- }
- void printArr(int task[],int n){
- for(int i=0;i<n;i++){
- printf("%d ",task[i]);
- }
- printf("\n");
- }
- //测试
- void main(){
- int task[]={0, 30, 155, 1, 80, 300, 170, 40, 99};
- int system_task[9]={-1};
- int user_task[9]={-1};
- scheduler(task,9,system_task,user_task);
- printf("排序完成后总任务为：\n");
- printArr(task,9);
- printf("系统任务为：\n");
- printArr(system_task,9);
- printf("用户任务为：\n");
- printArr(user_task,9);
- }
#include <stdio.h> using namespace std; // 利用一趟快速排序找分界线的位置i,即[low,i)为系统任务，[i,high]为用户任务 int findLine(int task[],int lowSpace,int highSpace,int key){ int low=lowSpace,high=highSpace; while(low<high){ while(low<high&&task[high]>key){ high--; } if(low<high){ int tmp=task[high]; task[high]=task[low]; task[low]=tmp; } while(low<high&&task[low]<key){ low++; } if(low<high){ int tmp=task[low]; task[low]=task[high]; task[high]=tmp; } } return low; } void quickSort(int subTask[],int lowSpace,int highSpace){ if(lowSpace<highSpace){//限制递归 int low=lowSpace,high=highSpace; int insertIndex;//待插入位置 int key=subTask[lowSpace];//关键字 while(low<high){ while(low<high&&subTask[high]>=key){ high--; } if(low<high){ int tmp=subTask[high]; subTask[high]=subTask[low]; subTask[low]=tmp; } while(low<high&&subTask[low]<=key){ low++; } if(low<high){ int tmp=subTask[low]; subTask[low]=subTask[high]; subTask[high]=tmp; } } insertIndex=low; subTask[insertIndex]=key; if(insertIndex==lowSpace) quickSort(subTask,insertIndex+1,highSpace);//只用排高区 else if(insertIndex==highSpace) quickSort(subTask,lowSpace,insertIndex-1);//只用排低区 else { quickSort(subTask,lowSpace,insertIndex-1); quickSort(subTask,insertIndex+1,highSpace); } } } void scheduler(int task[], int n, int system_task[], int user_task[]){ int index=findLine(task,0,n-1,50);//以50为关键字划分 //分别排序 quickSort(task,0,index); quickSort(task,index+1,n-1); int len=0;//记录用户任务的长度,因为需要剔除大于255的数，所以长度不一定为n-index for(int i=0;i<n;i++){ //系统任务[0,index) if(i<=index){ system_task[i]=i; } //用户任务[index,n) else if(i>index){ //剔除无效任务 if(task[i]>=50&&task[i]<=255){ user_task[i-index-1]=i; len++; } } } system_task[index+1]=-1;//结束 user_task[len]=-1; } void printArr(int task[],int n){ for(int i=0;i<n;i++){ printf("%d ",task[i]); } printf("\n"); } //测试 void main(){ int task[]={0, 30, 155, 1, 80, 300, 170, 40, 99}; int system_task[9]={-1}; int user_task[9]={-1}; scheduler(task,9,system_task,user_task); printf("排序完成后总任务为：\n"); printArr(task,9); printf("系统任务为：\n"); printArr(system_task,9); printf("用户任务为：\n"); printArr(user_task,9); }
输出：排序完成后总任务为：
0 1 30 40 80 99 155 170 300
系统任务为：
0 1 2 3 -1 0 0 0 0
用户任务为：
4 5 6 7 -1 0 0 0 0
请按任意键继续. . .突然发现自己把题意弄错了，我虽然实现了任务分离和任务，但是题目输出的是原始索引坐标，并不是排序后的。为了实现寻找原始索引，引入一个索引表，只要任务元素被移动，则table的索引随之移动，最后只要查表即可。
C#实现如下：
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- namespace 控制台编程练习
- {
- class 任务分配
- {
- //寻找关键字的分界线
- int findLine(int[] task,int lowSpace,int highSpace,int key,int[] table){
- int low=lowSpace,high=highSpace;
- while(low<high){
- while(low<high&&task[high]>key){
- high--;
- }
- if(low<high){
- swap(high, low, task);
- swap(high, low, table);
- }
- while(low<high&&task[low]<key){
- low++;
- }
- if(low<high){
- swap( low,high ,task);
- swap(low, high, table);
- }
- }
- return low;
- }
- //交换
- void swap(int a,int b,int[] task){
- int tmp= task[a];
- task[a]=task[b];
- task[b]=tmp;
- }
- //快排
- void quickSort(int[] subTask,int lowSpace,int highSpace,int[] index){
- if(lowSpace<highSpace){//限制递归
- int low=lowSpace,high=highSpace;
- int insertIndex;//待插入位置
- int key=subTask[lowSpace];//关键字
- int table_key = index[lowSpace];//表索引虚拟关键字
- while(low<high){
- while(low<high&&subTask[high]>=key){
- high--;
- }
- if(low<high){
- swap(high,low,subTask);
- swap(high,low,index);
- }
- while(low<high&&subTask[low]<=key){
- low++;
- }
- if(low<high){
- swap(low,high,subTask);
- swap(low,high,index);
- }
- }
- insertIndex=low;
- subTask[insertIndex]=key;
- index[insertIndex]=table_key;//索引表也要变动
- if(insertIndex==lowSpace)
- quickSort(subTask,insertIndex+1,highSpace,index);//只用排高区
- else if(insertIndex==highSpace)
- quickSort(subTask,lowSpace,insertIndex-1,index);//只用排低区
- else {
- quickSort(subTask,lowSpace,insertIndex-1,index);
- quickSort(subTask,insertIndex+1,highSpace,index);
- }
- }
- }
- //建立索引表
- int[] creatTable(int n)
- {
- int[] table = new int[n];
- for (int i = 0; i < n; i++)
- {
- table[i] = i;
- }
- return table;
- }
- void scheduler(int[] task, int n, int[] system_task, int[] user_task){
- int[] table = creatTable(n);
- int index = findLine(task, 0, n - 1, 50, table);//以50为关键字划分
- //分别排序
- quickSort(task,0,index,table);
- quickSort(task,index+1,n-1,table);
- int len=0;//记录用户任务的长度,因为需要剔除大于255的数，所以长度不一定为n-index
- for(int i=0;i<n;i++){
- //系统任务[0,index)
- if(i<=index){
- system_task[i]=table[i];
- }
- //用户任务[index,n)
- else if(i>index){
- //剔除无效任务
- if(task[i]>=50&&task[i]<=255){
- user_task[i-index-1]=table[i];
- len++;
- }
- }
- }
- system_task[index+1]=-1;//结束
- user_task[len]=-1;
- }
- void printArr(int[] task,int n){
- for(int i=0;i<n;i++){
- Console.Write(task[i]+" ");
- }
- Console.WriteLine();
- }
- static void Main()
- {
- 任务分配 s = new 任务分配();
- int[] task={0, 30, 155, 1, 80, 300, 170, 40, 99};
- int[] system_task=new int[9];
- int[] user_task=new int[9];
- Console.WriteLine("原始任务为:");
- s.printArr(task,9);
- s.scheduler(task, 9, system_task, user_task);
- Console.WriteLine("系统任务为:");
- s.printArr(system_task, 9);
- Console.WriteLine("用户任务为:");
- s.printArr(user_task, 9);
- }
- }
- }
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace 控制台编程练习 { class 任务分配 { //寻找关键字的分界线 int findLine(int[] task,int lowSpace,int highSpace,int key,int[] table){ int low=lowSpace,high=highSpace; while(low<high){ while(low<high&&task[high]>key){ high--; } if(low<high){ swap(high, low, task); swap(high, low, table); } while(low<high&&task[low]<key){ low++; } if(low<high){ swap( low,high ,task); swap(low, high, table); } } return low; } //交换 void swap(int a,int b,int[] task){ int tmp= task[a]; task[a]=task[b]; task[b]=tmp; } //快排 void quickSort(int[] subTask,int lowSpace,int highSpace,int[] index){ if(lowSpace<highSpace){//限制递归 int low=lowSpace,high=highSpace; int insertIndex;//待插入位置 int key=subTask[lowSpace];//关键字 int table_key = index[lowSpace];//表索引虚拟关键字 while(low<high){ while(low<high&&subTask[high]>=key){ high--; } if(low<high){ swap(high,low,subTask); swap(high,low,index); } while(low<high&&subTask[low]<=key){ low++; } if(low<high){ swap(low,high,subTask); swap(low,high,index); } } insertIndex=low; subTask[insertIndex]=key; index[insertIndex]=table_key;//索引表也要变动 if(insertIndex==lowSpace) quickSort(subTask,insertIndex+1,highSpace,index);//只用排高区 else if(insertIndex==highSpace) quickSort(subTask,lowSpace,insertIndex-1,index);//只用排低区 else { quickSort(subTask,lowSpace,insertIndex-1,index); quickSort(subTask,insertIndex+1,highSpace,index); } } } //建立索引表 int[] creatTable(int n) { int[] table = new int[n]; for (int i = 0; i < n; i++) { table[i] = i; } return table; } void scheduler(int[] task, int n, int[] system_task, int[] user_task){ int[] table = creatTable(n); int index = findLine(task, 0, n - 1, 50, table);//以50为关键字划分 //分别排序 quickSort(task,0,index,table); quickSort(task,index+1,n-1,table); int len=0;//记录用户任务的长度,因为需要剔除大于255的数，所以长度不一定为n-index for(int i=0;i<n;i++){ //系统任务[0,index) if(i<=index){ system_task[i]=table[i]; } //用户任务[index,n) else if(i>index){ //剔除无效任务 if(task[i]>=50&&task[i]<=255){ user_task[i-index-1]=table[i]; len++; } } } system_task[index+1]=-1;//结束 user_task[len]=-1; } void printArr(int[] task,int n){ for(int i=0;i<n;i++){ Console.Write(task[i]+" "); } Console.WriteLine(); } static void Main() { 任务分配 s = new 任务分配(); int[] task={0, 30, 155, 1, 80, 300, 170, 40, 99}; int[] system_task=new int[9]; int[] user_task=new int[9]; Console.WriteLine("原始任务为:"); s.printArr(task,9); s.scheduler(task, 9, system_task, user_task); Console.WriteLine("系统任务为:"); s.printArr(system_task, 9); Console.WriteLine("用户任务为:"); s.printArr(user_task, 9); } } }
输出：原始任务为:
0 30 155 1 80 300 170 40 99
系统任务为:
0 3 1 7 -1 0 0 0 0
用户任务为:
4 8 2 6 -1 0 0 0 0
请按任意键继续. . .10.奇偶插入排序
题目：
对一个数组，将数组中偶数从大到小排序，奇数从小到大排序,奇数和偶数交叉着放且输出数组第一位放奇数若奇数和偶数不等长，则把剩下的直接放到数组中。
思路：
将奇数和偶数元素分别存放，然后分别排序，最后一起交叉填充(覆盖)到原数组。C/C++实现如下：
- #include<stdio.h>
- #include<malloc.h>
- #define DEFAULT 0
- #define low_to_high 0//由小到大
- #define high_to_low 1//由大到小
- using namespace std;
- //折半插入排序
- void halfSort(int *a,int n,int type){
- for(int i=1;i<n;i++){
- int high=i-1;
- int low=0;
- int mid=(high+low)/2;
- int key=a[i];//待排关键字
- //寻找位置
- if(type==low_to_high){
- while(low<=high){
- if(a[mid]<key)
- low=mid+1;
- else
- high=mid-1;
- mid=(low+high)/2;
- }
- }
- else{
- while(low<=high){
- if(a[mid]<key)
- high=mid-1;
- else
- low=mid+1;
- mid=(low+high)/2;
- }
- }
- //插入位置在high+1，全体移动a[high+1]...a[i]
- for(int j=i;j>high+1;j--){
- a[j]=a[j-1];
- }
- a[high+1]=key;
- }
- }
- void print(int *a,int n){
- for(int i=0;i<n;i++){
- printf("%d ",*(a+i));
- }
- /*while(*a!='\0'){
- printf("%d ",*a++);
- }*/
- printf("\n");
- }
- void oddAndEvenSort(int a[],int n){
- int odd[10]={0};
- int even[10]={0};
- int evenCount=0;//偶数个数
- int oddCount=0;
- for(int i=0;i<n;i++){
- if(a[i]%2==0){
- even[evenCount]=a[i];
- evenCount++;
- }
- else{
- odd[oddCount]=a[i];
- oddCount++;
- }
- }
- halfSort(odd,oddCount,low_to_high);
- halfSort(even,evenCount,high_to_low);
- if(oddCount==0){
- print(even,evenCount);
- }
- else if(evenCount==0){
- print(odd,oddCount);
- }
- else if(oddCount<evenCount){
- for(int i=0;i<oddCount;i++){
- a[2*i]=odd[i];
- a[2*i+1]=even[i];
- }
- for(int j=oddCount;j<n;j++){//剩余偶数补全
- a[j+oddCount]=even[j];
- }
- print(a,n);
- }
- else if(oddCount==evenCount){
- for(int i=0;i<oddCount;i++){
- a[2*i]=odd[i];
- a[2*i+1]=even[i];
- }
- print(a,n);
- }
- else if(oddCount>evenCount){
- for(int i=0;i<evenCount;i++){
- a[2*i]=odd[i];
- a[2*i+1]=even[i];
- }
- for(int j=evenCount;j<n;j++){//剩余奇数补全
- a[j+evenCount]=odd[j];
- }
- print(a,n);
- }
- }
- void main(){
- int a1[]={2,4,6,8,10,12,14,16,18,1};
- oddAndEvenSort(a1,10);
- int a2[]={2,4,6,8,10,1,3,5,7,9};
- oddAndEvenSort(a2,10);
- int a3[]={2,4,6,1,3,5,7,9,11,13};
- oddAndEvenSort(a3,10);
- }
#include<stdio.h> #include<malloc.h> #define DEFAULT 0 #define low_to_high 0//由小到大 #define high_to_low 1//由大到小 using namespace std; //折半插入排序 void halfSort(int *a,int n,int type){ for(int i=1;i<n;i++){ int high=i-1; int low=0; int mid=(high+low)/2; int key=a[i];//待排关键字 //寻找位置 if(type==low_to_high){ while(low<=high){ if(a[mid]<key) low=mid+1; else high=mid-1; mid=(low+high)/2; } } else{ while(low<=high){ if(a[mid]<key) high=mid-1; else low=mid+1; mid=(low+high)/2; } } //插入位置在high+1，全体移动a[high+1]...a[i] for(int j=i;j>high+1;j--){ a[j]=a[j-1]; } a[high+1]=key; } } void print(int *a,int n){ for(int i=0;i<n;i++){ printf("%d ",*(a+i)); } /*while(*a!='\0'){ printf("%d ",*a++); }*/ printf("\n"); } void oddAndEvenSort(int a[],int n){ int odd[10]={0}; int even[10]={0}; int evenCount=0;//偶数个数 int oddCount=0; for(int i=0;i<n;i++){ if(a[i]%2==0){ even[evenCount]=a[i]; evenCount++; } else{ odd[oddCount]=a[i]; oddCount++; } } halfSort(odd,oddCount,low_to_high); halfSort(even,evenCount,high_to_low); if(oddCount==0){ print(even,evenCount); } else if(evenCount==0){ print(odd,oddCount); } else if(oddCount<evenCount){ for(int i=0;i<oddCount;i++){ a[2*i]=odd[i]; a[2*i+1]=even[i]; } for(int j=oddCount;j<n;j++){//剩余偶数补全 a[j+oddCount]=even[j]; } print(a,n); } else if(oddCount==evenCount){ for(int i=0;i<oddCount;i++){ a[2*i]=odd[i]; a[2*i+1]=even[i]; } print(a,n); } else if(oddCount>evenCount){ for(int i=0;i<evenCount;i++){ a[2*i]=odd[i]; a[2*i+1]=even[i]; } for(int j=evenCount;j<n;j++){//剩余奇数补全 a[j+evenCount]=odd[j]; } print(a,n); } } void main(){ int a1[]={2,4,6,8,10,12,14,16,18,1}; oddAndEvenSort(a1,10); int a2[]={2,4,6,8,10,1,3,5,7,9}; oddAndEvenSort(a2,10); int a3[]={2,4,6,1,3,5,7,9,11,13}; oddAndEvenSort(a3,10); }
输出：
1 18 16 14 12 10 8 6 4 2
1 10 3 8 5 6 7 4 9 2
1 6 3 4 5 2 7 9 11 13总结：又没仔细看题，偶数元素是从大到小，奇数是从小到大排序，题目虽简，但也须仔细认真，切记。
高级题样题：地铁换乘描述：已知2条地铁线路，其中A为环线，B为东西向线路，线路都是双向的。经过的站点名分别如下，两条线交叉的换乘点用T1、T2表示。编写程序，任意输入两个站点名称，输出乘坐地铁最少需要经过的车站数量（含输入的起点和终点，换乘站点只计算一次）。 地铁线A（环线）经过车站：A1 A2 A3 A4 A5 A6 A7 A8 A9 T1 A10 A11 A12 A13 T2 A14 A15 A16 A17 A18 地铁线B（直线）经过车站：B1 B2 B3 B4 B5 T1 B6 B7 B8 B9 B10 T2 B11 B12 B13 B14 B15输入：输入两个不同的站名输出：输出最少经过的站数,含输入的起点和终点，换乘站点只计算一次输入样例：A1 A3输出样例：3答案参考：1. import java.util.*;2.3.4. public class Main {5.6. private static int INVALID_POSITION = 255;7.8. class BusLine {9. String busstop[];10. String lineName;11.12. public BusLine(String line) {13. String[] stops = line.split(" ");14. this.busstop = new String[stops.length];15. for (int i = 0; i < stops.length; i++) {16. this.busstop = stops;17. lineName = stops[0].substring(0, 1);18. }19. }20.21. /* get the stop position from the line */22. int getStopPosition (String point) {23. for (int i = 0; i < busstop.length; i++) {24. if (busstop.equals(point)) {25. return i;26. }27. }28. return INVALID_POSITION;29. }30.31. int getDistance(String pointA, String pointB) {32. int positionA = 0;33. int positionB = 0;34. int len = 0;35.36. positionA = getStopPosition(pointA);37. positionB = getStopPosition(pointB);38.39. if (positionA != INVALID_POSITION && positionB != INVALID_POSITION) {40. len = Math.abs(positionA - positionB) + 1;41. if (lineName.equals("A") && len > (busstop.length - len + 2)) {42. len = (busstop.length - len + 2);43. }44.45. return len;46. }47.48. return INVALID_POSITION;49. }50.51. }52.53.54. public int getRide(String pointA, String pointB) {55. int i = 0;56. int min = 255;57. BusLine lineA = new BusLine("A1 A2 A3 A4 A5 A6 A7 A8 A9 T1 A10 A11 A12 A13 T2 A14 A15 A16 A17 A18");58. BusLine lineB = new BusLine("B1 B2 B3 B4 B5 T1 B6 B7 B8 B9 B10 T2 B11 B12 B13 B14 B15");59.60. int[] way = {255, 255, 255, 255, 255, 255, 255, 255};61.62. way[0] = lineA.getDistance(pointA, pointB);63. way[1] = lineB.getDistance(pointA, pointB);64.65. way[2] = lineA.getDistance(pointA, "T1") + lineB.getDistance(pointB, "T1") - 1;66. way[3] = lineB.getDistance(pointA, "T1") + lineA.getDistance(pointB, "T1") - 1;67.68. way[4] = lineA.getDistance(pointA, "T2") + lineB.getDistance(pointB, "T2") - 1;69. way[5] = lineB.getDistance(pointA, "T2") + lineA.getDistance(pointB, "T2") - 1;70.71. way[6] = lineB.getDistance(pointA, "T1") + lineB.getDistance(pointB, "T2") + lineA.getDistance("T1", "T2") - 2;72. way[7] = lineB.getDistance(pointA, "T2") + lineB.getDistance(pointB, "T1") + lineA.getDistance("T1", "T2") - 2;73.74. for (i = 0; i < 7; i++) {75. if (min > way) {76. min = way;77. }78. }79.80. return min;81. }82.83. public static void main(String[] args) {84. Main m = new Main();85. Scanner cin = new Scanner(System.in);86. String inputStr = cin.nextLine();87. String stops[] = inputStr.split(" ");88.89. System.out.println(m.getRide(stops[0], stops[1]));90. }91.92. }其实后来发现整个过程下来还是有点紧张的。数组、链表、指针、字符串、循环、枚举、排序等内容基本上都考察到了。大家借鉴下吧。我的难度比其他同学难度大了些，最后一个当时没测试通过，回来才调过。做对了两道。加油吧，毕业季里相互分享下资料，互惠互利。
