头像

tsao


访客:1580

离线:8天前



tsao
1个月前
class Solution {
    public int maxDistance(int[] a, int m) {
        Arrays.sort(a);
        int l = 0, r = (int) 1e9;
        while(l < r - 1){
            int mid = l + r >> 1;
            if(check(a, mid, m)) l = mid;
            else r = mid;
        }
        return check(a, l, m) ? l : r;
        // return r;
    }
    private boolean check(int[] a, int mid, int m){
        int last = a[0], cnt = 1;
        for(int i = 1; i < a.length; i++){
            if(a[i] - last >= mid){
                cnt++;
                last = a[i];
            }
        }
        return cnt >= m;
    }
}



tsao
9个月前

题目描述:
给定一个字符串,求该字符串中所有相同的字符均相邻的最小交换次数。

示例输入1 : “abba”
示例输出1 : 1。提示:一次交换后变成aabb或bbaa

示例输入2 : “abaccb”
示例输出2 : 2。提示:”abaccb” –> “aabccb” –> “aaccbb”

自己写了一个复杂度局高的暴力解法,很不满意。有没有人可以给出更好的解。

代码如下:

    public static void main(String[] args) {
        String str = "abbba";
        System.out.println (judge (str.toCharArray ()));
        int n = str.length (), cnt = 0, minm = Integer.MAX_VALUE;
        int swaps = minSwaps (str.toCharArray (), 0, n - 1, cnt, minm);
        System.out.print (swaps);
    }

    // 判断当前字符串是否满足要求:所有相同字符均相邻
    static boolean judge(char arr[]) {
        int[] idx = new int[26];
        Arrays.fill (idx, -1);
        for (int i = 0; i < arr.length; i++) {
            if (idx[arr[i] - 'a'] == -1 || idx[arr[i] - 'a'] == i - 1) {
                idx[arr[i] - 'a'] = i;
            } else {
                return false;
            }
        }
        return true;
    }


    static int minSwaps(char str[], int l, int r, int cnt, int minm) {
        if (l == r) {
            if (judge (str)) {
                return cnt;
            } else {
                return Integer.MAX_VALUE;
            }
        }
        // 从l+1开始,分别递归求l和i交换和不不交换的最小值
        for (int i = l + 1; i <= r; i++) {
            swap (str, i, l);
            int x = minSwaps (str, l + 1, r, cnt+1, minm);

            swap (str, i, l);
            int y = minSwaps (str, l + 1, r, cnt, minm);

            minm = Math.min (minm, Math.min (x, y));
        }

        return minm;
    }



tsao
11个月前

题目描述

思想都是一样的,线段树来做,
但是这里用Java实现的话会有个坑就是:
同样的方法Java会超时,想起之前看过某个大佬的博客提到Petr刷题的模板,
用这个就不会出现C++ 能过而 Java超时了

这个真的搞了我很久(太菜了,非科班也没参加过什么竞赛,没见过什么大的输入。。。。)
特地写出来给不知道的Java选手来避下坑。知道的就看个乐。

模板

public class InputTemplate {

    static class FR {
        BufferedReader br;
        StringTokenizer tk;

        FR(InputStream stream) {
            br = new BufferedReader (new InputStreamReader (stream), 32768);
            tk = null;
        }

        String next() {
            while (tk == null || !tk.hasMoreElements ()) {
                try {
                    tk = new StringTokenizer (br.readLine ());
                } catch (IOException e) {
                    e.printStackTrace ();
                }
            }
            return tk.nextToken ();
        }

        int nextInt() {
            return Integer.parseInt (next ());
        }
    }

    static void solve(InputStream stream, PrintWriter out) {
        FR in = new FR (stream);

        //  start code.....

    }

    public static void main(String[] args) {
        OutputStream os = System.out;
        InputStream is = System.in;
        PrintWriter out = new PrintWriter (os);
        solve (is, out);
        out.close (); // 不关闭就没有输出
    }
}

题解的全部 Java代码

import java.io.*;
import java.util.*;

class SegTree {
    // start 和 end 是区间范围
    int start;
    int end;
    long dat; // 记录的信息(最值,统计值)
    long tag; // 懒标记
}

public class Main {
    static class FR {
        BufferedReader br;
        StringTokenizer tk;

        FR(InputStream stream) {
            br = new BufferedReader (new InputStreamReader (stream), 32768);
            tk = null;
        }

        String next() {
            while (tk == null || !tk.hasMoreElements ()) {
                try {
                    tk = new StringTokenizer (br.readLine ());
                } catch (IOException e) {
                    e.printStackTrace ();
                }
            }
            return tk.nextToken ();
        }

