携程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++;
}
}
}