8000 add personal lc solutions · emon535/best-leetcode-resources@635708c · GitHub
[go: up one dir, main page]
Skip to content

Commit 635708c

Browse files
armankhondkerarmankhondker
authored
add personal lc solutions
1 parent b93a709 commit 635708c

12 files changed

+628
-32
lines changed

‎leetcode-solutions/BasicCalculator.java

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
Given a string s representing a valid expression, implement a basic calculator to evaluate it,
2+
and return the result of the evaluation.
3+
4+
Example 1:
5+
6+
Input: s = "1 + 1"
7+
Output: 2
8+
Example 2:
9+
10+
Input: s = " 2-1 + 2 "
11+
Output: 3
12+
Example 3:
13+
14+
Input: s = "(1+(4+5+2)-3)+(6+8)"
15+
Output: 23
16+
17+
USE A Stack
18+
TC: O(N)
19+
SC: O(N)
20+
21+
class Solution {
22+
public static int calculate(String s) {
23+
int len = s.length(), sign = 1, result = 0;
24+
Stack<Integer> stack = new Stack<Integer>();
25+
for (int i = 0; i < len; i++) {
26+
if (Character.isDigit(s.charAt(i))) {
27+
int sum = s.charAt(i) - '0';
28+
while (i + 1 < len && Character.isDigit(s.charAt(i + 1))) {
29+
sum = sum * 10 + s.charAt(i + 1) - '0';
30+
i++;
31+
}
32+
result += sum * sign;
33+
} else if (s.charAt(i) == '+')
34+
sign = 1;
35+
else if (s.charAt(i) == '-')
36+
sign = -1;
37+
else if (s.charAt(i) == '(') {
38+
stack.push(result);
39+
stack.push(sign);
40+
result = 0;
41+
sign = 1;
42+
} else if (s.charAt(i) == ')') {
43+
result = result * stack.pop() + stack.pop();
44+
}
45+
46+
}
47+
return result;
48+
}
49+
}

‎leetcode-solutions/addStrings.java

Lines changed: 17 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -1,44 +1,33 @@
1-
Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
1+
// Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
22

3-
Note:
3+
// Note:
44

5-
The length of both num1 and num2 is < 5100.
6-
Both num1 and num2 contains only digits 0-9.
7-
Both num1 and num2 does not contain any leading zero.
8-
You must not use any built-in BigInteger library or convert the inputs to integer directly.
5+
// The length of both num1 and num2 is < 5100.
6+
// Both num1 and num2 contains only digits 0-9.
7+
// Both num1 and num2 does not contain any leading zero.
8+
// You must not use any built-in BigInteger library or convert the inputs to integer directly.
99

