Acarus
BAN USERO(N) dynamic programming solution:
Let dp[i][0] - answer for first i elements with no i-th element included,
dp[i][1] - answer for first i elements with i-th element included.
Then dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) - if last element is not included lets select max from 2 possible answers for i - 1.
dp[i][1] = d[i - 1][0] + a[i] - select answer when prev is not included + current value.
Finally, answer is max(dp[n][1], dp[n][0]).
Here is implementation in Java:
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}
int[][] dp = new int[n + 1][2];
for (int i = 1; i <= n; i++) {
dp[i][1] = dp[i - 1][0] + arr[i - 1];
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
}
out.println(Math.max(dp[n][1], dp[n][0]));
Solution with O(N) time and O(1) memory (modifying tree):
Let's convert binary tree into a linked list where a right link points to the next element. And print all elements in a linked list.
import java.io.*;
import java.util.*;
public class Main {
static class TreeNode {
int x;
TreeNode left;
TreeNode right;
public TreeNode(int x) {
this.x = x;
}
}
static class Result {
TreeNode start;
TreeNode end;
public Result(TreeNode start, TreeNode end) {
this.start = start;
this.end = end;
}
}
private void solve(TreeNode root) {
Result res = flatten(root);
TreeNode curr = res.start;
while (curr != null) {
System.out.print(curr.x + " ");
curr = curr.right;
}
System.out.println();
}
private Result flatten(TreeNode root) {
if (root == null || (root.left == null && root.right == null)) {
return new Result(root, root);
}
if (root.left == null) {
Result right = flatten(root.right);
right.end.right = root;
root.right = null;
return new Result(right.start, root);
} else if (root.right == null) {
Result left = flatten(root.left);
left.end.right = root;
root.right = null;
return new Result(left.start, root);
} else {
Result left = flatten(root.left);
Result right = flatten(root.right);
left.end.right = right.start;
right.end.right = root;
root.right = null;
return new Result(left.start, root);
}
}
}
Could be solved with self join:
- Acarus November 22, 2016select distinct(a.email) from emails a join emails b on a.email=b.email and a.id!=b.id;