Java日记2018-06-12

57.1 和为 S 的两个数字
重新按照自己想法实现一遍,注意ArrayList的泛型不能是int，只能是Integer包装型

public static ArrayList<ArrayList<Integer>> FindNumbersWithSum(int[] arr, int sum) {
        ArrayList<ArrayList<Integer>> lst = new ArrayList<>();
        int cur=0;
        int start=0;
        int end = arr.length-1;
        while(start<end){
            cur=arr[start]+arr[end];
            if(cur==sum){
                ArrayList<Integer> lsts=new ArrayList<>();
                lsts.add(arr[start]);
                lsts.add(arr[end]);
                lst.add(lsts);
                start++;
            } else if(cur<sum){
                start++;
            }else{
                end--;
            }
        }
        return lst;
    }

57.2 和为 S 的连续正数序列

以数组的返回形式实现一遍

public static ArrayList<int[]> FindContinuousSequence(int sum) {
        ArrayList<int[]> lst = new ArrayList<>();
        int cur=3;
        int start=1;
        int end = 2;
        while(end<sum){
            if(cur==sum){
                int[] arrt= new int[2];
                arrt[0]=start;
                arrt[1]=end;
                lst.add(arrt);
                cur-=start;
                start++;
                end++;
                cur+=end;
            } else if(cur<sum){
                end++;
                cur+=end;
            }else{
                cur-=start;
                start++;
                
            }
        }
        return lst;
    }

58.1 翻转单词顺序列
留白
58.2 左旋转字符串
留白

59. 滑动窗口的最大值
    看题目意思居然理解错了，要认真审题啊
    给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，2 3 4的最大值是4，3 4 2的最大值是4，以此类推

使用优先级队列，题解漂亮的地方在于用了表达式，相当简化了

实现时候出的错误一个是优先级队列的表达式写反了，然后是队列加入的值错写成了索引

public static ArrayList<Integer> maxv(int[] arr,int k){
        if(arr==null) return null;
        ArrayList<Integer> lst= new ArrayList<>();
        //注意表达式怎么写的
        PriorityQueue<Integer> que = new PriorityQueue<>((s1,s2)->(s2-s1));
        for(int i=0;i<k;i++){
            que.add(arr[i]);
        }
        int curm=que.peek();
        lst.add(curm);
        //注意i j怎么初始化的
        for(int i=1,j=i+k-1;j<arr.length;i++,j++){
            que.remove(arr[i-1]);
            que.add(arr[j]);
            lst.add(que.peek());
        }
        return lst;
    }

60. n 个骰子的点数
    动态规划的解法 使用一个二维数组 dp 存储点数出现的次数，其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。
    那么第i-1次骰子产生的点数可能是n-1,n-2,n-3,n-4,n-5，n-6,至于循环时候当然要保证j>=k，不然就出现 dp[i - 1][j - k]里面的j-k小于0，这不合适
    具体没实现，拷贝前面的，复习待完成

public List<Map.Entry<Integer, Double>> dicesSum(int n) {
    final int face = 6;
    final int pointNum = face * n;
    long[][] dp = new long[n + 1][pointNum + 1];
    for (int i = 1; i <= face; i++)
        dp[1][i] = 1;

    for (int i = 2; i <= n; i++)
        for (int j = i; j <= pointNum; j++)  // 使用 i 个骰子最小点数为 i
            for (int k = 1; k <= face && k <= j; k++)
                dp[i][j] += dp[i - 1][j - k];

    final double totalNum = Math.pow(6, n);
    List<Map.Entry<Integer, Double>> ret = new ArrayList<>();
    for (int i = n; i <= pointNum; i++)
        ret.add(new AbstractMap.SimpleEntry<>(i, dp[n][i] / totalNum));
    return ret;
}