1.判2的乘方
题目：实现一个方法，判断一正整数是否是2的乘方（比如16是2的4次方，返回true；18不是2的乘方，返回false）要求性能尽可能高。
解法一：创建一个中间变量Temp，初始值是1，然后进入一个循环，循环中每次让Temp和目标整数比较，如果相等，则说明目标整数是2的乘方，如果不相等，则让Temp增加一 倍，继续循环比较。让Temp大于目标整数时，说明目标整数不是2的乘方。
1 public static boolean isPowerOf2(int number) { 2 int temp = 1; 3 while (temp <= number) { 4 if (temp == number) 5 return true; 6 } 7 return false; 8 }
解法二：把解法一的乘以2操作改成向左移位，移位的性能比乘法高的多，代码如下：
1 public static boolean isPowerOf2(int number) { 2 int temp = 1; 3 while (temp <= number) { 4 if (temp == number){ 5 return true; 6 } 7 temp = temp<<1; 8 } 9 return false; 10 }
前两种算法的时间复杂度是O（logN）.
解法三：
1) 把前两种解法的2的乘方的结果转换成2进制数，十进制的2转化成二进制是10B，4转换成二进制是100B，8转换成二进制是1000B...如下图
2)即只要是2的乘方的数转换成二进制结果中只有一个1，再把这些2的乘方都减去1，转换成二进制数为：
3）用2的乘方的本身和它减去1的结果进行按位与运算，也就是N&N-1，结果如下：
即只有是2的乘方，按以上步骤结果都为0，代码如下
public static boolean ispowerOf2(Integer number){
return (number & number - 1) == 0;
}
该算法的时间复杂度为O（1）。
2.筛法求素数
解法：
1 using System; 2 public class PrimeFilter{ 3 public static void Main( string [] args ){ 4 int N = 100; 5 bool [] a = new bool[N+1]; 6 for( int i=2; i<=N; i++ ) a[i]=true; 7 8 for( int i=2; i<N; i++ ) 9 { 10 if(a[i]) for( int j=i*2; j<=N; j+=i ) 11 a[j]=false; 12 } 13 14 for( int i=2; i<=N; i++) 15 if( a[i] ) Console.Write( i + " " ); 16 } 17 }
3.找素数
请编写程序，从键盘输入两个整数m，n，找出等于或大于m的前n个素数。
输入格式:
第一个整数为m，第二个整数为n；中间使用空格隔开。例如：
103 3
输出格式:
从小到大输出找到的等于或大于m的n个素数，每个一行。例如：
103
107
109
输入样例:
9223372036854775839 2
输出样例:
9223372036854775907
9223372036854775931
解法:
1 import java.math.BigInteger; 2 import java.util.Scanner; 3 public class Main { 4 public static void main(String[] args){ 5 Scanner in = new Scanner(System.in); 6 BigInteger m; 7 int n; 8 9 m=in.nextBigInteger(); 10 n=in.nextInt(); 11 int cnt=0; 12 while (cnt<n){ 13 if (m.isProbablePrime(100)){ 14 System.out.println(m); 15 cnt++; 16 } 17 m=m.nextProbablePrime(); 18 } 19 in.close(); 20 } 21 }
4.计算正五边形的面积和周长
从下列的抽象类shape类扩展出一个正五边形（regular pentagon）类RPentagon,这个类将正五边形的边长作为私有成员，类中包含初始化这个值的构造方法。
public abstract class shape {// 抽象类
/ 抽象方法 求面积 / public abstract double getArea();
/ 抽象方法 求周长 / public abstract double getPerimeter(); }
请编程从键盘输入正五边形的边长值，创建一个正五边形对象，然后输出正五边形的面积和正五边形的周长。计算正五边形的面积公式为： S=5a^2/(4tan(36度))其中a为边长。 或者：S=(1/4)a^2√(25+10√5) 输出结果保留4位小数。
输入格式:
输入正五边形的边长。例如：
5
输出格式:
输出正五边形的面积和周长。第一行输出面积，第二行输出周长。例如： 43.0119
25
输入样例:
16.8
输出样例:
485.5875
84解法:
1 import java.util.Scanner; 2 abstract class Shape{ 3 abstract double getArea(); 4 abstract double getPerimeter(); 5 } 6 class RPentagon extends Shape{ 7 private double a; 8 public RPentagon(double a){ 9 this.a = a; 10 } 11 public double getArea(){ 12 return 0.25*a*a*Math.sqrt(25+10*Math.sqrt(5)); 13 } 14 public double getPerimeter() { 15 return 5*a; 16 } 17 18 } 19 public class Main { 20 21 public static void main(String[] args) { 22 Scanner in = new Scanner(System.in); 23 double b=in.nextDouble(); 24 RPentagon r= new RPentagon(b); 25 System.out.println(String.format("%.4f",r.getArea())); 26 System.out.println((int)r.getPerimeter()); 27 } 28 29 }
5.简单的计算器
编程实现一个简单的计算器，实现两个整数的加、减、乘、除。 注意：输入的数字为整数，可能大于Long.MAX_VALUE (即： 9223372036854775807）
输入格式:
例如输入被除数和除数，除号是“/”：
199818221687230837883277970155607217447/15607605175531087007（除法运算）
输出格式:
12802618943776012921 （输出商）
输入样例:
268757455632088758902114193354244344883-187825044215992922193584201757800947591
输出样例:
80932411416095836708529991596443397292
提示：
一. 当字符串对象str存储的值为"199818221687230837883277970155607217447/15607605175531087007"时，下面的方法可以将str从除号"/"处分割成两个字符串：
String[] ob = str.split("\D", 0);
这时，ob[0]的值为"199818221687230837883277970155607217447";
ob[1]的值为"15607605175531087007".
二. 如果要检测字符串中是否包含除号'/'，可以用下面的方法检测：
(in1.indexOf('/') != -1)为true，表示包含'/'。
解法:
1 import java.math.BigDecimal; 2 3 import java.util.Scanner; 4 public class Main { 5 public static void main(String [] args){ 6 Scanner scanner = new Scanner(System.in); 7 String s = scanner.nextLine(); 8 char [] key = {'+', '-', '*', '/'}; 9 int len = -1; 10 int flag = 0; 11 for (int i = 0; i < key.length; i++) { 12 len = s.indexOf(key[i]); 13 if (len != -1){ 14 flag = i; 15 break; 16 } 17 } 18 BigDecimal m = new BigDecimal(s.substring(0, len)); 19 BigDecimal n = new BigDecimal(s.substring(len + 1)); 20 switch (flag){ 21 case 0:{ 22 System.out.println(m.add(n)); 23 break; 24 } 25 case 1:{ 26 System.out.println(m.subtract(n)); 27 break; 28 } 29 case 2:{ 30 System.out.println(m.multiply(n)); 31 break; 32 } 33 case 3:{ 34 System.out.println(m.divide(n)); 35 break; 36 } 37 } 38 } 39 40 }
6.求解给定字符串的前缀
求解给定字符串的前缀。
输入格式:
输入数目不定的多对字符串，每行两个，以空格分开。 例如：filename filepathTom Jack输出格式:
返回两个字符串的最大前缀，例如：The common prefix is fileNo common prefix输入样例:
filename filepath
Tom Jack
输出样例:
The common prefix is file
No common prefix解法:
1 public class Main6 { 2 public static String prefix(String s1, String s2){ 3 StringBuffer stringBuffer = new StringBuffer(""); 4 StringBuffer no = new StringBuffer("No common prefix"); 5 StringBuffer yes = new StringBuffer("The common prefix is "); 6 boolean hasPrefix = false; 7 int i=0; 8 while (i<s1.length()&&i<s2.length()){ 9 if (s1.charAt(i)==s2.charAt(i)) { 10 hasPrefix=true; 11 stringBuffer.append(s1.charAt(i)); 12 i++; 13 } 14 else { 15 break; 16 } 17 } 18 if (hasPrefix){ 19 stringBuffer=yes.append(stringBuffer); 20 }else{ 21 stringBuffer=no.append(stringBuffer); 22 } 23 return new String(stringBuffer); 24 } 25 public static void main(String[] args){ 26 String string1,string2; 27 Scanner in = new Scanner(System.in); 28 while (in.hasNext()) { 29 string1 = in.next(); 30 string2 = in.next(); 31 System.out.println(prefix(string1, string2)); 32 } 33 in.close(); 34 } 35 }
7.找出最大的对象
（找出最大的对象）编写一个方法，返回对象数组中最大的对象。方法签名如下：public static Object max(Comparable[] a)所有对象都是Comparable接口的实例。对象在数组中的顺序是由compareTo方法决定的。编写测试程序，从键盘输入5个字符串和5个整数，创建一个由5个字符串构成的数组、一个由5个整数构成的数组。找出数组中最大的字符串、整数并输出。
输入格式:
输入Xi'an （输入5个字符串，每行一个）BeijingShangHaiGuangZhouShenZhen8 9 12 7 6 （输入5个整数，以空格分隔）输出格式:
输出 Max string is Xi'an （输出最大的字符串）Max integer is 12 （输出最大的整数）输入样例:
France
Japan
German
China
India
6 34 89 168 53
输出样例:
Max string is Japan
Max integer is 168解法:
1 import java.util.Arrays; 2 import java.util.Scanner; 3 public class Main { 4 5 public static void main(String[] args) { 6 @SuppressWarnings("resource") 7 Scanner sc = new Scanner(System.in); 8 String [] list1 = new String[5]; 9 int [] list2 = new int[5]; 10 for(int i=0;i<5;i++){ 11 String str1 = sc.next(); 12 list1[i]=str1; 13 } 14 for(int i=0;i<5;i++){ 15 int str2 = sc.nextInt(); 16 list2[i]=str2; 17 } 18 19 20 Arrays.sort(list1); 21 Arrays.sort(list2); 22 System.out.println("Max string is "+list1[4]); 23 System.out.println("Max integer is "+list2[4]); 24 } 25 }
8. 使用公历类GregorianCalendar
使用公历类 GregorianCalendar，公历类 GregorianCalendar有方法setTimeInMillis(long);可以用它来设置从1970年1月1日算起的一个特定时间。请编程从键盘输入一个长整型的值，然后输出对应的年、月和日。例如输入：1234567898765，输出：2009-1-14
输入格式:
输入1234567898765 （毫秒数）输出格式:
输出2009-1-14 （输出年、月和日，实际应该是2月，因为Java API 从0开始计算月份）输入样例:
1450921070108
输出样例:
2015-11-24解法:
1 import java.util.Calendar; 2 import java.util.Scanner; 3 4 public class Main { 5 public static void main(String [] args){ 6 Scanner scanner = new Scanner(System.in); 7 String s = scanner.nextLine(); 8 Calendar ca = Calendar.getInstance(); 9 ca.setTimeInMillis(Long.parseLong(s)); 10 System.out.println(ca.get(Calendar.YEAR ) + "-" 11 + ca.get(Calendar.MONTH) + "-" + ca.get(Calendar.DAY_OF_MONTH)); 12 } 13 14 }
9.查找电话号码
文件phonebook1.txt中有若干联系人的姓名和电话号码。高富帅 13312342222白富美 13412343333孙悟空 13512345555唐三藏 13612346666猪悟能 13712347777沙悟净 13812348888请你编写一个简单的通信录程序，当从键盘输入一个姓名时查找到对应的电话号码并输出。如果没找到则显示Not found. 由于目前的自动裁判系统暂时不能支持用户读入文件，我们编写程序从键盘输入文件中的姓名和电话号码，当输入的名字为noname时，表示结束。noname后面有一个名字，需要查找其对应的电话号码。
输入格式:
高富帅 13312342222白富美 13412343333孙悟空 13512345555唐三藏 13612346666猪悟能 13712347777沙悟净 13812348888noname （表示结束）唐三藏 （需要查找此人的电话号码）输出格式:
13612346666 （输出对应的电话号码）输入样例:
白富美 13412343333
孙悟空 13512345555
唐三藏 13612346666
猪悟能 13712347777
沙悟净 13812348888
noname
白骨精
输出样例:
Not found.解法:
方法一：
1 import java.util.HashMap; 2 import java.util.Map; 3 import java.util.Scanner; 4 5 public class Main4 { 6 7 public static void main(String[] args) { 8 Map<String,String> phone = new HashMap<String,String>(); 9 Scanner in = new Scanner(System.in); 10 while(true) { 11 String name = in.next(); 12 if(name.equals("noname")) { 13 break; 14 } 15 String phoneNumber = in.next(); 16 phone.put(name, phoneNumber); 17 } 18 String s = in.next(); 19 if(!phone.containsKey(s)) { 20 System.out.println("Not Found。"); 21 } 22 else{ 23 System.out.println(phone.get(s)); 24 } 25 in.close(); 26 } 27 }
方法二：（优化）
1 import java.util.HashMap; 2 import java.util.Map; 3 import java.util.Scanner; 4 5 public class Main { 6 public static void main(String[] args) { 7 Map<String, String> list = new HashMap<String, String>(); 8 String s; 9 Scanner scanner = new Scanner(System.in); 10 String a= scanner.next(); 11 12 while (!a.equals("noname")) { 13 s = scanner.next(); 14 15 list.put(a, s); 16 a = scanner.next(); 17 18 } 19 String string = scanner.next(); 20 if (list.get(string) != null) { 21 System.out.println(list.get(string)); 22 } 23 24 else { 25 System.out.println("Not found."); 26 } 27 28 } 29 }
10.日期加减
请编程从键盘输入一个长整型的值，该值表示从1970年1月1日算起的一个特定时间（毫秒数），以此时间构造一个日期对象。再输入一个普通整型值，该值表示天数，加上该天数后，然后输出对应的年、月、日。
输入格式:
1234567898765 （第一行输入一个长整型数）
158 （第二行输入一个普通整型数，表示天数）
输出格式:
2009-02-14
2009-07-22
输入样例:
1234567898765
158
输出样例:
2009-02-14
2009-07-22
解法:
1 import java.text.SimpleDateFormat; 2 import java.util.*; 3 public class Main3 { 4 5 public static void main(String[] args) { 6 Scanner in = new Scanner(System.in); 7 Calendar date = Calendar.getInstance(); 8 SimpleDateFormat format = new SimpleDateFormat("yyyy-MM-dd"); 9 long l = in.nextLong(); 10 Long i = in.nextLong(); 11 date.setTimeInMillis(l); 12 long n=i*24*60*60*1000+l; 13 Date date2 = new Date(n); 14 System.out.println(format.format(date.getTime())); 15 System.out.println(format.format(date2)); 16 } 17 }
11.字符串替换
将文本文件中指定的字符串替换成新字符串。 由于目前的OJ系统暂时不能支持用户读入文件，我们编写程序从键盘输入文件中的内容，当输入的一行为end时，表示结束。end后面有两个字符串，要求用第二个字符串替换文本中所有的第一个字符串。
输入格式:
Xi’an Institute of Posts and Telecommunications is co-designed and implemented by the People’s Government of Shaanxi Province and the Ministry of Industry and Information Technology. The Institute is located in Xi’an, a historic city in Northwest China, famous for its magnificent ancient culture.end （表示结束）Institute （第一个字符串，要求用第二个字符串替换）University （第二个字符串）输出格式:
Xi’an University of Posts and Telecommunications is co-designed and implemented by the People’s Government of Shaanxi Province and the Ministry of Industry and Information Technology.The University is located in Xi’an, a historic city in Northwest China, famous for its magnificent ancient culture.输入样例:
Xi’an Institute of Posts and Telecommunications is co-designed and implemented by the People’s Government of Shaanxi Province and the Ministry of Industry and Information Technology.
The Institute is located in Xi’an, a historic city in Northwest China, famous for its magnificent ancient culture.
end
Institute
University
输出样例:
Xi’an University of Posts and Telecommunications is co-designed and implemented by the People’s Government of Shaanxi Province and the Ministry of Industry and Information Technology.The University is located in Xi’an, a historic city in Northwest China, famous for its magnificent ancient culture.解法:
1 import java.util.ArrayList; 2 import java.util.Scanner; 3 4 public class Tihua5_2 { 5 6 public static void main(String[] args) { 7 ArrayList<String> ls = new ArrayList<String>(); 8 Scanner in = new Scanner(System.in); 9 int len = 0; 10 ls.add(in.nextLine()); 11 while (ls.get(len).compareTo("end") != 0) { 12 len++; 13 ls.add(in.nextLine()); 14 } 15 String a = in.nextLine(); 16 String b = in.nextLine(); 17 String[] ss = new String[len]; 18 for (int i = 0; i < len; i++) 19 ss[i] = ls.get(i).replace(a, b); 20 for (int i = 0; i < len; i++) 21 System.out.println(ss[i]); 22 in.close(); 23 } 24 25 }
12.大数整除
请编写程序，从键盘输入一个整数n，找出大于long.MAX_VALUE且能被n整除的前3个数字。
输入格式:
输入一个作为除数的整数n，例如： 17输出格式:
输出大于long.MAX_VALUE且能被n整除的前3个数字，例如下列三个数能被17整除且大于long.MAX_VALUE： 922337203685477581692233720368547758339223372036854775850输入样例:
103
输出样例:
9223372036854775832
9223372036854775935
9223372036854776038解法:
方法一：
1 import java.math.BigInteger; 2 import java.util.Scanner; 3 4 public class Main4 { 5 public static void main(String[] args) throws InterruptedException { 6 BigInteger bigInteger = new BigInteger(String.valueOf(Long.MAX_VALUE)); 7 int count = 1; 8 Scanner in = new Scanner(System.in); 9 int n = in.nextInt(); 10 while (count <= 3) { 11 if (bigInteger.mod(BigInteger.valueOf(n)).intValue() == 0) { 12 System.out.println(bigInteger.toString()); 13 count++; 14 } 15 bigInteger = bigInteger.add(BigInteger.valueOf(1)); 16 } 17 18 } 19 20 }
方法 二：
1 import java.math.BigDecimal; 2 import java.util.Scanner; 3 4 public class Main { 5 public static void main(String[] args) throws InterruptedException { 6 BigDecimal bigDecimal = new BigDecimal(String.valueOf(Long.MAX_VALUE)); 7 // valueOf()返回长参数的字符串表示形式 8 int count = 1; 9 Scanner in = new Scanner(System.in); 10 int n = in.nextInt(); 11 while (count <= 3) { 12 if (bigDecimal.divideAndRemainder(BigDecimal.valueOf(n))[1].intValue() == 0) { 13 // intValue()将此BigInteger转换为int。 14 System.out.println(bigDecimal.toString()); 15 // toString()返回此BigInteger的十进制String表示形式 16 count++; 17 } 18 bigDecimal = bigDecimal.add(BigDecimal.valueOf(1)); 19 } 20 } 21 }
方法三：（优化）
1 import java.math.BigInteger; 2 import java.util.Scanner; 3 4 public class Main{ 5 public static void main(String[] args) { 6 Scanner in = new Scanner(System.in); 7 BigInteger m = new BigInteger(Long.MAX_VALUE + ""); 8 String s = in.next(); 9 BigInteger n = new BigInteger(s); 10 BigInteger zero = new BigInteger("0"); 11 m = m.add(BigInteger.ONE); 12 int count = 0; 13 14 while(count<3) { 15 if(division(m,n).compareTo(zero)==0) { 16 System.out.println(m); 17 count++; 18 } 19 m = m.add(BigInteger.ONE); 20 } 21 in.close(); 22 } 23 public static BigInteger division(BigInteger m,BigInteger n) { 24 return m.divideAndRemainder(n)[1]; 25 } 26 }
13.求几何形状的面积之和
（求几何形状的面积之和）编写一个方法，求数组中所有几何形状对象的面积之和。方法签名如下：
public static double sumArea(shape[] a)
编写测试程序，继承抽象类shape得到圆形类Circle和矩形类Rectangle。
abstract class shape {// 抽象类
/ 抽象方法 求面积 /
public abstract double getArea();
/ 抽象方法 求周长 /
public abstract double getPerimeter();
}
创建四个对象（两个圆和两个矩形）的数组，然后使用sumArea方法求出它们的总面积。（保留4位小数）
输入格式:
输入 1.1 （第1个圆形的半径） 1.8 （第2个圆形的半径） 2.3 3.8 （第1个矩形的宽和高） 5.9 16.8 （第2个矩形的宽和高）
输出格式:
The total area is 121.8401 （总面积，保留4位小数）
输入样例:
2.18
3.16
2.9 5.76
4.8 9.23
输出样例:
The total area is 107.3088
解法：
1 import java.util.Scanner; 2 3 abstract class shape { 4 public abstract double getArea(); 5 6 public abstract double getPerimeter(); 7 } 8 9 class Circle extends shape { 10 private double r; 11 12 public Circle(double r) { 13 this.r = r; 14 } 15 16 @Override 17 public double getArea() { 18 return Math.PI * r * r; 19 } 20 21 @Override 22 public double getPerimeter() { 23 return 2 * r * Math.PI; 24 } 25 26 } 27 28 class Rectangle extends shape { 29 private double side; 30 private double side1; 31 32 public Rectangle(double side, double side1) { 33 this.side = side; 34 this.side1 = side1; 35 } 36 37 @Override 38 public double getArea() { 39 return side * side1; 40 } 41 42 @Override 43 public double getPerimeter() { 44 return (side + side1) * 2; 45 } 46 47 } 48 49 public class Main { 50 public static double sumArea(shape[] a) { 51 double sum = 0; 52 for (int i = 0; i < a.length; i++) { 53 sum += a[i].getArea(); 54 } 55 return sum; 56 } 57 58 public static void main(String[] args) { 59 Scanner in = new Scanner(System.in); 60 shape[] a = new shape[4]; 61 double r = in.nextDouble(); 62 a[0] = new Circle(r); 63 r = in.nextDouble(); 64 a[1] = new Circle(r); 65 66 double w = in.nextDouble(); 67 double h = in.nextDouble(); 68 a[2] = new Rectangle(w, h); 69 w = in.nextDouble(); 70 h = in.nextDouble(); 71 a[3] = new Rectangle(w, h); 72 73 in.close(); 74 System.out.println(String.format("The total area is " + "%.4f", sumArea(a))); 75 76 } 77 }
14.数字格式异常
(NumberFormatException数字格式异常)编写一个程序，提示用户读取两个整数，然后显示他们的和。程序应该在输入不正确时提示用户再次输入数字。
输入格式:
i 9 （第1次输入） l 8 （第2次输入） 5 6 （第3次输入）输出格式:
Incorrect input and re-enter two integers: （第1次输出提示） Incorrect input and re-enter two integers: （第2次输出提示） Sum is 11 （输出结果）输入样例:
i 9
l 8
5 6
输出样例:
Incorrect input and re-enter two integers:
Incorrect input and re-enter two integers:
Sum is 11解法:
1 import java.util.InputMismatchException; 2 import java.util.Scanner; 3 import java.text.DecimalFormat; 4 5 public class Main { 6 public static void main(String[] args) { 7 Scanner in =new Scanner(System.in); 8 int m,n; 9 while(true){ 10 try{ 11 m=in.nextInt(); 12 n=in.nextInt(); 13 System.out.println("Sum is "+(m+n)); 14 break; 15 16 }catch(InputMismatchException e){ 17 System.out.println("Incorrect input and re-enter two integers:"); 18 in.nextLine(); 19 continue; 20 } 21 } 22 } 23 }
15.查找成绩并折算后输出
文件：期中考试成绩.txt中有若干学生的姓名和数学期中考试成绩。 Smith 67 Anderson 75 Lewis 83 Cook 58 David 96 请你编写一个简单的查询成绩程序，当从键盘输入一个姓名时查找到他的数学期中考试分数并按照21%折算后输出。如果没找到则显示Not found. 由于目前的OJ系统暂时不能支持用户读入文件，我们编写程序从键盘输入文件中的姓名和成绩，当输入的名字为noname时，表示结束。noname后面有一个名字，需要查找其成绩。
输入格式:
Smith 67
Anderson 75
Lewis 83
Cook 58
David 96
noname （表示结束）
Bill
输出格式:
Not found.
输入样例:
Smith 67 Anderson 75 Lewis 83 Cook 58 David 96 noname Lewis
输出样例:
17.43
源代码：
方法一：
1 import java.util.HashMap; 2 import java.util.Map; 3 import java.util.Scanner; 4 5 public class Main { 6 7 public static void main(String[] args) { 8 Map<String,Double> phone = new HashMap<String,Double>(); 9 Scanner in = new Scanner(System.in); 10 while(true) { 11 String name = in.next(); 12 if(name.equals("noname")) { 13 break; 14 } 15 Double phoneNumber = in.nextDouble(); 16 phone.put(name, phoneNumber); 17 } 18 String s = in.next(); 19 if(!phone.containsKey(s)) { 20 System.out.println("Not Found。"); 21 } 22 else{ 23 System.out.println((phone.get(s))*0.21); 24 } 25 in.close(); 26 } 27 }
方法二（优化）：
1 import java.util.HashMap; 2 import java.util.Map; 3 import java.util.Scanner; 4 5 6 public class Main{ 7 public static void main(String[] args){ 8 Map<String, Integer> list=new HashMap<String, Integer>(); 9 int a; 10 Scanner scanner=new Scanner(System.in); 11 String aString=scanner.next(); 12 13 while(!aString.equals("noname")) 14 { 15 a=scanner.nextInt(); 16 17 list.put(aString, a); 18 aString=scanner.next(); 19 20 } 21 String string=scanner.next(); 22 if(list.get(string) != null){ 23 System.out.println(list.get(string)*0.21); 24 } 25 26 else { 27 System.out.println("Not found."); 28 } 29 30 31 32 } 33 }
23.找素数
请编写程序，从键盘输入两个整数m，n，找出等于或大于m的前n个素数。
输入格式:
第一个整数为m，第二个整数为n；中间使用空格隔开。例如：103 3输出格式:
从小到大输出找到的等于或大于m的n个素数，每个一行。例如：103107109输入样例:
9223372036854775839 2
输出样例:
9223372036854775907
9223372036854775931解法:
1 import java.math.BigInteger; 2 import java.util.Scanner; 3 public class Main { 4 public static void main(String[] args){ 5 Scanner in = new Scanner(System.in); 6 BigInteger m; 7 int n; 8 9 m=in.nextBigInteger(); 10 n=in.nextInt(); 11 int cnt=0; 12 while (cnt<n){ 13 if (m.isProbablePrime(100)){ 14 System.out.println(m); 15 cnt++; 16 } 17 m=m.nextProbablePrime(); 18 } 19 in.close(); 20 } 21 }
24.计算正五边形的面积和周长
从下列的抽象类shape类扩展出一个正五边形（regular pentagon）类RPentagon,这个类将正五边形的边长作为私有成员，类中包含初始化这个值的构造方法。public abstract class shape {// 抽象类/ 抽象方法 求面积 / public abstract double getArea();/ 抽象方法 求周长 / public abstract double getPerimeter(); }请编程从键盘输入正五边形的边长值，创建一个正五边形对象，然后输出正五边形的面积和正五边形的周长。计算正五边形的面积公式为： S=5a^2/(4tan(36度))其中a为边长。 或者：S=(1/4)a^2√(25+10√5) 输出结果保留4位小数。
输入格式:
输入正五边形的边长。例如：5输出格式:
输出正五边形的面积和周长。第一行输出面积，第二行输出周长。例如： 43.011925输入样例:
16.8
输出样例:
485.5875
84源代码:
方法一：
1 import java.util.Scanner; 2 abstract class Shape{ 3 abstract double getArea(); 4 abstract double getPerimeter(); 5 } 6 class RPentagon extends Shape{ 7 private double a; 8 public RPentagon(double a){ 9 this.a = a; 10 } 11 public double getArea(){ 12 return 0.25*a*a*Math.sqrt(25+10*Math.sqrt(5)); 13 } 14 public double getPerimeter() { 15 return 5*a; 16 } 17 18 } 19 public class Main { 20 21 public static void main(String[] args) { 22 Scanner in = new Scanner(System.in); 23 double b=in.nextDouble(); 24 RPentagon r= new RPentagon(b); 25 System.out.println(String.format("%.4f",r.getArea())); 26 System.out.println((int)r.getPerimeter()); 27 } 28 29 }
方法二：（优化）
1 import java.lang.Math; 2 import java.math.BigDecimal; 3 import java.text.DecimalFormat; 4 import java.util.Scanner; 5 public class Main { 6 public static void main(String[] args){ 7 Scanner in=new Scanner(System.in); 8 double a=in.nextDouble(); 9 Bian b1=new Bian(a); 10 11 DecimalFormat df1 = new DecimalFormat("#.####"); 12 System.out.println(df1.format(b1.getArea())); 13 System.out.println(df1.format(b1.getPerimeter())); 14 } 15 } 16 abstract class shape{// 抽象类 17 public abstract double getArea(); 18 public abstract double getPerimeter(); 19 } 20 class Bian extends shape{ 21 private double a; 22 public Bian(double a){ 23 this.a=a; 24 } 25 public double getArea(){ 26 double s=a*a/4*(Math.sqrt(25+10*Math.sqrt(5.0))); 27 //BigDecimal s1=new BigDecimal(s); 28 //double s2=s1.setScale(4,BigDecimal.ROUND_HALF_UP).doubleValue(); 29 return s; 30 } 31 public double getPerimeter(){ 32 return a*5; 33 } 34 }
25.求阶乘factorial
编程从键盘输入一个整数，计算出阶乘并输出。
输入格式:
输入 39
输出格式:
输出：20397882081197443358640281739902897356800000000
输入样例:
58
输出样例:
2350561331282878571829474910515074683828862318181142924420699914240000000000000
解法：
1 import java.math.BigInteger; 2 import java.util.Scanner; 3 4 public class Main { 5 public static void main(String args[]) { 6 BigInteger sum = new BigInteger("1"); 7 Scanner in = new Scanner(System.in); 8 int n = in.nextInt(); 9 for(int i = 1; i<= n;i++){ 10 String temp1 = Integer.toString(i); 11 BigInteger temp2 = new BigInteger(temp1); 12 sum = sum.multiply(temp2); 13 } 14 System.out.println(sum); 15 16 } 17 }
26 .字符串替换
将文本文件中指定的字符串替换成新字符串。 由于目前的OJ系统暂时不能支持用户读入文件，我们编写程序从键盘输入文件中的内容，当输入的一行为end时，表示结束。end后面有两个字符串，要求用第二个字符串替换文本中所有的第一个字符串。
解法：
输入格式:
Xi’an Institute of Posts and Telecommunications is co-designed and implemented by the People’s Government of Shaanxi Province and the Ministry of Industry and Information Technology. The Institute is located in Xi’an, a historic city in Northwest China, famous for its magnificent ancient culture. end （表示结束） Institute （第一个字符串，要求用第二个字符串替换） University （第二个字符串）
输出格式:
Xi’an University of Posts and Telecommunications is co-designed and implemented by the People’s Government of Shaanxi Province and the Ministry of Industry and Information Technology.The University is located in Xi’an, a historic city in Northwest China, famous for its magnificent ancient culture.
输入样例:
Xi’an Institute of Posts and Telecommunications is co-designed and implemented by the People’s Government of Shaanxi Province and the Ministry of Industry and Information Technology. The Institute is located in Xi’an, a historic city in Northwest China, famous for its magnificent ancient culture. end Institute University
输出样例:
Xi’an University of Posts and Telecommunications is co-designed and implemented by the People’s Government of Shaanxi Province and the Ministry of Industry and Information Technology.The University is located in Xi’an, a historic city in Northwest China, famous for its magnificent ancient culture.
1 import java.io.*; 2 import java.util.*; 3 4 public class Main{ 5 public static void main(String[] args) throws IOException { 6 String x = null; 7 Scanner in = new Scanner(System.in); 8 String str = ""; 9 x = in.nextLine(); 10 while (!x.equals("end")) { 11 str += x; 12 x = in.nextLine(); 13 } 14 String a = in.nextLine(); 15 String b = in.nextLine(); 16 in.close(); 17 String str1 = str.replace(a, b+" "); 18 System.out.println(str1); 19 20 } 21 }
27.找出最大的对象
（找出最大的对象）编写一个方法，返回对象数组中最大的对象。方法签名如下：public static Object max(Comparable[] a)所有对象都是Comparable接口的实例。对象在数组中的顺序是由compareTo方法决定的。编写测试程序，从键盘输入5个字符串和5个整数，创建一个由5个字符串构成的数组、一个由5个整数构成的数组。找出数组中最大的字符串、整数并输出。
View Code
View Code
View Code
输入格式:
1 输入 2 3 Xi'an （输入5个字符串，每行一个） 4 5 Beijing 6 7 ShangHai 8 9 GuangZhou 10 11 ShenZhen 12 13 8 9 12 7 6 （输入5个整数，以空格分隔）
输出格式:
输出 Max string is Xi'an （输出最大的字符串） Max integer is 12 （输出最大的整数）
输入样例:
1 France 2 Japan 3 German 4 China 5 India 6 6 34 89 168 53
输出样例:
Max string is Japan Max integer is 168
解法：
1 import java.util.Arrays; 2 import java.util.Scanner; 3 public class Main { 4 5 public static void main(String[] args) { 6 @SuppressWarnings("resource") 7 Scanner sc = new Scanner(System.in); 8 String [] list1 = new String[5]; 9 int [] list2 = new int[5]; 10 for(int i=0;i<5;i++){ 11 String str1 = sc.next(); 12 list1[i]=str1; 13 } 14 for(int i=0;i<5;i++){ 15 int str2 = sc.nextInt(); 16 list2[i]=str2; 17 } 18 19 20 Arrays.sort(list1); 21 Arrays.sort(list2); 22 System.out.println("Max string is "+list1[4]); 23 System.out.println("Max integer is "+list2[4]); 24 } 25 }
28. 给定两个点的坐标，求解两个点的距离。
输入格式:
给定四个浮点数，作为线段的两个点。
输出格式:
输出该线段的距离。
输入样例:
0 0 1.0 1.0
输出样例:
The distance is 1.41
解法：
1 import java.util.Scanner; 2 3 public class Main{ 4 5 public static void main(String[] args) { 6 Scanner in = new Scanner(System.in); 7 double a1 = in.nextDouble(); 8 double a2 = in.nextDouble(); 9 double a3 = in.nextDouble(); 10 double a4 = in.nextDouble(); 11 double s = Math.sqrt(Math.pow((a3-a1), 2)+Math.pow((a3-a1),2)); 12 System.out.println(String.format("The distance is "+"%.2f", s)); 13 14 } 15 16 }
29.检验密码
一些网站设定了一些制定密码的规则。编写一个方法，检验一个字符串是否合法的密码。假设密码规则如下： 密码必须至少有8个字符。 密码只能包含字母和数字。 密码必须至少有2个数字。 请编写一个程序，提示用户输入密码，如果改密码符合规则就显示“Valid password”，否则显示“Invalid password”
解法：
1 public class Main{ 2 @SuppressWarnings("resource") 3 public static void main(String[] args) { 4 // Prompt the user to enter a password 5 java.util.Scanner input = new java.util.Scanner(System.in); 6 //System.out.print("Enter a string for password: "); 7 String s = input.nextLine(); 8 9 if (isValidPassword(s) == true) {//第一个空格 10 System.out.println("Valid password"); 11 } 12 else { 13 System.out.println("Invalid password"); 14 } 15 } 16 17 /** 检查字符串是否是有效的密码 */ 18 public static boolean isValidPassword(String s) { 19 // 只有数字和字母？charAt(i)(数字判断) 20 for (int i = 0; i < s.length(); i++) { 21 if (!Character.isLetter(s.charAt(i)) && !Character.isDigit(s.charAt(i)))//第二个空格 22 return false; 23 } 24 25 // 检查长度 26 if (s.length() < 8)//第三个空格 27 return false; 28 29 // 计数位数 30 int count = 0; 31 for (int i = 0; i < s.length(); i++) { 32 if (Character.isDigit(s.charAt(i))) 33 count++; 34 } 35 36 if (count >= 2)//第四个空格 37 return true; 38 else 39 return false; 40 } 41 }
30.二位数组排序
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序，请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否有该整数。
1 #include <stdio.h> 2 #include<stdbool.h> 3 int main() 4 { 5 int find(int matrix[4][4], int rows, int columns, int number); 6 int a[4][4] = {{ 1, 2, 8, 9 }, 7 { 2, 4, 9, 12 }, 8 { 4, 7, 10, 13 }, 9 { 6, 8, 11, 15 } }; 10 int result = find(a, 4, 4, 12); 11 if (result == 1) 12 printf("已经查到\n"); 13 else 14 printf("数组中没有此元素\n"); 15 return 0; 16 } 17 int find(int matrix[4][4], int rows, int columns, int number) 18 { 19 bool found = false; 20 if (matrix != NULL && rows>0 && columns>0) 21 { 22 int a = 0; 23 int b = columns - 1; 24 while (a<rows && b >= 0) 25 { 26 if (matrix[a][b] == number) 27 { 28 found = true; 29 break; 30 } 31 else if (matrix[a][b]> number) 32 --b; 33 else 34 ++a; 35 } 36 } 37 return found; 38 }
31.打印矩阵
输入一个矩阵，按照从里向外的顺序依次打印出每一个数字。
代码：
1 #include <cstdio> 2 3 void PrintMatrixInCircle(int** numbers, int columns, int rows, int start); 4 void printNumber(int number); 5 6 void PrintMatrixClockwisely(int** numbers, int columns, int rows) 7 { 8 if (numbers == nullptr || columns <= 0 || rows <= 0) 9 return; 10 11 int start = 0; 12 13 while (columns > start * 2 && rows > start * 2) 14 { 15 PrintMatrixInCircle(numbers, columns, rows, start); 16 17 ++start; 18 } 19 } 20 21 void PrintMatrixInCircle(int** numbers, int columns, int rows, int start) 22 { 23 int endX = columns - 1 - start; 24 int endY = rows - 1 - start; 25 26 // 从左到右打印一行 27 for (int i = start; i <= endX; ++i) 28 { 29 int number = numbers[start][i]; 30 printNumber(number); 31 } 32 33 // 从上到下打印一列 34 if (start < endY) 35 { 36 for (int i = start + 1; i <= endY; ++i) 37 { 38 int number = numbers[i][endX]; 39 printNumber(number); 40 } 41 } 42 43 // 从右到左打印一行 44 if (start < endX && start < endY) 45 { 46 for (int i = endX - 1; i >= start; --i) 47 { 48 int number = numbers[endY][i]; 49 printNumber(number); 50 } 51 } 52 53 // 从下到上打印一行 54 if (start < endX && start < endY - 1) 55 { 56 for (int i = endY - 1; i >= start + 1; --i) 57 { 58 int number = numbers[i][start]; 59 printNumber(number); 60 } 61 } 62 } 63 64 void printNumber(int number) 65 { 66 printf("%d\t", number); 67 } 68 69 // ====================测试代码==================== 70 void Test(int columns, int rows) 71 { 72 printf("Test Begin: %d columns, %d rows.\n", columns, rows); 73 74 if (columns < 1 || rows < 1) 75 return; 76 77 int** numbers = new int*[rows]; 78 for (int i = 0; i < rows; ++i) 79 { 80 numbers[i] = new int[columns]; 81 for (int j = 0; j < columns; ++j) 82 { 83 numbers[i][j] = i * columns + j + 1; 84 } 85 } 86 87 PrintMatrixClockwisely(numbers, columns, rows); 88 printf("\n"); 89 90 for (int i = 0; i < rows; ++i) 91 delete[](int*)numbers[i]; 92 93 delete[] numbers; 94 } 95 96 int main(int argc, char* argv[]) 97 { 98 /* 99 1 100 */ 101 Test(1, 1); 102 103 /* 104 1 2 105 3 4 106 */ 107 Test(2, 2); 108 109 /* 110 1 2 3 4 111 5 6 7 8 112 9 10 11 12 113 13 14 15 16 114 */ 115 Test(4, 4); 116 117 /* 118 1 2 3 4 5 119 6 7 8 9 10 120 11 12 13 14 15 121 16 17 18 19 20 122 21 22 23 24 25 123 */ 124 Test(5, 5); 125 126 /* 127 1 128 2 129 3 130 4 131 5 132 */ 133 Test(1, 5); 134 135 /* 136 1 2 137 3 4 138 5 6 139 7 8 140 9 10 141 */ 142 Test(2, 5); 143 144 /* 145 1 2 3 146 4 5 6 147 7 8 9 148 10 11 12 149 13 14 15 150 */ 151 Test(3, 5); 152 153 /* 154 1 2 3 4 155 5 6 7 8 156 9 10 11 12 157 13 14 15 16 158 17 18 19 20 159 */ 160 Test(4, 5); 161 162 /* 163 1 2 3 4 5 164 */ 165 Test(5, 1); 166 167 /* 168 1 2 3 4 5 169 6 7 8 9 10 170 */ 171 Test(5, 2); 172 173 /* 174 1 2 3 4 5 175 6 7 8 9 10 176 11 12 13 14 15 177 */ 178 Test(5, 3); 179 180 /* 181 1 2 3 4 5 182 6 7 8 9 10 183 11 12 13 14 15 184 16 17 18 19 20 185 */ 186 Test(5, 4); 187 188 return 0; 189 }
32.输出二叉树的镜像
代码：
1 #include<stdio.h> 2 #include<stdlib.h> 3 typedef struct node 4 { 5 char value; 6 struct node *lchild; 7 struct node *rchild; 8 }TreeNode,*Tree; 9 //头插法创建二叉树 10 Tree CreateTree(Tree &t) 11 { 12 char ch; 13 scanf_s("%c", &ch); 14 if (ch == '#') 15 t = NULL; 16 else 17 { 18 t = (Tree)malloc(sizeof(TreeNode)); 19 if (!t) 20 { 21 printf("分配内存出错！"); 22 return NULL; 23 } 24 t->value = ch; 25 CreateTree(t->lchild); 26 CreateTree(t->rchild); 27 } 28 return t; 29 } 30 //求二叉树镜像 31 void MirrorRecursively(Tree pNpde) 32 { 33 if (pNpde == NULL) 34 return ; 35 if (pNpde->lchild == NULL && pNpde->rchild == NULL) 36 return ; 37 Tree pTemp = pNpde->lchild; 38 pNpde->lchild = pNpde->rchild; 39 pNpde->rchild = pTemp; 40 if (pNpde->lchild) 41 MirrorRecursively(pNpde->lchild); 42 if (pNpde->rchild) 43 MirrorRecursively(pNpde->rchild); 44 } 45 //先序递归遍历 46 void PreOrder(Tree T) 47 { 48 if (T) 49 { 50 printf("%c",T->value); 51 PreOrder(T->lchild); 52 PreOrder(T->rchild); 53 } 54 } 55 int main() 56 { 57 Tree T; 58 printf("创建二叉树，‘#’代表空："); 59 CreateTree(T); 60 printf("先序遍历二叉树："); 61 PreOrder(T); 62 MirrorRecursively(T); 63 if (T) 64 { 65 printf("\n先序遍历镜像二叉树: "); 66 PreOrder(T); 67 } 68 else 69 printf("创建的树为空"); 70 printf("\n"); 71 return 0; 72 } 73 /* 74 创建二叉树，‘#’代表空：ABD##E##CF##G## 75 先序遍历二叉树：ABDECFG 76 先序遍历镜像二叉树: ACGFBED 77 请按任意键继续. . . 78 79 创建二叉树，‘#’代表空：# 80 先序遍历二叉树：创建的树为空 81 请按任意键继续. . . 82 83 */
33.判断两颗二叉树B是不是A的子结构。
代码：
1 #include<stdio.h> 2 #include<stdlib.h> 3 typedef char ElemType; 4 //树结构 5 typedef struct tree 6 { 7 ElemType data; 8 struct tree * lchild; 9 struct tree * rchild; 10 }TreeNode, *Tree; 11 12 Tree CreateTree(Tree &t) 13 { 14 char ch; 15 scanf_s("%c", &ch); 16 if (ch == '#') 17 t = NULL; 18 else 19 { 20 t = (Tree)malloc(sizeof(TreeNode)); 21 if (!t) 22 { 23 printf("分配内存出错！"); 24 return NULL; 25 } 26 t->data = ch; 27 CreateTree(t->lchild); 28 CreateTree(t->rchild); 29 } 30 return t; 31 } 32 bool DoedTreeHaveTree(Tree pRoot1,Tree pRoot2) 33 { 34 if (pRoot2 == NULL) 35 return true; 36 if (pRoot1 == NULL) 37 return false; 38 if (pRoot1->data != pRoot2->data) 39 return false; 40 return DoedTreeHaveTree(pRoot1->lchild, pRoot2->lchild) && DoedTreeHaveTree(pRoot1->rchild,pRoot2->rchild); 41 } 42 bool HasSubtree(Tree pRoot1,Tree pRoot2) 43 { 44 bool result = false; 45 if (pRoot1 != NULL && pRoot2 != NULL) 46 { 47 if (pRoot1->data == pRoot2->data) 48 result = DoedTreeHaveTree(pRoot1,pRoot2); 49 if (!result) 50 result = HasSubtree(pRoot1->lchild,pRoot2); 51 if (!result) 52 result = HasSubtree(pRoot1->rchild,pRoot2); 53 } 54 return result; 55 } 56 int main() 57 { 58 Tree T1 = (Tree)malloc(sizeof(TreeNode)); 59 bool result=false; 60 printf("\n按先序序列输入A树结点序列，'#'代表空："); 61 T1=CreateTree(T1); 62 fflush(stdin); //清除缓存，此语句很重要 63 Tree T2 = (Tree)malloc(sizeof(TreeNode)); 64 printf("\n按先序序列输入B树结点序列，'#'代表空："); 65 T2 = CreateTree(T2); 66 result = HasSubtree(T1,T2); 67 printf("\n"); 68 if (result == true) 69 printf("B是A的子结构\n\n"); 70 else 71 printf("B不是A的子结构\n\n"); 72 return 0; 73 } 74 75 76 结果如下： 77 按先序序列输入A树结点序列，'#'代表空：ABD##EF##G##C## 78 按先序序列输入B树结点序列，'#'代表空：BD##E## 79 B是A的子结构 80 请按任意键继续. . . 81 82 按先序序列输入A树结点序列，'#'代表空：ABD##EF##G##C## 83 按先序序列输入B树结点序列，'#'代表空：# 84 B不是A的子结构 85 请按任意键继续. . . 86 87 按先序序列输入A树结点序列，'#'代表空：# 88 按先序序列输入B树结点序列，'#'代表空：BD##E## 89 B不是A的子结构 90 请按任意键继续. . . 91 92 按先序序列输入A树结点序列，'#'代表空：ABD##EF##G##C## 93 按先序序列输入B树结点序列，'#'代表空：fq##n## 94 B不是A的子结构 95 请按任意键继续. . . 96 97 98 按先序序列输入A树结点序列，'#'代表空：ABD##EF##G##C## 99 按先序序列输入B树结点序列，'#'代表空：A## 100 B是A的子结构 101 请按任意键继续. . .
34. 合并两个递增链表使新的链表结点按照递增排序。
代码：
1 #include<stdio.h> 2 #include"malloc.h" 3 typedef struct node 4 { 5 struct node *next; 6 int data; 7 }*ListNode; 8 9 //尾插法创建链表(不带头结点) 10 ListNode creatrList() 11 { 12 ListNode p = (ListNode)malloc(sizeof(ListNode)); 13 ListNode s, q; 14 p->next = NULL; 15 q = p; 16 int x = 0; 17 scanf_s("%d", &x); 18 while (x != -1) 19 { 20 s = (ListNode)malloc(sizeof(ListNode)); 21 s->next = NULL; 22 p->data = x; 23 p->next = s; 24 p = s; 25 scanf_s("%d", &x); 26 } 27 return q; 28 } 29 //合并两个链表 30 ListNode Merge(ListNode AList,ListNode BList) 31 { 32 if (AList->next == NULL) 33 return BList; 34 else if (BList->next == NULL) 35 return AList; 36 ListNode CList = NULL; 37 if (AList->data < BList->data) 38 { 39 CList = AList; 40 CList->next = Merge(AList->next,BList); 41 } 42 else 43 { 44 CList = BList; 45 CList->next = Merge(AList, BList->next); 46 } 47 return CList; 48 } 49 50 int main() 51 { 52 ListNode AList, BList,CList; 53 printf("创建A链表，以-1结束："); 54 AList = creatrList(); 55 printf("创建B链表，以-1结束："); 56 BList = creatrList(); 57 CList = Merge(AList, BList); 58 printf("合并后的列表为:"); 59 while (CList->next!=NULL) 60 { 61 printf("%3d",CList->data); 62 CList = CList->next; 63 } 64 printf("\n"); 65 return 0; 66 67 } 68 /* 69 创建A链表，以-1结束：1 2 3 5 6 7 -1 70 创建B链表，以-1结束：8 9 11 14 16 19 21 23 25 27 -1 71 合并后的列表为: 1 2 3 5 6 7 8 9 11 14 16 19 21 23 25 27 72 请按任意键继续. . . 73 74 创建A链表，以-1结束：-1 75 创建B链表，以-1结束：1 2 3 4 5 6 7 8 -1 76 合并后的列表为: 1 2 3 4 5 6 7 8 77 请按任意键继续. . . 78 79 创建A链表，以-1结束：1 2 3 4 5 6 7 8 -1 80 创建B链表，以-1结束：1 2 3 4 5 6 7 8 -1 81 合并后的列表为: 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 82 请按任意键继续. . . 83 84 85 */
35. 输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
代码：
1 #include<stdio.h> 2 #include"malloc.h" 3 typedef struct node 4 { 5 struct node *next; 6 int data; 7 }*ListNode; 8 9 //尾插法创建链表(不带头结点) 10 ListNode creatrList() 11 { 12 ListNode p = (ListNode)malloc(sizeof(ListNode)); 13 ListNode s,q; 14 p ->next = NULL; 15 q = p; 16 int x=0; 17 printf("创建链表，以-1结束："); 18 scanf_s("%d", &x); 19 while (x!=-1) 20 { 21 s = (ListNode)malloc(sizeof(ListNode)); 22 s->next = NULL; 23 p->data = x; 24 p->next = s; 25 p = s; 26 scanf_s("%d", &x); 27 } 28 return q; 29 } 30 //反转链表 31 ListNode ReverseList(ListNode pHead) 32 { 33 ListNode prev = NULL; 34 ListNode pNode = pHead; 35 ListNode ReverPHead=NULL; 36 while (pNode != NULL) 37 { 38 ListNode pNext = pNode->next; 39 if (pNext == NULL) 40 ReverPHead = pNode; 41 pNode->next = prev; 42 prev = pNode; 43 pNode = pNext; 44 } 45 printf("%d",ReverPHead->data); 46 return ReverPHead; 47 } 48 49 int main() 50 { 51 ListNode h,RH; 52 h = creatrList(); 53 54 RH=ReverseList(h); 55 if (RH->next == NULL) 56 printf("链表为空\n"); 57 else 58 { 59 RH = RH->next; 60 while (RH != NULL) 61 { 62 printf("%3d", RH->data); 63 RH = RH->next; 64 } 65 printf("\n"); 66 } 67 return 0; 68 69 } 70 /* 71 创建链表，以-1结束：1 2 3 4 5 6 -1 72 6 5 4 3 2 1 73 请按任意键继续. . . 74 75 创建链表，以-1结束：-1 76 链表为空 77 请按任意键继续. . . 78 79 创建链表，以-1结束：4 -1 80 4 81 请按任意键继续. . . 82 */
46.输出链表中倒数第k个结点，链表从1开始计数吧，即链表的尾结点是倒数第1个结点。
要求：只能遍历一次链表找到k结点。
代码：
1 #include<stdio.h> 2 #include"malloc.h" 3 typedef struct node 4 { 5 int value; 6 struct node *next; 7 }*ListNode; 8 9 ListNode createList() 10 { 11 ListNode H = (ListNode)malloc(sizeof(ListNode)); 12 H->next = NULL; 13 ListNode r, s; 14 r = H; 15 int x; 16 printf("创建链表，输入整数，以-1结束："); 17 scanf_s("%d",&x); 18 while (x != -1) 19 { 20 s = (ListNode)malloc(sizeof(ListNode)); 21 s->value = x; 22 s->next = r->next; 23 r->next = s; 24 r = s; 25 scanf_s("%d", &x); 26 } 27 return H; 28 } 29 30 ListNode FindKToTail(ListNode H, unsigned int k) 31 { 32 //如果链表为空或k等于0，返回NULL 33 if (H->next == NULL || k == 0) 34 return NULL; 35 ListNode pBegin=H->next; 36 ListNode pEnd=NULL; 37 for (unsigned int i = 0; i < k - 1;i++) 38 { 39 if (pBegin->next != NULL) 40 pBegin = pBegin->next; 41 else 42 { 43 return NULL; //如果链表的长度小于K，返回NULL 44 } 45 } 46 pEnd = H->next; 47 while (pBegin->next !=NULL) 48 { 49 pBegin = pBegin->next; 50 pEnd = pEnd->next; 51 } 52 return pEnd; 53 } 54 int main() 55 { 56 ListNode H,p,q; 57 unsigned int k = 0; 58 H = createList(); 59 p = H->next; 60 printf("创建的链表为："); 61 while (p!=NULL) 62 { 63 printf("%3d",p->value); 64 p = p->next; 65 } 66 printf("\n"); 67 printf("链表创建完成，输入要查找的倒数位置："); 68 scanf_s("%d", &k); 69 q = FindKToTail(H,k); 70 if (q == NULL) 71 printf("链表为空或k大于链表的长度\n"); 72 else 73 printf("倒数第 %d 个位置的值为 %d\n",k,q->value); 74 75 return 0; 76 } 77 78 /* 79 创建链表，输入整数，以-1结束：1 2 3 4 5 6 7 8 9 10 -1 80 创建的链表为： 1 2 3 4 5 6 7 8 9 10 81 链表创建完成，输入要查找的倒数位置：5 82 倒数第 5 个位置的值为 6 83 请按任意键继续. . . 84 85 创建链表，输入整数，以-1结束：-1 86 创建的链表为： 87 链表创建完成，输入要查找的倒数位置：0 88 链表为空或k大于链表的长度 89 请按任意键继续. . . 90 91 创建链表，输入整数，以-1结束：1 2 3 -1 92 创建的链表为： 1 2 3 93 链表创建完成，输入要查找的倒数位置：5 94 链表为空或k大于链表的长度 95 请按任意键继续. . . 96 97 98 */
47.调整数组
输入一个整数数组，实现一个函数来调整该数组中的数字，使得所有奇数位于数组的前半部分，所有的偶数位于 数组的后半部分。
代码：
1 #include<stdio.h> 2 bool isEven(int n) 3 { 4 return (n & 1) == 0; 5 } 6 void Reorder(int *pData, unsigned int length, bool(*func)(int)) 7 { 8 if (pData == NULL || length == 0) 9 return; 10 int *pBegin = pData; 11 int *pEnd = pData + length - 1; 12 while (pBegin < pEnd) 13 { 14 while (pBegin < pEnd && !func(*pBegin)) //如果前面的指针指向的数字是奇数 15 pBegin++; 16 while (pBegin < pEnd && func(*pEnd)) //如果后面的指针指向的数字是偶数 17 pEnd--; 18 if (pBegin < pEnd) 19 { 20 int temp = *pBegin; 21 *pBegin = *pEnd; 22 *pEnd = temp; 23 } 24 } 25 26 } 27 int main() 28 { 29 int a[8] = { 5, 1, 6, 2, 3, 7, 8, 10 }; 30 Reorder(a,8,isEven); 31 for (int i = 0; i < 8; i++) 32 printf("%3d",a[i]); 33 printf("\n"); 34 return 0; 35 } 36 /* 37 5 1 7 3 2 6 8 10 38 请按任意键继续. . . 39 40 */
48.删除链表指定节点
在给定单链表的头结点指针和一个结点指针，定义一个函数在O（1）时间删除该结点。
代码：
1 #include <stdio.h> 2 #include "malloc.h" 3 struct ListNode 4 { 5 int value; 6 ListNode *next; 7 }; 8 //尾插法创建链表 9 ListNode *createList() 10 { 11 ListNode *H = (ListNode *)malloc(sizeof(ListNode)); 12 H->next = NULL; 13 ListNode *s, *r = H; //r指向尾节点，s为要插入的结点 14 int x; 15 scanf_s("%d",&x); 16 while (x!=-1) 17 { 18 s = (ListNode *)malloc(sizeof(ListNode)); 19 s->value = x; 20 s->next = r->next; 21 r->next = s; 22 r = s; 23 scanf_s("%d", &x); 24 } 25 return H; 26 } 27 void DeleteNode(ListNode **pListHead,ListNode *pToDelete) 28 { 29 if (pListHead == NULL || *pListHead == NULL || pToDelete == NULL) 30 return; 31 //要删除的结点不是尾结点，将需要删除的结点后面的结点覆盖到要删除的结点，将后面的结点删除 32 if (pToDelete->next != NULL) 33 { 34 ListNode *pNode = pToDelete->next; 35 pToDelete->value = pNode->value; 36 pToDelete->next = pNode->next; 37 delete pNode; 38 pNode = NULL; 39 } 40 //链表中只有一个结点，删除头结点（也是尾结点） 41 else if (*pListHead == pToDelete) 42 { 43 delete pToDelete; 44 pToDelete = NULL; 45 pListHead = NULL; 46 } 47 //链表中有多个结点，要删除的结点在尾部，需要找到删除结点的前一个结点(常规方法) 48 else 49 { 50 ListNode *pNodes = *pListHead; 51 while (pNodes->next != pToDelete) 52 { 53 pNodes = pNodes->next; 54 } 55 pNodes->next = NULL; 56 delete pToDelete; 57 pToDelete = NULL; 58 } 59 } 60 ListNode *find(ListNode *list, int x) 61 { 62 ListNode *fq; 63 fq = list->next; 64 if (fq == NULL) 65 return NULL; 66 while (fq != NULL) 67 { 68 if (fq->value == x) 69 return fq; 70 fq = fq->next; 71 } 72 return NULL; 73 } 74 75 int main() 76 { 77 int x; 78 ListNode *p,*q; 79 ListNode *H = (ListNode *)malloc(sizeof(ListNode)); 80 printf("输入单链表的结点值，以-1结束："); 81 H = createList(); 82 printf("输入要删除的结点的值："); 83 scanf_s("%d",&x); 84 q = find(H,x); 85 DeleteNode(&H,q); 86 p = H->next; 87 printf("删除一个结点%d后的值为 ：",x); 88 while (p != NULL) 89 { 90 printf("%3d",p->value); 91 p = p->next; 92 } 93 printf("\n"); 94 95 return 0; 96 } 97 98 /* 99 输入单链表的结点值，以-1结束：1 2 3 4 5 6 -1 100 输入要删除的结点的值：1 101 删除一个结点1后的值为 ： 2 3 4 5 6 102 请按任意键继续. . . 103 104 输入单链表的结点值，以-1结束：1 2 3 4 5 6 -1 105 输入要删除的结点的值：3 106 删除一个结点3后的值为 ： 1 2 4 5 6 107 请按任意键继续. . . 108 109 输入单链表的结点值，以-1结束：1 2 3 4 5 6 -1 110 输入要删除的结点的值：6 111 删除一个结点6后的值为 ： 1 2 3 4 5 112 请按任意键继续. . . 113 */
49. 不使用库函数求次方
实现函数double Power(double base,int exponent),求base的exponent次方，不得使用库函数，同时不需要考虑大数问题。
首先，对于此题目，可以考虑以下几种情况：
1.当次数为负数且底数为0的时候，是没有意义的；
2.当底数为0，次数也为0的时候，也是没有意义的，可以输出1或0；
3.其他情况
代码：
1 #include <stdio.h> 2 bool g_InvalidInput = false; //当出错时，这个变量为true，否则为false，这样可以把返回值直接传给其他变量 3 //比较两个数是否相等 4 bool equal(double num1,double num2) 5 { 6 if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001)) 7 return true; 8 else 9 return false; 10 } 11 12 double PowerWithUnsignedExponent(double base,unsigned int exponent) 13 { 14 double result = 1.0; 15 for (int i = 1; i <= exponent; i++) 16 result *= base; 17 return result; 18 } 19 double power(double base, int exponent) 20 { 21 g_InvalidInput = false; 22 if (equal(base, 0.0) && exponent < 0){ 23 g_InvalidInput = true; //出错时，g_InvalidInput = false; 24 return 0.0; 25 } 26 unsigned int absExponent = (unsigned int )(exponent); 27 if (exponent < 0) 28 absExponent = (unsigned int)(-exponent); 29 double result = PowerWithUnsignedExponent(base,absExponent); 30 if (exponent < 0) 31 result = 1.0 / result; //指数为负数，对结果求倒数 32 return result; 33 } 34 int main() 35 { 36 double base, exponent; 37 scanf_s("%lf", &base); 38 scanf_s("%lf", &exponent); 39 printf("%lf\n", power(base, exponent)); 40 return 0; 41 } 42 /* 43 2.0 3.0 44 8.000000 45 请按任意键继续. . . 46 47 2.0 -3.0 48 0.125000 49 请按任意键继续. . . 50 51 0 0 52 1.000000 53 请按任意键继续. . . 54 55 */
PowerWithUnsignedExponent方法改进：
即利用公式
a^n = a^(n/2) * a^(n/2) n为偶数
a^n = a^((n-1)/2) * a^((n-1)/2) * a n为奇数
代码：
1 double PowerWithUnsignedExponent(double base, unsigned int exponent) 2 { 3 if (exponent == 0) 4 return 1; 5 if (exponent == 1) 6 return base; 7 double result = PowerWithUnsignedExponent1(base, exponent >> 1); 8 result *= result; 9 if (exponent & 0x1 == 1) 10 result *= base; 11 return result; 12 }
50.输出指定数字中的二进制表示形式中1的个数
实现一个函数，输入一个整数，输出该数的二进制表示形式中1的个数，；例如把9表示成二进制是1001，有2位是1，因此如果输入9，改函数输出2.
代码：
1 #include<stdio.h> 2 //二进制中1的个数解法一:为了避免死循环，首先把n和1做与运算，判断n最低位是不是1，接着把1 3 //左移一位得到2，再和n做与运算，整数中有多少位，就需要循环多少次 4 // 5 int NumberOf1(int n) 6 { 7 int count = 0; 8 unsigned int flag = 1; 9 while (flag) 10 { 11 if (n & flag) 12 count++; 13 flag = flag << 1; 14 } 15 return count; 16 17 } 18 //解法二：把一个整数减去1再和原来的整数做与运算，就会把该整数的二进制表示形式中最右边的1变成0，那么，一个整数中有多少个1就需要循环多少次 19 int NumberOf2(int n) 20 { 21 int count = 0; 22 while (n) 23 { 24 ++count; 25 n = (n - 1)& n; 26 } 27 return count; 28 } 29 int main() 30 { 31 int n; 32 scanf_s("%d", &n); 33 printf("解法一：该整数表示成二进制的形式中1 的个数为：%d\n", NumberOf1(n)); 34 printf("解法二：该整数表示成二进制的形式中1 的个数为：%d\n", NumberOf2(n)); 35 return 0; 36 } 37 /* 38 7 39 解法一：该整数表示成二进制的形式中1 的个数为：3 40 解法二：该整数表示成二进制的形式中1 的个数为：3 41 请按任意键继续. . . 42 43 */
51.把一个数组最开始的若干各元素搬到数组的末尾
把一个数组最开始的若干各元素搬到数组的末尾，称之为旋转数组，输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}是数组{1,2,3,4,5}的一个旋转，该数组的最小值为1；
1 #include<stdio.h> 2 int MinInOrder(int r[], int p1, int p2) 3 { 4 int result = r[p1]; 5 for (int i = p1 + 1; i <= p2; i++) 6 { 7 if (r[i] < result) 8 result = r[i]; 9 } 10 return result; 11 } 12 int Min(int r[], int length) 13 { 14 if (r == NULL || length <= 0) 15 return 0; 16 int p1 = 0; 17 int p2 = length - 1; 18 int mid = p1; 19 while (r[p1] >= r[p2]) 20 { 21 if (p2 - p1 == 1) 22 { 23 mid = p2; 24 break; 25 } 26 mid = (p1 + p2) / 2; 27 if (r[p1] == r[p2] && r[mid] == r[p2]) 28 return MinInOrder(r, p1, p2); 29 if (r[mid] >= r[p1]) 30 p1 = mid; 31 else if (r[mid] <= r[p2]) 32 p2 = mid; 33 } 34 return r[mid]; 35 } 36 37 int main() 38 { 39 int a[8] = { 1, 1, 1, 0, 1 }; 40 printf("%d\n", Min(a, 5)); 41 return 0; 42 }
52.分割数字
给定一个整数n和一个整数m，将n按照位分割成多个数字，使得这多个数字的和最接近m，
例如n=654321，m=50，则最大值为48（6+5+4+32+1）。
分析：
（1）对于一个Integer类型的数字n和m，首先有种特殊情况; 即 n<m :直接返回n；
（2）将整数n按位存入一个整型数组中，所求的最大值的位数肯定小于等于m的位数，
则以2为大小作为窗口在n所在的数组上进行滑动，每滑动一次，将窗口中的数字表示成十进制并和窗口为的其他数字进行相加，判断是否大于设定的一个numMax,
并且这个数字小于m，则将这个数字赋给numMax。
（3）依次增加窗口的大小直到小于等于m的位数为止。
java代码:
1 package cvte; 2 3 import java.util.Scanner; 4 5 /* 6 * 题目：给定一个整数n和一个整数m，将n按照位分割成多个数字，使得这多个数字的和最接近m， 7 * 例如n=654321，m=50，则最大值为48（6+5+4+32+1） 8 * */ 9 public class Main { 10 // 求最大值 11 public static Integer plimit(Integer n, Integer m) { 12 if (n < m) 13 return n; 14 Integer add = 0; //把所有的位加起来的和 15 Integer maxNum = 0; //最终所求结果 16 Integer count = 0; //辅助计数器，计算每个子数组中按位加起来的的和 17 Integer madd = 0; //辅助计数，把每个子数组中的数字表示成十进制 18 Integer mc = 0; //辅助计数，把每个子数组中的数字表示成十进和其他位按位加起来的总和 19 int a = 0, b = 0; //标记子数组第一位和最后一位的指针 20 String nstr = n.toString(); //将n转化成字符串 21 String mstr = m.toString(); //将m转化字符串 22 int nlength = nstr.length(); // n的长度 23 int mlength = mstr.length(); // m的长度 24 int[] narr = new int[nlength]; // 新建一个数组用来保存num每一位的数字 25 for (int i = 0; i < nlength; i++) { 26 Character ch = nstr.charAt(i); // 遍历nstr将每一位数字添加到narr 27 narr[i] = Integer.parseInt(ch.toString()); 28 } 29 for (int i = 0; i < nlength; i++) { 30 add += narr[i]; 31 } 32 if (add < m){ 33 for (int i = 2; i <= mlength; i++) { 34 a = 0; 35 b = i - 1; 36 while (b < nlength) { 37 for (int j = a; j <=b; j++) { 38 //System.out.println("j="+j); 39 count += narr[j]; 40 madd = madd + (int) (narr[j] * Math.pow(10, (b - j))); 41 a++; 42 } 43 mc = (add - count) + madd; 44 //System.out.println("mc="+mc); 45 if (mc > maxNum && mc < m) { 46 maxNum = mc; 47 } 48 b++; 49 a = b - i + 1; 50 madd=0; 51 count=0; 52 //System.out.println("a= b="+a+" "+b); 53 } 54 55 } 56 } 57 return maxNum; 58 } 59 60 public static void main(String[] args) { 61 Scanner in = new Scanner(System.in); 62 Integer n = in.nextInt(); 63 Integer m = in.nextInt(); 64 System.out.println(plimit(n, m)); 65 } 66 67 } 68 /* 69 例一： 70 输入： 71 50 72 输出： 73 例二： 74 输入： 75 661 76 输出： 77 */
53.矩阵压缩处理
1.特殊矩阵
（1）上三角形
上三角形的矩阵的有效元素只有n(n+1)/2，上三角形中元素A[i][j]在一维数组中存储地址为：
按行存储：LOC(A[i][j])=LOC(A[1][1])+(i-1)(2n-i+2)/2+j-i;
（2）下三角形
上三角形的矩阵的有效元素只有n(n+1)/2，上三角形中元素A[i][j]在一维数组中存储地址为：
按行存储：LOC(A[i][j])=LOC(A[1][1])+i(i-1)/2+j-1;
（3）三对角矩阵
按行存储：LOC(A[i][j])=LOC(A[1][1])+2（i-1）+j-1;
54.斐波那契数列
（1）.含义：斐波那契数列是根据兔子的繁殖得到的一组数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55,89, 144, 233....其特点是从第三项开始每一项都等于前两项之和。
（2）.解法
对于这个数列，第一种解法就是用公式 f(n) = f(n-1)+f(n-2) 递归调用，但这种方法有大量的计算是重复的，时间复杂度以n的指数增加，具体代码如下：
1 long f1(int n) 2 { 3 if(n<=0) 4 return 0; 5 if (n ==1) 6 return 1; 7 return f1(n-1) + f1(n-2); 8 }
第二种解法也比较好理解，如果先求f(1),f(2),再根据f(1)和f(2)就出f（3），以此论推求出f（n），这种计算方法的时间复杂度是O(n)。这种方法是给数列前面加一个0，也就是说序列是从0开始，具体代码如下：
1 long f1(int n) 2 { 3 long x = 0, y = 1; 4 for (int i = 1; i < n; i++) 5 { 6 y = x + y; //当前得值等于前两项之和 7 x = y - x; //当前项的前一项等于当前项减去当前项的前一项的前一项 8 } 9 return y; 10 }