2.8143AC字节笔试4.12坑点解析

第一题AC

思路过于简单直接给代码，坑点是，不能把b数组也记录下来（不记录时间复杂度为2n，记录则时间复杂度为3n。。。别问我为什么这么优化，因为没其他地方优化。。。）

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    int[] nums = new int[t];
    for (int i = 0; i < t; i++) {
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int j = 0; j < n; j++) {
            a[j] = sc.nextInt();
        }
        boolean res = true;
        boolean chan = false;
        int k = 0;
        int right = 0;
        for (int j = 0; j < n; j++) {
            int b = sc.nextInt();
            if(b == a[j]) continue;
            if(a[j] > b){
                res = false;
                right = n - j - 1;
                break;
            }
            if(a[j] != b){
                k = b - a[j];
                if(chan){
                    res = false;
                    right = n - j - 1;
                    break;
                }else {
                    while (j < n){
                        if(a[j] == b){
                            break;
                        }
                        if(a[j] + k != b){
                            res = false;
                            break;
                        }
                        b = sc.nextInt();
                        j++;
                    }
                    chan = true;
                }
            }
        }
        if(res) nums[i] = 1;
        else nums[i] = 2;
        for (int j = 0; j < right; j++) {
            sc.nextInt();
        }
    }
    sc.close();
    for (int i = 0; i < t; i++) {
        if(nums[i] == 1) System.out.println("YES");
        else if(nums[i] == 2)System.out.println("NO");
    }
}

第二题0.2

也是很暴力的思路，但是还有一些条件没考虑到，不知道大佬有没有优秀的解法

private static int res = 0;
private static ArrayList<Integer> nums = new ArrayList<>();
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    for (int i = 0; i < n; i++) {
        nums.add(sc.nextInt());
    }
    sc.close();
    if(n == 1) System.out.println(0);
    else {
        cut(0);
        System.out.println(res);
    }
}

private static void cut(int i) {
    if(i == nums.size()) return;
    if(i == nums.size() - 1){
        if(nums.get(i) >= nums.get(i - 1)) return;
        cut(i - 1);
    }
    if(nums.get(i) <= nums.get(i + 1)) cut(i + 1);
    else if(i == 0){
        int sum = nums.get(i);
        int right = nums.get(i + 1);
        int curr = sum;
        while (curr > right) curr /= 2;
        nums.remove(0);
        int index = 0;
        while (sum > right){
            sum -= curr;
            nums.add(0, curr);
            res++;
            index++;
        }
        nums.add(0, sum);
        cut(index);
    }else {
        int sum = nums.get(i);
        int right = nums.get(i + 1);
        int left = nums.get(i - 1);
        if (sum < left) cut(i - 1);
        nums.remove(i);
        int index = i;
        while (sum > right * 2) {
            nums.add(i, right);
            res++;
            index++;
            sum -= right;
        }
        if (sum > right + left) {
            nums.add(i, right);
            nums.add(i, sum - right);
            res++;
        }else {
            nums.add(i, left);
            nums.add(i, sum - left);
            res++;
        }
        cut(index + 1);
    }
}

第三题0.9

也是很暴力的思路。。坑点：1.找优惠券的时候用一下二分查找；2.可能存在没有优惠券可用的情况（所有优惠券面额都大于该价格），对了，不要用数组记录第二个数组，那样会多了m的复杂度

private static int[] cuts;
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    cuts = new int[n];
    for (int i = 0; i < n; i++) {
        cuts[i] = sc.nextInt();
    }
    Arrays.sort(cuts);
    int money = 0;
    long res = 0;
    for (int i = 0; i < m; i++) {
        money = sc.nextInt();
        int left = find(money);
        while (left >= 0 && cuts[left] > money){
            left--;
        }
        if(left >= 0) res = res + (long) money - (long) cuts[left];
        else res = res + (long) money;
    }
    sc.close();
    System.out.println(res);
}
public static int find(int mon){
    int left = 0, right = cuts.length - 1;
    int mid = (left + right) / 2;
    while (left < right){
        if(cuts[mid] < mon) left = mid + 1;
        else if(cuts[mid] > mon) right = mid - 1;
        else return mid;
        mid = (left + right) / 2;
    }
    return left;
}

第四题0.7143

也是暴力。。。。坑点：如果在循环直接输出，ac0.5714，如果记录下结果最后输出0.7143.。。字节今天的题都很简单很暴力，但很烦，而且有很多奇奇怪怪的细节

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    ArrayList<String> ans = new ArrayList<>();
    for (int i = 0; i < t; i++) {
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int j = 0; j < n; j++) {
            nums[j] = sc.nextInt();
        }
        StringBuffer curr = new StringBuffer();
        for (int j = 0; j < n; j++) {
            int val = nums[j];
            int left = j - 1;
            int res = 0;
            while (left >= 0 && nums[left] <= val){
                left--;
                res++;
            }
            int right = j + 1;
            while (right < n && nums[right] <= val){
                right++;
                res++;
            }
            if(j < n - 1) curr.append(res + " ");
            else curr.append(res);
        }
        ans.add(curr.toString());
    }
    sc.close();
    for (int i = 0; i < ans.size(); i++) {
        System.out.println(ans.get(i));
    }
}

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