可能的二分法：DFS染色法
1604 · 两数最大和
给定一个由N个整数组成的数组A，返回两个数字的最大总和，规定这两个数的所有位加起来相等。 如果没有两个数字的各个位相加和相等，则该函数应返回-1。
- N的范围是
[1, 200000] - A中的每一个参数的范围是
[1, 1000000000]
样例
示例1:
输入:
A = [51, 71, 17, 42]
输出: 93
解释：这里有两对各个位相加和相等的数：(51, 42) 和 (17,71)，第一对的和是93
示例2:
输入:
A = [42, 33, 60]
输出: 102
解释：所有的数各个位相加的和都相等，选择42 + 60 = 102
示例3:
输入:
A = [51, 32, 43]
输出: -1
解释: 所有数的各个位相加和都不一样，因此返回-1
遍历，相同的个位数和放在一起。
public class Solution {
/**
* @param a: An Integer array
* @return: returns the maximum sum of two numbers
*/
public int maximumSum(int[] a) {
// write your code here
Map<Integer,List<Integer>> map = new HashMap<>();
for(int n:a) {
int bitSum = getBitSum(n);
if(!map.containsKey(bitSum)) {
map.put(bitSum,new ArrayList<>());
}
map.get(bitSum).add(n);
}
int result = -1;
for(int key:map.keySet()) {
List<Integer> list = map.get(key);
if(list.size()==1) continue;
Collections.sort(list,(x,y)->y-x);
result = Math.max(result,list.get(0)+list.get(1));
}
return result;
}
private int getBitSum(int num) {
int result = 0;
while(num!=0) {
result += num%10;
num/=10;
}
return result;
}
}
1704 · 二叉搜索树的范围和
给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。
二叉搜索树保证具有唯一的值。
树中的结点数量最多为 10000 个。最终的答案保证小于 2^31。
样例 1:
输入：root = [10,5,15,3,7,null,18], L = 7, R = 15
输出：32
中序遍历
这个还是比较容易想到的。
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: the root node
* @param l: an integer
* @param r: an integer
* @return: the sum
*/
public int rangeSumBST(TreeNode root, int l, int r) {
// 10
// 5 15
// 3 7 null 18
// 中序遍历
if(root==null) return 0;
Deque<TreeNode> deque = new ArrayDeque<>();
List<Integer> list = new ArrayList<>();
deque.addLast(root);
TreeNode cur = root.left;
while(!deque.isEmpty()||cur!=null) {
if(cur!=null) {
deque.addLast(cur);
cur = cur.left;
} else {
cur = deque.pollLast();
list.add(cur.val);
cur = cur.right;
}
}
System.out.println(list);
int sum = 0;
boolean findL = false;
for(int i=0;i<list.size();i++) {
if(list.get(i)==l) {
findL = true;
}
if(findL) sum+=list.get(i);
if(list.get(i)==r) return sum;
}
return sum;
}
}
递归查找（不查多余的）
public class Solution {
/**
* @param root: the root node
* @param l: an integer
* @param r: an integer
* @return: the sum
*/
public int rangeSumBST(TreeNode root, int l, int r) {
if(root==null) return 0;
if(root.val<l) {
return rangeSumBST(root.right, l, r);
}
if(root.val>r) {
return rangeSumBST(root.left, l, r);
}
return root.val+rangeSumBST(root.left, l, r)+rangeSumBST(root.right, l, r);
}
}
1596 · 可能的二分法
DFS 染色法
给定一组 N 人（编号为 1, 2, ..., N）， 我们想把每个人分进任意大小的两组。
每个人都可能不喜欢其他人，那么他们不应该属于同一组。
形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。
当可以用这种方法将每个人分进两组时，返回 true；否则返回 false。
1 <= N <= 2000
0 <= dislikes.length <= 10000
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
对于 dislikes[i] == dislikes[j] 不存在 i != j
样例
例 1：
输入：N = 4, dislikes = [[1,2],[1,3],[2,4]]
输出：true
解释：group1 [1,4], group2 [2,3]
例 2：
输入：N = 3, dislikes = [[1,2],[1,3],[2,3]]
输出：false
例 3：
输入：N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出：false
public class Solution {
/**
* @param n: sum of the set
* @param dislikes: dislikes peoples
* @return: if it is possible to split everyone into two groups in this way
*/
public boolean possibleBipartition(int n, int[][] dislikes) {
List<List<Integer>> edges = new ArrayList<>();
for(int i=0;i<=n;i++) {
edges.add(new ArrayList<>());
}
for(int i=0;i<dislikes.length;i++) {
edges.get(dislikes[i][0]).add(dislikes[i][1]);
edges.get(dislikes[i][1]).add(dislikes[i][0]);
}
int[] colors = new int[n+1];
for(int i=1;i<=n;i++) {
if(colors[i]==0) {
if(!paint(-1,edges,colors,i)) return false;
}
}
return true;
}
private boolean paint(int icolor,List<List<Integer>> edges,int[] colors,int i) {
if(colors[i]!=0) return colors[i]==icolor;
colors[i] = icolor;
for(int k=0;k<edges.get(i).size();k++) {
if(!paint(-icolor,edges,colors,edges.get(i).get(k))) return false;
}
return true;
}
}