Skip to content

Commit f31acbe

Browse files
mission-peacemission-peace
committed
Bunch of leetcode qs
1 parent 3a16191 commit f31acbe

40 files changed

Lines changed: 1931 additions & 0 deletions

‎src/com/interview/array/HIndex.java‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package com.interview.array;
2+
3+
/**
4+
* Given an array of citations (each citation is a non-negative integer) of a researcher,
5+
* write a function to compute the researcher's h-index.
6+
* https://leetcode.com/problems/h-index/
7+
*/
8+
public class HIndex {
9+
public int hIndex(int[] citations) {
10+
int[] count = new int[citations.length + 1];
11+
for (int c : citations) {
12+
if (c <= citations.length) {
13+
count[c]++;
14+
} else {
15+
count[citations.length]++;
16+
}
17+
}
18+
19+
int sum = 0;
20+
int max = 0;
21+
for (int i = 0; i < count.length; i++) {
22+
sum += count[i];
23+
//we are trying to see if i is answer.
24+
//already everything before i has less than i citations.
25+
//so only thing to check is that p >= i where p is
26+
//total number of papers with i or more citations.
27+
int p = citations.length - sum + count[i];
28+
if (i <= p) {
29+
max = i;
30+
}
31+
}
32+
return max;
33+
}
34+
35+
public static void main(String args[]) {
36+
HIndex hi = new HIndex();
37+
int[] input = {0, 1, 1, 1, 1, 6, 7 ,8};
38+
System.out.print(hi.hIndex(input));
39+
}
40+
}
41+
42+
//0 1 2 6 6 6 6 7
43+
//0 1 2 3 4 5 6 7
44+
//0 1 1 1 3 6 7 8
45+
//0 1 2 3 4 5 6 7
46+
47+
//0 1 2 5 6

‎src/com/interview/array/LongestSubstringWithAtMost2Char.java‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package com.interview.array;
2+
3+
/**
4+
* Longest Substring with At Most Two Distinct Characters
5+
* https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/
6+
*/
7+
public class LongestSubstringWithAtMost2Char {
8+
public int lengthOfLongestSubstringTwoDistinct(String s) {
9+
int count1 = 0;
10+
int count2 = 0;
11+
char c1 = 0;
12+
char c2 = 0;
13+
int start = 0;
14+
int current = 0;
15+
int max = 0;
16+
for (char ch: s.toCharArray()) {
17+
if (ch == c1 || ch == c2) {
18+
if (ch == c1) {
19+
count1++;
20+
} else {
21+
count2++;
22+
}
23+
} else {
24+
if (count1 != 0 && count2 != 0) {
25+
while (start < current) {
26+
if (s.charAt(start) == c1) {
27+
count1--;
28+
} else if (s.charAt(start) == c2) {
29+
count2--;
30+
}
31+
start++;
32+
if (count1 == 0 || count2 == 0) {
33+
break;
34+
}
35+
}
36+
}
37+
if (count1 == 0) {
38+
c1 = ch;
39+
count1 = 1;
40+
} else {
41+
c2 = ch;
42+
count2 = 1;
43+
}
44+
}
45+
max = Math.max(max, current - start + 1);
46+
current++;
47+
}
48+
return max;
49+
}
50+
51+
public static void main(String args[]) {
52+
LongestSubstringWithAtMost2Char lc = new LongestSubstringWithAtMost2Char();
53+
System.out.print(lc.lengthOfLongestSubstringTwoDistinct("eceba"));
54+
}
55+
}

‎src/com/interview/array/SelfCrossing.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package com.interview.array;
2+
3+
/**
4+
* Created by tushar_v_roy on 3/10/16.
5+
*/
6+
public class SelfCrossing {
7+
8+
public boolean isSelfCrossing(int[] x) {
9+
if (x.length < 4) {
10+
return false;
11+
}
12+
int v1 = -x[0];
13+
int v2 = -x[1];
14+
15+
int i = 2;
16+
while (i < x.length) {
17+
if (i % 2 == 0) {
18+
if (i % 4 == 0) {
19+
v1 -= x[i];
20+
} else {
21+
v1 += x[i];
22+
}
23+
} else {
24+
if ((i + 1) % 4 == 0) {
25+
v2 += x[i];
26+
} else {
27+
v2 -= x[i];
28+
}
29+
}
30+
if (i % 2 != 0) {
31+
if ((v1 >= 0 && v2 <= 0) || (v1 <= 0 && v2 >= 0)) {
32+
return true;
33+
}
34+
}
35+
i++;
36+
}
37+
return false;
38+
}
39+
40+
public static void main(String args[]) {
41+
SelfCrossing sc = new SelfCrossing();
42+
int input[] = {3, 3, 4, 2, 2};
43+
System.out.print(sc.isSelfCrossing(input));
44+
}
45+
}

‎src/com/interview/array/ThreeSumSmallerThanTarget.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.interview.array;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* Given an array of n integers nums and a target, find the number of index triplets i, j, k
7+
* with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
8+
*
9+
* https://leetcode.com/problems/3sum-smaller/
10+
*/
11+
public class ThreeSumSmallerThanTarget {
12+
public int threeSumSmaller(int[] nums, int target) {
13+
if (nums.length < 3) {
14+
return 0;
15+
}
16+
Arrays.sort(nums);
17+
int count = 0;
18+
for (int i = 0; i < nums.length; i++) {
19+
int j = i + 1;
20+
int k = nums.length - 1;
21+
while (j < k) {
22+
if (nums[i] + nums[j] + nums[k] >= target) {
23+
k--;
24+
} else {
25+
count += k - j;
26+
j++;
27+
}
28+
}
29+
}
30+
return count;
31+
}
32+
}

