在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。示例：
输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3先把输出数组排序，从排序的数组中找出重复数字只需从头到尾扫描排序后的数组即可。
class Solution { public int findRepeatNumber(int[] nums) { Arrays.sort(nums); for (int i = 1; i < nums.length; i++) { if (nums[i] == nums[i - 1]) return nums[i]; } return -1; } }在本方法中，对数组进行排序的时间复杂度为O(n·logn)，遍历数组的时间复杂度为O(n)，所以最终的时间复杂度为O(n·logn)，空间复杂度为O(1)。
从头到尾按顺序扫描整个数组的数字，每扫描到一个数字的时候，都可以用O(1)的时间来判断哈希表里是否包含了该数字，若哈希表中还没有这个数字，就将其加入到哈希表中，若有，那就get到结果了。
class Solution { public int findRepeatNumber(int[] nums) { HashSet<Integer> set = new HashSet<>(); for (int i = 0; i < nums.length; i++) { if (set.contains(nums[i])) return nums[i]; set.add(nums[i]); } return -1; } }在本方法中，由于在哈希表中的查找的时间复杂度为O(1)，所以该方法的时间复杂度为O(n)，但其提高了时间复杂度的同时，是以开辟一个哈希表为代价的，空间复杂度为O(1)。
这道题存在一个细节，就是数组长度为n，然后数组中的数字都是在0 ~ n-1的范围内，这也就是说，如果数组中没有重复元素，那么数组中的n个元素，一定分别为0、1、……、n-1。而如果没有重复的元素，那这些元素如果排序的话，其数组中的值恰恰等于索引值！所以我们可以考虑手动维护一个哈希表，将每个元素哈希映射到其该在的位置上。
从头到尾依次扫描数组中的每个数字n，当扫描到下标为i 的数字时 ，首先比较这个n是否等于i：
如果是，则扫描下一个数字；如果不是，则将它和第n个数字进行比较： 如果它和第n个数字相等，就找到了一个重复的数字；如果不相等，就把第i个数字和第n个数字交换，也就是吧数字n（第i个数字）放到它该在的位置上去重复上述比较，直到我们发现重复数字就可以返回结果，若遍历整个数组都没有，那么就是没有重复的数字。
class Solution { public int findRepeatNumber(int[] nums) { for (int i = 0; i < nums.length; i++) { //用while表示直到将其交换到其最终位置 while (nums[i] != i) { if (nums[nums[i]] == nums[i]) return nums[i]; swap(nums, i, nums[i]); } } return -1; } public void swap(int[] nums, int i1, int i2) { int tmp = nums[i1]; nums[i1] = nums[i2]; nums[i2] = tmp; } }在本方法中，时间复杂度为O(n)，空间复杂度也优化为了O(1)。
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。示例：
现有矩阵 matrix 如下： [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] 给定 target = 5，返回 true。 给定 target = 20，返回 false。暴力法虽然简单，但是其时间复杂度为O(n^2)，查找太慢
由于矩阵具有每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序的特点，如果我们首先选取矩阵中右上角的数字：
如果该数字num等于要查找数字target，则查找过程结束；如果该数字num大于要查找数字target，那么由于每一列都按照从上到下递增，所以可以剔除num所在的列；如果该数字num小于要查找数字target，那么由于每一行都按照从上到下递增，所以可以剔除num所在的行。用上述的查找方式，若数字target不在右上角的话，那么在该查找过程中，每次删选都会剔除一整行或一整列，这就大幅减少了查找的时间。
class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false; int rows = matrix.length, columns = matrix[0].length; int r = 0, c = columns - 1; while (r < rows && c >= 0) { if (matrix[r][c] == target) return true; else if (matrix[r][c] > target) c--; else r++; } return false; } }请实现一个函数，把字符串 s 中的每个空格替换成"%20"。示例：
输入：s = "We are happy." 输出："We%20are%20happy."这题作为Java语言实现其实没啥好说的，Java字符串也不像C字符串一样由\0结尾，这道题我就直接用StringBuilder可变数组做了：
class Solution { public String replaceSpace(String s) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == ' ') sb.append("%20"); else sb.append(s.charAt(i)); } return sb.toString(); } }首先定义链表的数据结构如下：
public class ListNode { int val; ListNode next; ListNode(int x) {this.val = x;} }输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。示例：
输入：head = [1,3,2] 输出：[2,3,1]由于题目要求从头到尾打印链表，也就是说是反着遍历链表，这无疑应该让我们想到先进后出的数据结构——栈，所以本题也自然而然的想到用栈来解决问题：
class Solution { public int[] reversePrint(ListNode head) { Deque<Integer> stack = new LinkedList<>(); ListNode cur = head; while (cur != null) { stack.push(cur.val); cur = cur.next; } int[] res = new int[stack.size()]; int i = 0; while(!stack.isEmpty()) res[i++] = stack.pop(); return res; } }首先定义二叉树的数据结构如下：
public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) {this.val = x;} }输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。示例：
给出： 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3 / \ 9 20 / \ 15 7先根据前序遍历的第一个数字创建根节点，然后在中序遍历序列中找到根节点的位置，这样就能够确定左、右子树节点的数量，在前序遍历和中序遍历序列中划分了左、右子树后，就可以调用递给函数继续构建其子树的左、右子树：
class Solution { int[] preorder; HashMap<Integer, Integer> map = new HashMap<>(); //存放元素在中序遍历中的索引 public TreeNode buildTree(int[] preorder, int[] inorder) { this.preorder = preorder; for (int i = 0; i < inorder.length; i++) { this.map.put(inorder[i], i); } return recursive(0, 0, inorder.length - 1); } public TreeNode recursive(int pre_root_idx, int in_left_idx, int in_right_idx) { if (in_left_idx > in_right_idx) return null; TreeNode root = new TreeNode(this.preorder[pre_root_idx]); int in_idx = map.get(this.preorder[pre_root_idx]); //得到根节点在中序序列中的索引 root.left = recursive(pre_root_idx + 1, in_left_idx, in_idx - 1); root.right = recursive(pre_root_idx + (in_idx - in_left_idx + 1), in_idx + 1, in_right_idx); return root; } }用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )。示例：
输入： ["CQueue","appendTail","deleteHead","deleteHead"] [[],[3],[],[]] 输出：[null,null,3,-1]用两个栈实现队列，我们可以用一个栈inStack只负责模拟入队，用另一栈outStack只负责模拟出队：
对于inStack模拟入队，就是每当有元素入队时，压入inStack即可；而对于outStack模拟出队：
当outStack不为空时，在outStack栈顶的元素即为最先进入队列的元素，弹出就可以模拟出队；当outStack为空时，我们就把inStack中的元素逐个弹出并压入outStack中，直到inStack中没有元素。由于先进入队列的元素被压倒inStack的底端，所以经过弹出压入操作后就处于了outStack的顶端，所以outStack顶端就又是第一个进入队列的元素，弹出就可以模拟出队 class CQueue { Deque<Integer> inStack; Deque<Integer> outStack; public CQueue() { this.inStack = new LinkedList(); this.outStack = new LinkedList(); } public void appendTail(int value) { inStack.push(value); } public int deleteHead() { if (inStack.isEmpty() && outStack.isEmpty()) return -1; if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.pop(); } }