补充一下

最近半年的时间我都在准备研究生考试，因此没有继续学习Java的主流框架。初试成绩出来后，按照以往的分数线我是可以参加复试的，所以这两个月在准备复试机试。考虑到可以使用eclipse （JAVA 6）的编译器，因此准备用Java来准备。虽然Java没有C/C++的速度，但是我更熟悉Java。

准备工作

复试上机环境是Java SE 6，因此将IDE的编译环境切换为Java SE 6。
根据《算法笔记》和《王道计算机考研机试指南》的顺序，按照经典入门题、数据结构相关、数学问题、图论问题、搜索算法和动态规划这几个模块来准备。

经典入门题

排序

我们知道，最快捷的排序方法是快速排序，但是大部分人都没有直接记住排序的代码，因此在考场直接写快排是很麻烦的，因此我们可以借助Java库中的Arrays.Sort()函数来实现快速排序。我们只要定义好每个元素的比较方法即可。

我们以一道成绩排序题为例(清华大学2000年研究生机试题)，来看下如何调用类库中的Sort()进行快速操作。

package com.algorithm.test;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author fzm
 * @date 2019-02-19
 */
public class GradeSort {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        Student[] students = new Student[n];
        String[] str;
        for (int i = 0; i < n; i++) {
            str = sc.nextLine().split(" ");
            students[i] = new Student(Integer.parseInt(str[0]), Integer.parseInt(str[1]));
        }
        Arrays.sort(students);
        for (Student s:
             students) {
            System.out.println(s.id + " " + s.grade);
        }
    }


    private static class Student implements Comparable<Student> {
        int id;
        int grade;

        public Student() {
        }

        public Student(int id, int grade) {
            this.id = id;
            this.grade = grade;
        }


        @Override
        /*
          定义排序的比较方案
         */
        public int compareTo(Student o) {
            //成绩比较更优先
            if (this.grade < o.grade) {
                return -1;
            } else if (this.grade > o.grade) {
                return 1;
              //如果相等，再比较学号
            } else {
                if (this.id < o.id) {
                    return -1;
                } else {
                    return 1;
                }
            }
        }
    }
}

要注意的地方就是定义的compareTo()函数，返回-1表示被比较对象较小，反之较大。

日期类问题

日期类问题也是在机试题中频繁出现的题目，我们要注意的仅仅是闰年的计算和2月天数的不同。以一道日期类问题为例（上海交大2009年机试题），来看下如何进行日期操作。

package com.algorithm.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author fzm
 * @date 2019-02-19
 */
public class DayOfWeek {

    private static int[] times = {
            31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
    };
    private static String[] months = {
            "January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"
    };
    private static String[] days = {
            "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"
    };

    public static void main(String[] args) {
        List<String> inList = new ArrayList<String>();
        String in;
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            in = sc.nextLine();
            if (in.equals("")) {
                break;
            }
            inList.add(in);
        }

        for (String res :
                inList) {
            String[] strs = res.split(" ");
            int day = Integer.parseInt(strs[0]);
            int month = Arrays.asList(months).indexOf(strs[1]) + 1;
            int year = Integer.parseInt(strs[2]);
            OwnDate date = new OwnDate(year, month, day);
            OwnDate flagDate = new OwnDate(2019, 2, 24);
            int diff;
            //根据两个日期的早晚，选定计数方式
            boolean fl = flag(date, flagDate);
            if (fl) {
                diff = (getValue(date, flagDate) - 1) % 7;
            } else {
                diff = (getValue(flagDate, date) - 1) % 7;
            }
            //判断往前计数还是往后计数
            if (fl) {
                System.out.println(days[7 - diff]);
            } else {
                System.out.println(days[diff]);
            }
        }

    }

    private static class OwnDate {
        int year;
        int month;
        int day;

        public OwnDate(int year, int month, int day) {
            this.year = year;
            this.month = month;
            this.day = day;
        }

        public OwnDate() {
        }

        @Override
        public String toString() {
            return "OwnDate{" +
                    "year=" + year +
                    ", month=" + month +
                    ", day=" + day +
                    '}';
        }
    }

    /**
     * 是否为闰年
     */
    private static boolean isLeap(int year) {
        return (year % 4 == 0 && year % 100 != 0 || year % 100 == 0 && year % 400 == 0);
    }


    private static int getValue(OwnDate date1, OwnDate date2) {
        int res = 1;
        int diff = 0;
        int i;
        for (i = date1.year; i < date2.year; i++) {
            res += isLeap(i) ? 366 : 365;
        }

        if (date1.month < date2.month) {
            for (int j = date1.month - 1; j < date2.month - 1; j++) {
                diff += times[j];
                if (isLeap(i) && j == 1) {
                    diff++;
                }
            }
            res += diff;
        } else if (date1.month > date2.month) {
            for (int j = date2.month - 1; j < date1.month - 1; j++) {
                diff += times[j];
                if (isLeap(i) && j == 1) {
                    diff++;
                }
            }
            res -= diff;
        }

        res += (date2.day - date1.day);

        return res;
    }

    /**
     * 比较两个日期的大小
     * @return 如果date1早于date2，则返回true
     */
    private static boolean flag(OwnDate date1, OwnDate date2) {
        boolean flag = false;
        if (date1.year < date2.year) {
            flag = true;
        } else if (date1.year == date2.year) {
            if (date1.month < date2.month) {
                flag = true;
            } else if (date1.month == date2.month) {
                if (date1.day < date2.day) {
                    flag = true;
                }
            }
        }
        return flag;
    }
}

