Seeker的奇妙求职历险（bilibili笔试）

24点

题目：

给出4个数字，判断这4个数字能否通过加减乘除使得最后的值为24.

输入

[7,2,1,10]

输出

true

分析：一开始的时候想复杂了，还以为需要判断优先级和交换律，卡在42%一直过不去，最后改成dfs枚举每个数字的状态就莫名其妙过了。

static boolean res;
static HashSet<Integer> set;
public static boolean get24(int[] nums){
    res = false;
    set = new HashSet<>();
    backtrace(nums,0.0);
    return res;
}

private static void backtrace(int[] nums, double sum) {
    if(res)
        return;
    if(set.size() == 4){
        if(sum == 24)
            res = true;
        return;
    }
    for(int i=0;i<nums.length;i++){
        if(set.contains(nums[i]))
            continue;
        set.add(nums[i]);
        backtrace(nums,sum+nums[i]);
        backtrace(nums,sum-nums[i]);
        backtrace(nums,sum*nums[i]);
        backtrace(nums,sum/nums[i]);
        set.remove(nums[i]);
    }
}
           

有效的括号

力扣原题：https://leetcode-cn.com/problems/valid-parentheses/

题目大意：

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 注意空字符串可被认为是有效字符串。

分析：一开始以为还要考虑括号优先级，没想到连括号优先级都不用考虑。直接用栈做就行了。

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList<>();
        HashMap<Character,Character> map = new HashMap<>();
        map.put(')','(');
        map.put('}','{');
        map.put(']','[');
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(stack.isEmpty()){
                stack.push(c);
            }else{
                char tmp = '0';
                if(map.containsKey(c))
                    tmp = map.get(c);
                if(stack.peek() == tmp)
                    stack.pop();
                else
                    stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}
           

最少零钱

题目：

现有1,4,16,64,1024的纸币，小明拿着1024的纸币去购买一个价格为N的物品，求最少会找回多少零钱。

输入

200

输出

17

分析：一开始想复杂了，以为是一道完全背包的问题，直接dp做了，做完之后才发现原来是道贪心。不过好在过了。

//dp
public static int GetCoinCount (int N) {
    // write code here
    int n = 1024-N;
    int[] dp = new int[n+1];
    int[] money = new int[]{1,4,16,64,1024};
    Arrays.fill(dp,1024);
    dp[0]=0;
    for(int m:money){
        for(int i=1;i<dp.length;i++){
            if(i>=m)
                dp[i] = Math.min(dp[i],dp[i-m]+1);
        }
    }
    return dp[n];
}
//贪心 一直拿最大的纸币直到拿不下了
public static int GetCoinCount (int N) {
    // write code here
    int n = 1024-N;
    int count = 0;
    int[] money = new int[]{1,4,16,64,1024};
    for(int i=money.length-1;i>=0;i--){
        if(n >= money[i]){
            int tmp = n/money[i];
            count += tmp;
            n -= tmp*money[i];
        }
    }
    return count;
}
           

后记

这B站的题目也有点太简单了吧，我好几题都自己想复杂了，其他大厂的笔试要是有这么简单就好了，括号匹配还不用判断括号优先级。

下周二晚上网易有道面试，好好准备一下，希望能过吧。