头像

dongwa_zzuli

郑州轻工业大学




离线:5天前


最近来访(34)
用户头像
夏野了_0
用户头像
CCPC菜狗
用户头像
善良的大铁牛
用户头像
StayAlive
用户头像
zyj..
用户头像
小JAVA千
用户头像
bbxl
用户头像
爱吃面条的阿泽
用户头像
gugugaga
用户头像
杨大鑫_ωノ
用户头像
努力ing
用户头像
fujang
用户头像
刷刷刷算法
用户头像
吴霖峰
用户头像
栗子ing
用户头像
星逐月丶
用户头像
不哭死神
用户头像
coolmannewkeyNG
用户头像
深藏功与名
用户头像
dfs+dp


dongwa_zzuli
8个月前

算法题目

题目链接
给定一个长度为n的整数数列,请你计算数列中的逆序对的数量。

逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满足 i < j 且 a[i] > a[j],则其为一个逆序对;否则不是。

输入格式

第一行包含整数n,表示数列的长度。

第二行包含 n 个整数,表示整个数列。

输出格式

输出一个整数,表示逆序对的个数。

数据范围

1≤n≤100000

输入样例:

6
2 3 4 5 6 1

输出样例:

5

算法思路

求逆序对的算法是利用了归并排序的思想,在归并排序的过程中会将序列分为两部分,此时逆序对可以分为三种情况:两个数都在左边的(设为s1)。两个数都在右边的(s2),一个数在左边一个数在右边的(s3)。现在假设我们在归并排序的时候写的函数merge_sort(int[] arr, int l, int r)可以返回lr区间中逆序对数量。那么s1=mergeSort(a, l, mid),s2=mergeSort(a, mid + 1, r);s3很显然没有直观的答案。

那么核心问题就在于怎么求s3,以及怎么使我们的merge_sort(int[] arr, int l, int r)可以返回lr区间中逆序对数量。

算法实现

怎么求s3?

s3可以看作下图中红色圈圈的情况。对于右边的中的任意一个数,在左边的数只要大于他就构成逆序对,我们只能要统计出这些数,就能求出s3。
240358d50ace903a16f4700203564edc.png
如何能快速地统计出来这些数呢?我们知道在归并排序中,左右两边都是排序好的数列。因此,对于右图中的B我们只需要找到左边第一个大于B的数A,那么A后面的数都是大于B的。假设A的下标为i,不难得到我们要统计的数目为:mid-i+1,恰巧在归并排序的合并过程中正好有两边序列依次比大小的过程:

if (arr[i] <= arr[j])
    tmp[k++] = arr[i++];
else
    tmp[k++] = arr[j++];

else中的语句即代表左边数列中的数大于右边中的数了,我们可以在此时将mid-i+1加到总答案中去。那么s3的问题就解决了。

if (a[i] <= a[j])
    tem[k++] = a[i++];
else {
    res += mid - i + 1;
    tem[k++] = a[j++];
}

s3的问题解决后,我们的函数还没有解决问题的能力,只需要在递归出口的时候return 0;因为递归结束的时候数列中只有一个数了,不存在逆数对。还需要在递归归并排序的时候统计两边的逆序对数量之和long res = mergeSort(a, l, mid) + mergeSort(a, mid + 1, r);即可。

这里注意一点,因为题目中的数据范围最大是100000,一般对于数据范围大于10w的题目就要考虑数据溢出、时间复杂度等问题。

那么对于最大100000规模的数据,逆序对最多的数量为多少呢?

当数列是一个倒序的数列时应该是逆序对数量最大的时候,每一个数可以和他后面所有的数形成逆数对,如果有n个数,那么总的逆序对数量为:(n-1)+(n-2)+……+1即$\frac{n(n-1)}{2}$个,大约$\frac{n^2}{2}$个,代入10w的数据范围得最多逆数对个数为:$5\times10^9$,这个数据大于int的范围。所以这个题用int的话会溢出,我们采用long来存结果。

java代码实现

import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {

    public static void main(String[] args)  {
        Scanner sacnner = new Scanner(new InputStreamReader(System.in));
        int n = sacnner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sacnner.nextInt();
        }
        System.out.println(mergeSort(a, 0, n - 1));
        sacnner.close();
    }

    private static long mergeSort(int[] a, int l, int r) {
        if (l >= r)
            return 0;

        int mid = l + r >> 1;
        long res = mergeSort(a, l, mid) + mergeSort(a, mid + 1, r);
        int tmp[] = new int[r-l+1];
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (a[i] <= a[j])
                tmp[k++] = a[i++];
            else {
                res += mid - i + 1;
                tmp[k++] = a[j++];
            }
        }
        while (i <= mid)
            tmp[k++] = a[i++];
        while (j <= r)
            tmp[k++] = a[j++];
        for(i=l,j=0;i<=r;i++,j++)a[i]=tmp[j];
        return res;
    }

}


活动打卡代码 AcWing 867. 分解质因数

