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; }
京公网安备 11010502036488号