8.13 B站后端开发笔试
1. 24点游戏:4个数,加减乘除使其结果为24
boolean result = false; public boolean Game24Points (int[] arr) { if(arr == null || arr.length == 0) { return false; } f(arr, 1, arr[0]); return result; } public void f(int[] arr, int index,int sum) { if(index >= arr.length || result == true) { if(sum == 24) { result = true; } return; } f(arr, index+1, sum + arr[index]); f(arr, index+1, sum - arr[index]); f(arr, index+1, sum * arr[index]); if(arr[index]!= 0) { f(arr, index+1, sum / arr[index]); } }
再贴一个我的沙雕代码,根本没想到用dfs(我TM...),我直接把可能的情况列出来了.....我人傻了,只过了85%,再重申一遍,我是沙雕...再点一首凉凉送给自己
public static boolean Game24Points (int[] arr) { // write code here int n1 = arr[0]; int n2 = arr[1]; int n3 = arr[2]; int n4 = arr[3]; /* 1. 不能的情况有 2. 假设无重复,尽可能多地假设能的情况 1. 两两相乘再相加,2*7 + 1*10 2. 全部相加,1+9+6+8 3. 全部相乘,1*2*3*4 4. 两个相乘再加上剩余的两个,3*4+6+8 5. 两个相乘再减去剩余的两个,5*6-2-3 6. 两两相乘再相减,6*7 - 2*9 7. 两两相乘先减再加,5*6 - 8+2 8. 三个相乘再减,3*5*2-6 9. 两个相乘再除再加,6*7/2 + 3 10. 两个相乘再除再减,6*8/2 - 4 11. 两个相乘再除再乘,6*8/2 * 1 */ if(Method1(n1,n2,n3,n4)){ return true; }else if(Method2(n1,n2,n3,n4)){ return true; }else if(Method3(n1,n2,n3,n4)){ return true; }else if(Method4(n1,n2,n3,n4)){ return true; }else if(Method5(n1,n2,n3,n4)) { return true; }else if(Method6(n1,n2,n3,n4)) { return true; }else if(Method7(n1,n2,n3,n4)) { return true; }else if(Method8(n1,n2,n3,n4)) { return true; }else if(Method9(n1,n2,n3,n4)) { return true; }else if(Method10(n1,n2,n3,n4)) { return true; }else if(Method11(n1,n2,n3,n4)){ return true; }else{ return false; } } //11. 两个相乘再除再乘,6*8/2 * 1 private static boolean Method11(int n1, int n2, int n3, int n4) { if(n1*n2/n3*n4 == 24 || n1*n2/n4*n3 == 24 || n1*n3/n2*n4 == 24 || n1*n3/n4*n2 == 24 || n1*n4/n2*n3 == 24 || n1*n4/n3*n2 == 24 || n2*n3/n1*n4 == 24 || n2*n3/n4*n1 == 24 || n2*n4/n1*n3 == 24 || n2*n4/n3*n1 == 24 || n3*n4/n1*n2 == 24 || n3*n4/n2*n1 == 24){ return true; }else{ return false; } } //10. 两个相乘再除再减,6*8/2 - 4 private static boolean Method10(int n1, int n2, int n3, int n4) { if(n1*n2/n3-n4 == 24 || n1*n2/n4-n3 == 24 || n1*n3/n2-n4 == 24 || n1*n3/n4-n2 == 24 || n1*n4/n2-n3 == 24 || n1*n4/n3-n2 == 24 || n2*n3/n1-n4 == 24 || n2*n3/n4-n1 == 24 || n2*n4/n1-n3 == 24 || n2*n4/n3-n1 == 24 || n3*n4/n1-n2 == 24 || n3*n4/n2-n1 == 24){ return true; }else{ return false; } } //9. 两个相乘再除再加,6*7/2 + 3 private static boolean Method9(int n1, int n2, int n3, int n4) { if(n1*n2/n3+n4 == 24 || n1*n2/n4+n3 == 24 || n1*n3/n2+n4 == 24 || n1*n3/n4+n2 == 24 || n1*n4/n2+n3 == 24 || n1*n4/n3+n2 == 24 || n2*n3/n1+n4 == 24 || n2*n3/n4+n1 == 24 || n2*n4/n1+n3 == 24 || n2*n4/n3+n1 == 24 || n3*n4/n1+n2 == 24 || n3*n4/n2+n1 == 24){ return true; }else{ return false; } } //8. 三个相乘再减,3*5*2-6 private static boolean Method8(int n1, int n2, int n3, int n4) { if(n1*n2*n3 - n4 == 24 || n1*n2*n4 - n2 == 24 || n1*n3*n4 - n2 == 24 || n2*n3*n4 - n1 == 24){ return true; }else{ return false; } } //1. 两两相乘再相加,2*7 + 1*10 private static boolean Method1(int n1, int n2, int n3, int n4) { if(n1*n2 + n3*n4 == 24 || n1*n3 + n2*n4 ==24 || n1*n4 + n2*n3 == 24){ return true; }else{ return false; } } //2. 全部相加,1+9+6+8 private static boolean Method2(int n1, int n2, int n3, int n4) { if(n1+n2+n3+n4 == 24){ return true; }else{ return false; } } //3. 全部相乘,1*2*3*4 private static boolean Method3(int n1, int n2, int n3, int n4) { if(n1*n2*n3*n4 == 24){ return true; }else{ return false; } } //4. 两个相乘再加上剩余的两个,3*4+6+8 private static boolean Method4(int n1, int n2, int n3, int n4) { if(n1*n2 +n3+n4 ==24 || n1*n3 +n2+n4 ==24 || n1*n4 +n2+n3 == 24 || n2*n3 +n1+n4 ==24 || n2*n4 +n1+n3 == 24 || n3*n4 +n1+n2 == 24){ return true; }else{ return false; } } //5. 两个相乘再减去剩余的两个,5*6-2-3 private static boolean Method5(int n1, int n2, int n3, int n4) { if(n1*n2 -n3-n4 ==24 || n1*n3 -n2-n4 ==24 || n1*n4 -n2-n3 == 24 || n2*n3 -n1-n4 ==24 || n2*n4 -n1-n3 == 24 || n3*n4 -n1-n2 == 24){ return true; }else{ return false; } } //6. 两两相乘再相减,6*7 - 2*9 private static boolean Method6(int n1, int n2, int n3, int n4) { if(n1*n2 - n3*n4 == 24 || n1*n3 - n2*n4 ==24 || n1*n4 - n2*n3 == 24){ return true; }else{ return false; } } //7. 两两相乘先减再加,5*6 - 8+2 private static boolean Method7(int n1, int n2, int n3, int n4) { if(n1*n2 -n3+n4 ==24 || n1*n3 -n2+n4 ==24 || n1*n4 -n2+n3 == 24 || n2*n3 -n1+n4 ==24 || n2*n4 -n1+n3 == 24 || n3*n4 -n1+n2 == 24){ return true; }else{ return false; } }
2. 有效括号:LC20,原题
//单调栈可解,当前左,栈存右,如果栈为空或者下一个字符不等于栈顶(右半),返回false public boolean isValid(String s) { char[] str = s.toCharArray(); Stack<Character> stack = new Stack<>(); for(char c : str){ if(c == '('){ stack.push(')'); }else if(c == '{'){ stack.push('}'); }else if(c == '['){ stack.push(']'); }else if(stack.isEmpty() || stack.pop() != c){ //如果栈为空或者栈顶与下一个字符不同,false return false; } } //如果栈为空,能够匹配,返回true if(stack.isEmpty()){ return true; }else{ return false; }
3. 找零:LC322
先贴一个自己的背包解
public static int GetCoinCount (int N) { // write code here int amount = 1024 - N; int[] coins = {1, 4, 16, 64}; int[] dp = new int[amount+1]; for(int i=1;i<=amount;i++){ dp[i] = Integer.MAX_VALUE; } for(int i=1;i<=amount;i++){ for(int j=0;j<coins.length;j++){ if(i-coins[j] >= 0 && dp[i-coins[j]] != Integer.MAX_VALUE){ dp[i] = Math.min(dp[i],dp[i-coins[j]]+1); } } } if(dp[amount] == Integer.MAX_VALUE){ return -1; }else{ return dp[amount]; } }
-
public int GetCoinCount(int N) { N = 1024 - N; int count = 0; while (N > 0) { if (N >= 64) { N -= 64; } else if (N >= 16) { N -= 16; } else if (N >= 4) { N -= 4; } else { N--; } //先从大的面额开始减,减完一次就+1 count++; } return count; }