        int nextInt() {
            return Integer.parseInt (next ());
        }
    }
    static void solve(InputStream stream, PrintWriter out) {
        FR sc = new FR (stream);

        //  start code.....
        int n = sc.nextInt ();
        int m = sc.nextInt ();
        int[] arr = new int[n + 1];
        SegTree[] tree = new SegTree[n << 2 + 1];
        for (int i = 0; i < tree.length; i++) {
            tree[i] = new SegTree ();
        }
        for (int i = 1; i <= n; i++) {
            arr[i] = sc.nextInt ();
        }
        build_ (arr, tree, 1, 1, n);
        while (m-- > 0) {
            String str = sc.next ();
            int l = sc.nextInt (), r = sc.nextInt ();
            if (str.equals ("Q")) {
                System.out.println (query_ (tree, 1, l, r));
            } else {
                int val = sc.nextInt ();
                update_ (tree, 1, l, r, val);
            }
        }

    }
    public static void main(String[] args) {
        OutputStream os = System.out;
        InputStream is = System.in;
        PrintWriter out = new PrintWriter (os);
        solve (is, out);
        out.close (); // 不关闭就没有输出
    }

    // 1. 建树,初始调用 build(1, 1, n);
    static void build_(int[] arr, SegTree[] tree, int rt, int l, int r) {
        if (l == r) {
            tree[rt].dat = arr[l];
            tree[rt].start = l;
            tree[rt].end = r;
//            System.out.println ("rt:" + rt + " l:" + l + " r:" + r + " " + idx++);
            // 单点区间不能再分,递归结束
            return;
        }

        // 递归左右子树
        int mid = l + r >> 1;
        build_ (arr, tree, rt << 1, l, mid);
        build_ (arr, tree, rt << 1 | 1, mid + 1, r);

        //回溯时更新
        tree[rt].dat = tree[rt << 1].dat + tree[rt << 1 | 1].dat;
        tree[rt].start = tree[rt << 1].start;
        tree[rt].end = tree[rt << 1 | 1].end;
    }


    // 2. 懒标记
    static void spread_(SegTree[] tree, int rt) {
        if (tree[rt].tag != 0) {
            int ls = rt << 1, rs = rt << 1 | 1;
            long lazy = tree[rt].tag;
            // 修改区间信息并更新懒标记
            tree[ls].dat += lazy * (tree[ls].end - tree[ls].start + 1);
            tree[ls].tag += lazy;

            tree[rs].dat += lazy * (tree[rs].end - tree[rs].start + 1);
            tree[rs].tag += lazy;

            // 大区间信息已经传递给下一层,因此要清零。
            tree[rt].tag = 0;
        }
    }

    // 3. 区间修改
    static void update_(SegTree[] tree, int rt, int l, int r, int val) {
        if (l <= tree[rt].start && r >= tree[rt].end) {
            // 如果一个结点表示的区间被修改区间覆盖,那它就是连续区间的一段
            // 如果它所包含的小区间都不用修改,只要修改懒标记就行了
            tree[rt].dat += val * (tree[rt].end - tree[rt].start + 1);
            tree[rt].tag += val;

            return;// 因为不用修改,直接返回就行
        }
        // 保证懒标记只在最新的区间上
        spread_ (tree, rt);

        int mid = tree[rt].start + tree[rt].end >> 1;

        if (l <= mid) update_ (tree, rt << 1, l, r, val);
        if (r >= mid + 1) update_ (tree, rt << 1 | 1, l, r, val);

        // 递归回溯时修改dat
        tree[rt].dat = tree[rt << 1].dat + tree[rt << 1 | 1].dat;
    }

    static long query_(SegTree[] tree, int rt, int l, int r) {
        if (l <= tree[rt].start && r >= tree[rt].end) {
            return tree[rt].dat;
        }
        spread_ (tree, rt);

        int mid = tree[rt].start + tree[rt].end >> 1;
        long ans = 0;
        if (l <= mid) ans += query_ (tree, rt << 1, l, r);
        if (r >= mid + 1) ans += query_ (tree, rt << 1 | 1, l, r);
        return ans;
    }
}




tsao
2019-09-26 06:44

前天做笔试碰到的一个题目。题目大意:
1~n个点,m条边的有向图。无重边,无负环,每条边有两个属性,长度和花费的金币,求从1到n的花费不超过k的最短路。
我当时是dfs+剪枝:遍历所有花费不超过k的路,然后更新最短路。每次递归检测当前花费,超过k的之间return。但是超时了
我的问题是:
能否使用Dijkstra算法来做,dist数组定义为二维,但是具体思路有人能指导一下吗?

顺便感谢AcWing上的各位小伙伴,我是非科班转行来的,在这里学到了很多。




tsao
2019-08-26 17:17

题目链接 LeetCode XXX

为什么在可能存在负权边的图中,求最短路时spfa却跟Bellman-Ford和Floyd的判断条件不一样。

spfa

int INF = 0x3f3f3f3f;
res = dist[n] == INF ? -1 : dist[n];

Bellman-Ford 和 Floyd判断:

// Bellman-Ford
int INF = 0x3f3f3f3f;
int res = dist[n] > INF/2 ? -1 : dist[n];
// Floyd
int res = d[i][j] > INF /2 ? -1 : d[i][j];



tsao
2019-08-08 16:24

有没有人能解答下,依赖关系是怎么利用 e[]、ne[]、h[] 这三个数组保存的,没太看懂。求解答!谢谢