笔试编程题整理

归并排序：

//将有序数组a[]和b[]合并到c[]中 void MemeryArray(int a[], int n, int b[], int m, int c[]) { int i, j, k; i = j = k = 0; while (i < n && j < m) { if (a[i] < b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; } // 当其中一个列表的所有数据都比另一个列表的所有数据小的时候，例如 i = n，j = 0； while (i < n) c[k++] = a[i++]; while (j < m) c[k++] = b[j++]; } 

解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

构建 Hash 表的时候（散列函数的设计）

f( key ) = key mod p ( p ≤ m ) mod ... 使用除留余数法的一个经验是，若散列表表长为m，通常p为小于或等于表

如何合理选取p值

使用除留余数法的一个经验是，若散列表表长为m，通常p为小于或等于表长（最好接近m)的最小质数或不包含小于20质因子的合数。

• 这句话怎么理解呢？要不这样吧，我再举个例子：某散列表的长度为100，散列函数H(k)=k%P,则P通常情况下最好选择哪个呢？A、91 B、93 C、97 D、99

• 实践证明，当P取小于哈希表长的最大质数时，产生的哈希函数较好。我选97，因为它是离长度值最近的最大质数。

可以盛最多水的容器

解法：我们可以循环遍历所有的两天边的乘积，取最大的值。

编程试题：求数列的和 使用语言：JAVA 参考正解代码如下： import java.util.*; class Main{ public static void main(String args[]){ int m; double sum,n; Scanner sc = new Scanner(System.in); while(sc.hasNext()){ n=sc.nextInt(); m=sc.nextInt(); sum=0; for(int i=0;i<m;i++){ sum=sum+n; n=Math.sqrt(n); } System.out.printf("%.2f",sum); System.out.println(); } } } 使用语言：C++ 参考正解代码如下： #include <math.h> #include <stdio.h> int main() { int n; double x, s; while (~scanf("%lf%d", &x, &n)) { for(s = 0.0; n--; x = sqrt(x)) s += x; printf("%.2lf\n", s); } return 0; } 使用语言：C# 参考正解代码如下： using System; namespace myApp { class Program { public static void Main() { string line; string[] p; int m, n; double nn; while (!string.IsNullOrEmpty(line = Console.ReadLine())) { p = line.Split(' '); n = int.Parse(p[0]); m = int.Parse(p[1]); double sum = 0; nn = n; for (int i = 0; i < m; i++) { sum = sum + nn; nn = Math.Sqrt(nn); } Console.WriteLine(string.Format("{0:f}", sum)); } } } } 使用语言：JavaScript 参考正解代码如下： var m; var sum,n; var sc while(sc = read_line()){ var arr = sc.split(' '); n=parseInt(arr[0]); m=parseInt(arr[1]); sum=0; for(var i=0;i<m;i++){ sum=sum+n; n=Math.sqrt(n); } print(sum.toFixed(2)); } 

注意上面的三个代码有几点注意：

一：JavaScript 的输入和输出为 sc = read——line() 输出：print(); 精确到后两位：sum.toFixed(2)

二：C / C++ 精确到两位小数为：printf("%.2lf\n", s);

三：Java编写程序的时候精确到小数点后两位的写法：System.out.printf("%.2f",sum);

截图如下，防止丢失代码块部分数据

水仙花的求解

编程试题：水仙花 使用语言：JAVA 参考正解代码如下： import java.util.Scanner; public class Main{ public static void main(String args[]){ Scanner reader=new Scanner(System.in); while(reader.hasNextInt()){ int m=reader.nextInt(); int n=reader.nextInt(); if(100<=m&&m<=n&&n<=999){ int j=0; for(int i=m;i<=n;i++) { int geWei,shiWei,baiWei; baiWei=i/100; shiWei=(i-baiWei*100)/10; geWei=i-baiWei*100-shiWei*10; if(i==geWei*geWei*geWei+shiWei*shiWei*shiWei+baiWei*baiWei*baiWei) {j=j+1; if(j>1){ System.out.print(" "+i); } else{ System.out.print(i); } } } if(j==0){ System.out.print("no"); } System.out.println(); } } } } 使用语言：C++ 参考正解代码如下： #include<stdio.h> int main(){ int m,n; while(scanf("%d%d",&m,&n)!=EOF){ int t=0; for(int i=m; i<=n; i++){ int a=i/100; int b=i%100/10; int c=i%10; if(i==a*a*a+b*b*b+c*c*c && t==0){ printf("%d ",i); t++; } else if(i==a*a*a+b*b*b+c*c*c && t==1){ printf("%d ",i); } } if(t!=0){ printf("\n"); } if(t==0){ printf("no\n"); } } return 0; } 使用语言：C# 参考正解代码如下： using System; namespace myApp { class Program { public static void Main() { string line; string[] p; int m, n; while ((line = Console.ReadLine()) != null) { p = line.Split(' '); n = int.Parse(p[1]); m = int.Parse(p[0]); var j=0; for(var i=m;i<=n;i++) { int geWei,shiWei,baiWei; baiWei = (i/100); shiWei = ((i-baiWei*100)/10); geWei = i-baiWei*100-shiWei*10; if(i==geWei*geWei*geWei+shiWei*shiWei*shiWei+baiWei*baiWei*baiWei) { j=j+1; if(j>1) { Console.Write(" "+i); } else { Console.Write(i); } } } if(j==0) { Console.Write("no"); } Console.Write("\r\n"); } } } } 使用语言：JavaScript 参考正解代码如下： var sc; while(sc = read_line()){ var arr = sc.split(' '); n=parseInt(arr[1]); m=parseInt(arr[0]); if(100<=m&&m<=n&&n<=999){ var out = []; var j=0; for(var i=m;i<=n;i++) { var geWei,shiWei,baiWei; baiWei=parseInt(i/100); shiWei=parseInt((i-baiWei*100)/10); geWei=i-baiWei*100-shiWei*10; if(i==geWei*geWei*geWei+shiWei*shiWei*shiWei+baiWei*baiWei*baiWei) { j=j+1; if(j>1){ out.push(" "+i); } else{ out.push(i); } } } if(j==0){ out.push("no"); } print(out.join('')); } } 

