前言:这周六杭电的师傅们倾心办的一场算法比赛,题目是2019年南大机试,题目对于我来说有点难,但学到很多知识,感谢师傅的们对这次比赛的搭建。
题目链接:http://acm.hdu.edu.cn/diy/contest_show.php?cid=36342。
下面是对三道题的个人总结

第一题

Description

A number is called a stepping number if all adjacent digits have an absolute difference of 1, e.g. ‘321’ is a Stepping Number while ‘421’ is not. Given two integers n and m, count the number of all the stepping numbers in range [N,M]. Note that the stepping numbers should have adjacent digits, which means that they consist of at least 2 digits.

思路

时间限制的比较紧,这道题目直接枚举是不能通过的,需要更高效的解决思路,比枚举更高效些的算法可以想到搜索,如BFS、DFS。那么针对这道题目,关键点如何把它抽象成搜索算法可以解决的问题。

对于stepping number,可以总结规则如下。

  • 数字第一位为1-9的任何一个数字
  • 数字的后一位为前一位的加一或减一

用数学形式表示如下,设数字的第i位为$n_i$:

  • $n1 = {1 … 9}$

  • $n_{i+1} = {n_i + 1, n_i – 1}$(当9时只有$n_i – 1$,当0时只有$n_i +1$)

根据这个规律可以以$1…9$为初始状态,进行搜索。

代码

package sousuo;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * 南京大学2019考研计算机机试 - 题目1
 * 题目:stepping number,:例如123、321、8987656,等一类的数字。
 * 给定区间 [N, M],算出区间内stepping number的数量
 *
 * 解决思路:使用BFS搜索,起点是[1, 2, 3, 4, 5, 6, 7, 8, 9]。
 */
public class HDU_KY1001 {
    static Scanner sc = new Scanner(System.in);

    static int start[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    public static void main(String[] args) {
        int T = sc.nextInt();
        int m, n;
        for(int i=0;i<T;i++){
            n = sc.nextInt();
            m = sc.nextInt();
            System.out.println(bfs(n, m));
        }
    }

    static int bfs(int n, int m){
        int ans = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i=0;i<start.length;i++){
            queue.add(start[i]);
        }
        while (!queue.isEmpty()){
            int cur = queue.remove();
            if(cur <= m/10){
                if(cur%10!=9) {
                    int curAdd = cur * 10 + (cur % 10) + 1;
                    if (curAdd <= m) {
                        if(curAdd >= n) ans++;
                        queue.add(curAdd);
                    }
                }
                if(cur%10!=0){
                    int curSub = cur * 10 + (cur%10)-1;
                    if(curSub <= m){
                        if(curSub >= n) ans++;
                        queue.add(curSub);
                    }
                }
            }
        }
        return ans;
    }
}

第二题

Description

There is a binary tree with N nodes indexing from 0 to N-1, where 0 is the root. Each edge of the tree has an integer weight W. At first all the nodes could be reached from the root, through a sequence of edges.
An integer threshold X (X >= 0) is used to close the edge, which means that all the edges whose weights are less than X will be closed.
Given the tree and an integer Y, please find the minimum threshold X so that the number of nodes reachable from the root (including the root itself) is no more than Y.

思路

首先第一步,需要遍历整个图计算出每个节点到root节点通路上最小的边长度;那么正常思路是这样:

for(int i=1;i<n;i++){
    dfs(i);
}

即遍历除root节点的所有节点到root节点的通路,这就需要进行n-1dfs搜索,dfs过程中记录路径,结束后得到路径中最短的边边长。

与第一题一样,题目对时间限制比较紧,这样无法通过,需要更高效的解决办法 ——————- 一次dfs过程获得答案。

如下图所示,通过维前一个节点以及前一个节点在通路中最短边长,进行遍历。

上图表格中的过程可以用算法描述如下:

void dfs(Node curNode, Node preNode, int distance){
    minArray[curNode] = distance;
    foreach(Node p : curNode.adj){
        if(p != preNode){
            dfs(p, curNode, min(distance, p.length));
        }
    }
}

第二行将当前所得最短路径记录入数组;第三行后对当前节点的邻居节点进行遍历,由于二叉树的特性,这里没有必要维护整张图的访问记录数组,只需维护上一个访问过的节点(我描述不出来,但大家可以想一想为什么)。

代码

import java.util.Arrays;
import java.util.Scanner;

/**
 * 南京大学2019考研计算机机试 - 题目2
 * 给定一个二叉树,一个阈值x,小于阈值的边关闭。
 * 求给定一个y,计算出最小的x满足条件:从根节点最多可以到达y个节点。
 *
 * 思路:计算每个节点到根节点通路上的最短边。(可以用DFS记录路径,也可以用BFS记录路径)
 * 把结果排序。输出 mmin[n-y] + 1
 */

class Node {
    public int n;
    public int len;
    public Node nxt;
    public Node() {
        n = -1;
    }
}

public class Main {
    static Scanner sc = new Scanner(System.in);

    static Node header[];
    static int mmin[];

    static void add_edge(int v, int u, int w){
        Node p = new Node();
        p.nxt = header[v];
        p.n = u;
        p.len = w;
        header[v] = p;
    }

    static void dfs(int cur, int pre, int distance){
        mmin[cur] = distance;
        for(Node ii=header[cur]; ii != null; ii = ii.nxt){
            if(ii.n != pre){
                dfs(ii.n, cur, Math.min(distance, ii.len));
            }
        }
    }