dongwa_zzuli
8个月前
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            dividePrime(scanner.nextInt());
            System.out.println();
        }
        scanner.close();
    }

    private static void dividePrime(int n) {
        /**
         * 就是把每个能除的数给它彻底除完,这样的话能除的一定都是质数。
         * 因为刚开始除的2就是质数而它的倍数也会被除完3同理,就算最初这个数有4这个因子也会因为被2除完了不会出现。
         */
        for (int i = 2; i <= n / i; i++) {
            if (n % i == 0) {
                int s = 0;
                while (n % i == 0) {
                    n /= i;
                    s++;
                }
                System.out.println(i + " " + s);
            }
        }
        if (n > 1)
            System.out.println(n + " " + 1);
    }
}




dongwa_zzuli
8个月前
import java.util.Scanner;

/**
 * 试除法判断质数
 * 
 * @author dongwa
 *
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            System.out.println(isprime(scanner.nextInt()));
        }
        scanner.close();
    }

    private static String isprime(int x) {
        if (x < 2)
            return "No";
        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0)
                return "No";
        }
        return "Yes";
    }
}



活动打卡代码 AcWing 3302. 表达式求值

dongwa_zzuli
8个月前
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String str = scanner.nextLine();
        Calculator calculator = new Calculator(str);
        System.out.println(calculator.eval());
        scanner.close();
    }

    // 计算中缀表达式
    static class Calculator {
        String expression; // 表达式字符串
        Stack<Integer> nums; // 存储操作符的栈
        Stack<Character> op; // 存储操作数的栈
        Map<Character, Integer> priority;// 操作符的优先级

        /**
         * @param expression
         */
        public Calculator(String expression) {
            this.expression = expression;
            nums = new Stack<>();
            op = new Stack<>();
            priority = new HashMap<>();
            priority.put('+', 1);
            priority.put('-', 1);
            priority.put('*', 2);
            priority.put('/', 2);
        }

    // 向外暴露的方法,计算表达式,并将结果返回
        public int eval() {
            for (int i = 0; i < expression.length(); i++) {
                char cur = expression.charAt(i);
                if (Character.isDigit(cur)) {
                    // 若当前字符是数字的话。需要将这个数从字符串中抠出来
                    int x = 0, j = i;
                    while (j < expression.length() && Character.isDigit(expression.charAt(j))) {
                        x = x * 10 + expression.charAt(j++) - '0';
                    }
                    i = j - 1;
                    // 将所有的操作数压入nums中
                    nums.push(x);
                }
                // 碰见右括号直接压入
                else if (cur == '(')
                    op.push(cur);
                else if (cur == ')') {
                    // 碰见左括号。计算两个括号之间的表达式
                    while (op.peek() != '(')
                        calculate();
                    //括号中的表达式求完了,将'('弹出
                    op.pop();
                } else {
                    // 遇到一个操作符,若他的优先级比栈顶的优先级小,那么先将栈顶的那个操作符运算了
                    while (!op.isEmpty() && op.peek() != '(' && priority.get(op.peek()) >= priority.get(cur))
                        calculate();
                    // 然后再将他压入栈中
                    op.push(cur);
                }
            }
            // 将所有的运算符操作
            while (!op.isEmpty())
                calculate();
            // 所有的运算符处理完后,nums中就只剩下最后的运算结果了
            return this.nums.peek();
        }

    //内部方法,用于计算栈顶两个操作数的结果,在将结果压入nums栈中
        private void calculate() {
            int b = nums.pop();
            int a = nums.pop();
            char c = op.pop();
            int res;
            if (c == '+')
                res = a + b;
            else if (c == '-')
                res = a - b;
            else if (c == '*')
                res = a * b;
            else
                res = a / b;
            nums.push(res);
        }

    }
}



活动打卡代码 AcWing 907. 区间覆盖

dongwa_zzuli
8个月前
import java.util.Arrays;
/**
 * 区间覆盖问题
 * https://www.acwing.com/problem/content/909/
 */
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 给定区间左右两断点
        int start = scanner.nextInt(), end = scanner.nextInt();
        // 区间数
        int n = scanner.nextInt();

        Section[] sections = new Section[n];
        for (int i = 0; i < n; i++) {
            sections[i] = new Section(scanner.nextInt(), scanner.nextInt());
        }
        // 将区间按左端点排序
        Arrays.sort(sections, (a, b) -> a.l - b.l);

        int res = 0;
        // 依次遍历每个区间,选取 l < s 且r最大的区间
        for (int i = 0; i < n; i++) {
            // 找到那个l < s 且r最大的区间
            int j = i, r = -Integer.MAX_VALUE;
            while (j < n && sections[j].l <= start) {
                r = Math.max(r, sections[j].r);
                j++;
            }
            // 若找到的最大的r < start 说明无解
            if (r < start) {
                res = -1;
                break;
            }
            // 找到一个区间,res++
            res++;
            // 更新起点
            start = r;
            // 此时的j是i后面的最长的区间,那么i至j-1中间的区间就可以不用考虑了
            i = j - 1;
            // 若找到的最大的r >= end 说明区间覆盖完了
            if (r >= end) {
                System.out.println(res);
                return;
            }

        }
        //程序没有return 走到了这里,说明没有将区间覆盖完
        System.out.println(-1);
        scanner.close();
    }

    static class Section {
        int l, r;

        /**
         * @param l 区间左端点
         * @param r 区间右端点
         */
        public Section(int l, int r) {
            this.l = l;
            this.r = r;
        }

    }
}