整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

• I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
• X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
• C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例 1:

输入: 3 输出: "III" 

示例 2:

输入: 4 输出: "IV" 

示例 3:

输入: 9 输出: "IX" 

示例 4:

输入: 58 输出: "LVIII" 解释: C = 100, L = 50, XXX = 30, III = 3. 

示例 5:

输入: 1994 输出: "MCMXCIV" 解释: M = 1000, CM = 900, XC = 90, IV = 4. 

解法：在求解的时候把所有的可能性全部定义出来，不要再中间进行判断。

public class Solution { public String intToRoman(int num) { if(num <= 0) { return ""; } int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}; String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; StringBuilder res = new StringBuilder(); int digit = 0; while (num > 0) { int times = num / nums[digit]; num -= nums[digit] * times; for ( ; times > 0; times --) { res.append(symbols[digit]); } digit++; } return res.toString(); } } 

这里特殊的情况上面也已经提到，一个是 900，一个是 400，一个是 90，还有一个是 40，还有一个是 9，一个是 4。全部显式的定义在数组中即可。

罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

• I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
• X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
• C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

输入: "III" 输出: 3 

示例 2:

输入: "IV" 输出: 4 

示例 3:

输入: "IX" 输出: 9 

示例 4:

输入: "LVIII" 输出: 58 解释: L = 50, V= 5, III = 3. 

九章算术解答

public class Solution { public int romanToInt(String s) { if (s == null || s.length()==0) { return 0; } Map<Character, Integer> m = new HashMap<Character, Integer>(); m.put('I', 1); m.put('V', 5); m.put('X', 10); m.put('L', 50); m.put('C', 100); m.put('D', 500); m.put('M', 1000); int length = s.length(); int result = m.get(s.charAt(length - 1)); for (int i = length - 2; i >= 0; i--) { if (m.get(s.charAt(i + 1)) <= m.get(s.charAt(i))) { result += m.get(s.charAt(i)); } else { result -= m.get(s.charAt(i)); } } return result; } } 

通过 Map 集合来做，在其中加入 key 和 value。

问：Keep 编程题，Keep 有很多课程，每门课程有一个开始时间和一个结束时间。写一个函数判断一个人是否可以参加所有的课程。输出为 true or false

#include <iostream> #include <cstdio> using namespace std; int main() { int s, e; int temp = -1; while(scanf("%d,%d", &s, &e) != EOF) { if(s < temp) { printf("false\n"); return 0; } temp = e; } printf("true\n"); return 0; } 

问：输入一个字符串 s ，字符串 s 包含 1 - 50 个字符，字符串 s 中每个字符是 ‘ a’ 和 ‘b’，如果有多个最优解，可以返回任何一个

思路：

1. 遍历判断字符串是否是回文串
2. 情况一，如果是，不管是‘a’ 还是’b’，全部当成一组输出，即全是1
3. 情况二，如果不是，遇到‘a’ 输出1，遇到’b’，输出2

#include <iostream> #include <cstdio> #include <string> using namespace std; int main() { string s; cin >> s; bool flag = true; for(int i=0,j=s.size()-1; i<j; ++i,--j)//判断是否是回文串 { if(s[i] != s[j]) { flag = false; break; } } if(flag)//是回文串，情况一 { for(int i=0; i<s.size()-1; ++i) { printf("1,"); } printf("1\n"); } else//不是回文串，情况二 { for(int i=0; i<s.size()-1; ++i) { if(s[i] == 'a') printf("1,"); else printf("2,"); } if(s[s.size()-1] == 'a') printf("1\n"); else printf("2\n"); } return 0; }