挑战程序竞赛系列（20）：3.2尺取法

用户1147447

发布于 2019-05-26 09:22:49

5040

发布于 2019-05-26 09:22:49

文章被收录于专栏：机器学习入门机器学习入门机器学习入门

挑战程序竞赛系列（20）：3.2尺取法

详细代码可以fork下Github上leetcode项目，不定期更新。

练习题如下：

POJ 3061: Subsequence

有趣的题目，刚学完二分，此题可以用二分做，时间复杂度为O(nlogn)O(n \log n).

思路：

计算累加和，因为sum{i,j+1} > sum{i,j}，一旦sum{i,j}满足条件，则不在需要求j+1后面的元素，所以我们转而去判断i可能的位置，有了sumj，自然有sumj - s，把它作为key，利用二分查找最大的位置i，自然是答案。

代码如下：

public class SolutionDay26_P3061 {
    InputStream is;
    PrintWriter out;
    String INPUT = "./data/judge/3061.txt";

    void solve() {
        int N = ni();
        for (int i = 0; i < N; ++i){
            int n = ni();
            int s = ni();
            int[] a = na(n);
            int[] sum = new int[n+1];
            for (int j = 0; j < n; ++j){
                sum[j+1] = sum[j] + a[j];
            }

            if (sum[n] < s){
                out.println(0);
                continue;
            }

            int min = 1 << 30;
            for (int j = 1; j < n + 1; ++j){
                int l = binarySearch(sum, 0, j - 1, sum[j] - s);
                if (l != -1){
                    min = Math.min(min, j - l);
                }
            }
            out.println(min);
        }
    }

    public int binarySearch(int[] sum, int lf, int rt, int key){
        while (lf < rt){
            int mid = lf + (rt - lf + 1) / 2;
            if (sum[mid] > key) rt = mid - 1;
            else lf = mid;
        }
        if (sum[lf] <= key) return lf;
        return -1;
    }

    void run() throws Exception {
        is = oj ? System.in : new FileInputStream(new File(INPUT));
        out = new PrintWriter(System.out);

        long s = System.currentTimeMillis();
        solve();
        out.flush();
        tr(System.currentTimeMillis() - s + "ms");
    }

    public static void main(String[] args) throws Exception {
        new SolutionDay26_P3061().run();
    }

    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;

