欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LeetCode每日一题(20200822)

程序员文章站 2022-03-23 09:08:41
原题地址思考过程:先看本题的所有可能性,四个数字排列,4*3*2=24种,然后后在两个数字之间加一个运算符号,4*4*4=64,所以穷举有1536种可能性,是一个量级不大的常数,所以穷举可行;代码实现:第一版代码执行不通过(和以下代码类似),再来思考思路是否有缺漏,我考虑到的穷举是,四个数字排列,然后以此对四个数字做运算,但是ab运算后,cd运算后,两个结果再运算,这种可能没有考虑在内。按此再修改出如下代码:public boolean judgePoint24(int[] nums)...

原题地址

思考过程:

先看本题的所有可能性,四个数字排列,4*3*2=24种,然后后在两个数字之间加一个运算符号,4*4*4=64,所以穷举有1536种可能性,是一个量级不大的常数,所以穷举可行;

代码实现:

第一版代码执行不通过(和以下代码类似),再来思考思路是否有缺漏,我考虑到的穷举是,四个数字排列,然后以此对四个数字做运算,但是ab运算后,cd运算后,两个结果再运算,这种可能没有考虑在内。按此再修改出如下代码:

public boolean judgePoint24(int[] nums) {

        Set<Integer> set = new HashSet<>();
        Set<String> history = new HashSet<>();
        for (int a = 0; a < 4; a++) {
            set.add(a);
            for (int b = 0; b < 4; b++) {
                if (!set.contains(b)) {
                    set.add(b);
                    for (int c = 0; c < 4; c++) {
                        if (!set.contains(c)) {
                            set.add(c);
                            for (int d = 0; d < 4; d++) {
                                if (!set.contains(d)) {
                                    if (check(nums[a], nums[b], nums[c], nums[d], history)) {
                                        return true;
                                    }
                                }
                            }
                            set.remove(c);
                        }

                    }
                    set.remove(b);
                }
            }
            set.remove(a);
        }

        return false;

    }

    private boolean check(int a, int b, int c, int d, Set<String> history) {
        if (history.contains(a + "-" + b + "-" + c + "-" + d)) {
            return false;
        }
        for (int i = 0; i < 6; i++) {
            float ab;
            switch (i) {
                default:
                case 0:
                    ab = (float) a + (float) b;
                    break;
                case 1:
                    ab = (float) a - (float) b;
                    break;
                case 2:
                    ab = (float) a * (float) b;
                    break;
                case 3:
                    ab = (float) a / (float) b;
                    break;
                case 4:
                    ab = (float) b - (float) a;
                    break;
                case 5:
                    ab = (float) b / (float) a;
            }

            for (int j = 0; j < 6; j++) {
                float abc;
                switch (j) {
                    default:
                    case 0:
                        abc = (float) ab + (float) c;
                        break;
                    case 1:
                        abc = (float) ab - (float) c;
                        break;
                    case 2:
                        abc = (float) ab * (float) c;
                        break;
                    case 3:
                        abc = (float) ab / (float) c;
                        break;
                    case 4:
                        abc = (float) c - (float) ab;
                        break;
                    case 5:
                        abc = (float) c / (float) a;
                }

                for (int k = 0; k < 6; k++) {
                    switch (k) {
                        default:
                        case 0:
                            if ((abc + (float) d) - 24 == 0) {
                                return true;
                            }
                            break;
                        case 1:
                            if ((abc - (float) d) - 24 == 0) {
                                return true;
                            }
                            break;
                        case 2:
                            if ((abc * (float) d) - 24 == 0) {
                                return true;
                            }
                            break;
                        case 3:
                            if ((abc / (float) d) - 24 == 0) {
                                return true;
                            }
                            break;
                        case 4:
                            if (((float) d / abc) - 24 == 0) {
                                return true;
                            }
                            break;
                        case 5:
                            if (((float) d - abc) - 24 == 0) {
                                return true;
                            }
                            break;
                    }
                }
            }

        }

        float ab = 0;
        for (int i = 0; i < 6; i++) {
            switch (i) {
                default:
                case 0:
                    ab = (float) a + (float) b;
                    break;
                case 1:
                    ab = (float) a - (float) b;
                    break;
                case 2:
                    ab = (float) a * (float) b;
                    break;
                case 3:
                    ab = (float) a / (float) b;
                    break;
                case 4:
                    ab = (float) b - (float) a;
                    break;
                case 5:
                    ab = (float) b / (float) a;
                    break;
            }
        }

        float cd = 0;
        for (int i = 0; i < 6; i++) {
            switch (i) {
                default:
                case 0:
                    cd = (float) c + (float) d;
                    break;
                case 1:
                    cd = (float) c - (float) d;
                    break;
                case 2:
                    cd = (float) c * (float) d;
                    break;
                case 3:
                    cd = (float) c / (float) d;
                    break;
                case 4:
                    cd = (float) d - (float) c;
                    break;
                case 5:
                    cd = (float) d / (float) c;
                    break;
            }
        }

        for (int i = 0; i < 4; i++) {
            switch (i) {
                default:
                case 0:
                    if ((ab + cd) - 24 == 0) {
                        return true;
                    }
                    break;
                case 1:
                    if ((ab - cd) - 24 == 0) {
                        return true;
                    }
                    break;
                case 2:
                    if ((ab * cd) - 24 == 0) {
                        return true;
                    }
                    break;
                case 3:
                    if ((ab / cd) - 24 == 0) {
                        return true;
                    }
                    break;
                case 4:
                    if ((cd - ab) - 24 == 0) {
                        return true;
                    }
                    break;
                case 5:
                    if ((cd / ab) - 24 == 0) {
                        return true;
                    }
                    break;

            }

        }
        history.add(a + "-" + b + "-" + c + "-" + d);
        return false;
    }

