首页 > 携程2021-4-1算法笔试分享【含全a代码】
头像
奋斗路上的打工人
编辑于 2021-04-05 20:02
+ 关注

携程2021-4-1算法笔试分享【含全a代码】

第一题:
1.找出数组中连续子数组的和等于n的字数组的数量(双指针)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        while (sc.hasNextLine()){

            //输入
            String[] split = s.split(",");
            int[] arr = new int[split.length];
            for (int i = 0; i < split.length; i++) {
                arr[i] = Integer.parseInt(split[i]);
            }
            String s1 = sc.nextLine();
            int Len = Integer.parseInt(s1);

            //2.判断极端条件
            int left = 0, right = 0;
            if(Len == 0 || arr.length == 0) {
                System.out.println(0);
                continue;
            }else if( arr.length == 1 && arr[0] == Len){
                System.out.println(1);
                continue;
            }

            //3.遍历
            int tmpSum = 0;
            int res = 0;
            while (right<arr.length){
                tmpSum = 0;
                for(int i=left; i<=right; i++){
                    tmpSum += arr[i];
                }
                if(tmpSum == Len){
                    res++;
                    left++;
                }else if(tmpSum > Len){
                    left++;
                }else {
                    right++;
                }
                if(left>right) right=left;
            }
            System.out.println(res);
        }

    }
}


第2题:
有n个果盘,每个果盘里有多个苹果和梨,先要求尽可能多的选择果盘,使得苹果数和梨的数量不多于m和n个(动态规划)
输入:
# a,ppap,ap,aaappa,p 2 3
其中a代表苹果,p代表梨,果盘用逗号隔开,最后是m和n 
思路:建立一个二维数组dp[m+1][n+1]
import java.util.Scanner;

public class Main {
    public static int curANum = 0;
    public static int curPNum = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()){
            String s = sc.nextLine();
            String[] strings = s.split(" ");
            String[] fruits = strings[0].split(",");
            int aNum = Integer.parseInt(strings[1]);
            int pNum = Integer.parseInt(strings[2]);
            int[][] dp = new int[aNum+1][pNum+1];

            for (String fruit : fruits) {
                countNum(fruit);
                for(int i=aNum; i>=curANum; i--){
                    for (int j=pNum; j>=curPNum; j--){
                        dp[i][j] = Math.max(dp[i][j],dp[i-curANum][j-curPNum]+1);

                    }
                }
            }
            System.out.println(dp[aNum][pNum]);

        }
    }

    public static void countNum(String str){
        curANum = 0;
        curPNum = 0;
        for (int i = 0; i < str.length(); i++) {
            if(str.charAt(i) == 'a') curANum++;
            else if(str.charAt(i) == 'p') curPNum++;
        }
    }


}




全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