Hash的应用

将数据的存储位置与数据本身对应起的手段就是Hash，我们所知的Hash算法、计数排序等都运用了这种思想。当我们遇到了统计学生人数的问题时，我们便可以使用Hash的思想。以一道该类型的题目为例（2006年浙江大学机试真题）。

package com.algorithm.test;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * @author fzm
 * @date 2019-02-19
 */
public class StuGrade {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int num;
        String[] gradeStrs;
        String specGrade;

        while (sc.hasNextLine()) {
            num = Integer.parseInt(sc.nextLine());
            if (num == 0) return;
            gradeStrs = sc.nextLine().split(" ");
            specGrade = sc.nextLine();
            out(num, gradeStrs, specGrade);
        }


    }

    private static void out(int n, String[] str, String spec) {
        //用HashMap来一一对应，少去不必要的操作
        Map<String, Integer> map = new HashMap<String, Integer>();
        for (String s :
                str) {
            map.put(s, map.get(s) == null ? 1 : map.get(s) + 1);
        }
        System.out.println(map.get(spec) == null ? 0 : map.get(spec));
    }
}

查找

查找的重要性在整个算法体系中是不言而喻的，所以在机试中极有可能出现查找的题目，或者需要运用到。我们先来了解一下几个查找的基本要素。

1、查找空间。也常被称为解空间。所谓查找，就是在该查找空间中找寻符合我们要求的解的过程。

2、查找目标。我们需要一个目标来判断查找空间中的各个元素是否符合我们的要求，以便判断查找活动是否已经成功。

3、查找方法。即利用某种特定的策略在查找空间中查找各个元素。不同的策略对查找的效率和结果有不同的影响。

我们以一道普通的查找题为例（2003年清华大学研究生机试），来看下查找代码如何写。

package com.algorithm.test;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * @author fzm
 * @date 2019-02-20
 */
public class FindStuInfo {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<String, String> inMap = new HashMap<String, String>();
        sc.nextLine();
        for (int i = 0; i < n; i++) {
            String str = sc.nextLine();
            //由于每个学生的学号不同，因此可以使用Hash的方法来存储
            inMap.put(str.split(" ")[0], str);
        }
        int m = sc.nextInt();
        sc.nextLine();
        String[] nums = new String[m];
        for (int i = 0; i < m; i++) {
            nums[i] = sc.nextLine();
        }

        for (String num :
                nums) {
            System.out.println(inMap.get(num) == null ? "No Answer!" : inMap.get(num));
        }
    }
}

在上一例中使用的是Hash方法，Java的HashMap中get()方法使用的是普通的遍历方法，这样的时间复杂度就非常的大了，这样可能导致程序不合格。为了满足条件，我们可以使用二分查找法，来加快查找速度，算法如下：
1
2
3
4
5
6
7
int base = 0, top = size;
while (base <= top){ //二分循环与二分查找一致
int mid = (base + size) / 2;
if (a[mid] <= target) base = mid + 1;
else top = mid - 1;
}
int ans = top;

