## 第一题 24点
回溯算法,写得有点丧心病狂。。。
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]; } }
全部评论
(7) 回帖