Q1: O(24)
int ans;
public int maxDistance(int[] nums) {
ans = 0;
backtrack(nums, 0);
return ans;
}
private void backtrack(int[] nums, int pos) {
int n = nums.length;
if(pos==4) {
int diff1 = nums[0]-nums[1];
int diff2 = nums[2]-nums[3];
ans = Math.max(ans, diff1*diff1 + diff2*diff2);
return;
}
for(int i=pos; i<n; i++) {
swap(nums, pos, i);
backtrack(nums, pos+1);
swap(nums, pos, i);
}
}
Q2: O(dfs)
class Solution {
int ans;
public int goodNodes(TreeNode root) {
ans = 0;
dfs(root, Integer.MIN_VALUE);
return ans;
}
private void dfs(TreeNode node, int max) {
if(node==null) return;
if(node.val>=max) {
ans++;
max = node.val;
}
dfs(node.left, max);
dfs(node.right, max);
}
}
Q3: nlogn greedy
public int minRelocations(int[] items) {
int sum = 0, ans = 0;
PriorityQueue<Integer> largestExpenses = new PriorityQueue<>();
for(int item : items) {
sum+=item;
if(item<0) largestExpenses.offer(item);
if(sum<0) {
sum-=largestExpenses.poll();
ans++;
}
}
return ans;
}