假设Andy和Doris想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设总是存在一个答案。
示例 1:
输入: [“Shogun”, “Tapioca Express”, “Burger King”, “KFC”] [“Piatti”, “The Grill at Torrey Pines”, “Hungry Hunter Steakhouse”, “Shogun”] 输出: [“Shogun”] 解释: 他们唯一共同喜爱的餐厅是“Shogun”。
class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
Map<Integer, List<String>> map = new HashMap<>();
for (int i = 0; i < list1.length; i++) {
for (int j = 0; j < list2.length; j++) {
if (list1[i].equals(list2[j])) {
if (!map.containsKey(i + j)) {
map.put(i + j, new ArrayList<>());
}
map.get(i + j).add(list1[i]);
}
}
}
int min = Integer.MAX_VALUE;
for (int i : map.keySet()) {
min = Math.min(min, i);
}
String[] ans = new String[map.get(min).size()];
return map.get(min).toArray(ans);
}
}
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) {
return root2;
}
if (root2 == null) {
return root1;
}
TreeNode ans = new TreeNode(root1.val + root2.val);
ans.left = mergeTrees(root1.left, root2.left);
ans.right = mergeTrees(root1.right, root2.right);
return ans;
}
}
给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
示例 1：
输入：nums = [1,2,3]
输出：6
class Solution {
public int maximumProduct(int[] nums) {
int min1 = Integer.MAX_VALUE;
int min2 = Integer.MAX_VALUE;
int max3 = Integer.MIN_VALUE;
int max2 = Integer.MIN_VALUE;
int max1 = Integer.MIN_VALUE;
for (int num : nums) {
if (num < min1) {
min2 = min1;
min1 = num;
} else if (num < min2) {
min2 = num;
}
if (num > max1) {
max3 = max2;
max2 = max1;
max1 = num;
} else if (num > max2) {
max3 = max2;
max2 = num;
} else if (num > max3) {
max3 = num;
}
}
return Math.max(min1 * min2 * max1, max3 * max2 * max1);
}
}
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
dfs(candidates, target, 0, 0);
return ans;
}
public void dfs(int[] candidates, int target, int sum, int index){
if (target < sum) {
return;
}
if (target == sum) {
ans.add(new ArrayList<>(path));
return;
}
for (int i = index; i< candidates.length;i++) {
if (i > index && candidates[i] == candidates[i - 1]){ //注意这里进行剪枝
continue;
}
sum += candidates[i];
path.add(candidates[i]);
dfs(candidates, target, sum, i + 1);
sum -= candidates[i];
path.remove(path.size() - 1);
}
}
}