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

Commitdf8835d

Browse files
author
zhenyu zhang
committed
update challenge30days day9、10、12
1 parentf10acbe commitdf8835d

File tree

3 files changed

+216
-0
lines changed

3 files changed

+216
-0
lines changed
Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
packagecom.hadley.challenge30days;
2+
3+
/*
4+
2020.04.10
5+
Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.
6+
7+
Example 1:
8+
9+
Input: S = "ab#c", T = "ad#c"
10+
Output: true
11+
Explanation: Both S and T become "ac".
12+
Example 2:
13+
14+
Input: S = "ab##", T = "c#d#"
15+
Output: true
16+
Explanation: Both S and T become "".
17+
Example 3:
18+
19+
Input: S = "a##c", T = "#a#c"
20+
Output: true
21+
Explanation: Both S and T become "c".
22+
Example 4:
23+
24+
Input: S = "a#c", T = "b"
25+
Output: false
26+
Explanation: S becomes "c" while T becomes "b".
27+
*/
28+
29+
importjava.util.Stack;
30+
31+
publicclassBackspaceStringCompare {
32+
33+
//use stack: first in, last out
34+
publicbooleanbackspaceCompare(StringS,StringT) {
35+
StringresultS ="";
36+
StringresultT ="";
37+
Stack<Character>stack =newStack<Character>();
38+
char[]charListS =S.toCharArray();
39+
for(inti =0;i <charListS.length;i++){
40+
if(charListS[i] =='#'){
41+
if(!stack.empty()){
42+
stack.pop();
43+
}
44+
}else{
45+
stack.push(charListS[i]);
46+
}
47+
}
48+
//resultS
49+
while(!stack.empty()){
50+
resultS +=stack.pop();
51+
}
52+
53+
char[]charListT =T.toCharArray();
54+
for(intj =0;j <charListT.length;j++){
55+
if(charListT[j] =='#'){
56+
if(!stack.empty()){
57+
stack.pop();
58+
}
59+
}else{
60+
stack.push(charListT[j]);
61+
}
62+
}
63+
while(!stack.empty()){
64+
resultT +=stack.pop();
65+
}
66+
67+
returnresultS.equals(resultT);
68+
}
69+
70+
//method 2: use pointer
71+
72+
publicstaticvoidmain(String[]args) {
73+
BackspaceStringComparebs =newBackspaceStringCompare();
74+
System.out.println(bs.backspaceCompare("xywrrmp","xywrrm#p"));
75+
}
76+
77+
}
Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
packagecom.hadley.challenge30days;
2+
3+
/*
4+
2020.04.13
5+
We have a collection of stones, each stone has a positive integer weight.
6+
7+
Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:
8+
9+
If x == y, both stones are totally destroyed;
10+
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.
11+
At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)
12+
13+
14+
15+
Example 1:
16+
17+
Input: [2,7,4,1,8,1]
18+
Output: 1
19+
Explanation:
20+
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
21+
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
22+
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
23+
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.
24+
*/
25+
26+
importjava.util.ArrayList;
27+
importjava.util.Arrays;
28+
29+
publicclassLastStoneWeight {
30+
31+
//use iterator to delete one element in the list
32+
//link: https://blog.csdn.net/sinat_38301574/article/details/79601177?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-3&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-3
33+
publicintlastStoneWeight(int[]stones) {
34+
Arrays.sort(stones);
35+
if(stones.length ==1){
36+
returnstones[0];
37+
}elseif(stones.length ==0){
38+
return0;
39+
}else{
40+
inta =stones[stones.length-1];
41+
intb =stones[stones.length-2];
42+
if(a ==b){
43+
int[]newList =newint[stones.length-2];
44+
for(inti =0;i <stones.length-2;i++){
45+
newList[i] =stones[i];
46+
}
47+
returnlastStoneWeight(newList);
48+
}else{
49+
int[]newList =newint[stones.length-1];
50+
for(inti =0;i <stones.length-2;i++){
51+
newList[i] =stones[i];
52+
}
53+
newList[newList.length-1] =a -b;
54+
returnlastStoneWeight(newList);
55+
}
56+
57+
}
58+
}
59+
60+
//solution2:优先队列做法 link:https://www.cnblogs.com/fatttcat/p/11179442.html
61+
62+
publicstaticvoidmain(String[]args) {
63+
64+
Stringstr ="apple";
65+
char[]charList =str.toCharArray();
66+
67+
int[]resultList = {2,7,4,1,8,1};
68+
// Arrays.sort(resultList);
69+
// for(int i = 0; i < resultList.length; i++){
70+
// System.out.println(resultList[i]);
71+
// }
72+
LastStoneWeightlsw =newLastStoneWeight();
73+
System.out.println(lsw.lastStoneWeight(resultList));
74+
75+
}
76+
}
Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
packagecom.hadley.challenge30days;
2+
3+
importjava.util.ArrayList;
4+
5+
/*
6+
2020.04.10
7+
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
8+
9+
push(x) -- Push element x onto stack.
10+
pop() -- Removes the element on top of the stack.
11+
top() -- Get the top element.
12+
getMin() -- Retrieve the minimum element in the stack.
13+
14+
15+
Example:
16+
17+
MinStack minStack = new MinStack();
18+
minStack.push(-2);
19+
minStack.push(0);
20+
minStack.push(-3);
21+
minStack.getMin(); --> Returns -3.
22+
minStack.pop();
23+
minStack.top(); --> Returns 0.
24+
minStack.getMin(); --> Returns -2.
25+
*/
26+
publicclassMinStack {
27+
ArrayList<Integer>stack =newArrayList<>();
28+
ArrayList<Integer>minStack =newArrayList<>();
29+
30+
/** initialize your data structure here. */
31+
publicMinStack() {
32+
33+
}
34+
35+
publicvoidpush(intx) {
36+
stack.add(x);
37+
if(minStack.isEmpty() ||minStack.get(minStack.size()-1) >=x ){
38+
minStack.add(x);
39+
}
40+
}
41+
42+
publicvoidpop() {
43+
if(stack.isEmpty())return;
44+
intelem =stack.remove(stack.size()-1);
45+
if(!minStack.isEmpty() &&elem ==minStack.get(minStack.size()-1)){
46+
minStack.remove(minStack.size()-1);
47+
}
48+
}
49+
50+
publicinttop() {
51+
if(!stack.isEmpty()){
52+
returnstack.get(stack.size()-1);
53+
}
54+
return0;
55+
}
56+
57+
publicintgetMin() {
58+
if(!minStack.isEmpty()){
59+
returnminStack.get(minStack.size()-1);
60+
}
61+
return0;
62+
}
63+
}

0 commit comments

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