Skip to content

Commit e511be1

Browse files
varunu28varunu28
committed
Modified 6 solutions
1 parent 6219c7f commit e511be1

6 files changed

Lines changed: 126 additions & 98 deletions

‎Easy/Climbing Stairs.java‎

Lines changed: 17 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,20 @@
11
class Solution {
2-
public int climbStairs(int n) {
3-
if (n == 1) return 1;
4-
if (n == 2) return 2;
5-
6-
int oneStep = 2;
7-
int twoStep = 1;
8-
int all = 0;
9-
10-
for (int i=2;i<n;i++) {
11-
all = oneStep + twoStep;
12-
twoStep = oneStep;
13-
oneStep = all;
14-
}
15-
16-
return all;
2+
int[] memo;
3+
public int climbStairs(int n) {
4+
if (n == 1) {
5+
return 1;
176
}
7+
memo = new int[n + 1];
8+
memo[1] = 1;
9+
memo[2] = 2;
10+
return helper(n);
11+
}
12+
13+
private int helper(int n) {
14+
if (memo[n] != 0) {
15+
return memo[n];
16+
}
17+
memo[n] = helper(n - 1) + helper(n - 2);
18+
return memo[n];
19+
}
1820
}

‎Easy/Find All Numbers Disappeared in an Array.java‎

Lines changed: 16 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,17 @@
1-
public class Solution {
2-
public List<Integer> findDisappearedNumbers(int[] nums) {
3-
List<Integer> ans = new ArrayList<Integer>();
4-
5-
for(int i = 0; i < nums.length; i++) {
6-
int val = Math.abs(nums[i]) - 1;
7-
if(nums[val] > 0) {
8-
nums[val] = -nums[val];
9-
}
10-
}
11-
12-
for(int i = 0; i < nums.length; i++) {
13-
if(nums[i] > 0) {
14-
ans.add(i+1);
15-
}
16-
}
17-
return ans;
1+
class Solution {
2+
public List<Integer> findDisappearedNumbers(int[] nums) {
3+
for (int i = 0; i < nums.length; i++) {
4+
int newIdx = Math.abs(nums[i]) - 1;
5+
if (nums[newIdx] > 0) {
6+
nums[newIdx] *= -1;
7+
}
188
}
19-
}
9+
List<Integer> list = new ArrayList<>();
10+
for (int i = 1; i <= nums.length; i++) {
11+
if (nums[i - 1] > 0) {
12+
list.add(i);
13+
}
14+
}
15+
return list;
16+
}
17+
}

‎Easy/Maximum 69 Number.java‎

Lines changed: 17 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,23 @@
11
class Solution {
22
public int maximum69Number (int num) {
3-
char[] chars = String.valueOf(num).toCharArray();
4-
for (int i = 0; i < chars.length; i++) {
5-
if (chars[i] == '6') {
6-
chars[i] = '9';
7-
break;
3+
int lastSixIndex = Integer.MAX_VALUE;
4+
int count = 0;
5+
int copy = num;
6+
while (copy > 0) {
7+
int rem = copy % 10;
8+
if (rem == 6) {
9+
lastSixIndex = count;
810
}
11+
copy /= 10;
12+
count++;
913
}
10-
return Integer.parseInt(String.valueOf(chars));
14+
if (lastSixIndex == Integer.MAX_VALUE) {
15+
return num;
16+
}
17+
return (
18+
((num / ((int) Math.pow(10, lastSixIndex + 1))) * ((int) Math.pow(10, lastSixIndex + 1))) +
19+
(9 * ((int) Math.pow(10, lastSixIndex))) +
20+
(num % ((int) Math.pow(10, lastSixIndex)))
21+
);
1122
}
1223
}

‎Easy/Nested List Weight Sum.java‎

Lines changed: 22 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -27,21 +27,29 @@
2727
* }
2828
*/
2929
class Solution {
30-
int sum;
31-
public int depthSum(List<NestedInteger> nestedList) {
32-
sum = 0;
33-
helper(nestedList, 1);
34-
return sum;
30+
public int depthSum(List<NestedInteger> nestedList) {
31+
int level = 1;
32+
Queue<NestedInteger> queue = new LinkedList<>();
33+
int sum = 0;
34+
for (NestedInteger nestedInteger : nestedList) {
35+
queue.add(nestedInteger);
3536
}
36-
37-
private void helper(List<NestedInteger> nestedList, int level) {
38-
for (NestedInteger nested : nestedList) {
39-
if (nested.isInteger()) {
40-
sum += nested.getInteger() * level;
41-
}
42-
else {
43-
helper(nested.getList(), level + 1);
44-
}
37+
while (!queue.isEmpty()) {
38+
int size = queue.size();
39+
while (size-- > 0) {
40+
NestedInteger nestedInteger = queue.remove();
41+
if (nestedInteger.isInteger()) {
42+
sum += nestedInteger.getInteger() * level;
4543
}
44+
else {
45+
List<NestedInteger> nList = nestedInteger.getList();
46+
for (NestedInteger nInteger : nList) {
47+
queue.add(nInteger);
48+
}
49+
}
50+
}
51+
level++;
4652
}
53+
return sum;
54+
}
4755
}

‎Easy/Squares of a Sorted Array.java‎

Lines changed: 31 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -1,21 +1,35 @@
11
class Solution {
2-
public int[] sortedSquares(int[] A) {
3-
int[] arr = new int[A.length];
4-
int start = 0;
5-
int end = A.length - 1;
6-
int idx = A.length - 1;
7-
8-
while (start <= end) {
9-
if (Math.abs(A[start]) < Math.abs(A[end])) {
10-
arr[idx--] = A[end] * A[end];
11-
end--;
12-
}
13-
else {
14-
arr[idx--] = A[start] * A[start];
15-
start++;
16-
}
2+
public int[] sortedSquares(int[] A) {
3+
int posIdx = A.length;
4+
for (int i = 0; i < A.length; i++) {
5+
if (A[i] >= 0) {
6+
posIdx = i;
7+
break;
8+
}
9+
}
10+
int[] ans = new int[A.length];
11+
int negIdx = posIdx - 1;
12+
int idx = 0;
13+
while (negIdx >= 0 || posIdx < A.length) {
14+
if (negIdx >= 0 && (posIdx >= 0 && posIdx < A.length)) {
15+
if (A[negIdx] * A[negIdx] > A[posIdx] * A[posIdx]) {
16+
ans[idx++] = A[posIdx] * A[posIdx];
17+
posIdx++;
18+
}
19+
else {
20+
ans[idx++] = A[negIdx] * A[negIdx];
21+
negIdx--;
1722
}
18-
19-
return arr;
23+
}
24+
else if (negIdx >= 0 && posIdx >= A.length) {
25+
ans[idx++] = A[negIdx] * A[negIdx];
26+
negIdx--;
27+
}
28+
else {
29+
ans[idx++] = A[posIdx] * A[posIdx];
30+
posIdx++;
31+
}
2032
}
33+
return ans;
34+
}
2135
}

‎Medium/Nested List Weight Sum II.java‎

Lines changed: 23 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -27,36 +27,31 @@
2727
* }
2828
*/
2929
class Solution {
30-
int maxDepth;
31-
int sum;
32-
public int depthSumInverse(List<NestedInteger> nestedList) {
33-
maxDepth = 0;
34-
maxDepthHelper(nestedList, 1);
35-
36-
sum = 0;
37-
helper(nestedList, maxDepth);
38-
39-
return sum;
30+
public int depthSumInverse(List<NestedInteger> nestedList) {
31+
Queue<NestedInteger> queue = new LinkedList<>();
32+
int prevSum = 0;
33+
int currSum = 0;
34+
for (NestedInteger nestedInteger : nestedList) {
35+
queue.add(nestedInteger);
4036
}
41-
42-
private void helper(List<NestedInteger> nestedList, int level) {
43-
for (NestedInteger nested : nestedList) {
44-
if (nested.isInteger()) {
45-
sum += nested.getInteger() * level;
46-
}
47-
else {
48-
helper(nested.getList(), level - 1);
49-
}
37+
while (!queue.isEmpty()) {
38+
int size = queue.size();
39+
int levelSum = 0;
40+
while (size-- > 0) {
41+
NestedInteger removed = queue.remove();
42+
if (removed.isInteger()) {
43+
levelSum += removed.getInteger();
5044
}
51-
}
52-
53-
private void maxDepthHelper(List<NestedInteger> nestedList, int currLevel) {
54-
maxDepth = Math.max(maxDepth, currLevel);
55-
56-
for (NestedInteger nestedInteger : nestedList) {
57-
if (!nestedInteger.isInteger()) {
58-
maxDepthHelper(nestedInteger.getList(), currLevel + 1);
59-
}
45+
else {
46+
List<NestedInteger> nList = removed.getList();
47+
for (NestedInteger nInteger : nList) {
48+
queue.add(nInteger);
49+
}
6050
}
51+
}
52+
prevSum += levelSum;
53+
currSum += prevSum;
6154
}
55+
return currSum;
56+
}
6257
}

0 commit comments

Comments
 (0)