1. Window Sum

注意(arraylist == null || arraylist.size() == 0)要return一个已经初始化的arrayList而不是null。

注意 corner cases。

class myCode
{
    public static void main (String[] args) throws java.lang.Exception
    {
        List<Integer> input = new ArrayList<>();
        input.addAll(Arrays.asList(2,3,4,2,5,7,8,9,6));
//      List<Integer> input1 = new ArrayList<>();
//      input1.addAll(Arrays.asList(1,2));
        List<Integer> output = windowSum(input, 3);
        for(int i: output) System.out.print(i + " ");
    }


    public static List<Integer> windowSum(List<Integer> input, int k) {
        List<Integer> res = new ArrayList();

        if (input == null || input.size() == 0 || k <= 0)
                return res;

        if (k >= input.size()) {
            int t = 0;
            for (int a : input) {
                t += a;
            }
            res.add(t);
            return res;
        }

        int n = input.size();
        int[] sum = new int[n+1];

        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i-1] + input.get(i-1);
        }

        for (int i = k; i <= n; i++) {
            res.add(sum[i] - sum[i-k]);
        }

        return res;
    }

    // 2,3,4,2   2
    // 5,7, 6
}

RoundRobin

public static void main(String[] args) {
        // TODO Auto-generated method stub
        //int[] arriveTime = {0, 1, 3, 9};
        //int[] runTime = {2, 1, 7, 5};
        int[] arriveTime = {0,2,4,5};
        int[] runTime = {7,4,1,4};
        System.out.println(roundRobin(arriveTime, runTime, 3));
    }

    public static double roundRobin(int[] start, int[] end, int qt) {

        if (start == null || start.length == 0 || start.length != end.length)
            return 0.0;

        int length = start.length;

        Queue<Process> q = new LinkedList();

        int curtime = 0;
        int wait = 0;
        int index = 0;

        while (!q.isEmpty() || index < length) {

            if (q.isEmpty()) {
                q.offer (new Process(start[index], end[index]));
                curtime = start[index++];
            } else {
                Process cur = q.poll();
                wait += curtime - cur.arr;
                curtime += Math.min(cur.burst, qt);

                for (; index < length && start[index] < curtime; index++) {
                    q.offer(new Process(start[index], end[index]));
                }

                if (cur.burst > qt) {
                    q.offer(new Process(curtime, cur.burst - qt));
                }
            }
        }

        return wait * 1.0 / length;


    }

    class Process {
    int arr;
    int burst;

    public Process(int arr, int burst) {
        this.arr = arr;
        this.burst = burst;
    }
}