快手校招真题四

最少数量货物装箱问题

题目描述
有重量分别为3，5，7公斤的三种货物，和一个载重量为X公斤的箱子（不考虑体积等其它因素，只计算重量）
需要向箱子内装满X公斤的货物，要求使用的货物个数尽可能少（三种货物数量无限）

输入描述:
输入箱子载重量X(1 <= X <= 10000)，一个整数。
输出描述:
如果无法装满，输出 -1。
如果可以装满，输出使用货物的总个数。

4

-1

import java.util.*;

public class Main {

    // 完全背包问题，只是要求必须装满

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        if (x < 8){
            if(x == 3 || x == 5 || x == 7){
                System.out.println(1);
            }else if (x == 6){
                System.out.println(2);
            }else{
                System.out.println(-1);
            }
        }else {
            // 使用贪心法
            int[] dp = new int[x + 1];
            // 求最小 先赋值最大
            for (int i = 0; i <= x; i++) {
                dp[i] = x + 1;
            }
            dp[3] = 1;
            dp[5] = 1;
            dp[7] = 1;
            dp[6] = 2;
            for (int i = 8; i < x + 1; i++) {
                dp[i] = Math.min(dp[i - 3], Math.min(dp[i - 5], dp[i - 7]))+1;
            }
            System.out.println(dp[x]);
        }
    }
}

回文子串的个数

题目描述
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
("回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。)
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
可用C++,Java,C#实现相关代码逻辑
输入描述:
输入一个字符串S 例如“aabcb”(1 <= |S| <= 50), |S|表示字符串S的长度。
输出描述:
符合条件的字符串有"a","a","aa","b","c","b","bcb"

所以答案:7

import java.util.*;

public class Main {

    // 完全字符串dp问题，

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();
        boolean[][] dp = new boolean[line.length()][line.length()];
        int count = line.length();
        for (int i=0;i<line.length();i++){
            dp[i][i] = true;
        }
        // 这里一定要注意这里要逆序，否则，dp[i][j] = dp[i+1][j-1];，dp[i+1][] 还没计算
        for (int i=line.length()-2;i>=0;i--){
            for (int j=i+1;j<line.length();j++){
                if (j - i <=1 && line.charAt(i) == line.charAt(j)){
                    dp[i][j] = true;
                }else if (line.charAt(i) == line.charAt(j)){
                    dp[i][j] = dp[i+1][j-1];
                }
                if (dp[i][j]){
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

字符串压缩

对字符串进行RLE压缩，将相邻的相同字符，用计数值和字符值来代替。例如：aaabccccccddeee，则可用3a1b6c2d3e来代替。

输入描述:
输入为a-z,A-Z的字符串，且字符串不为空，如aaabccccccddeee
输出描述:
压缩后的字符串，如3a1b6c2d3e

import java.util.*;

public class Main {

    // 完全字符串dp问题，

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 字符串压缩，采用，顺序遍历的思路
        String line = in.nextLine();
        char[] lineChar = line.toCharArray();
        int left = 0;
        char pre = line.charAt(0);
        StringBuilder res = new StringBuilder();
        for(int i=1;i<lineChar.length;i++){
            if (lineChar[i] != pre){
                res.append(i-left);
                res.append(pre);
                pre = lineChar[i];
                left = i;
            }
        }
        res.append(lineChar.length-left);
        res.append(pre);
        System.out.println(res.toString());
    }
}

解析加减法运算

解析加减法运算
如：
输入字符串："1+2+3" 输出："6"
输入字符串："1+2-3" 输出："0"
输入字符串："-1+2+3" 输出："4"
输入字符串："1" 输出："1"
输入字符串："-1" 输出："-1"

已知条件：输入的运算都是整数运算，且只有加减运算
要求：输出为String类型，不能使用内建的eval()函数

输入描述:
输入字符串："1+2+3"

输出描述:
输出："6"

import java.util.*;

public class Main {

    // 解析加减法，转换为只有加法，减法转为负数即可

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();
        int sum = 0;
        int i = 0;
        while (i < line.length()){
            int num = 0;int flag = 1;
            if (line.charAt(i) == '-' || line.charAt(i) == '+'){
                if(line.charAt(i) == '-')
                flag = -1;
                i++;
            }
            while (i < line.length() && line.charAt(i) >= '0' && line.charAt(i) <= '9'){
                num = num * 10 + (line.charAt(i) - '0');
                i++;
            }
            sum += flag * num;
        }
        System.out.println(sum);
    }
}

求连续子数组的最大和

题目描述
一个非空整数数组，选择其中的两个位置，使得两个位置之间的数和最大。
如果最大的和为正数，则输出这个数；如果最大的和为负数或0，则输出0
输入描述:
3,-5,7,-2,8
输出描述:
13

import java.util.*;

public class Main {

    // dp 连续子数组最大和

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();
        String[] numStrs = line.split(",");
        int[] nums = new int[numStrs.length];
        for (int i=0;i<numStrs.length;i++){
            nums[i] = Integer.parseInt(numStrs[i]);
        }
        int curMax = 0;
        int max = Integer.MIN_VALUE;
        for (int x:nums){
            if (curMax <= 0){
                curMax = x;
            }else {
                curMax += x;
            }
            max = Math.max(max,curMax);
        }
        if (max <= 0){
            System.out.println(0);
        }else {
            System.out.println(max);
        }
    }
}