1. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x)—— 将元素 x 推入栈中。pop()—— 删除栈顶的元素。top()—— 获取栈顶元素。getMin()—— 检索栈中的最小元素。
示例:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出： [null,null,null,null,-3,null,0,-2]
解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
提示：
pop、top 和 getMin 操作总是在 非空栈 上调用。
出处：
https://edu.csdn.net/practice/27913069
代码：
class MinStack { Stack<Integer> data_stack; Stack<Integer> min_stack; /** initialize your data structure here. */ public MinStack() { data_stack = new Stack<Integer>(); min_stack = new Stack<Integer>(); } public void push(int x) { data_stack.push(x); if (min_stack.isEmpty()) { min_stack.push(x); } else { if (x > min_stack.peek()) { x = min_stack.peek(); } min_stack.push(x); } } public void pop() { data_stack.pop(); min_stack.pop(); } public int top() { return data_stack.peek(); } public int getMin() { return min_stack.peek(); } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */
输出：
略
2. 组合总和 II
给定一个数组 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]]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:[[1,2,2],[5]]
出处：
https://edu.csdn.net/practice/27913070
代码：
import java.util.*; public class Solution { public static List<List<Integer>> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); List<List<Integer>> res = new ArrayList<List<Integer>>(); if (candidates.length == 0 || target < candidates[0]) return res; List<Integer> tmp = new ArrayList<Integer>(); helper(candidates, target, 0, tmp, res); return res; } public static void helper(int[] a, int target, int start, List<Integer> tmp, List<List<Integer>> res) { if (target < 0) return; if (target == 0) { res.add(new ArrayList<Integer>(tmp)); return; } for (int i = start; i < a.length; i++) { tmp.add(a[i]); int newtarget = target - a[i]; helper(a, newtarget, i + 1, tmp, res); tmp.remove(tmp.size() - 1); if (newtarget <= 0) break; while (i + 1 < a.length && a[i] == a[i + 1])// 组合中有重复元素，不要重复开头 i++; } } public static void main(String[] args) { int[] candidates = {10,1,2,7,6,1,5}; System.out.println(combinationSum2(candidates, 8)); int[] candidates2 = {2,5,2,1,2}; System.out.println(combinationSum2(candidates2, 5)); } }
输出：
[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
[[1, 2, 2], [5]]
3. 相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：
输入：p = [1,2], q = [1,null,2]
输出：false
示例 3：
输入：p = [1,2,1], q = [1,1,2]
输出：false
提示：
两棵树上的节点数目都在范围 [0, 100] 内
-10^4 <= Node.val <= 10^4
出处：
https://edu.csdn.net/practice/27913071
代码：
import java.util.*; import java.util.LinkedList; public class Solution { public final static int NULL = Integer.MIN_VALUE; //用NULL来表示空节点 public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() { } TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } public static boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p != null && q != null && p.val == q.val) { return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } else { return false; } } public static TreeNode createBinaryTree(Integer[] nums) { Vector<Integer> vec = new Vector<Integer>(Arrays.asList(nums)); if (vec == null || vec.size() == 0) { return null; } Queue<TreeNode> queue = new LinkedList<>(); TreeNode root = new TreeNode(vec.get(0)); queue.offer(root); int i = 1; while (!queue.isEmpty()) { int size = queue.size(); for (int j = 0; j < size; j++) { TreeNode node = queue.poll(); if (i < vec.size() && vec.get(i) != NULL) { node.left = new TreeNode(vec.get(i)); queue.offer(node.left); } i++; if (i < vec.size() && vec.get(i) != NULL) { node.right = new TreeNode(vec.get(i)); queue.offer(node.right); } i++; } } return root; } public static void main(String[] args) { Integer[] np1 = {1,2,3}; Integer[] nq1 = {1,2,3}; TreeNode p = createBinaryTree(np1); TreeNode q = createBinaryTree(nq1); System.out.println(isSameTree(p, q)); Integer[] np2 = {1,2}; Integer[] nq2 = {1,NULL,2}; p = createBinaryTree(np2); q = createBinaryTree(nq2); System.out.println(isSameTree(p, q)); Integer[] np3 = {1,2,1}; Integer[] nq3 = {1,1,2}; p = createBinaryTree(np3); q = createBinaryTree(nq3); System.out.println(isSameTree(p, q)); } }
输出：
true
false
false
