Array
Last updated
Was this helpful?
Last updated
Was this helpful?
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import java.util.HashMap;
import java.util.Map;
/**
* <a href="https://leetcode.com/problems/two-sum/">Two Sum</a>
*/
class TwoSum {
private final Map<Integer, Integer> cache = new HashMap<>();
public int[] twoSum(final int[] nums, final int target) {
for (int i = 0; i < nums.length; i++) {
final int residual = target - nums[i];
if (cache.containsKey(residual)) {
return new int[]{cache.get(residual), i};
}
cache.put(nums[i], i);
}
return new int[]{};
}
@Test
void givenInput1_whenCheckTheTwoSum_thenItShouldReturn0And1() {
final int[] nums = new int[]{2, 7, 11, 15};
final int target = 9;
Assertions.assertArrayEquals(new int[]{0, 1}, twoSum(nums, target));
}
@Test
void givenInput2_whenCheckTheTwoSum_thenItShouldReturn1And2() {
final int[] nums = new int[]{3, 2, 4};
final int target = 6;
Assertions.assertArrayEquals(new int[]{1, 2}, twoSum(nums, target));
}
@Test
void givenInput3_whenCheckTheTwoSum_thenItShouldReturn0And1() {
final int[] nums = new int[]{3, 3};
final int target = 6;
Assertions.assertArrayEquals(new int[]{0, 1}, twoSum(nums, target));
}
}import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
class MaxProfit {
public int maxProfit(final int[] prices) {
int maxProfit = 0;
int min = Integer.MAX_VALUE;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < min) {
min = prices[i];
}
if (prices[i] - min > maxProfit) {
maxProfit = prices[i] - min;
}
}
return maxProfit;
}
@Test
void givenInput1_whenCalculateTheMaxProfit_thenItShouldReturn5() {
final int[] prices = new int[]{7, 1, 5, 3, 6, 4};
assertEquals(5, maxProfit(prices));
}
@Test
void givenInput2_whenCalculateTheMaxProfit_thenItShouldReturn0() {
final int[] prices = new int[]{7, 6, 4, 3, 1};
assertEquals(0, maxProfit(prices));
}
}class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> results = new ArrayList<>();
for (int i = 0; i < intervals.length; i++) {
int[] tmp = intervals[i];
if (colide(tmp, newInterval)) {
newInterval[0] = Math.min(tmp[0], newInterval[0]);
newInterval[1] = Math.max(tmp[1], newInterval[1]);
} else if (tmp[1] < newInterval[0]) {
results.add(tmp);
} else {
// tmp[0] > newInterval[1]
results.add(newInterval);
results.add(tmp);
for (int j = i+1; j < intervals.length; j++) {
results.add(intervals[j]);
}
return results.toArray(new int[results.size()][]);
}
}
results.add(newInterval);
return results.toArray(new int[results.size()][]);
}
private boolean colide(int[] a, int[] b) {
return a[0] <= b[1] && a[1] >= b[0];
}
// This is the most concise solution
private int[][] solution1(int[][] intervals, int[] newInterval) {
List<int[]> results = new ArrayList<>();
for (int i = 0; i < intervals.length; i++) {
int[] tmp = intervals[i];
if (tmp[1] < newInterval[0]) {
results.add(tmp);
} else if (newInterval[1] < tmp[0]) {
results.add(newInterval);
newInterval = tmp;
} else {
newInterval[0] = Math.min(tmp[0], newInterval[0]);
newInterval[1] = Math.max(tmp[1], newInterval[1]);
}
}
results.add(newInterval);
return results.toArray(new int[results.size()][]);
}
}class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> res;
int size = intervals.size();
for (int i = 0; i < size; i++) {
vector<int>& tmp = intervals[i];
if (collide(tmp, newInterval)) {
newInterval[0] = min(tmp[0], newInterval[0]);
newInterval[1] = max(tmp[1], newInterval[1]);
} else if (tmp[1] < newInterval[0]) {
res.emplace_back(tmp);
} else {
// newInterval[1] < tmp[0]
res.emplace_back(newInterval);
res.emplace_back(tmp);
for (int j = i+1; j < size; j++) {
res.emplace_back(intervals[j]);
}
return res;
}
}
res.emplace_back(newInterval);
return res;
}
bool collide(const vector<int>& a, const vector<int>& b) {
return a[0] <= b[1] && a[1] >= b[0];
}
};class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> result = new HashSet<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
return new ArrayList<>(result);
}
int head = i+1;
int tail = nums.length - 1;
while (head < tail) {
int sum = nums[i] + nums[head] + nums[tail];
if (sum == 0) {
List<Integer> tmp = new ArrayList<>();
tmp.add(nums[i]);
tmp.add(nums[head]);
tmp.add(nums[tail]);
result.add(tmp);
head++;
} else if (sum > 0) {
tail--;
} else {
head++;
}
}
}
return new ArrayList<>(result);
}
}class Solution {
public int[] productExceptSelf(int[] nums) {
return solution2(nums);
}
// Time Complexity: O(N)
// Space Complexity: O(N)
public int[] solution1(int[] nums) {
int length = nums.length;
int[] before = new int[length];
before[0] = 1;
for (int i = 1; i < length; i++) {
before[i] = before[i-1] * nums[i-1];
}
int[] after = new int[length];
after[length - 1] = 1;
for (int i = length-2; i >= 0; i--) {
after[i] = after[i+1] * nums[i+1];
}
int[] result = new int[length];
for (int i = 0; i < length; i++) {
result[i] = before[i] * after[i];
}
return result;
}
// Time Complexity: O(N)
// Space Complexity: O(1)
public int[] solution2(int[] nums) {
int length = nums.length;
int[] result = new int[length];
result[0] = 1;
for (int i = 1; i < length; i++) {
result[i] = result[i-1] * nums[i-1];
}
int after = 1;
for (int i = length - 1; i>=0; i--) {
result[i] = result[i] * after;
after = nums[i] * after;
}
return result;
}
}Using backtrack, not sure if there is other solutions like the memorization or dp.
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> results = new ArrayList<>();
List<Integer> current = new ArrayList<>();
Arrays.sort(candidates);
backtrack(candidates, target, current, 0, results);
return results;
}
private void backtrack(int[] candidates, int target, List<Integer> current, int index, List<List<Integer>> results) {
if (target == 0) {
results.add(new ArrayList<>(current));
}
for (int i = index; i < candidates.length; i++) {
if (candidates[i] > target) {
break;
} else {
current.add(candidates[i]);
backtrack(candidates, target - candidates[i], current, i, results);
current.remove(current.size() - 1);
}
}
}
}class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> results;
vector<int> current;
std::sort(candidates.begin(), candidates.end()); // Sort candidates for early exit and duplicate handling
backtrack(candidates, target, current, 0, results);
return results;
}
void backtrack(const vector<int>& candidates, const int target, vector<int>& current, const int index, vector<vector<int>>& results) {
if (target == 0) {
results.push_back(current); // copy
return;
}
for (int i = index; i < candidates.size(); i++) {
if (candidates[i] > target) {
break;
}
current.push_back(candidates[i]);
backtrack(candidates, target - candidates[i], current, i, results);
// remove the last added candidate
current.pop_back();
}
}
};class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> {
if (a[0] == b[0]) {
return 0;
}
return a[0] > b[0] ? 1 : -1;
});
int[] tmp = intervals[0];
List<int[]> result = new ArrayList<>();
for (int i = 1; i < intervals.length; i++) {
int[] cur = intervals[i];
if (cur[0] > tmp[1]) {
result.add(tmp);
tmp = cur;
} else if (cur[1] < tmp[0]) {
result.add(cur);
} else {
tmp = new int[] {Math.min(tmp[0], cur[0]), Math.max(tmp[1], cur[1])};
}
}
result.add(tmp);
return result.toArray(new int[result.size()][]);
}
}class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
vector<vector<int>> res;
vector<int> tmp = intervals[0];
for (int i = 1; i < intervals.size(); i++) {
vector<int>& cur = intervals[i];
if (tmp[0] > cur[1]) {
res.emplace_back(cur);
} else if (tmp[1] < cur[0]) {
res.emplace_back(tmp);
tmp = cur;
} else {
tmp[0] = min(tmp[0], cur[0]);
tmp[1] = max(tmp[1], cur[1]);
}
}
res.emplace_back(tmp);
return res;
}
};class Solution {
public int majorityElement(int[] nums) {
return solution3(nums);
}
// sort
private int solution1(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
// Moore Voting Algorithm
// https://leetcode.com/problems/majority-element/
private int solution2(int[] nums) {
int count = 0;
int candidate = 0;
for (int i = 0; i < nums.length; i++) {
if (count == 0) {
candidate = nums[i];
count++;
} else if (nums[i] == candidate) {
count++;
} else {
count--;
}
}
return candidate;
}
private int solution3(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
int target = nums.length / 2;
for (int i = 0; i < nums.length; i++) {
int prev = map.computeIfAbsent(nums[i], k -> 0);
int cur = ++prev;
if (cur > target) {
return nums[i];
}
map.put(nums[i], cur);
}
return 0;
}
}// - [] Capture nothing (or, a scorched earth strategy?)
// - [&] Capture any referenced variable by reference
// - [=] Capture any referenced variable by making a copy
// - [=, &foo] Capture any referenced variable by making a copy, but capture variable foo by reference
// - [bar] Capture bar by making a copy; don't copy anything else
// - [this] Capture the this pointer of the enclosing class
class Solution {
public:
int majorityElement(vector<int>& nums) {
return solution3(nums);
}
private:
int solution1(vector<int>& nums) {
sort(nums.begin(), nums.end(), [](int a, int b){ return a < b; });
return nums[nums.size()/2];
}
int solution2(vector<int>& nums) {
int candidate = 0;
int count = 0;
for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++) {
if (count == 0) {
candidate = *it;
count++;
} else if (*it != candidate) {
count--;
} else {
count++;
}
}
return candidate;
}
int solution3(vector<int>& nums) {
unordered_map<int, int> m;
int target = nums.size()/2;
for (int i : nums) {
// if m[i] not existing, the default value is 0 in this case
m[i]++;
if (m[i] > target) {
return i;
}
}
return 0;
}
};class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int candidate1 {0}, candidate2 {0}, count1 {0}, count2 {0};
for (const auto& x : nums) {
if (x == candidate1) {
count1++;
} else if (x == candidate2) {
count2++;
} else if (!count1) {
candidate1 = x;
count1++;
} else if (!count2) {
candidate2 = x;
count2++;
} else {
count1--;
count2--;
}
}
count1 = count2 = 0;
for (const auto& x : nums) {
if (x == candidate1) {
count1++;
} else if (x == candidate2) {
count2++;
}
}
vector<int> res;
if (count1 > nums.size()/3) res.push_back(candidate1);
if (count2 > nums.size()/3) res.push_back(candidate2);
return res;
}
};class Solution {
// Dutch National Flag algorithm
public void sortColors(int[] nums) {
int head = 0;
int mid = 0;
int tail = nums.length - 1;
while (mid <= tail) {
if (nums[mid] == 0 && nums[head] != 0) {
int tmp = nums[head];
nums[head++] = nums[mid];
nums[mid++] = tmp;
} else if (nums[mid] == 0 && nums[head] == 0) {
mid++;
head++;
} else if (nums[mid] == 1) {
mid++;
} else {
int tmp = nums[tail];
nums[tail] = nums[mid];
nums[mid] = tmp;
tail--;
}
}
}
}class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
return solution4(nums);
}
private:
bool solution1(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (nums[i] == nums[j]) {
return true;
}
}
}
return false;
}
bool solution2(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = 1; i < nums.size(); i++) {
if (nums[i] == nums[i-1]) {
return true;
}
}
return false;
}
bool solution3(vector<int>& nums) {
unordered_set<int> s;
for (int i = 0; i < nums.size(); i++) {
if (s.count(nums[i]) > 0) {
return true;
}
s.insert(nums[i]);
}
return false;
}
bool solution4(vector<int>& nums) {
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); i++) {
if (m[nums[i]] > 0) {
return true;
}
m[nums[i]]++;
}
return false;
}
};class Solution {
public boolean containsDuplicate(int[] nums) {
return solution4(nums);
}
private boolean solution1(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (nums[i] == nums[j]) {
return true;
}
}
}
return false;
}
private boolean solution2(int[] nums) {
Arrays.sort(nums);
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i-1]) {
return true;
}
}
return false;
}
private boolean solution3(int[] nums) {
Set<Integer> s = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (s.contains(nums[i])) {
return true;
}
s.add(nums[i]);
}
return false;
}
private boolean solution4(int[] nums) {
Map<Integer, Integer> m = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (m.containsKey(nums[i])) {
return true;
}
m.put(nums[i], 1);
}
return false;
}
}class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int maxArea = 0;
while (left < right) {
int area = min(height[left], height[right]) * (right - left);
maxArea = max(area, maxArea);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
};// bubble sort
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int lastExchangeIndex = 0; // optimization 2
int sortedBoarder = nums.size() - 1; // optimization 2
for (int i = 0; i < nums.size() - 1; i++) { // note that we need to minus 1
bool sorted = true; // optimization 1
for (int j = 0; j < sortedBoarder; j++) { // note that we need to minus (i+1) for optimization
if (nums[j] > nums[j+1]) {
int tmp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = tmp;
sorted = false;
lastExchangeIndex = j;
}
}
sortedBoarder = lastExchangeIndex;
if (sorted) {
break;
}
}
return nums;
}
};// cocktail
//TODO// quick sort - double sides
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
quickSort(nums, 0, nums.size()-1);
return nums;
}
void quickSort(vector<int>& nums, int start, int end) {
if (start >= end) {
return;
}
int pivotIndex = partition(nums, start, end);
quickSort(nums, start, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, end);
}
// return the pivot index
int partition(vector<int>& nums, int start, int end) {
int pivot = nums[start];
int left = start;
int right = end;
while(left < right) { // check left < right
while(left < right && nums[right] > pivot) { // note we check left < right again
right--;
}
while(left < right && nums[left] <= pivot) { // note we check left < right again
left++;
}
if (left < right) { // note we check left < right again
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
}
}
nums[start] = nums[left];
nums[left] = pivot;
return left;
}
};// quick sort - single side
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
quickSort(nums, 0, nums.size()-1);
return nums;
}
void quickSort(vector<int>& nums, int start, int end) {
if (start >= end) {
return;
}
int pivotIndex = partition(nums, start, end);
quickSort(nums, start, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, end);
}
// return the pivot index
int partition(vector<int>& nums, int start, int end) {
int pivot = nums[start];
int mark = start;
for (int i = start; i <= end; i++) {
if (nums[i] < pivot) {
mark++;
int tmp = nums[i];
nums[i] = nums[mark];
nums[mark] = tmp;
}
}
nums[start] = nums[mark];
nums[mark] = pivot;
return mark;
}
};// insertion sort - suitable for almost sorted data
// Insertion sort has a running time of O(n) at best when the list is already sorted or nearly-sorted, and O(n2) at worst when the list is in reverse.
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
for (int i = 1; i < nums.size(); i++) {
int insertValue = nums[i];
int j = i - 1;
for (; j >= 0 && insertValue < nums[j]; j--) {
nums[j+1] = nums[j];
}
nums[j+1] = insertValue;
}
}
};package com.damonyuan.matchingengine.service;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Stack;
public class RoomManagerImpl implements RoomManager {
@Override
public int getRooms(int[] checkIn, int[] checkOut) {
if (checkIn == null || checkOut == null) {
throw new RuntimeException("invalid input");
}
if (checkIn.length != checkOut.length) {
throw new RuntimeException("invalid length");
}
if (checkIn.length == 0) {
return 0;
}
return solution3(checkIn, checkOut);
}
// using ranges and brute-force
private static int solution3(int[] checkIn, int[] checkOut) {
final List<int[]> ranges = new ArrayList<>();
for (int i = 0; i < checkIn.length; i++) {
ranges.add(new int[] {checkIn[i], checkOut[i]});
}
ranges.sort(Comparator.comparingInt(a -> a[0]));
int start = ranges.get(0)[0];
int end = 0;
for (int[] range : ranges) {
end = Math.max(range[1], end);
}
int res = 0;
for (int i = start; i <= end; i++) {
int count = 0;
for (int[] range : ranges) {
if (i >= range[0] && i <= range[1]) {
count++;
}
}
res = Math.max(res, count);
}
return res;
}
// using a stack
private static int solution2(int[] checkIn, int[] checkOut) {
final List<Integer> absSortedInAndOut = getAbsSortedCombinedList(checkIn, checkOut);
int res = 0;
final Stack<Integer> s = new Stack<>();
for (int e : absSortedInAndOut) {
if (e > 0) {
s.push(e);
res = Math.max(res, s.size());
} else {
s.pop();
}
}
return res;
}
// using a variable
private static int solution1(int[] checkIn, int[] checkOut) {
final List<Integer> absSortedInAndOut = getAbsSortedCombinedList(checkIn, checkOut);
int res = 0;
int rooms = 0;
for (int e : absSortedInAndOut) {
if (e > 0) {
rooms++;
res = Math.max(rooms, res);
} else {
rooms--;
}
}
return res;
}
private static List<Integer> getAbsSortedCombinedList(int[] checkIn, int[] checkOut) {
final List<Integer> inAndOut = new ArrayList<>();
for (int i : checkIn) {
inAndOut.add(i);
}
for (int o : checkOut) {
inAndOut.add(-o);
}
inAndOut.sort(Comparator.comparingInt(Math::abs));
return inAndOut;
}
}class Solution {
public:
int getRooms(vector<int>& checkIn, vector<int>& checkOut) {
if (checkIn.size() != checkOut.size()) {
throw std::invalid_argument("invalid length");
}
vector<int> combined;
for (const int i : checkIn) {
combined.emplace_back(i);
}
for (const int o : checkOut) {
combined.emplace_back(-o);
}
sort(combined.begin(), combined.end(), [](const int a, const int b) {
return abs(a) < abs(b);
});
int res = 0;
int count = 0;
for (const int& i : combined) {
if (i > 0) {
count++;
res = max(res, count);
} else {
count--;
}
}
return res;
}
};