    public static void main(String[] args) {
        int T = sc.nextInt();
        int n,y,u,v,w;
        while(T-- != 0){
            n = sc.nextInt();
            y = sc.nextInt();

            header = new Node[n+1];
            mmin = new int[n+1];
            Arrays.fill(mmin, Integer.MAX_VALUE);

            for(int i=0;i<n-1;i++){
                u = sc.nextInt();
                v = sc.nextInt();
                w = sc.nextInt();
                add_edge(v, u, w);
                add_edge(u, v, w);
            }

            int ttt = 0;
            for(Node ii=header[1];ii != null; ii = ii.nxt){
                if(ii.n == 0) {
                    ttt = ii.len;
                    break;
                }
            }
            dfs(0, -1, Integer.MAX_VALUE);
            Arrays.sort(mmin, 1, n);
            if(n==y){
                System.out.println(0);
            }else{
                System.out.println(mmin[n-y]+1);
            }
        }
    }
}

第三题

Description

Given a string S and a string T, count the number of distinct subsequences of S which is equal to T.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "nus" is a subsequence of "njucs" while "nsu" is not).

思路

首先这个是一个简单的动态规划简单应用,把S称为母串,把T称为子串,dp数组意义如下:

dp[i][j]表示母串S[0:i]含有子序列子串T[0:j] 的个数。首先是初始化,当子串长度为0时,无论母串长度为多少都为1,即对于任意i满足dp[i][0] = 1;当母串长度为0时,无论子串长度为多少都为0,即对于任意j满足dp[0][j]=1;

初始化代码则表现如下:

for(int i=0;i<=strS.length();i++){
    dp[i][0] = 1;
}
for(int j=0;j<=strJ.length();j++){
    dp[0][j] = 0;
}

保持子串长度不改变,进行迭代推导:

S[i]!=T[j]时,问题相对于S[0:i-1], T[0:j]没有改变,相当于只是在原母串的基础上添加了一个无关紧要的字符。

S[i] == T[j]时,问题相对于在S[0:i-1], T[0:j]的基础之上,再添加去除S和T最后一个字符,添加上S[0:i-1],T[0:j-1]

总结推导方程为:

$dp[i][j] = dp[i-1][j] + (S[i]==s[j] \space ? \space dp[i-1][j-1] : 0)$

上述思路用代码实现如下:

int dpFunc(String strs, String strj){
    int[][] dp = new int[strs.length()+1][strj.length()+1];
    for(int i=0;i<=strs.length();i++){
        dp[i][0] = 1;
    }
    for(int j=1;j<=strj.length();j++){
        for(int i=1;i<=strs.length();i++){
            dp[i][j] = dp[i-1][j] +
                (strs.charAt(i-1) == strj.charAt(j-1) ? dp[i-1][j-1] : 0);
        }
    }
    return dp[strs.length()][strj.length()];
}

但是同理,题目对时间限制比较严格,上述复杂度为$O(n^2)$的代码是无法通过的,要求进行更进一步的优化,同时这一题的大数据对内存要求也是很严格的,$O(n*m)$的内存也是不行的。

1、可以通过滚动数组对内存进行优化。

没有了解过滚动数组,滚动数组介绍如下,为了方便理解,先从一维滚动数组开始讲起:

int fib(int n){
    int dp = new int[n];
    dp[0] = 1;
    dp[1] = 1;
    for(int i=2;i<n;i++)
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n-1];
}

注意到上述过程仅仅占用了计算对象的前两个数组,为了节省空间,优化如下:

int fib(int n){
    int dp = new int[3];
    dp[0] = 1;
    dp[1] = 1;
    for(int i=2;i<n;i++){
        dp[0] = dp[1];
        dp[1] = dp[2];
        dp[2] = dp[0] + dp[1];
    }
    return dp[2];
}

这样仅仅用了大小为3的数组,可以注意到的是,这想到于将上一步计算结果整体向前平移了一位,上述还可以写作:

int fib(int n){
    int dp = new int[3];
    dp[0] = 1;
    dp[1] = 1;
    for(int i=2;i<n;i++){
        dp[i%3] = dp[(i-1)%3] + dp[(i-2)%3];
    }
    return dp[(n-1)%3];
}

这就是数组滚动。

在动态规划中往往是二维数组,例如下图是一个:

假设状态转移式子为:dp[i][j] = dp[i][j-1] +dp[i-1][j]时,可以得到如下图:

可以对i维或是j维度进行滚动数组,当然在这道题目中,滚动数组选择i维。

代码

import java.util.Scanner;

/**
 * 南京大学2019考研计算机机试 - 题目3
 * 题目:distinct 子序列
 *
 * 思路:动态规划 + 滚动数组
 */
public class Main {
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int T = sc.nextInt();
        while (T-- != 0){
            String strx = sc.nextLine();
            String stry = sc.nextLine();
            int ans = dpFunc(strx, stry);
            System.out.println(ans);
        }
    }

    static int dpFunc(String strs, String strj){
        int[][] dp = new int[2][strj.length()+1];
        for(int i=0;i<2;i++){
            dp[i][0] = 1;
        }
        for(int i=1;i<=strs.length();i++){
            for(int j=1;j<=strj.length();j++){
                dp[i%2][j] = dp[(i-1)%2][j] +
                        (strs.charAt(i-1) == strj.charAt(j-1) ? dp[(i-1)%2][j-1] : 0);
            }
        }
        return dp[strs.length()%2][strj.length()];
    }
}