Skip to content

Commit 5807f89

Browse files
yanglbmeyanglbme
authored
Merge branch 'master' into master
2 parents c502da8 + a2eec02 commit 5807f89

13 files changed

+388
-139
lines changed

‎DataStructures/Lists/SinglyLinkedList.java

Lines changed: 72 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -54,20 +54,16 @@ public void insert(int data) {
5454
* @param data data to be stored in a new node
5555
* @param position position at which a new node is to be inserted
5656
*/
57-
5857
public void insertNth(int data, int position) {
59-
if (position < 0 || position > getSize()) {
60-
throw new IndexOutOfBoundsException("position less than zero or position more than the count of list");
61-
} else {
62-
Node cur = head;
63-
Node node = new Node(data);
64-
for (int i = 0; i < position; ++i) {
65-
cur = cur.next;
66-
}
67-
node.next = cur.next;
68-
cur.next = node;
69-
size++;
58+
checkBounds(position, 0, size);
59+
Node cur = head;
60+
for (int i = 0; i < position; ++i) {
61+
cur = cur.next;
7062
}
63+
Node node = new Node(data);
64+
node.next = cur.next;
65+
cur.next = node;
66+
size++;
7167
}
7268

7369
/**
@@ -90,41 +86,57 @@ public void delete() {
9086
* This method deletes an element at Nth position
9187
*/
9288
public void deleteNth(int position) {
93-
if (position < 0 || position > size - 1) {
94-
throw new IndexOutOfBoundsException("position less than zero or position more than the count of list");
95-
} else {
96-
Node cur = head;
97-
for (int i = 0; i < position; ++i) {
98-
cur = cur.next;
99-
}
100-
101-
Node destroy = cur.next;
102-
cur.next = cur.next.next;
103-
destroy = null; // clear to let GC do its work
104-
105-
size--;
89+
checkBounds(position, 0, size - 1);
90+
Node cur = head;
91+
for (int i = 0; i < position; ++i) {
92+
cur = cur.next;
10693
}
94+
95+
Node destroy = cur.next;
96+
cur.next = cur.next.next;
97+
destroy = null; // clear to let GC do its work
98+
99+
size--;
107100
}
108101

109102
/**
110-
* Checks if the list is empty
111-
*
112-
* @return true is list is empty
103+
* @param position to check position
104+
* @param low low index
105+
* @param high high index
106+
* @throws IndexOutOfBoundsException if {@code position} not in range {@code low} to {@code high}
113107
*/
114-
public boolean isEmpty() {
115-
return size == 0;
108+
public void checkBounds(int position, int low, int high) {
109+
if (position < low || position > high) {
110+
throw new IndexOutOfBoundsException(position + "");
111+
}
116112
}
117113

118114
/**
119-
* Prints contents of the list
115+
* clear all nodes in list
120116
*/
121-
public void display() {
122-
Node current = head.next;
123-
while (current != null) {
124-
System.out.print(current.value + " ");
125-
current = current.next;
117+
public void clear() {
118+
if (size == 0) {
119+
return;
126120
}
127-
System.out.println();
121+
Node prev = head.next;
122+
Node cur = prev.next;
123+
while (cur != null) {
124+
prev = null; // clear to let GC do its work
125+
prev = cur;
126+
cur = cur.next;
127+
}
128+
prev = null;
129+
head.next = null;
130+
size = 0;
131+
}
132+
133+
/**
134+
* Checks if the list is empty
135+
*
136+
* @return true is list is empty
137+
*/
138+
public boolean isEmpty() {
139+
return size == 0;
128140
}
129141

130142
/**
@@ -134,6 +146,20 @@ public int getSize() {
134146
return size;
135147
}
136148

149+
@Override
150+
public String toString() {
151+
if (size == 0) {
152+
return "";
153+
}
154+
StringBuilder builder = new StringBuilder();
155+
Node cur = head.next;
156+
while (cur != null) {
157+
builder.append(cur.value).append("->");
158+
cur = cur.next;
159+
}
160+
return builder.replace(builder.length() - 2, builder.length(), "").toString();
161+
}
162+
137163
/**
138164
* Main method
139165
*
@@ -148,19 +174,24 @@ public static void main(String args[]) {
148174
myList.insertHead(7);
149175
myList.insertHead(10);
150176

151-
myList.display(); // 10 -> 7 -> 5
177+
System.out.println(myList);; // 10 -> 7 -> 5
152178

153179
myList.deleteHead();
154180

155-
myList.display(); // 7 -> 5
181+
System.out.println(myList);; // 7 -> 5
156182

157183
myList.insertNth(11, 2);
158184

159-
myList.display(); // 7 -> 5 -> 11
185+
System.out.println(myList);; // 7 -> 5 -> 11
160186

161187
myList.deleteNth(1);
162188

163-
myList.display(); // 7-> 11
189+
System.out.println(myList);; // 7-> 11
190+
191+
myList.clear();
192+
assert myList.isEmpty();
193+
194+
System.out.println(myList); // ""
164195

165196
}
166197
}

‎DataStructures/Stacks/BalancedBrackets.java

Lines changed: 46 additions & 50 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,8 @@
1-
package data_structures.Stacks;
1+
package DataStructures.Stacks;
22

3-
import java.util.Scanner;
43
import java.util.Stack;
54

65
/**
7-
*
86
* The nested brackets problem is a problem that determines if a sequence of
97
* brackets are properly nested. A sequence of brackets s is considered properly
108
* nested if any of the following conditions are true: - s is empty - s has the
@@ -15,71 +13,69 @@
1513
* returns true if S is nested and false otherwise.
1614
*
1715
* @author akshay sharma
18-
* @date: 2017-10-17
1916
* @author <a href="https://github.com/khalil2535">khalil2535<a>
20-
*
17+
* @author shellhub
2118
*/
2219
class BalancedBrackets {
2320

2421
/**
22+
* Check if {@code leftBracket} and {@code rightBracket} is paired or not
23+
*
24+
* @param leftBracket left bracket
25+
* @param rightBracket right bracket
26+
* @return {@code true} if {@code leftBracket} and {@code rightBracket} is paired,
27+
* otherwise {@code false}
28+
*/
29+
public static boolean isPaired(char leftBracket, char rightBracket) {
30+
char[][] pairedBrackets = {
31+
{'(', ')'},
32+
{'[', ']'},
33+
{'{', '}'},
34+
{'<', '>'}
35+
};
36+
for (char[] pairedBracket : pairedBrackets) {
37+
if (pairedBracket[0] == leftBracket && pairedBracket[1] == rightBracket) {
38+
return true;
39+
}
40+
}
41+
return false;
42+
}
43+
44+
/**
45+
* Check if {@code brackets} is balanced
2546
*
26-
* @param s
27-
* @return
47+
* @param brackets the brackets
48+
* @return {@code true} if {@code brackets} is balanced, otherwise {@code false}
2849
*/
29-
static boolean is_balanced(String s) {
50+
public static boolean isBalanced(String brackets) {
51+
if (brackets == null) {
52+
throw new IllegalArgumentException("brackets is null");
53+
}
3054
Stack<Character> bracketsStack = new Stack<>();
31-
char[] text = s.toCharArray();
32-
for (char x : text) {
33-
switch (x) {
34-
case '{':
35-
case '<':
55+
for (char bracket : brackets.toCharArray()) {
56+
switch (bracket) {
3657
case '(':
3758
case '[':
38-
bracketsStack.push(x);
59+
case '{':
60+
bracketsStack.push(bracket);
3961
break;
40-
case '}':
41-
if (!bracketsStack.empty() && bracketsStack.pop() == '{') {
42-
break;
43-
} else {
44-
return false;
45-
}
46-
case '>':
47-
if (!bracketsStack.empty() && bracketsStack.pop() == '<') {
48-
break;
49-
} else {
50-
return false;
51-
}
5262
case ')':
53-
if (!bracketsStack.empty() && bracketsStack.pop() == '(') {
54-
break;
55-
} else {
56-
return false;
57-
}
5863
case ']':
59-
if (!bracketsStack.empty() && bracketsStack.pop() == '[') {
60-
break;
61-
} else {
64+
case '}':
65+
if (!(!bracketsStack.isEmpty() && isPaired(bracketsStack.pop(), bracket))) {
6266
return false;
6367
}
68+
break;
69+
default: /* other character is invalid */
70+
return false;
6471
}
6572
}
66-
return bracketsStack.empty();
73+
return bracketsStack.isEmpty();
6774
}
6875

69-
/**
70-
*
71-
* @param args
72-
* @TODO remove main method and Test using JUnit or other methodology
73-
*/
74-
public static void main(String args[]) {
75-
try (Scanner in = new Scanner(System.in)) {
76-
System.out.println("Enter sequence of brackets: ");
77-
String s = in.nextLine();
78-
if (is_balanced(s)) {
79-
System.out.println(s + " is balanced");
80-
} else {
81-
System.out.println(s + " ain't balanced");
82-
}
83-
}
76+
77+
public static void main(String[] args) {
78+
assert isBalanced("[()]{}{[()()]()}");
79+
assert !isBalanced("[(])");
8480
}
8581
}

‎DataStructures/Stacks/DecimalToAnyUsingStack.java

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package DataStructures.Stacks;
2+
3+
import java.util.Stack;
4+
5+
public class DecimalToAnyUsingStack {
6+
public static void main(String[] args) {
7+
assert convert(0, 2).equals("0");
8+
assert convert(30, 2).equals("11110");
9+
assert convert(30, 8).equals("36");
10+
assert convert(30, 10).equals("30");
11+
assert convert(30, 16).equals("1E");
12+
}
13+
14+
/**
15+
* Convert decimal number to another radix
16+
*
17+
* @param number the number to be converted
18+
* @param radix the radix
19+
* @return another radix
20+
* @throws ArithmeticException if <tt>number</tt> or <tt>radius</tt> is invalid
21+
*/
22+
private static String convert(int number, int radix) {
23+
if (radix < 2 || radix > 16) {
24+
throw new ArithmeticException(
25+
String.format("Invalid input -> number:%d,radius:%d", number, radix));
26+
}
27+
char[] tables = {
28+
'0', '1', '2', '3', '4',
29+
'5', '6', '7', '8', '9',
30+
'A', 'B', 'C', 'D', 'E', 'F'
31+
};
32+
Stack<Character> bits = new Stack<>();
33+
do {
34+
bits.push(tables[number % radix]);
35+
number = number / radix;
36+
} while (number != 0);
37+
38+
StringBuilder result = new StringBuilder();
39+
while (!bits.isEmpty()) {
40+
result.append(bits.pop());
41+
}
42+
return result.toString();
43+
}
44+
}

0 commit comments

Comments
 (0)