贪心算法

这种算法思路较为简单，即一种总是选择“当前最好的选择”，而不从整体上去把握的思想，往往这种“贪心”的策略能够得到接近最优的结果，甚至最优的结果。我们以一道上机题为例（2012年浙江大学机试To fill or not to fill)，代码如下：

package com.algorithm.test;

import java.text.DecimalFormat;
import java.util.*;

/**
 * @author fzm
 * @date 2019-02-20
 */
public class ToFillOrNot {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        DecimalFormat df = new DecimalFormat("#.00");

        while (sc.hasNextLine()) {
            //最大油量
            double cMax = sc.nextDouble();
            //初始油量
            double capacity = 0;
            int maxDis = sc.nextInt();
            //平均油量路程
            int dAvg = sc.nextInt();
            //加油站数目
            int num = sc.nextInt();
            double onceMaxDis = cMax * dAvg;
            int dis = 0;
            double price = 0;
            //定义两个以距离或价格的加油站的排序数组
            Station[] disStations = new Station[num];
            Station[] priceStations = new Station[num];
            Station here = null;
            sc.nextLine();
            int maxStationDis = 0;
            for (int i = 0; i < num; i++) {
                String[] str = sc.nextLine().split(" ");
                Station station = new Station(Double.parseDouble(str[0]), Integer.parseInt(str[1]));
                maxStationDis = Math.max(maxStationDis, Integer.parseInt(str[1]));
                disStations[i] = station;
                priceStations[i] = station;
                //选定一个初始加油站
                if (station.distance == 0) {
                    here = station;
                }
            }

            Arrays.sort(disStations, new DisSort());
            Arrays.sort(priceStations, new PriceSort());


            boolean success;
            boolean great;
            while (true) {
                //判断能否找到最优方案
                great = false;

                for (Station s : disStations)
                    if (s != here && dis <= s.distance && s.distance <= dis + onceMaxDis) {
                        if (s.price <= here.price) {
                            //计算油费
                            if ((s.distance - here.distance) / dAvg > capacity) {
                                price += ((double) (s.distance - here.distance) / dAvg - capacity) * here.price;
                                capacity = 0;
                            } else {
                                capacity -= (double) (s.distance - here.distance);
                            }
                            dis += (s.distance - here.distance);
                            here = s;
                            great = true;
                            break;
                        }
                    }

                if (!great) {
                    for (Station s : priceStations) {
                        if (s != here && dis <= s.distance && s.distance <= dis + onceMaxDis) {
                            //将油加满
                            price += (cMax - capacity) * here.price;
                            dis += (s.distance - here.distance);
                            capacity = cMax - (double) (s.distance - here.distance) / dAvg;
                            here = s;
                            break;
                        }  //无法抵达

                    }
                }

                if (here != null) {
                    if (here.distance == maxStationDis) {
                        if (maxDis < maxStationDis + onceMaxDis) {
                            price += (double) (maxDis - maxStationDis) / dAvg * here.price;
                            success = true;
                            break;
                        } else {
                            dis += onceMaxDis;
                            success = false;
                            break;
                        }
                    }
                }
            }

            if (success) {
                System.out.println(df.format(price));
            } else {
                System.out.println("The maximum travel distance = " + df.format(dis));
            }

        }

    }

    private static class DisSort implements Comparator<Station> {

        @Override
        public int compare(Station o1, Station o2) {
            if (o1.distance < o2.distance) {
                return -1;
            } else if (o1.distance == o2.distance) {
                return 0;
            } else {
                return 1;
            }
        }
    }

    private static class PriceSort implements Comparator<Station> {
        @Override
        public int compare(Station o1, Station o2) {
            return Double.compare(o1.price, o2.price);
        }
    }

    private static class Station {
        double price;
        int distance;

        public Station(double price, int distance) {
            this.price = price;
            this.distance = distance;
        }

        public Station() {
        }

        @Override
        public String toString() {
            return "Station{" +
                    "price=" + price +
                    ", distance=" + distance +
                    '}';
        }
    }
}

总结

本文介绍了排序、日期类问题、Hash、查找、贪心等在机试中频繁出现的基本算法。在完全了解后，相信能解决大部分简单的机试题了。

LightYears's Blog

研究生机试算法