2024/8/18 字节跳动25秋招第一场笔试后端算法

时间是2024/8/18 晚上7点到9点两个半小时

总共4道算法题

第一题

定义一个数组为特殊数组：数组大小至少为3 只有两种数字组成且其中一种数字恰好出现一次

例如[1,1,4][1,4,1]是特殊数组

例如[1,4][5,1,4][1,1,1]不是特殊数组

给出一个长度为n的数组问有多少个子数组是特殊数组

当时想用滑动窗口解超时只过了20%

package Dduo;
import java.math.BigInteger;
import java.util.*;


public class Main {

    static Scanner sc = new Scanner(System.in);
    static long mod = (long) (1e9 + 7);
    static int cnt = 0;

    public static void main(String[] args) {
        int t = 1;
//        t=sc.nextInt();
        while (t-- > 0) {
            solve();
        }
        sc.close();
        return;
    }

    private static void solve() {
    	
    	int n=sc.nextInt();
    	int arr[]=new int[n];
    	for(int i=0;i<n;i++)arr[i]=sc.nextInt();
    	
    	System.out.print(count(arr));
         

    }
    
    public static int count(int[] a) {
        int n = a.length;
        int specialCount = 0;

        for (int start = 0; start < n; start++) {
            Map<Integer, Integer> freq = new HashMap<>();
            for (int end = start; end < n; end++) {
                int num = a[end];
                freq.put(num, freq.getOrDefault(num, 0) + 1);
                
                if (freq.size() == 2) {
                    int[] counts = new int[2];
                    int index = 0;
                    for (int count : freq.values()) {
                        counts[index++] = count;
                    }
                    if (counts[0] == 1 || counts[1] == 1) {
                        if (end - start + 1 >= 3) {
                            specialCount++;
                        }
                    }
                }
            }
        }

        return specialCount;
    }
    

}

第二题

现在有n个事件

每个事件可以在两种选项中选择一种

1 消耗x颗宝石获得y金币

2 获得z宝石

不过宝石不能大于m 大于m的部分会消失

在n个事件结束后每拥有一颗宝石都可以换算成1个金币

一开始没有宝石想知道在最优策略下可以获得多少金币

线性解的过了15%

想想应该用动态规划吧

package Dduo;
import java.math.BigInteger;
import java.util.*;


public class Main {

    static Scanner sc = new Scanner(System.in);
    static long mod = (long) (1e9 + 7);
    static int cnt = 0;

    public static void main(String[] args) {
        int t = 1;
//        t=sc.nextInt();
        while (t-- > 0) {
            solve();
        }
        sc.close();
        return;
    }

    private static void solve() {
    	
    	int n=sc.nextInt();//n行
    	int m=sc.nextInt();//上限
    	
    	int arr[][]=new int[n][3];
    	
    	for(int i=0;i<n;i++) {
    		arr[i][0]=sc.nextInt();//消耗宝石
    		arr[i][1]=sc.nextInt();//获取金币
    		arr[i][2]=sc.nextInt();//直接获取宝石
    	}
    	
    	int cntBS=arr[0][2];
    	
    	int cntMoney=0;
    	
    	for(int i=1;i<n;i++) {
    		if(cntBS>=arr[i][0]&&arr[i][1]>arr[i][0]) {
    			cntMoney+=arr[i][1];
    			cntBS-=arr[i][0];
    		}else {
    			cntBS+=arr[i][2];
    			if(cntBS>m)cntBS=m;
    		}
    	}
    	
    	cntMoney+=cntBS;
    	
    	System.out.print(cntMoney);
    	   
    }
    
}

第三题

有一条长度为n*10e1000的彩带彩带的每一个位置有一个价值 ai

小红的彩带是由一条长度为n的彩带一直循环得到的 i>n时 ai=ai-n

小红每次会从左往后或从右往左剪一段长度为x的彩带想知道每次剪下来的彩带的价值和是多少

输入

6 3

1 1 4 5 1 4

L 2

L 3

R 12

输出

当时感觉是队列题

但是因为被第一题和第二题卡太长时间了

没时间写

赛后复盘

也请教了学校的acmer

感觉难度赶得上牛客周赛的d和e

import java.util.Scanner;

public class Main {
    static final int N = 200005;
    static long[] a = new long[N];
    static long[] pre = new long[N];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int t = 1;  
        while (t-- > 0) {
            long n = scanner.nextLong();
            long q = scanner.nextLong();

            for (int i = 1; i <= n; ++i) {
                a[i] = scanner.nextLong();
                pre[i] = pre[i - 1] + a[i];
            }

            long l = 0;
            long r = n + 1;

            for (int i = 0; i < q; ++i) {
                char op = scanner.next().charAt(0);
                long num = scanner.nextLong();
                long res = 0;
                long cnt = num / n;
                res += cnt * pre[n];
                num = num % n;

                if (num == 0) {
                    System.out.println(res);
                    continue;
                }

                if (op == 'L') {
                    if (l + num >= n) {
                        res += pre[n] - pre[(int)l];
                        l = l + num - n;
                        res += pre[(int)l];
                    } else {
                        res += pre[(int)(l + num)] - pre[(int)l];
                        l += num;
                    }
                } else {  // op == 'R'
                    if (num >= r - 1) {
                        res += pre[(int)(r - 1)];
                        r = r - num + n;
                        res += pre[n] - pre[(int)(r - 1)];
                    } else {
                        res += pre[(int)(r - 1)] - pre[(int)(r - num - 1)];
                        r -= num;
                    }
                }
                System.out.println(res);
            }
        }
        scanner.close();
    }
}