leetcode | 분할 치료

241 연산 식 디자인 우선 순위
숫자 와 연산 자 를 포함 하 는 문자열 을 지정 하여 표현 식 에 괄호 를 추가 하고 연산 우선 순 위 를 바 꾸 어 서로 다른 결 과 를 얻 도록 합 니 다.너 는 가능 한 모든 조합의 결 과 를 제시 해 야 한다.유효한 연산 기호 포함+ ,  -  그리고  *  。
예시 1:

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

예시 2:

  : "2*3-4*5"
  : [-34, -14, -10, -10, 10]
  : (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

문제 풀이

class Solution {
    public List diffWaysToCompute(String input) {
        List res = new ArrayList<>();
        if (input == null || input.length() == 0){
            return res;
        }
        //                 
       int num = 0;
        //          
        int index = 0;
        while (index < input.length() && !isOperation(input.charAt(index))) {
            num = num * 10 + input.charAt(index) - '0';
            index ++;
        }
        //            
        if (index == input.length()) {
            res.add(num);
            return res;
        }

        for(int i=0; i res1 = diffWaysToCompute(input.substring(0,i));
                List res2 = diffWaysToCompute(input.substring(i+1));
                for (int j = 0; j < res1.size(); j++){
                    for (int k = 0; k < res2.size(); k++){
                        num = calculate(res1.get(j), input.charAt(i), res2.get(k));
                        res.add(num);
                    }
                }
            }
        }
        return res;

    }
    //          
    public int calculate(int num1, char op, int num2){
        switch(op){
            case '+':
                return num1 + num2;
            case '-':
                return num1 - num2;
            case '*':
                return num1 * num2;
        }
        return -1;
    }

    public boolean isOperation(char ch){
        return ch == '+' || ch == '-' || ch == '*';
    }
}

재 귀적 분할 최적화: Map 은 계 산 된 결 과 를 저장 합 니 다.

Solution {
    public List diffWaysToCompute(String input) {
        List res = new ArrayList<>();
        Map map = new HashMap();

        //   map    input     ，       res，   。
        if (map.containsKey(input)){
            res.add(map.get(input));
            return res;
        }
        if (input == null || input.length() == 0){
            return res;
        }
        //                 
       int num = 0;
        //          
        int index = 0;
        while (index < input.length() && !isOperation(input.charAt(index))) {
            num = num * 10 + input.charAt(index) - '0';
            index ++;
        }
        //            
        if (index == input.length()) {
            res.add(num);
            return res;
        }

        for(int i=0; i res1 = diffWaysToCompute(input.substring(0,i));
                List res2 = diffWaysToCompute(input.substring(i+1));
                for (int j = 0; j < res1.size(); j++){
                    for (int k = 0; k < res2.size(); k++){
                        num = calculate(res1.get(j), input.charAt(i), res2.get(k));
                        res.add(num);
                        map.put(input, num);
                    }
                }
            }
        }
        return res;

    }
    //          
    public int calculate(int num1, char op, int num2){
        switch(op){
            case '+':
                return num1 + num2;
            case '-':
                return num1 - num2;
            case '*':
                return num1 * num2;
        }
        return -1;
    }

    public boolean isOperation(char ch){
        return ch == '+' || ch == '-' || ch == '*';
    }
}

95. 서로 다른 이 진 트 리 II
정수 n 을 지정 하여 모든 것 을 1 로 생 성 합 니 다. 노드 로 구 성 된 이 진 트 리 입 니 다.
예시:

  ：3
  ：
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
  ：
          5            ：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

 
알림: 0 < = n < = 8
문제 풀이:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List generateTrees(int n) {
        List res = new ArrayList<>();
        if (n<=0){
            return res;
        }
        return help(1, n);
    }

    public List help(int start, int end){
        List list = new ArrayList<>();
        if (start > end){
            list.add(null);
            return list;
        }
        if (start == end){
            list.add(new TreeNode(start));
        }
        else if (start < end){
            for (int i = start; i<=end; i++){
                
                List leftTrees = help(start, i-1);
                List rightTrees = help(i+1, end);
                for (TreeNode left: leftTrees){
                    for (TreeNode right: rightTrees){
                        TreeNode root = new TreeNode(i, left, right);
                        list.add(root);
                    }
                }

            }
        }
        return list;
    }
}