哔哩哔哩8月13日后端笔试题

public class Solution {
    boolean ans = false;
    public boolean Game24Points(int[] arr) {
        backtrack(arr, 24, new HashSet<>());
        return ans;
    }

    private boolean backtrack(int[] arr, double num, Set<Integer> path) {
        if (num == 0) {
            ans = true;
            return true;
        }

        for (int i = 0; i < arr.length - 1; i++) {
            if (path.contains(i)) continue;
            for (int j = i + 1; j < arr.length; j++) {
                if (path.contains(j)) continue;

                path.add(i);
                path.add(j);

                if (backtrack(arr, num - (arr[i] + arr[j]), path)) return true;
                else if (backtrack(arr, num / (arr[i] + arr[j]), path)) return true;


                else if (backtrack(arr, num - (arr[i] - arr[j]), path)) return true;
                else if (backtrack(arr, num / (arr[i] - arr[j]), path)) return true;


                else if (backtrack(arr, num - (arr[j] - arr[i]), path)) return true;
                else if (backtrack(arr, num / (arr[j] - arr[i]), path)) return true;


                else if (backtrack(arr, num - (arr[i] * arr[j]), path)) return true;
                else if (backtrack(arr, num / (arr[i] * arr[j]), path)) return true;


                else if (backtrack(arr, num - ((double) arr[i] / arr[j]), path)) return true;
                else if (backtrack(arr, num / ((double) arr[i] / arr[j]), path)) return true;

                else if (backtrack(arr, num - ((double) arr[j] / arr[i]), path)) return true;
                else if (backtrack(arr, num / ((double) arr[j] / arr[i]), path)) return true;

                path.remove(i);
                path.remove(j);

            }
        }

        return false;
    }
}

public class Solution {

    public static boolean IsValidExp(String s) {
        if (s == null || s.length() == 0) return true;
        if ((s.length() & 1) == 1) return false;

        Stack<Character> stack = new Stack<>();

        for (char ch : s.toCharArray()) {
            if (ch == '(') stack.push(')');
            else if (ch == '[') stack.push(']');
            else if (ch == '{') stack.push('}');
            else {
                if (stack.pop() != ch) return false;
            }
        }

        return stack.isEmpty();
    }
}

public class Main {
    public static int GetCoinCount(int N) {
        int amount = 1024 - N;
        int[] coins = {1, 4, 16, 64};

        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int i = 0; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) dp[i] = dp[i - coin] + 1;
            }
        }

        return dp[amount];
    }
}