ak_domi
BAN USERSolution in Java. Basic idea is that we create a key from each string by using lower case non repeated sorted chars and store each string in a list of similar strings.
public static void main(String[] args) throws Exception {
String str = "May student students dog studentssess god Cat act tab bat flow wolf lambs Amy Yam balms looped poodle john alice ";
String[] words = str.split(" ");
List<List<String>> repeated = getRepeatedStrings(words);
}
static List<List<String>> getRepeatedStrings(String[] words) {
Map<String, List<String>> lookup = new HashMap<>();
for(String current : words) {
String key = getKey(current);
List<String> matches = lookup.computeIfAbsent(key, o-> new ArrayList<String>());
matches.add(current);
}
return lookup.values().stream().filter(list-> list.size() > 1).collect(Collectors.toList());
}
static int[] chars = new int[256];
static String getKey(String s) {
List<Character> keyChars = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
char c = Character.toLowerCase(s.charAt(i));
if(chars[(int)c] == 0) {
keyChars.add(c);
chars[(int)c]++;
}
}
Collections.sort(keyChars);
StringBuilder sb = new StringBuilder();
keyChars.forEach(c-> {
chars[(int)c]--;
sb.append(c);
});
return sb.toString();
}
Find 3 biggest intervals, recurse on non intersecting, find max sum.
public static void main(String[] args) throws Exception {
Scanner in = new Scanner(new FileReader("test.txt"));
int n = in.nextInt();
int k = in.nextInt();
int arraySize = in.nextInt();
int[] a = new int[arraySize];
for (int i = 0; i < arraySize; i++) {
a[i] = in.nextInt();
}
List<Interval> intervals = getBiggestIntSum(a, n, k, new ArrayList<>());
}
static List<Interval> getBiggestIntSum(int[] a, int n, int k, List<Interval> exclude) {
Queue<Interval> candidates = new PriorityQueue<>(n);
int left= 0;
int right = 0;
int sum = 0;
while(right < a.length) {
if(right-left <k) {
sum += a[right];
right++;
} else {
boolean intersects = false;
Interval candidate = new Interval(left, right - 1, sum);
for(Interval exc : exclude) {
if (exc.intersects(candidate)) {
intersects = true;
break;
}
}
if(!intersects) {
if(candidates.size() < n) {
candidates.add(candidate);
} else {
if(candidates.peek().sum < candidate.sum) {
candidates.poll();
candidates.add(candidate);
}
}
}
sum -= a[left];
left++;
}
}
List<Interval> candidatesList = candidates.stream().collect(Collectors.toList());
if(candidatesList.size() == 1)
return candidatesList;
List<Interval> intersecting = new ArrayList<>();
List<Interval> nonIntersecting = new ArrayList<>();
for (int i = 0; i < candidatesList.size(); i++) {
Interval candidate = candidatesList.get(i);
boolean intersects = false;
for (int j = i+1; j < candidatesList.size(); j++) {
if(candidate.intersects(candidatesList.get(j))) {
intersects = true;
break;
}
}
if(!intersects) {
nonIntersecting.add(candidate);
} else {
intersecting.add(candidate);
}
}
int globalSum = 0;
List<Interval> results = new ArrayList<>();
if(nonIntersecting.size() == n)
return nonIntersecting;
else if(nonIntersecting.size() > 0) {
List<Interval> newExclude = new ArrayList<>();
newExclude.addAll(exclude);
newExclude.addAll(nonIntersecting);
List<Interval> tmpResults = getBiggestIntSum(a, n - nonIntersecting.size(), k, newExclude);
int tmpSum = tmpResults.stream().mapToInt(o -> o.sum).sum() + nonIntersecting.stream().mapToInt(o-> o.sum).sum();
if(tmpSum > globalSum) {
globalSum = tmpSum;
results = tmpResults;
results.addAll(nonIntersecting);
}
}
for (int i = 0; i < intersecting.size(); i++) {
Interval candidate = intersecting.get(i);
List<Interval> newExclude = new ArrayList<>();
newExclude.addAll(exclude);
newExclude.add(candidate);
List<Interval> tmpResults = getBiggestIntSum(a, n -1, k, newExclude);
int tmpSum = tmpResults.stream().mapToInt(o -> o.sum).sum() + candidate.sum;
if(tmpSum > globalSum) {
globalSum = tmpSum;
results = tmpResults;
results.add(candidate);
}
}
return results;
}
static class Interval implements Comparable<Interval> {
int left;
int right;
int sum;
public Interval(int left, int right, int sum) {
this.left = left;
this.right = right;
this.sum = sum;
}
public boolean intersects(Interval interval) {
if(left <= interval.left) {
if(right >= interval.left)
return true;
} else {
if(left <= interval.right)
return true;
}
return false;
}
@Override
public int compareTo(Interval o) {
return Integer.compare(sum, o.sum);
}
}
Just go starting from the end of the array and check if we see the a bigger stock price we memorize it, else we check if we can profit from buying on ith day to sell on maxPrice day.
int maxProfit(int[] prices, int fee) {
int profit = 0;
int maxPrice = -1;
for(int i = prices.length-1; i>=0; i--) {
if(a[i] > maxPrice) maxPrice = a[i];
else {
int tmpProfit = maxPrice - a[i] - fee;
if(tmpProfit > 0)
profit +=tmpProfit;
}
}
return profit;
}
- ak_domi April 06, 2017