Skip to content

Commit 6b4da91

Browse files
varunu28varunu28
committed
Added 1 solution & modified 6 solutions
1 parent f780f37 commit 6b4da91

7 files changed

+192
-177
lines changed

‎Easy/Reverse words in a String III.java

Lines changed: 22 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,23 @@
1-
public class Solution {
2-
public String reverseWords(String s) {
3-
String[] words=s.split("\\s");
4-
for (int i=0;i<words.length;i++) {
5-
StringBuilder input1 = new StringBuilder();
6-
input1.append(words[i]);
7-
input1 = input1.reverse();
8-
words[i] = input1.toString();
9-
}
10-
return String.join(" ", words);
1+
class Solution {
2+
public String reverseWords(String s) {
3+
int idx = 0;
4+
int n = s.length();
5+
StringBuilder sb = new StringBuilder();
6+
int start = 0;
7+
while (idx < n) {
8+
while (idx < n && s.charAt(idx) != ' ') {
9+
idx++;
10+
}
11+
int curr = idx - 1;
12+
while (curr >= start) {
13+
sb.append(s.charAt(curr--));
14+
}
15+
if (idx != n) {
16+
sb.append(" ");
17+
}
18+
idx++;
19+
start = idx;
1120
}
12-
}
21+
return sb.toString();
22+
}
23+
}

‎Medium/Design Circular Deque.java

Lines changed: 95 additions & 107 deletions
Original file line numberDiff line numberDiff line change
@@ -1,118 +1,106 @@
11
class MyCircularDeque {
2+
DequeNode head;
3+
DequeNode tail;
4+
int k;
5+
int currCapacity;
26

3-
/** Initialize your data structure here. Set the size of the deque to be k. */
4-
Queue<Integer> main;
5-
Queue<Integer> backup;
6-
int capacity;
7-
8-
public MyCircularDeque(int k) {
9-
main = new LinkedList<>();
10-
backup = new LinkedList<>();
11-
capacity = k;
12-
}
13-
14-
/** Adds an item at the front of Deque. Return true if the operation is successful. */
15-
public boolean insertFront(int value) {
16-
if (main.size() == capacity) {
17-
return false;
18-
}
19-
20-
while(!main.isEmpty()) {
21-
backup.add(main.remove());
22-
}
23-
24-
main.add(value);
25-
26-
while (!backup.isEmpty()) {
27-
main.add(backup.remove());
28-
}
29-
30-
return true;
31-
}
32-
33-
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
34-
public boolean insertLast(int value) {
35-
if (main.size() == capacity) {
36-
return false;
37-
}
38-
39-
main.add(value);
40-
41-
return true;
42-
}
43-
44-
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
45-
public boolean deleteFront() {
46-
if (main.isEmpty()) {
47-
return false;
48-
}
49-
50-
main.remove();
51-
52-
return true;
7+
/** Initialize your data structure here. Set the size of the deque to be k. */
8+
public MyCircularDeque(int k) {
9+
currCapacity = 0;
10+
this.k = k;
11+
head = new DequeNode(-1);
12+
tail = new DequeNode(-1);
13+
head.front = tail;
14+
tail.back = head;
15+
}
16+
17+
/** Adds an item at the front of Deque. Return true if the operation is successful. */
18+
public boolean insertFront(int value) {
19+
if (isFull()) {
20+
return false;
5321
}
54-
55-
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
56-
public boolean deleteLast() {
57-
if (main.isEmpty()) {
58-
return false;
59-
}
60-
61-
while(!main.isEmpty()) {
62-
backup.add(main.remove());
63-
}
64-
65-
int size = backup.size();
66-
67-
while (size-- > 1) {
68-
main.add(backup.remove());
69-
}
70-
71-
backup.remove();
72-
73-
return true;
22+
DequeNode node = new DequeNode(value);
23+
node.front = head.front;
24+
head.front.back = node;
25+
node.back = head;
26+
head.front = node;
27+
currCapacity++;
28+
return true;
29+
}
30+
31+
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
32+
public boolean insertLast(int value) {
33+
if (isFull()) {
34+
return false;
7435
}
75-
76-
/** Get the front item from the deque. */
77-
public int getFront() {
78-
if (main.isEmpty()) {
79-
return -1;
80-
}
81-
82-
return main.peek();
36+
DequeNode node = new DequeNode(value);
37+
node.front = tail;
38+
node.back = tail.back;
39+
tail.back.front = node;
40+
tail.back = node;
41+
currCapacity++;
42+
return true;
43+
}
44+
45+
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
46+
public boolean deleteFront() {
47+
if (isEmpty()) {
48+
return false;
8349
}
84-
85-
/** Get the last item from the deque. */
86-
public int getRear() {
87-
if (main.isEmpty()) {
88-
return -1;
89-
}
90-
91-
while(!main.isEmpty()) {
92-
backup.add(main.remove());
93-
}
94-
95-
int size = backup.size();
96-
97-
while (size-- > 1) {
98-
main.add(backup.remove());
99-
}
100-
101-
int ans = backup.peek();
102-
main.add(backup.remove());
103-
104-
return ans;
50+
DequeNode next = head.front.front;
51+
head.front = next;
52+
next.back = head;
53+
currCapacity--;
54+
return true;
55+
}
56+
57+
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
58+
public boolean deleteLast() {
59+
if (isEmpty()) {
60+
return false;
10561
}
106-
107-
/** Checks whether the circular deque is empty or not. */
108-
public boolean isEmpty() {
109-
return main.isEmpty();
62+
DequeNode prev = tail.back.back;
63+
tail.back = prev;
64+
prev.front = tail;
65+
currCapacity--;
66+
return true;
67+
}
68+
69+
/** Get the front item from the deque. */
70+
public int getFront() {
71+
if (isEmpty()) {
72+
return -1;
11073
}
111-
112-
/** Checks whether the circular deque is full or not. */
113-
public boolean isFull() {
114-
return main.size() == capacity;
74+
return head.front.val;
75+
}
76+
77+
/** Get the last item from the deque. */
78+
public int getRear() {
79+
if (isEmpty()) {
80+
return -1;
11581
}
82+
return tail.back.val;
83+
}
84+
85+
/** Checks whether the circular deque is empty or not. */
86+
public boolean isEmpty() {
87+
return currCapacity == 0;
88+
}
89+
90+
/** Checks whether the circular deque is full or not. */
91+
public boolean isFull() {
92+
return currCapacity == k;
93+
}
94+
}
95+
96+
class DequeNode {
97+
int val;
98+
DequeNode front;
99+
DequeNode back;
100+
101+
public DequeNode(int val) {
102+
this.val = val;
103+
}
116104
}
117105

118106
/**

‎Medium/Find the duplicate number.java

Lines changed: 17 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,17 +1,20 @@
11
class Solution {
2-
public int findDuplicate(int[] nums) {
3-
int n = nums.length;
4-
int slow = n;
5-
int fast = n;
6-
do{
7-
slow = nums[slow-1];
8-
fast = nums[nums[fast-1]-1];
9-
}while (slow != fast);
10-
slow = n;
11-
while (slow != fast) {
12-
slow = nums[slow-1];
13-
fast = nums[fast-1];
14-
}
15-
return slow;
2+
public int findDuplicate(int[] nums) {
3+
int tortoise = nums[0];
4+
int hare = nums[0];
5+
while(true) {
6+
tortoise = nums[tortoise];
7+
hare = nums[nums[hare]];
8+
if (tortoise == hare) {
9+
break;
10+
}
1611
}
12+
int p1 = nums[0];
13+
int p2 = tortoise;
14+
while (p1 != p2) {
15+
p1 = nums[p1];
16+
p2 = nums[p2];
17+
}
18+
return p1;
19+
}
1720
}

‎Medium/Insufficient Nodes in Root to Leaf Paths.java

Lines changed: 10 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -8,18 +8,15 @@
88
* }
99
*/
1010
class Solution {
11-
public TreeNode sufficientSubset(TreeNode root, int limit) {
12-
if (root == null) {
13-
return null;
14-
}
15-
16-
if (root.left == null && root.right == null) {
17-
return root.val < limit ? null : root;
18-
}
19-
20-
root.left = sufficientSubset(root.left, limit - root.val);
21-
root.right = sufficientSubset(root.right, limit - root.val);
22-
23-
return root.left == root.right ? null : root;
11+
public TreeNode sufficientSubset(TreeNode root, int limit) {
12+
if (root == null) {
13+
return null;
2414
}
15+
if (root.left == null && root.right == null) {
16+
return root.val < limit ? null : root;
17+
}
18+
root.left = sufficientSubset(root.left, limit - root.val);
19+
root.right = sufficientSubset(root.right, limit - root.val);
20+
return root.left == root.right ? null : root;
21+
}
2522
}

‎Medium/Minimum Domino Rotations For Equal Row.java

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
class Solution {
2+
public int minDominoRotations(int[] A, int[] B) {
3+
int[] counterA = new int[7];
4+
int[] counterB = new int[7];
5+
int[] same = new int[7];
6+
int n = A.length;
7+
for (int i = 0; i < n; i++) {
8+
counterA[A[i]]++;
9+
counterB[B[i]]++;
10+
if (A[i] == B[i]) {
11+
same[A[i]]++;
12+
}
13+
}
14+
for (int i = 1; i < 7; i++) {
15+
if (counterA[i] + counterB[i] - same[i] == n) {
16+
return n - Math.max(counterA[i], counterB[i]);
17+
}
18+
}
19+
return -1;
20+
}
21+
}

‎Medium/Sum of Nodes with Even-Valued Grandparent.java

Lines changed: 9 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -8,22 +8,21 @@
88
* }
99
*/
1010
class Solution {
11+
int sum;
1112
public int sumEvenGrandparent(TreeNode root) {
12-
int[] ans = {0};
13-
helper(root, -1, -1, ans);
14-
return ans[0];
13+
sum = 0;
14+
helper(root, null, null);
15+
return sum;
1516
}
1617

17-
private void helper(TreeNode root, int parent, int grandparent, int[] ans) {
18+
private void helper(TreeNode root, TreeNode parent, TreeNode grandparent) {
1819
if (root == null) {
1920
return;
2021
}
21-
if (grandparent > 0 && grandparent % 2 == 0) {
22-
ans[0] += root.val;
22+
if (grandparent != null && grandparent.val % 2 == 0) {
23+
sum += root.val;
2324
}
24-
grandparent = parent;
25-
parent = root.val;
26-
helper(root.left, parent, grandparent, ans);
27-
helper(root.right, parent, grandparent, ans);
25+
helper(root.left, root, parent);
26+
helper(root.right, root, parent);
2827
}
2928
}

0 commit comments

Comments
 (0)