依然不通过,思来想去,没有找到问题所在。

 

查看官方解法:

思路和我略有不同,如下:

先在四个数种找两个,进行运算,4*3*4

然后四个数变三个数,找两个运算,3*2*4

然后变成两个数,2*4

所以共有9216种。

官方代码如下:

    static final int TARGET = 24;
    static final double EPSILON = 1e-6;
    static final int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;

    public boolean judgePoint24(int[] nums) {
        List<Double> list = new ArrayList<Double>();
        for (int num : nums) {
            list.add((double) num);
        }
        return solve(list);
    }

    public boolean solve(List<Double> list) {
        if (list.size() == 0) {
            return false;
        }
        if (list.size() == 1) {
            return Math.abs(list.get(0) - TARGET) < EPSILON;
        }
        int size = list.size();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (i != j) {
                    List<Double> list2 = new ArrayList<Double>();
                    for (int k = 0; k < size; k++) {
                        if (k != i && k != j) {
                            list2.add(list.get(k));
                        }
                    }
                    for (int k = 0; k < 4; k++) {
                        if (k < 2 && i > j) {
                            continue;
                        }
                        if (k == ADD) {
                            list2.add(list.get(i) + list.get(j));
                        } else if (k == MULTIPLY) {
                            list2.add(list.get(i) * list.get(j));
                        } else if (k == SUBTRACT) {
                            list2.add(list.get(i) - list.get(j));
                        } else if (k == DIVIDE) {
                            if (Math.abs(list.get(j)) < EPSILON) {
                                continue;
                            } else {
                                list2.add(list.get(i) / list.get(j));
                            }
                        }
                        if (solve(list2)) {
                            return true;
                        }
                        list2.remove(list2.size() - 1);
                    }
                }
            }
        }
        return false;
    }

总结:

思考问题时,想到来这个问题的解是有限常数个,可以使用穷举法,但是在思考问题的全面性和代码实现上还有很大的不足。

按照官方的思路,实现自己的代码(待续。。。)

本文地址:https://blog.csdn.net/Payne_xy/article/details/108188123