leetcode241. Different Ways to Add Parentheses

xi4oh4o 發布于2019-08-15 14:22 / 1257人閱讀

摘要：思路與算法這是經典的分治法。我們將算式從一個操作符的位置分割開，并分別得出左邊和右邊算式所有可能的值。再將左右的值分別按照操作符進行計算。將已經遍歷過的結果存入緩存中，如果碰到重復的計算式，就可以直接獲取其所有可能的值。

題目要求

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. 
The valid operators are +, - and *.


Example 1
Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]


Example 2
Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]

現在有一個字符串形式的算式，求該算式在任意位置加上任意數量的括號后能夠得出的所有可能的值。

思路與算法

這是經典的分治法。我們將算式從一個操作符的位置分割開，并分別得出左邊和右邊算式所有可能的值。再將左右的值分別按照操作符進行計算。這里通過遞歸實現。

    public List diffWaysToCompute(String input) {
        return diffWaysToCompute(input, 0, input.length());
    }
    
    public List diffWaysToCompute(String input, int startIndex, int endIndex){
        boolean isDigit = true;
        List result = new ArrayList();
        for(int i = startIndex ; i leftValue = diffWaysToCompute(input, startIndex, i);
                List rightValue = diffWaysToCompute(input, i+1, endIndex);
                result.addAll(compute(leftValue, rightValue,cur));
            }
        }
        if(isDigit){
            result.add(Integer.parseInt(input.substring(startIndex, endIndex)));
        }
        return result;
    }
    
    public List compute(List leftValue, List rightValue, char operator){
        switch(operator){
        case "+" : return add(leftValue, rightValue);
        case "-" : return minus(leftValue, rightValue);
        case "*" : return multiply(leftValue, rightValue);
        }
        return new ArrayList<>();
    }
    
    public List add(List leftValue, List rightValue){
        List result = new ArrayList();
        for(int left : leftValue){
            for(int right : rightValue){
                result.add(left + right);
            }
        }
        return result;
    }
    
    public List minus(List leftValue, List rightValue){
        List result = new ArrayList();
        for(int left : leftValue){
            for(int right : rightValue){
                result.add(left - right);
            }
        }
        return result;
    }
    
    public List multiply(List leftValue, List rightValue){
        List result = new ArrayList();
        for(int left : leftValue){
            for(int right : rightValue){
                result.add(left * right);
            }
        }
        return result;
    }

提高性能的方法是通過Map實現緩存。將已經遍歷過的結果存入緩存中，如果碰到重復的計算式，就可以直接獲取其所有可能的值。

    Map> cache = new HashMap>();
    public List diffWaysToCompute_withCache(String input){
        if(cache.containsKey(input)) return cache.get(input);
        List result = new ArrayList();
        boolean isDigit = true;
        for(int i = 0 ; i leftValues = diffWaysToCompute_withCache(input.substring(0, i));
                List rightValues = diffWaysToCompute_withCache(input.substring(i+1));
                for(Integer left : leftValues){
                    for(Integer right : rightValues){
                        switch(cur){
                        case "+" : result.add(left + right); break;
                        case "-" : result.add(left - right); break;
                        case "*" : result.add(left * right); break;
                        }
                    }
                }
            }
        }
        if(isDigit){ result.add(Integer.parseInt(input));}
        cache.put(input, result);
        return result;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 Parentheses Different Ways Leetcod

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/68565.html

leetcode241. Different Ways to Add Parentheses

摘要：思路與算法這是經典的分治法。我們將算式從一個操作符的位置分割開，并分別得出左邊和右邊算式所有可能的值。再將左右的值分別按照操作符進行計算。將已經遍歷過的結果存入緩存中，如果碰到重復的計算式，就可以直接獲取其所有可能的值。題目要求 Given a string of numbers and operators, return all possible results from comp...

since1986 2019-08-06 13:29 評論0 收藏0
leetcode22. Generate Parentheses

摘要：當右括號和左括號的剩余量均為時，及為一個最終結果。而則會在直接原來的對象上進行修改，其指針仍然指向原來的對象。因此在遞歸的過程中使用一定要注意，對對象的修改不要相互干擾。題目要求 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses....

騫諱護 2019-08-14 18:35 評論0 收藏0
LeetCode[22] Generate Parentheses

摘要：復雜度思路注意的地方，要限制左括號和右括號。每出現一次左括號，就相對于限定了，最多只能出現那么多右括號。所以，為了完成這種限定，用來控制。不然會有的情況出現。 LeetCode[22] Generate Parentheses Given n pairs of parentheses, write a function to generate all combinations of ...

Jonathan Shieber 2019-08-14 15:02 評論0 收藏0
[Leetcod] Generate Parentheses 產生括號

摘要：而對于右括號，必須前面放了一個左括號，我們才能放一個右括號。所以我們根據剩余可放置左括號，和剩余可放置右括號，代入遞歸，就可以求解。 Generate Parentheses 最新更新請見：https://yanjia.me/zh/2019/01/... Given n pairs of parentheses, write a function to generate all co...

Ilikewhite 2019-08-14 12:45 評論0 收藏0
[LeetCode] 22. Generate Parentheses

Problem Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ ((())), (()()), (())(), ()(()), ...

curlyCheng 2019-08-19 11:15 評論0 收藏0