    private int readByte() {
        if (lenbuf == -1)
            throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {
                lenbuf = is.read(inbuf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (lenbuf <= 0)
                return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean isSpaceChar(int c) {
        return !(c >= 33 && c <= 126);
    }

    private int skip() {
        int b;
        while ((b = readByte()) != -1 && isSpaceChar(b))
            ;
        return b;
    }

    private double nd() {
        return Double.parseDouble(ns());
    }

    private char nc() {
        return (char) skip();
    }

    private String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
                                    // ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) {
            buf[p++] = (char) b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private char[][] nm(int n, int m) {
        char[][] map = new char[n][];
        for (int i = 0; i < n; i++)
            map[i] = ns(m);
        return map;
    }

    private int[] na(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = ni();
        return a;
    }

    private int ni() {
        int num = 0, b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
            ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }

        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
            ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }

        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

    private void tr(Object... o) {
        if (!oj)
            System.out.println(Arrays.deepToString(o));
    }
}

时间复杂度是否还可以优化？二分的做法，把每个sumj - s的查找看成独立的了，其实它们之间有着密不可分的关系，因为sum{i,j}二分求得的i是可以帮助查找sum{i’,j+1}的i’。

性质如下：

sumj+1 - s > sumj - s，由此得不存在这样的i′i'使得i′<ii' \lt i。所以，ii的更新只会往后走，而不会访问已经走过的位置。

优化代码如下：

void solve() {
    int N = ni();
    for (int i = 0; i < N; ++i){
        int n = ni();
        int s = ni();
        int[] a = na(n);
        int[] sum = new int[n+1];
        for (int j = 0; j < n; ++j){
            sum[j+1] = sum[j] + a[j];
        }

        if (sum[n] < s){
            out.println(0);
            continue;
        }

        int min = 1 << 30;
        for (int j = 1, k = 0; j < n + 1; ++j){
            int key = sum[j] - s;
            if (key >= 0){
                while (k < j && sum[k] <= key) k++;
                min = Math.min(min, j - k + 1);
            }
        }
        out.println(min);
    }
}

上述空间复杂度为O(n)O(n)，它还可以优化，也就是书中介绍的尺取法，学到了。

代码如下：

void solve() {
        int N = ni();
        for (int i = 0; i < N; ++i){
            int n = ni();
            int s = ni();
            int[] a = na(n);

            int l = 0, j = 0, sum = 0;
            int min = n + 1;
            for (;;){
                while (j < n && sum < s){
                    sum += a[j++];
                }
                if (sum < s) break; //所以更新的时候，一直保证这sum > s这个条件
                min = Math.min(min, j - l);
                sum -= a[l++];
            }
            out.println(min > n ? 0 : min);
        }
    }

POJ 3320: Jessica’s Reading Problem

提供两种解法，但核心思想差不多。

思路：

记录所有非重复知识点的个数，可以放在set中。
当遇到连续的所有知识点时，更新区间大小。

滑动窗口的做法：

用Map记录知识点出现的次数，当map的大小等于知识点的个数时，说明此时的区间为合法区间，更新。但可能出现知识点重复多次的情况，从头开始，如果头指向的知识点的次数大于1次，说明可以缩减窗口，并更新。

代码如下：

    void solve() {
        int n = ni();
        int[] a = na(n);
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < n; ++i) set.add(a[i]);
        Map<Integer,Integer> window = new HashMap<Integer, Integer>();
        int min = n;
        for (int i = 0, l = 0; i < n; ++i){
            if(!window.containsKey(a[i])) window.put(a[i],0);
            window.put(a[i], window.get(a[i]) + 1);

            if(window.size() == set.size()){
                min = Math.min(min, i - l + 1);
                while (l < n && window.get(a[l]) >= 2){
                    min = Math.min(min, i - l);
                    window.put(a[l],window.get(a[l]) - 1);
                    l++;
                }
            }
        }
        out.println(min);
    }

核心思想是保持合法窗口不变，在合法窗口满足的情况下更新最小区间。

尺取法：

有意思，尺取法的做法和滑动窗口有着异曲同工之妙，却又有些差别，它的第一个while循环保证，抵达下一步之前，总能找到合法窗口，当然已经是合法窗口则不需要操作，而找不到合法窗口时直接跳出循环。而更新过程中，则比较缓慢，每次自减一，可能会破坏窗口也可能不会。

代码如下：

void solve(){
        int n = ni();
        int[] a = na(n);
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < n; ++i) set.add(a[i]);
        Map<Integer,Integer> window = new HashMap<Integer, Integer>();
        int min = n;
        int l = 0, k = 0, len = set.size();
        for(;;){
            while (l < n && window.size() < len){
                if (!window.containsKey(a[l])) window.put(a[l], 0);
                window.put(a[l], window.get(a[l]) + 1);
                l++;
            }
            if (window.size() < len) break;
            min = Math.min(min, l - k);
            if(window.get(a[k]) == 1){
                window.remove(a[k]);
                k++;
            }else{
                window.put(a[k], window.get(a[k]) - 1);
                k++;
            }
        }
        out.println(min);
    }

POJ 2566: Bound Found

思路：

求的还是个区间和和给定的diff最小情况的最小区间，为了求连续的区间需要累加和，起码累加和能给我们连续区间和的查询操作。不用它用谁？

因为数中存在负数，所以单纯的累加和求出来的结果可以说是无序的，无序带来了一个很坏的结果，在给定某个下标j，知道了sum{j}的值，一个想法是扫描其他下标，如果存在ii使得sum{i} - sum{j}的绝对值在diff范围内，且diff差距最小，则更新最小diff和区间的两个边界l和r。

我没想到排序，对绝对值的理解不够深刻，其实给了绝对值，排序后得到的结果和无序得到的结果是一样的，且有序有一个非常大的好处，在搜索某个sum{j}-diff的过程中，一定从区间0，j-1中搜索，这样就可以使用尺取法了么？

不急，可以先看看传统的做法，我们要找的是符合sum{j} - diff的某个sum{i}，i是多少呢，可以采用二分，但二分有个问题，此题二分找到的i候选值还不是一个，因为并不是严格找sum{j}-diff的值，而是在一个很小的范围。

尺取法的好处，对于i的查找不会那么严格，类似于遍历，但遍历的顺序保证它一定是安全，一定有解存在于它的遍历顺序中。

那么尺取法为什么能够降低时间复杂度呢？很简单，尺取法每次都会确定一个上界，但每个抵达的上界在整个遍历结构中只会出现一次，为什么？

就拿这道题，寻找sum{j} - sum{i} < diff的下标i和j，但我们知道，因为sum被排序了，所以sum{j+1} - sum{i} >= sum{j} - sum{i}，在j以后的值是不需要遍历的，而尺取法能够很好的做到这点。