‎src/com/interview/array/WaterContainer.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package com.interview.array;
2+
3+
/**
4+
* Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai).
5+
* n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines,
6+
* which together with x-axis forms a container, such that the container contains the most water.
7+
*
8+
* https://leetcode.com/problems/container-with-most-water/
9+
*/
10+
public class WaterContainer {
11+
public int maxArea(int[] height) {
12+
int i = 0;
13+
int j = height.length - 1;
14+
int maxArea = 0;
15+
while (i < j) {
16+
if (height[i] < height[j]) {
17+
maxArea = Math.max(maxArea, (height[i]) * (j - i));
18+
i++;
19+
} else {
20+
maxArea = Math.max(maxArea, height[j] * (j - i));
21+
j--;
22+
}
23+
}
24+
return maxArea;
25+
}
26+
}

‎src/com/interview/binarysearch/MinimumInSortedRotatedArray.java‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package com.interview.binarysearch;
2+
3+
/**
4+
* Created by tushar_v_roy on 3/21/16.
5+
*/
6+
public class MinimumInSortedRotatedArray {
7+
public int findMin(int[] nums) {
8+
int low = 0;
9+
int high = nums.length - 1;
10+
while (low < high) {
11+
int middle = (low + high)/2;
12+
if ((middle == 0 || nums[middle] < nums[middle - 1]) && (middle == nums.length - 1 || nums[middle] < nums[middle + 1])) {
13+
return nums[middle];
14+
}
15+
else if (nums[middle] > nums[high]) {
16+
low = middle + 1;
17+
} else {
18+
high = middle - 1;
19+
}
20+
}
21+
22+
return nums[low];
23+
}
24+
}

‎src/com/interview/binarysearch/SearchInsertPosition.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package com.interview.binarysearch;
2+
3+
/**
4+
* https://leetcode.com/problems/search-insert-position/
5+
*/
6+
public class SearchInsertPosition {
7+
public int searchInsert(int[] nums, int target) {
8+
int low = 0;
9+
int high = nums.length - 1;
10+
while (low <= high) {
11+
int middle = (low + high)/2;
12+
if (nums[middle] == target) {
13+
return middle;
14+
}
15+
if (nums[middle] < target && (middle == nums.length - 1 || nums[middle + 1] > target)) {
16+
return middle + 1;
17+
}
18+
if (nums[middle] < target) {
19+
low = middle + 1;
20+
} else {
21+
high = middle - 1;
22+
}
23+
}
24+
return 0;
25+
}
26+
}

‎src/com/interview/binarysearch/SquareRootOfNumber.java‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package com.interview.binarysearch;
2+
3+
/**
4+
*
5+
* https://leetcode.com/problems/sqrtx/
6+
*/
7+
public class SquareRootOfNumber {
8+
public int mySqrt(int x) {
9+
if (x == 0)
10+
return 0;
11+
int left = 1, right = x;
12+
while (true) {
13+
int mid = left + (right - left)/2;
14+
if (mid > x/mid) {
15+
right = mid - 1;
16+
} else {
17+
if (mid + 1 > x/(mid + 1))
18+
return mid;
19+
left = mid + 1;
20+
}
21+
}
22+
}
23+
}

‎src/com/interview/dynamic/MinimumNumberOfPerfectSquares.java‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package com.interview.dynamic;
2+
3+
/**
4+
* https://leetcode.com/problems/perfect-squares/
5+
*/
6+
public class MinimumNumberOfPerfectSquares {
7+
public int numSquares(int n) {
8+
int count = (int)Math.ceil(Math.sqrt(n));
9+
10+
int[] T = new int[n + 1];
11+
12+
T[0] = 0;
13+
14+
for (int i = 1; i < T.length; i++) {
15+
T[i] = Integer.MAX_VALUE;
16+
for (int j = 1; j <= count; j++) {
17+
if (i < j*j) {
18+
break;
19+
}
20+
T[i] = Math.min(T[i], T[i - j*j] + 1);
21+
}
22+
}
23+
return T[n];
24+
}
25+
}

‎src/com/interview/dynamic/MinimumTriangleSum.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package com.interview.dynamic;
2+
3+
import java.util.List;
4+
5+
/**
6+
* Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on
7+
* the row below.
8+
* https://leetcode.com/problems/triangle/
9+
*/
10+
public class MinimumTriangleSum {
11+
public int minimumTotal(List<List<Integer>> triangle) {
12+
int n = triangle.size();
13+
int[] dp = new int[n];
14+
15+
for (int i = 0; i < triangle.get(n - 1).size(); i++) {
16+
dp[i] = triangle.get(n - 1).get(i);
17+
}
18+
19+
for (int i = triangle.size() - 2; i >= 0; i--) {
20+
for (int j = 0; j < triangle.get(i).size(); j++) {
21+
dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
22+
}
23+
}
24+
return dp[0];
25+
}
26+
}

0 commit comments

Comments
 (0)