1010
//TC: O(n) where n is max length of two arrays, because we loop through them bothß
1111
//SC: O(n) where n is max length between num1 and num2 to store char array
1212
class Solution {
1313
public String addStrings(String num1, String num2) {
14-
char[] nums1 = num1.toCharArray();
15-
char[] nums2 = num2.toCharArray();
16-
17-
StringBuilder sb = new StringBuilder();
18-
19-
int carry = 0;
20-
21-
int i =nums1.length-1;
22-
int j =nums2.length-1;
23-
24-
while(i>=0 || j>=0){
25-
int sum = carry;
14+
int i=num1.length()-1;
15+
int j = num2.length() -1;
16+
int carry = 0;
17+
StringBuilder res = new StringBuilder();
18+
while(i>=0 || j>=0 || carry > 0){
19+
int sum = carry;
2620
if(i>=0){
27-
sum+= nums1[i] - '0';
21+
sum += num1.charAt(i) - '0';
2822
i--;
2923
}
3024
if(j>=0){
31-
sum+= nums2[j] -'0';
25+
sum+=num2.charAt(j) - '0';
3226
j--;
3327
}
34-
carry = sum/10;
35-
sb.append(sum%10);
28+
carry = sum/10;
29+
res.append(sum%10);
3630
}
37-
if(carry >0){
38-
sb.append(carry);
39-
}
40-
41-
sb.reverse();
42-
return sb.toString();
31+
return res.reverse().toString();
4332
}
4433
}

‎leetcode-solutions/basicCalculatorII.java

Lines changed: 38 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -17,7 +17,9 @@
1717
// Output: 5
1818

1919

20-
USE A STACK
20+
USE A STACK and keep track of sign
21+
TC: O(N) where N is length of string
22+
SC: O(N) where N is length of string
2123

2224
public class Solution {
2325
public int calculate(String s) {
@@ -49,9 +51,41 @@ public int calculate(String s) {
4951
}
5052

5153
int re = 0;
52-
for(int i:stack){
53-
re += i;
54+
while(!stack.isEmpty()){
55+
re += s.pop();
5456
}
5557
return re;
5658
}
57-
}
59+
}
60+
61+
OPTIMIZED without the stack, use a "LAST NUMBER" to represent the stack
62+
TC: O(N)
63+
SC: O(1)
64+
class Solution {
65+
public int calculate(String s) {
66+
if (s == null || s.isEmpty()) return 0;
67+
int length = s.length();
68+
int currentNumber = 0, lastNumber = 0, result = 0;
69+
char operation = '+';
70+
for (int i = 0; i < length; i++) {
71+
char currentChar = s.charAt(i);
72+
if (Character.isDigit(currentChar)) {
73+
currentNumber = (currentNumber * 10) + (currentChar - '0');
74+
}
75+
if (!Character.isDigit(currentChar) && !Character.isWhitespace(currentChar) || i == length - 1) {
76+
if (operation == '+' || operation == '-') {
77+
result += lastNumber;
78+
lastNumber = (operation == '+') ? currentNumber : -currentNumber;
79+
} else if (operation == '*') {
80+
lastNumber = lastNumber * currentNumber;
81+
} else if (operation == '/') {
82+
lastNumber = lastNumber / currentNumber;
83+
}
84+
operation = currentChar;
85+
currentNumber = 0;
86+
}
87+
}
88+
result += lastNumber;
89+
return result;
90+
}
91+
}

‎leetcode-solutions/checkIfTwoStringAreEquivalent.java

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
Given two string arrays word1 and word2, return true if the two arrays represent the same string, and false otherwise.
2+
3+
A string is represented by an array if the array elements concatenated in order forms the string.
4+
5+
BUILD UP TWO STRINGS and compare, can use stringbuilder
6+
7+
TC: O(N)
8+
SC: O(N)
9+
class Solution {
10+
public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
11+
StringBuilder sb = new StringBuilder();
12+
StringBuilder sb2 = new StringBuilder();
13+
for(String s: word1){
14+
sb.append(s);
15+
}
16+
for(String s: word2){
17+
sb2.append(s);
18+
}
19+
20+
return sb.toString().equals(sb2.toString());
21+
}
22+
}
23+
24+
25+
OPTMIZED, TWO POINTER, USE two nested pointers
26+
27+
1) set of pointers for ith string we are on
28+
2) set of pointers for the first char we are currently on, which we will reset to 0
29+
30+
TC: O(N)
31+
SC: O(1)
32+
33+
public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
34+
int p1 = 0, p2 = 0; // inner pointer for chars
35+
int w1 = 0, w2 = 0; // outer pointer for the string we are on
36+
37+
while (w1 < word1.length && w2 < word2.length) {
38+
String curr1 = word1[w1], curr2 = word2[w2];
39+
40+
if (curr1.charAt(p1) != curr2.charAt(p2)) return false;
41+
42+
if (p1 < curr1.length() - 1) {
43+
p1++;
44+
} else {
45+
p1 = 0;
46+
w1++;
47+
}
48+
49+
if (p2 < curr2.length() - 1) {
50+
p2++;
51+
} else {
52+
p2 = 0;
53+
w2++;
54+
}
55+
}
56+
57+
return w1 == word1.length && w2 == word2.length;

