字节跳动4.12服务器和客户端笔试（Java实现）

题目描述记不真切就不写了，参加过笔试的应该有印象。

欢迎交流更优解法。

第一题：简单交换

public class ByteDance2020041201 {
    public static void main(String[] args) {
        //简单交换
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int i = 0; i < t; i++) {
            int n = in.nextInt();
            int[] array1 = new int[n];
            int[] array2 = new int[n];
            for (int j = 0; j < n; j++) {
                array1[j] = in.nextInt();
            }
            for (int j = 0; j < n; j++) {
                array2[j] = in.nextInt() - array1[j];
            }
            int index = 0;
            int gap = 0;
            while (index < n) {
                if (array2[index] != 0) {
                    gap = array2[index];
                    break;
                }
                index++;
            }
            while (index < n) {
                if (array2[index] != gap) {
                    gap  = array2[index];
                    break;
                }
                index++;
            }
            if (gap != 0) {
                if (index == n) {
                    System.out.println("YES");
                    break;
                }
                System.out.println("NO");
                break;
            }
            while (index < n) {
                if (array2[index] != gap) {
                    break;
                }
                index++;
            }
            if (index == n) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

第二题：折木棒

思路是，倒序遍历找到一个a[i]>a[i+1]。向上取整的除法直接算出需要折断几次，并且用尽可能平均的数替换当前a[i]。（比如数组中存在19,4，需要19/4=5(向上取整)个位置，就需要折断5-1=4次，19/5=3，可以使用3,4,4,4,4替换19，那么直接用3替换19）尽可能平均是为了让a[i-1]的折木棒次数尽量少。

public class Main {
    //折木棒
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(in.nextInt());
        }
        if (n == 1) {
            System.out.println(0);
            return;
        }
        int count = 0;
        for (int i = n - 2; i >= 0; i--) {
            if (list.get(i) > list.get(i + 1)) {
                int count1 = (int) Math.ceil((double) list.get(i) / list.get(i + 1));
                list.set(i, list.get(i) / count1);
                count += count1 - 1;
            }
        }
        System.out.println(count);
    }
}

第三题：优惠券
对优惠券和商品价格排序，可以直接用指针记录优惠券位置。

据说使用long的res记录结果可以AC。(int过80%)

public class Main {
    //优惠券
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] account = new int[n];
        int[] price = new int[m];
        for (int i = 0; i < n; i++) {
            account[i] = in.nextInt();
        }
        for (int i = 0; i < m; i++) {
            price[i] = in.nextInt();
        }
        Arrays.sort(account);
        Arrays.sort(price);
        int aIndex = 0;
        int pIndex = 0;
        long res = 0;
        while (pIndex < price.length) {
            int currPrice = price[pIndex];
            while (aIndex < account.length - 1) {
                if (account[aIndex + 1] <= currPrice) {
                    aIndex++;
                } else {
                    break;
                }
            }
            if (account[aIndex] <= currPrice) {
                res += currPrice - account[aIndex];
            } else if (aIndex == 0) {
                res += currPrice;
            } else {
                res += currPrice - account[aIndex - 1];
            }
            pIndex++;
        }
        System.out.println(res);
    }
}

第四题：站得高看得远

单调栈记录数组索引。

public class Main {
    //站得高看得远
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int i = 0; i < t; i++) {
            int n = in.nextInt();
            int[] height = new int[n];
            for (int j = 0; j < n; j++) {
                height[j] = in.nextInt();
            }
            int[] res = new int[n];
            Stack<Integer> stack = new Stack<>();
            int[] left = new int[n];
            int[] right = new int[n];
            for (int j = 0; j < n; j++) {
                while (!stack.isEmpty() && height[stack.peek()] <= height[j]) {
                    stack.pop();
                }
                if (stack.isEmpty()) {
                    left[j] = 0;
                } else {
                    left[j] = stack.peek() + 1;
                }
                stack.push(j);
            }
            stack.clear();
            for (int j = n - 1; j >= 0; j--) {
                while (!stack.isEmpty() && height[stack.peek()] <= height[j]) {
                    stack.pop();
                }
                if (stack.isEmpty()) {
                    right[j] = n - 1;
                } else {
                    right[j] = stack.peek() - 1;
                }
                stack.push(j);
            }
            for (int j = 0; j < n; j++) {
                res[j] = right[j] - left[j];
            }
            for (int j = 0; j < n; j++) {
                System.out.print(res[j] + " ");
            }
            System.out.println();
        }
    }
}

#字节跳动##笔试题目#