笔试编程题整理

归并排序:

//将有序数组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,因为它是离长度值最近的最大质数

可以盛最多水的容器

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

笔试编程题整理
01.png
编程试题:求数列的和 

使用语言: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);

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


笔试编程题整理
02.png

水仙花的求解

编程试题:水仙花  

使用语言: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;
}

上一篇:Android 开源框架ImageLoader的完美例子


下一篇:sqoop数据迁移(基于Hadoop和关系数据库服务器之间传送数据)