‎leetcode-solutions/cloestBinarySearchTreeValue.java

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target.
2+
If there are multiple answers, print the smallest.
3+
4+
5+
Run binary search, since we are given a BST
6+
NOTE doesn't take care of printing smallest case
7+
8+
TC: O(LogN)
9+
SC: O(1)
10+
11+
class Solution {
12+
public int closestValue(TreeNode root, double target) {
13+
//binary search
14+
if(root == null) return 0;
15+
int closestVal = root.val;
16+
while(root != null){
17+
if(Math.abs(target - root.val) < Math.abs(target - closestVal)){
18+
closestVal = root.val; //UPDATE newly found closest value
19+
}
20+
21+
22+
if (root.val > target){ //binary serach on left
23+
root = root.left;
24+
} else { //binary search on right
25+
root = root.right;
26+
}
27+
}
28+
return closestVal;
29+
}
30+
}
31+
32+
FIX TO HANDLE PRINTING SMALLEST IF DIFFERENCE IS THE SAME
33+
34+
class Solution {
35+
public int closestValue(TreeNode root, double target) {
36+
int val = root.val;
37+
int closest = root.val;
38+
while(root!=null){
39+
val = root.val;
40+
if(Math.abs(target - val) < Math.abs(target-closest)){
41+
closest=val;
42+
} else if(Math.abs(target - val) == Math.abs(target-closest) && val < closest){
43+
closest=val;
44+
}
45+
if(root.val > target){
46+
root=root.left;
47+
} else {
48+
root=root.right;
49+
}
50+
51+
}
52+
return closest;
53+
}
54+
}

‎leetcode-solutions/commonlyUsedCode.java

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
Pair<TreeNode, Integer> p = new Pair<>();
2+
key = p.getKey();
3+
value = p.getValue();
4+
5+
Collections.sort(toSort, (a,b)->b-a);
6+
Collections.reverse(array);
7+
8+
double total = 10;
9+
Math.random()*total
10+
11+
HashMap<Integer, Integer> map = new HashMap<>();
12+
map.getOrDefault(i, 0);
13+
for(int x: map.keySet()){
14+
}
15+
16+
String s = "arman khondker"
17+
String [] sa = s.split("a") //[rm, n khondker]
18+
19+
Deque<Integer> q = new ArrayDeque<>(); //can be used as both a stack and a queue
20+
q.removeFirst() //removes the first element
21+
q.removeLast(); removes the last element
22+
q.pollFirst();
23+
q.pollLast();
24+
*** q.poll() //it treats as queue (not a stack) and polls the first element!
25+
26+
String Concatenation
27+
one line concatenation with "+" and StringBuilder.append() generate exactly the same bytecode.
28+
exceptions :
29+
multithreaded environment : StringBuffer
30+
concatenation inside of loops : StringBuilder/StringBuffer
31+
32+
int[][] dirs = new int[]{{-1,0}, {1, 0}, {0, 1}, {0,-1}}
33+
34+
throw new IllegalArgumentException("Invalid input as p and q are guaranteed to exist");
35+
36+
String [] split = path.split("/")
37+
38+
39+
if(arr[1].equals("start")) //STRING COMPARISON USE .equals
40+
41+
Integer.parseInt(s); //to convert from STRING to int. valueOf(s) is used to convert to Integer
42+
43+
44+
45+
Algorithms
46+
47+
QuickSort (uses QuickSelect method, Java uses under the hood)
48+
TC: O(N) in average case, O(N^2) worst case when we select the pivot in bad position
49+
SC: O(logN)
50+
51+
Morris Traversal
52+
can traverse a tree in O(N) time
53+
54+
Union Find
55+
an algorithm for finding connected components in a graph

0 commit comments

Comments
 (0)
0