秋招突击——9/10、9\11——算法练习——携程笔试练习——2024年秋招第一批笔试
文章目录
- 引言
- 笔试准备
- 2024年秋招研发第一批
- 第一题
- 第二题
- 第二次实现
- 第三题
- 第四题
- 第五题
- 参考实现
- 总结
引言
- 准备全力冲携程，好好做算法，去线下面试！
- 今天就好好做做携程往年的笔试！
笔试准备
2024年秋招研发第一批
第一题
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static boolean isPrime(int n) {
for (int i = 2; i <= Math.sqrt(n); i ++) {
if (n % i == 0) return false;
}
return true;
}
static int res;
static boolean[] visited;
public static void dfs(int n, int idx, List<Integer> temp) {
if (idx == n) {
// 已经到达了终点，直接添加对应的元素
res ++;
// System.out.println(temp.toString());
return;
}
for (int i = 1; i <= n; i ++) {
if (!visited[i]) {
// 没有访问过
if (temp.isEmpty() || !isPrime(i + temp.get(temp.size() - 1))) {
visited[i] = true;
temp.add(i);
dfs(n, idx + 1, temp);
temp.remove(temp.size() - 1);
visited[i] = false;
}
}
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int n = in.nextInt();
visited = new boolean[n + 1];
dfs(n, 0, new ArrayList<Integer>());
System.out.println(res);
}
}
}
总结
- 明明是一个dfs，还是比较简单的dfs，但是有很多细节没注意到位，很难受！
第二题
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static boolean judge(int[] a,int[] b,int[] c) {
// 判断是否为对应符合条件的三个点
if((a[0] == b[0] && a[1] == c[1]) || (a[0] ==c[0] && a[1] == b[1])) return true;
if((b[0] == a[0] && b[1] == c[1]) || (b[0] ==c[0] && b[1] == a[1])) return true;
if((c[0] == b[0] && c[1] == a[1]) || (c[0] ==a[0] && c[1] == b[1])) return true;
return false;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int m = in.nextInt();
int n = in.nextInt();
char[][] chars = new char[m][n];
List<int[]> listY = new ArrayList<>();
List<int[]> listO = new ArrayList<>();
List<int[]> listU = new ArrayList<>();
for(int i = 0;i < m;i ++){
String str = in.next();
chars[i] = str.toCharArray();
for(int j = 0;j < chars[i].length;j ++){
if(chars[i][j] == 'y') listY.add(new int[]{i,j});
if(chars[i][j] == 'o') listO.add(new int[]{i,j});
if(chars[i][j] == 'u') listU.add(new int[]{i,j});
}
}
// 开始具体的逻辑处理
int count = 0;
for(int[] pointY : listY){
for(int[] pointO:listO){
for(int[] pointU:listU){
if(judge(pointY,pointO,pointU)) {
count ++;
}
}
}
}
System.out.println(count );
}
}
}
总结
- 仅仅通过三组，这里直接暴力，可以使用dp做一下，下次再试试看，因为每一个中心点，都要记录一下之前有多少u、o和y，明天再做
第二次实现
- 计算每一行或者每一列的前n项的y、o、u的累加和，然后在计算乘积就行了！
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static boolean judge(int[] a, int[] b, int[] c) {
// 判断是否为对应符合条件的三个点
if ((a[0] == b[0] && a[1] == c[1]) || (a[0] == c[0] &&
a[1] == b[1])) return true;
if ((b[0] == a[0] && b[1] == c[1]) || (b[0] == c[0] &&
b[1] == a[1])) return true;
if ((c[0] == b[0] && c[1] == a[1]) || (c[0] == a[0] &&
c[1] == b[1])) return true;
return false;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int m = in.nextInt();
int n = in.nextInt();
char[][] chars = new char[m][n];
int[][] rowCount = new int[m][3]; // 0表示y，1表示o，2表示u
int[][] colCount = new int[n][3]; // 0表示y，1表示o，2表示u
// 这个是遍历的标签
for (int i = 0; i < m; i ++) {
String str = in.next();
chars[i] = str.toCharArray();
for (int j = 0; j < chars[i].length; j ++) {
if (chars[i][j] == 'y') {
rowCount[i][0] ++;
colCount[j][0] ++;
}
if (chars[i][j] == 'o') {
rowCount[i][1] ++;
colCount[j][1] ++;
}
if (chars[i][j] == 'u') {
rowCount[i][2] ++;
colCount[j][2] ++;
}
}
}
// 开始具体的逻辑处理
long count = 0;
for (int i = 0; i < m; i ++) {
for (int j = 0; j < n; j ++) {
if (chars[i][j] == 'y') {
count = count + rowCount[i][1] * colCount[j][2] + rowCount[i][2] *
colCount[j][1] ;
}
if (chars[i][j] == 'o') {
count = count + rowCount[i][0] * colCount[j][2] + rowCount[i][2] *
colCount[j][0] ;
}
if (chars[i][j] == 'u') {
count = count + rowCount[i][1] * colCount[j][0] + rowCount[i][0] *
colCount[j][1] ;
}
}
}
System.out.println(count );
}
}
}
第三题
- 编写一个SQL查询，返回每个商品的销售总量，先按照商品类别升序排序，再按销售总量降序排列，同时包括商品名称和销售总量。此外，还需要在结果中包含每个商品在其所属类别内的排名，排名相同的商品可以按照 product_id 升序排序。
初始版本
- 这个题目一开始只能写成下面那个初始化的版本，并不知道怎么在同一类别中再进行排名。
SELECT products.name as product_name, sum(quantity) as total_sales , products.category as category_rank
FROM orders
join products on products.product_id = orders.product_id
group by products.name , products.category ,orders.product_id;
最终版本
SELECT
products.name as product_name,
SUM(orders.quantity) AS total_sales,
RANK() OVER (
PARTITION BY
products.category
ORDER BY
SUM(orders.quantity) DESC,
products.product_id ASC
) AS category_rank
FROM
products
JOIN orders ON products.product_id = orders.product_id
GROUP BY
products.name,
products.category,
products.product_id
ORDER BY
products.category ASC,
total_sales DESC,
products.product_id ASC;
复习的知识
- Rank关键字
- 用来给结果集中的每一行分配一个排名，通过over来确定排名如何运用。
- 需要使用order by来指定排名顺序
- 通过partion by将数据进行分组，然后按组内的数据进行排名。上述要求中，是按照同类别的销售总量进行的排序，所以需要增加一个partion by关键字
rank() over (
partition by products.category
order by sum(quantity) DESC , products.product_id ASC) as category_rank
第四题
个人实现
- 无限次加一和减一操作，总量sum是不变的，直接计算一下平均值，看看能不能范围内，借此判定是否可以操作。然后计算所有小于左边界差值的累加和以及所有大于右边界的差值的累加和，然后选一个最大值就行了！
- 这个代码写的很快，但是剩下的样例不知道怎么过了，感觉没啥问题！
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int T = in.nextInt();
while (T-- > 0) { // 注意 while 处理多个 case
int n = in.nextInt();
int l = in.nextInt();
int r = in.nextInt();
int[] nums = new int[n];
long sum = 0L;
for(int i = 0;i < n;i ++) {
nums[i] = in.nextInt();
sum += nums[i];
}
long avg = (long)sum / n;
if(avg > r || avg < l) System.out.println(-1);
else{
long subCount = 0;
long addCount = 0;
for(int x:nums){
if(x < l) addCount += (l - x);
if(x > r) subCount += (x - r);
}
System.out.println(Math.max(addCount , subCount));
}
// 现在进一步进行判定
}
}
}
- 忽然间想到，我是使用long保存的平均值，会报错，具体如下
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int T = in.nextInt();
while (T-- > 0) { // 注意 while 处理多个 case
int n = in.nextInt();
int l = in.nextInt();
int r = in.nextInt();
int[] nums = new int[n];
long sum = 0L;
for(int i = 0;i < n;i ++) {
nums[i] = in.nextInt();
sum += nums[i];
}
double avg = sum / (double)n;
if(avg > r || avg < l) System.out.println(-1);
else{
long subCount = 0;
long addCount = 0;
for(int x:nums){
if(x < l) addCount += (l - x);
if(x > r) subCount += (x - r);
}
System.out.println(Math.max(addCount , subCount));
}
// 现在进一步进行判定
}
}
}
第五题
个人实现
- 这个先简单点，直接用滑动窗口去做，然后统计一下每一次滑动窗口是否符合条件！但是问题在于，如何写出一个统计函数，计算每一个子串是不是好串！怎么写？需要记录一下状态，也就是每一个序列中，到当前序列而言，对应的零和一的数量，然后在进行计算！
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNext()) { // 注意 while 处理多个 case
String str = in.next();
char chars[] = str.toCharArray();
// 使用滑动窗口进行遍历
int count0 = 0;
int count1 = 0;
int res = 0;
int n = chars.length;
for (int l = 0, r = 0; r < n; r++) {
if (chars[r] == '0') count0 ++;
if (chars[r] == '1') count1 ++;
// 移动l，保证l到r是一个好子串
while (l <= r && count0 < count1) {
if (chars[l] == '0') count0 --;
else count1 --;
l ++;
}
if (count0 > count1)
res ++;
}
System.out.println(res);
}
}
}
总结
- 写的快，但是通过的样例也少了，如果按照正常的考试时间安排，能够通过三个题，差不多可以进面。第四题，应该还有其他的方法，这里直接看解析！
再次尝试，使用状态记录
- 效果属实一般，全部超时！
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNext()) { // 注意 while 处理多个 case
String str = in.next();
char chars[] = str.toCharArray();
// 使用滑动窗口进行遍历
int count0 = 0;
int count1 = 0;
int res = 0;
int n = chars.length;
int[][][] dp = new
int[n][n][3]; // 第一个数字表示1合法序列，0未非法序列，后续两个分别是0和1的数量
for (int l = 0; l < n; l++) {
for (int r = l ; r < n; r ++) {
if (l == r) {
if (chars[l] == '0') {
dp[l][r][0] = 1;
dp[l][r][1] = 1;
dp[l][r][2] = 0;
res ++;
} else {
dp[l][r][0] = 0;
dp[l][r][1] = 0;
dp[l][r][2] = 1;
}
}
// 两者不相等，直接进行判断
else {
// 更新一下0和1的数量
if (chars[r] == '0') {
dp[l][r][1] = dp[l][r - 1][1] + 1;
} else {
dp[l][r][2] = dp[l][r - 1][2] + 1;
}
if (dp[l][r - 1][0] == 0) {
// 上一个状态的子串是非法的
dp[l][r][0] = 0;
} else {
if (dp[l][r][1] > dp[l][r][2]) {
// 0的数量大于1，那么直接更新
dp[l][r][0] = 1;
res ++;
} else {
dp[l][r][0] = 0;
}
}
}
}
}
System.out.println(res);
}
}
}
参考实现
import java.util.*;
class Main {
static final int MAXN = (int) (1e5 + 10);
static char[] chs = new char[MAXN];
static long res = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
int n = s.length();
for(int i = 1; i <= n; i++) {
chs[i] = s.charAt(i - 1);
}
int cnt1 = 0, cnt0 = 0;
for(int l = 1, r = 1; r <= n; r++) {
if(chs[r] == '0')
cnt0++;
else
cnt1++;
while(cnt1 >= cnt0 && l <= r) {
if(chs[l] == '0')
cnt0--;
else
cnt1--;
l++;
}
res += (r - l + 1);
res -= 2L * cnt1;
}
System.out.println(res);
}
}
总结
- 基本思路都是滑动窗口的，但是最后那里去除不合法子串那里，有点问题，感觉有点疑惑，然后计算所有合法子串那里确实世界计算r-l +1 的结果，因为开头变了，子串的状态就变了！
总结
- 提前练了一下携程的笔试，感觉还行，基本上能过个三四题！继续加油！冲！