活动打卡代码 AcWing 906. 区间分组

dongwa_zzuli
8个月前
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        Section[] sections = new Section[n];
        for (int i = 0; i < n; i++) {
            sections[i] = new Section(scanner.nextInt(), scanner.nextInt());
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        Arrays.sort(sections, (o1, o2) -> o1.l - o2.l);
        // 从小到大遍历每个区间
        for (int i = 0; i < n; i++) {
            if (queue.isEmpty() || queue.peek() >= sections[i].l) {
                // 队列为空或者当前区间不可以分在这个组中,新开一个组
                queue.add(sections[i].r);
            } else {
                // 当前区间可以分在这个组中,更新组的最大右端点
                queue.poll();
                queue.add(sections[i].r);
            }
        }
        System.out.println(queue.size());
        scanner.close();
    }

    static class Section {
        int l, r;

        /**
         * @param l 区间左端点
         * @param r 区间右端点
         */
        public Section(int l, int r) {
            this.l = l;
            this.r = r;
        }

    }
}



活动打卡代码 AcWing 905. 区间选点

dongwa_zzuli
8个月前
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        Section[] sections = new Section[n];

        for (int i = 0; i < n; i++) {
            sections[i] = new Section(scanner.nextInt(), scanner.nextInt());
        }
        // 将所有区间按右端点排序
        Arrays.sort(sections);
        int ans = 0, index = -Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (sections[i].l > index) {
                ans++;
                index = sections[i].r;
            }
        }

        System.out.println(ans);
        scanner.close();
    }

    static class Section implements Comparable<Section> {
        int l, r;

        /**
         * @param l
         * @param r
         */
        public Section(int l, int r) {
            this.l = l;
            this.r = r;
        }

        @Override
        public int compareTo(Section o) {
            return this.r - o.r;
        }

    }
}



活动打卡代码 AcWing 901. 滑雪

dongwa_zzuli
8个月前
/**
 * 滑雪问题
 * dp[i][j] 表示从ij点作为起点的路径的最大值
 * 由于从点ij开始有上下左右4个方向可以滑,那么dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1],dp[i][j+1],dp[i+1][j])+1;
 */
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt(), m = scanner.nextInt();
        int[][] g = new int[n + 1][m + 1];
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                g[i][j] = scanner.nextInt();
                dp[i][j] = -1;
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                ans = Math.max(ans, skiing(i, j, n, m, g, dp));
            }
        }
        System.out.println(ans);
        scanner.close();
    }

    private static int skiing(int x, int y, int n, int m, int[][] g, int[][] dp) {
        int[] dx = { -1, 0, 1, 0 }, dy = { 0, 1, 0, -1 };
        if (dp[x][y] != -1)
            return dp[x][y];

        dp[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[a][b])
                dp[x][y] = Math.max(dp[x][y], skiing(a, b, n, m, g, dp) + 1);
        }
        return dp[x][y];
    }
}



活动打卡代码 AcWing 900. 整数划分

dongwa_zzuli
8个月前
/**
 * 整数划分问题,
 * dp[i][j] 表示总和为i恰好是j个数的和的方案数,
 * 状态转移:若 dp[i][j] 中的方案最小值是1,那么dp[i][j] = dp[i-1][j-1] 减去1这个最小值后,总和变成i-1,恰好是j-1个数的和,
 * 若dp[i][j] 中的最小值不是1,那么也就是j个数都是大于1的,那么每个数都减去1的话,dp[i][j] = d[i-j][j] 就变成总和为i-j,恰好是j个数的和了
 */
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[][] dp = new int[n + 1][n + 1];
        int mod = (int) 1e9 + 7;
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - j][j]) % mod;
            }
        }
        int ans = 0;
        for (int i = 0; i <= n; i++) {
            ans = (ans + dp[n][i]) % mod;
        }
        System.out.println(ans);
        scanner.close();
    }
}




dongwa_zzuli
8个月前
import java.util.Scanner;

/**
 * 最长上升子序列
 * 
 * @author dongwa
 *
 */
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] a = new int[n + 1];
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++)
            a[i] = scanner.nextInt();

        for (int i = 1; i <= n; i++) {
            dp[i] = 1;
            for (int j = 1; j < i; j++)
                if (a[i] > a[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);

        }
        int ans = 0;
        for (int i : dp)
            ans = Math.max(ans, i);

        System.out.println(ans);
        scanner.close();
    }

}