Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit4303b65

Browse files
authored
Improved task 770
1 parente000558 commit4303b65

File tree

1 file changed

+144
-155
lines changed

1 file changed

+144
-155
lines changed
Lines changed: 144 additions & 155 deletions
Original file line numberDiff line numberDiff line change
@@ -1,193 +1,182 @@
11
packageg0701_0800.s0770_basic_calculator_iv;
22

33
// #Hard #String #Hash_Table #Math #Stack #Recursion
4-
// #2022_04_30_Time_8_ms_(96.92%)_Space_42.9_MB_(93.85%)
4+
// #2025_04_17_Time_8_ms_(95.70%)_Space_45.18_MB_(49.46%)
55

66
importjava.util.ArrayList;
7+
importjava.util.Arrays;
78
importjava.util.Collections;
9+
importjava.util.Comparator;
810
importjava.util.HashMap;
911
importjava.util.List;
1012
importjava.util.Map;
13+
importjava.util.TreeMap;
1114

1215
publicclassSolution {
13-
privatestaticclassResult {
14-
privateMap<List<String>,Integer>map;
16+
privateStrings;
17+
privatechar[]arr;
18+
privateint[]braces;
19+
privatefinalMap<String,Integer>variables =newHashMap<>();
1520

16-
Result() {
17-
map =newHashMap<>();
18-
}
19-
20-
Result(Map<List<String>,Integer>map) {
21-
this.map =map;
22-
}
23-
24-
voidupdate(List<String>key,intval) {
25-
map.put(key,map.getOrDefault(key,0) +val);
26-
}
27-
28-
Map<List<String>,Integer>getMap() {
29-
returnmap;
30-
}
31-
32-
List<String>toList() {
33-
List<List<String>>keyList =newArrayList<>(map.keySet());
34-
Map<List<String>,String>list2String =newHashMap<>();
35-
for (List<String>key :keyList) {
36-
StringBuildersb =newStringBuilder();
37-
for (Stringk :key) {
38-
sb.append(k).append("*");
39-
}
40-
list2String.put(key,sb.toString());
21+
publicList<String>basicCalculatorIV(Stringexpression,String[]evalvars,int[]evalints) {
22+
s =expression;
23+
arr =s.toCharArray();
24+
intn =arr.length;
25+
braces =newint[n];
26+
Arrays.fill(braces, -1);
27+
int[]stack =newint[n /2];
28+
intindex = -1;
29+
for (inti =0;i <n; ++i) {
30+
if (arr[i] =='(') {
31+
stack[++index] =i;
32+
}elseif (arr[i] ==')') {
33+
intlast =stack[index--];
34+
braces[last] =i;
35+
braces[i] =last;
4136
}
42-
keyList.sort(
43-
(a,b) ->
44-
(a.size() ==b.size()
45-
?list2String.get(a).compareTo(list2String.get(b))
46-
:b.size() -a.size()));
47-
List<String>res =newArrayList<>();
48-
for (List<String>key :keyList) {
49-
if (map.get(key) ==0) {
50-
continue;
51-
}
52-
StringBuildersb =newStringBuilder();
53-
sb.append(map.get(key));
54-
for (Stringk :key) {
55-
sb.append("*").append(k);
37+
}
38+
for (inti =0;i <evalvars.length; ++i) {
39+
variables.put(evalvars[i],evalints[i]);
40+
}
41+
List<Term>terms =dewIt(0,n -1);
42+
Map<String,Integer>map =
43+
newTreeMap<>(
44+
newComparator<>() {
45+
publicintcompare(Stringa,Stringb) {
46+
intca =countStars(a);
47+
intcb =countStars(b);
48+
if (ca !=cb) {
49+
returncb -ca;
50+
}else {
51+
returna.compareTo(b);
52+
}
53+
}
54+
55+
privateintcountStars(Strings) {
56+
intans =0;
57+
for (charc :s.toCharArray()) {
58+
if (c =='*') {
59+
++ans;
60+
}
61+
}
62+
returnans;
63+
}
64+
});
65+
for (Termterm :terms) {
66+
if (term.coeff !=0) {
67+
Stringkey =term.getKey();
68+
if (map.containsKey(key)) {
69+
intoldCoeff =map.get(key);
70+
if (oldCoeff == -term.coeff) {
71+
map.remove(key);
72+
}else {
73+
map.put(key,oldCoeff +term.coeff);
74+
}
75+
}else {
76+
map.put(key,term.coeff);
5677
}
57-
res.add(sb.toString());
5878
}
59-
returnres;
6079
}
61-
}
62-
63-
privateMap<String,Integer>evalMap;
64-
privateinti =0;
65-
66-
publicList<String>basicCalculatorIV(Stringexpression,String[]evalvars,int[]evalints) {
67-
evalMap =newHashMap<>();
68-
for (intj =0;j <evalvars.length;j++) {
69-
evalMap.put(evalvars[j],evalints[j]);
80+
List<String>ans =newArrayList<>();
81+
for (Map.Entry<String,Integer>entry :map.entrySet()) {
82+
ans.add(entry.getValue() +entry.getKey());
7083
}
71-
i = -1;
72-
next(expression);
73-
Resultres =expression(expression);
74-
returnres.toList();
84+
returnans;
7585
}
7686

77-
privateResultexpression(Strings) {
78-
Resultres =term(s);
79-
while (i <s.length() && (s.charAt(i) =='+' ||s.charAt(i) =='-')) {
80-
intc =s.charAt(i);
81-
next(s);
82-
if (c =='+') {
83-
res =add(res,term(s));
87+
privateList<Term>dewIt(inta,intb) {
88+
if (braces[a] ==b) {
89+
returndewIt(a +1,b -1);
90+
}
91+
List<Term>ans =newArrayList<>();
92+
List<Term>buffer =newArrayList<>();
93+
buffer.add(newTerm(1,newArrayList<>()));
94+
inti =a;
95+
while (i <=b) {
96+
intj =i;
97+
List<Term>curr;
98+
if (arr[i] =='(') {
99+
j =braces[i] +1;
100+
curr =dewIt(i +1,j -2);
84101
}else {
85-
res =subtract(res,term(s));
102+
while (j <=b &&arr[j] !=' ') {
103+
++j;
104+
}
105+
Stringexp =s.substring(i,j);
106+
intval =1;
107+
List<String>vars =newArrayList<>();
108+
if (variables.containsKey(exp)) {
109+
val =variables.get(exp);
110+
}elseif (exp.charAt(0) <='9') {
111+
val =Integer.parseInt(exp);
112+
}else {
113+
vars.add(exp);
114+
}
115+
curr =newArrayList<>();
116+
curr.add(newTerm(val,vars));
86117
}
118+
buffer =multiply(buffer,curr);
119+
if (j >b ||arr[j +1] =='+' ||arr[j +1] =='-') {
120+
ans.addAll(buffer);
121+
buffer =newArrayList<>();
122+
}
123+
if (j <b) {
124+
++j;
125+
if (arr[j] =='+') {
126+
buffer.add(newTerm(1,newArrayList<>()));
127+
}elseif (arr[j] =='-') {
128+
buffer.add(newTerm(-1,newArrayList<>()));
129+
}
130+
j +=2;
131+
}
132+
i =j;
87133
}
88-
returnres;
89-
}
90-
91-
privateResultterm(Strings) {
92-
Resultres =factor(s);
93-
while (i <s.length() &&s.charAt(i) =='*') {
94-
next(s);
95-
res =multiply(res,factor(s));
96-
}
97-
returnres;
134+
returnans;
98135
}
99136

100-
privateResultmultiply(Resultr1,Resultr2) {
101-
Map<List<String>,Integer>map1 =r1.getMap();
102-
Map<List<String>,Integer>map2 =r2.getMap();
103-
Map<List<String>,Integer>map =newHashMap<>();
104-
for (Map.Entry<List<String>,Integer>entry1 :map1.entrySet()) {
105-
for (Map.Entry<List<String>,Integer>entry2 :map2.entrySet()) {
106-
List<String>key =newArrayList<>(entry1.getKey());
107-
key.addAll(entry2.getKey());
108-
Collections.sort(key);
109-
map.put(key,map.getOrDefault(key,0) +entry1.getValue() *entry2.getValue());
137+
privateList<Term>multiply(List<Term>a,List<Term>b) {
138+
List<Term>ans =newArrayList<>();
139+
for (Termx :a) {
140+
for (Termy :b) {
141+
Termprod =x.copy();
142+
prod.multiply(y);
143+
ans.add(prod);
110144
}
111145
}
112-
returnnewResult(map);
146+
returnans;
113147
}
114148

115-
privateResultadd(Resultr1,Resultr2) {
116-
Map<List<String>,Integer>map1 =r1.getMap();
117-
Map<List<String>,Integer>map2 =r2.getMap();
118-
Map<List<String>,Integer>map =newHashMap<>();
119-
for (Map.Entry<List<String>,Integer>entry1 :map1.entrySet()) {
120-
map.put(entry1.getKey(),map.getOrDefault(entry1.getKey(),0) +entry1.getValue());
121-
}
122-
for (Map.Entry<List<String>,Integer>entry2 :map2.entrySet()) {
123-
map.put(entry2.getKey(),map.getOrDefault(entry2.getKey(),0) +entry2.getValue());
124-
}
125-
returnnewResult(map);
126-
}
149+
privatestaticclassTerm {
150+
intcoeff;
151+
List<String>vars;
127152

128-
privateResultsubtract(Resultr1,Resultr2) {
129-
Map<List<String>,Integer>map1 =r1.getMap();
130-
Map<List<String>,Integer>map2 =r2.getMap();
131-
Map<List<String>,Integer>map =newHashMap<>();
132-
for (Map.Entry<List<String>,Integer>entry1 :map1.entrySet()) {
133-
map.put(entry1.getKey(),map.getOrDefault(entry1.getKey(),0) +entry1.getValue());
134-
}
135-
for (Map.Entry<List<String>,Integer>entry2 :map2.entrySet()) {
136-
map.put(entry2.getKey(),map.getOrDefault(entry2.getKey(),0) -entry2.getValue());
153+
publicTerm(inta,List<String>c) {
154+
this.coeff =a;
155+
vars =newArrayList<>();
156+
vars.addAll(c);
137157
}
138-
returnnewResult(map);
139-
}
140158

141-
privateResultfactor(Strings) {
142-
Resultres =newResult();
143-
if (s.charAt(i) =='(') {
144-
next(s);
145-
res =expression(s);
146-
next(s);
147-
returnres;
148-
}
149-
if (Character.isLowerCase(s.charAt(i))) {
150-
returnidentifier(s);
159+
publicStringgetKey() {
160+
StringBuilderb =newStringBuilder();
161+
Collections.sort(vars);
162+
for (Stringx :vars) {
163+
b.append('*');
164+
b.append(x);
165+
}
166+
returnb.toString();
151167
}
152-
res.update(newArrayList<>(),number(s));
153-
returnres;
154-
}
155168

156-
privateResultidentifier(Strings) {
157-
Resultres =newResult();
158-
StringBuildersb =newStringBuilder();
159-
while (i <s.length() &&Character.isLowerCase(s.charAt(i))) {
160-
sb.append(s.charAt(i));
161-
i++;
162-
}
163-
i--;
164-
next(s);
165-
Stringvariable =sb.toString();
166-
if (evalMap.containsKey(variable)) {
167-
res.update(newArrayList<>(),evalMap.get(variable));
168-
}else {
169-
List<String>key =newArrayList<>();
170-
key.add(variable);
171-
res.update(key,1);
172-
}
173-
returnres;
174-
}
175-
176-
privateintnumber(Strings) {
177-
intres =0;
178-
while (i <s.length() &&s.charAt(i) >='0' &&s.charAt(i) <='9') {
179-
res =res *10 + (s.charAt(i) -'0');
180-
i++;
169+
publicvoidmultiply(Termthat) {
170+
this.coeff *=that.coeff;
171+
if (this.coeff ==0) {
172+
vars.clear();
173+
}else {
174+
this.vars.addAll(that.vars);
175+
}
181176
}
182-
i--;
183-
next(s);
184-
returnres;
185-
}
186177

187-
privatevoidnext(Strings) {
188-
i++;
189-
while (i <s.length() &&s.charAt(i) ==' ') {
190-
i++;
178+
publicTermcopy() {
179+
returnnewTerm(coeff,vars);
191180
}
192181
}
193182
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp