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

Commit0137c61

Browse files
authored
Improved task 770
1 parent4303b65 commit0137c61

File tree

1 file changed

+155
-144
lines changed

1 file changed

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

33
// #Hard #String #Hash_Table #Math #Stack #Recursion
4-
// #2025_04_17_Time_8_ms_(95.70%)_Space_45.18_MB_(49.46%)
4+
// #2025_04_18_Time_8_ms_(95.70%)_Space_44.97_MB_(82.80%)
55

66
importjava.util.ArrayList;
7-
importjava.util.Arrays;
87
importjava.util.Collections;
9-
importjava.util.Comparator;
108
importjava.util.HashMap;
119
importjava.util.List;
1210
importjava.util.Map;
13-
importjava.util.TreeMap;
1411

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

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;
36-
}
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;
3730
}
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);
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());
41+
}
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);
7756
}
57+
res.add(sb.toString());
7858
}
59+
returnres;
7960
}
80-
List<String>ans =newArrayList<>();
81-
for (Map.Entry<String,Integer>entry :map.entrySet()) {
82-
ans.add(entry.getValue() +entry.getKey());
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]);
8370
}
84-
returnans;
71+
i = -1;
72+
next(expression);
73+
Resultres =expression(expression);
74+
returnres.toList();
8575
}
8676

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);
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));
10184
}else {
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));
85+
res =subtract(res,term(s));
11786
}
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;
13387
}
134-
returnans;
88+
returnres;
13589
}
13690

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);
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;
98+
}
99+
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());
144110
}
145111
}
146-
returnans;
112+
returnnewResult(map);
147113
}
148114

149-
privatestaticclassTerm {
150-
intcoeff;
151-
List<String>vars;
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+
}
152127

153-
publicTerm(inta,List<String>c) {
154-
this.coeff =a;
155-
vars =newArrayList<>();
156-
vars.addAll(c);
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());
157137
}
138+
returnnewResult(map);
139+
}
158140

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

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-
}
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);
176172
}
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++;
181+
}
182+
i--;
183+
next(s);
184+
returnres;
185+
}
177186

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

0 commit comments

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