牛客巅峰赛钻石组第8场AB题题解

一题都没做出来。。。

牛牛选物

链接：https://ac.nowcoder.com/acm/contest/9887/A
牛牛有现在有n个物品，每个物品有一个体积v[i]和重量g[i],他想选择其中总体积恰好为V的若干个物品，想使这若干个物品的总重量最大，他想知道最大总重量为多少。（如果不存在合法方案，返回-1）

解题思路：dfs、位运算；由于V最大为1e9，所以不能用dp

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回总体积为V若干物品的最大总重量，如果g存在选择若干物品总体积为V的情况，返回-1
     * @param v int整型一维数组 
     * @param g int整型一维数组 
     * @param V int整型 
     * @return int整型
     */
    public int Maximumweight (int[] v, int[] g, int V){
        int[] res = {-1};
        dfs(v, g, V, 0, 0, 0, res);
        return res[0];
    }
    private void dfs(int[] v, int[] g, int V, int index, int currV, int currG, int[] res){
        if(currV == V){
            res[0] = Math.max(res[0], currG);
            return;
        }
        if(currV > V){return;}
        for(int i = index; i < v.length; ++i){
            dfs(v, g, V, i + 1, currV, currG, res);
            dfs(v, g, V, i + 1, currV + v[i], currG + g[i], res);
        }
    }

    // 0-1背包不行，因为V很大，dp数组内存不足。
    /*public int Maximumweight2 (int[] v, int[] g, int V) {
        int len = Math.min(v.length, g.length);
        int[] dp = new int[V + 1];
        for(int i = 1; i <= V; ++i){
            dp[i] = -1;
        }
        for(int i = 0; i < len; ++i){
            for(int k = V; k >= v[i]; --k){
                if(dp[k - v[i]] != -1){
                    dp[k] = Math.max(dp[k], dp[k - v[i]] + g[i]);
                }
            }
        }
        return dp[V];
    }*/
}

牛牛字符串最长相同前后缀

链接：https://ac.nowcoder.com/acm/contest/9887/B
牛牛拿到了一个字符串。他想知道除去字符串本身以外，这个字符串最大的公共前后缀的长度是多少？
例如，对于字符串ABABA而言，“ABA”即是它的前缀，也是它的后缀，且是最长的公共前后缀，因此最大的长度是3。
牛牛无法解决该问题，所以他只好向你求助，给定一个只包含大写字母的字符串s，返回除去字符串本身以外公共前后缀最大长度，如果没有任何一个公共前后缀满足要求，返回-1即可。

解题思路：KMP算法、双指针。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 给定一个字符串s，返回具有相同前缀后缀的子串的第二大长度，反之，返回-1即可。
     * @param s string字符串 代表题意中的字符串s
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        int len = s.length();
        if(len == 1){return 1;}
        int[] next = new int[len];
        next[0] = -1;
        int k = -1;
        for(int i = 1; i < len; ++i){
            while(k != -1 && s.charAt(i) != s.charAt(k + 1)){k = next[k];}
            if(s.charAt(i) == s.charAt(k + 1)){
                ++k;
            }
            next[i] = k;
        }
        return next[len - 1] + 1 == 0 ? -1: next[len - 1] + 1;
    }
}