另外一点需要注意：排序后，原本的index发生了变化，有必要记录下。

代码如下：

class Pair{
        int sum;
        int index;

        public Pair(int sum, int index){
            this.sum = sum;
            this.index = index;
        }

        @Override
        public String toString() {
            return "["+sum+", "+index+"]";
        }
    }

    Pair[] sums;
    void solve(){
        while (true){
            int N = ni();
            int Q = ni();
            if (N == 0 && Q == 0) break;
            int[] a = na(N);
            int[] q = na(Q);
            sums = new Pair[N+1];
            for (int i = 0; i <= N; ++i) sums[i] = new Pair(0,i);
            for (int i = 0; i < N; ++i){
                sums[i+1].sum = sums[i].sum + a[i]; 
            }
            Arrays.sort(sums, new Comparator<Pair>() {
                @Override
                public int compare(Pair o1, Pair o2) {
                    return o1.sum == o2.sum ? o2.index - o1.index : o1.sum - o2.sum;
                }
            });

            for (int i = 0; i < Q; ++i){
                int diff = q[i];
                int lb = 0, ub = 0, sum = -1;
                res = 0x80808080;
                l = 0;
                r = 0;
                for(;;){
                    while (ub < N && sum < diff){
                        sum = getSum(lb, ++ub, diff);
                    }
                    if (sum < diff) break;
                    sum = getSum(++lb, ub, diff);
                }
                out.println(res + " " + l + " " + r);
            }
        }
    }

    int res, l, r;
    private int getSum(int lb, int ub, int diff){
        if (lb >= ub) return -1 << 30;
        int sum = sums[ub].sum - sums[lb].sum;
        if (Math.abs(diff - sum) < Math.abs(diff - res)){
            res = sum;
            int i = sums[ub].index;
            int j = sums[lb].index;
            l = i < j ? i + 1 : j + 1;
            r = i < j ? j : i;
        }
        return sum;
    }

POJ 2739: SUm of Consecutive Prime Numbers

强大的技巧，真不知道是技巧指导解题，还是思路本身推出技巧，whatever，没认识到这技巧，估计我要痛苦一会。

代码如下：

int MAX_N = 10000 + 16;
    int[] prime = new int[MAX_N + 1];
    boolean[] isPrime = new boolean[MAX_N + 1];
    int N = 0;
    void seive(){
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i <= MAX_N; ++i){
            if (isPrime[i]){
                prime[N++] = i;
                for (int j = 2 * i; j <= MAX_N; j += i){
                    isPrime[j] = false;
                }
            }
        }
    }

    void solve() {
        seive();
        while (true){
            int num = ni();
            if (num == 0) break;
            int lb = 0, rb = 0, cnt = 0, sum = 0;
            for(;;){
                while (lb < N && sum < num){
                    sum += prime[rb++];
                }
                if (sum < num) break;
                if (sum == num) cnt++;
                sum -= prime[lb++];
            }
            out.println(cnt);
        }
    }

POJ 2100: Graveyard Design

题目理解起来费劲，将一个整数分解为连续数平方之和，有多少种分法？

也没难度，防止溢出，都用了long。

代码如下：

class Pair{
        long l;
        long r;
        public Pair(long l, long r){
            this.l = l;
            this.r = r;
        }
    }

    void solve() {
        long num = nl();
        long n = (int)Math.sqrt(num);
        long lb = 1, rb = 1;
        long sum = 0;
        List<Pair> list = new ArrayList<Pair>();
        for(;;){
            while (lb <= n && sum < num){
                sum += (rb * rb);
                rb++;
            }
            if (sum < num) break;
            if (sum == num){
                list.add(new Pair(lb,rb - 1));
            }
            sum -= lb * lb;
            lb++;
        }
        out.println(list.size());
        for (Pair p : list){
            long size = p.r - p.l + 1;
            StringBuilder sb = new StringBuilder();
            sb.append(size + " ");
            for (long i = p.l; i <= p.r; ++i){
                sb.append(i + " ");
            }
            out.println(sb.toString().trim());
        }
    }

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017年06月27日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度

挑战程序竞赛系列（20）：3.2尺取法

挑战程序竞赛系列（20）：3.2尺取法

挑战程序竞赛系列（20）：3.2尺取法

POJ 3061: Subsequence

POJ 3320: Jessica’s Reading Problem

POJ 2566: Bound Found

POJ 2739: SUm of Consecutive Prime Numbers

POJ 2100: Graveyard Design

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