博客

第一题：数24点

原题见：

679. 24 点游戏


题目描述：你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。

思路：回溯法

public class Main {

    public boolean Game24Points (int[] arr) {
        ArrayList<Double> A=new ArrayList<>();
        for(int a:arr) A.add((double) a);
        return solve(A);
    }

    private boolean solve(ArrayList<Double> a) {
        if(a.size()==0) return false;
        if(a.size()==1) return Math.abs(a.get(0)-24)<1e-6;
        for(int i=0;i<a.size();i++){
            for(int j=0;j<a.size();j++){
                if(i!=j){
                    ArrayList<Double> a2=new ArrayList<>();
                    for(int k=0;k<a.size();k++){
                        if(k!=i&&k!=j)
                            a2.add(a.get(k));
                    }
                    for(int k=0;k<4;k++){
                        if(k<2 && j>i) continue;
                        if (k == 0) a2.add(a.get(i) + a.get(j));
                        if (k == 1) a2.add(a.get(i) * a.get(j));
                        if (k == 2) a2.add(a.get(i) - a.get(j));
                        // 避免除数为0
                        if (k == 3) {
                            if (a.get(j) != 0) {
                                a2.add(a.get(i) / a.get(j));
                            } else {
                                continue;
                            }
                        }
                        if(solve(a2))
                            return true;
                        a2.remove(a2.size()-1);
                    }
                }
            }
        }
        return false;
    }
}

第二题：括号匹配

原题见：

有效的括号


题目描述：

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

解题思路：栈

  public boolean IsValidExp(String s) {
        Stack<Character> stack=new Stack<>();
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(ch=='('||ch=='['||ch=='{')
                stack.add(s.charAt(i));
            else {
                if(stack.isEmpty())
                    return false;
                char tmp=stack.pop();
                if(ch==')'&&tmp!='(')
                    return false;
                if(ch==']'&&tmp!='[')
                    return false;
                if(ch=='}'&&tmp!='{')
                    return false;
            }
        }
        return stack.isEmpty();
    }

第三题：找零

原题见：

零钱兑换


题目描述：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

解题思路：动态规划

    public static int GetCoinCount (int[] coins, int amount) {
        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(i>=coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
        }
        return dp[amount]<=amount?dp[amount]:-1;
    }