Java日记2018-05-20

第一题 和为 S 的连续正数序列

输出所有和为 S 的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

例如和为 100 的连续序列有：

[9, 10, 11, 12, 13, 14, 15, 16]
[18, 19, 20, 21, 22]。

package com.lyc.dataautest;

import java.util.ArrayList;

public class FindContinuousSequence {
    public static ArrayList<ArrayList<Integer>> find(int n) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        int start = 1;
        int end = 2;
        int sum = start + end;
        while (start < end) {
            if (sum < n) {
                end++;
                sum += end;
            } else if (sum > n) {
                sum -= start;
                start++;
            } else {
                ArrayList<Integer> list = new ArrayList<Integer>();
                for (int i = start; i <= end; i++) {
                    list.add(i);
                }
                ret.add(list);
                sum -= start;
                start++;
            }
        }

        return ret;
    }

    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> res = find(100);
        for (int i = 0; i < res.size(); i++)
            System.out.println(res.get(i));

    }

}

第二题 翻转单词顺序列
先旋转每个单词，再旋转整个字符串。

public class ReverseSentence {
    public static String ReverseSentence(String str) {
        if (str == null) return null;
        String res=null;
        StringBuffer strb = new StringBuffer(str);
        int i=0;
        int j=1;

        //先旋转整个句子
        swap(strb, 0, str.length()- 1);
        //旋转单词
        while(j<str.length()) {
                       //注意下边的空格是char类型，因此是' '
            if(strb.charAt(j)!=' ') {
                j++;
            } else {
                swap(strb,i,j-1);
                i=j+1;
                j=j+2;  
            }
        }
        
        res = strb.toString();
        System.out.println(res);
        return res;
    }

    public static void swap(StringBuffer strb, int i, int j) {
        while (i < j) {
            char temp = strb.charAt(i);
            strb.setCharAt(i, strb.charAt(j));
            strb.setCharAt(j, temp);
            i++;
            j--;
        }
    }
    
    public static void main(String[] args) {
        String str="I am a student.";
        ReverseSentence(str);
    }

}

第三题 左旋转字符串
对于一个给定的字符序列 S，请你把其循环左移 K 位后的序列输出。例如，字符序列 S=”abcXYZdef”, 要求输出循环左移 3 位后的结果，即“XYZdefabc”。

思路 将 "abcXYZdef" 旋转左移三位，可以先将 "abc" 和 "XYZdef" 分别旋转，得到 "cbafedZYX"，然后再把整个字符串旋转得到 "XYZdefabc"。
借用上题的方法就行，不再说明

第四题 滑动窗口的最大值
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，他们的最大值分别为 {4, 4, 6, 6, 6, 5}。

最暴力的方法就是滑动找最大值，以滑动窗口为3为例子，仔细思考如果滑动一个窗口，其实有两个已经比较过大小，再次比较就浪费了，可以使用优先级队列