leetcode | 분할 치료
숫자 와 연산 자 를 포함 하 는 문자열 을 지정 하여 표현 식 에 괄호 를 추가 하고 연산 우선 순 위 를 바 꾸 어 서로 다른 결 과 를 얻 도록 합 니 다.너 는 가능 한 모든 조합의 결 과 를 제시 해 야 한다.유효한 연산 기호 포함
+
, -
그리고 *
。 예시 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;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.