共计 6200 个字符，预计需要花费 16 分钟才能阅读完成。
03. 数组中的反复数字
题目形容: 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范畴内。数组中某些数字是反复的，但不晓得有几个数字反复了，也不晓得每个数字反复了几次。请找出数组中任意一个反复的数字。示例 1：输出：[2, 3, 1, 0, 2, 5, 3] 输入：2 或 3。
思路一：排序
先对原数组进行排序，再在排序的数组中遍历，判断 num[n]和 nums[n+1]是否相等，如果相等就间接输入。这种思路比较简单，代码如下：
| class Solution {public int findRepeatNumber(int[] nums) {Arrays.sort(nums); | |
| for(int i=0;i<nums.length-1;i++) {if(nums[i] == nums[i+1]) {return nums[i]; | |
| } | |
| } | |
| return -1; | |
| } | |
| } |
复杂度剖析：
- 工夫复杂度：数组排序工夫复杂度为 O(nlogn)，数组遍历工夫复杂度为 O(n)，总的工夫复杂度为 O(nlogn)。
- 空间复杂度：没有引入额定的存储，因而空间复杂度为 O(1)。
思路二：哈希
引入一个哈希表，程序遍历数组，以数组元素值为 key，如果 key 不存在就退出哈希表，如果 key 存在就间接输入，代码如下：
| class Solution {public int findRepeatNumber(int[] nums) {HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>(); | |
| int result = -1; | |
| for(int i=0;i < nums.length;i++) {if(hashMap.get(nums[i]) == null) {hashMap.put(nums[i], 1); | |
| }else{result = nums[i]; | |
| break; | |
| } | |
| } | |
| return result; | |
| } | |
| } |
复杂度剖析：
- 工夫复杂度：对数组做一次遍历，工夫复杂度为 O(n)。
- 空间复杂度：应用了一个 Hash 表的额定存储，空间复杂度为 O(n)。
相比思路一，工夫复杂度晋升了，然而引入了额定的空间复杂度。
思路三：挪动
下面两种思路比拟通用，对于任何大小的数据都能实用，然而没有利用一个要害的信息：所有数字都在 0~n- 1 的范畴内。如果一个长度为 n 的数组没有反复，且所有数字都在 0~n- 1 的范畴内，其排序后的元素值与数组下标肯定是一一对应的。如果此时退出了一个反复元素，就会存在一个元素下标 i 等于其值 x，另一个下标 j 的值也等于 x 的状况。咱们的思路是，对于一个给定的数组，从第一个元素开始，做以下操作：
- 判断下标 i 和元素 nums[i]= x 是否相等，如果相等就跳过（i++）；不等就判断 nums[x]是否等于 x，如果相等就阐明找到反复数据了，否则：将 i 和 x 两个地位的元素替换地位，再进行判断，反复这个过程，直到满足 nums[i]= x 的条件。
以 [2, 3, 1, 0, 2, 5, 3] 为例，执行流程如下：
代码如下：
| class Solution {public int findRepeatNumber(int[] nums) {for(int i=0;i<nums.length;i++) {while(nums[i] != i) {if(nums[nums[i]] == nums[i]) {return nums[i]; | |
| } | |
| // 替换 | |
| int tmp = nums[i]; | |
| nums[i] = nums[tmp]; | |
| nums[tmp] = tmp; | |
| } | |
| } | |
| return -1; | |
| } | |
| } |
复杂度剖析：
- 工夫复杂度：代码中尽管有两重循环，然而每个数字最多替换两次就能找到属于他本人的地位，因而总的工夫复杂度为 O(n)。
- 空间复杂度：没有引入额定的存储，因而空间复杂度为 O(1)。
04. 二维数组中的查找
题目形容：在一个 n * m 的二维数组中，每一行都依照从左到右 非递加 的程序排序，每一列都依照从上到下 非递加 的程序排序。请实现一个高效的函数，输出这样的一个二维数组和一个整数，判断数组中是否含有该整数。示例数组：
[
[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]
]
思路：这道题目次要是找法则，跳出固定思维，找到利于计算机迭代计算的办法。须要关注运算的终点，如果这个终点在左上角或者右下角，那么横向或者纵向挪动数字的变化趋势是一样的，这就很难定位到应该往哪个方向挪动可能会定位到指标数字。而换个思路，从左下角（或者右上角）登程，向上的数字总是变小的，向右的数字总是变大的，这就很容易定位到指标数字的地位。实现上也比较简单，留神细节即可，代码如下：
| class Solution {public boolean findNumberIn2DArray(int[][] matrix, int target) {if(matrix == null || matrix.length == 0) {return false;} | |
| // 定义起始地位为左下角 | |
| int i = matrix.length - 1; | |
| int j = 0; | |
| while(i >= 0 && j < matrix[0].length) {if(matrix[i][j] == target) {return true;}else if(matrix[i][j] < target) {j++;}else{i--;} | |
| } | |
| return false; | |
| } | |
| } |
05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成 ”%20″。示例：输出：s = “We are happy.” 输入：“We%20are%20happy.”
这里须要留神一个点，如果字符串是可变的，且不要求原地替换，那么新建一个字符串，程序把相应的字符赋值即可。然而个别会要求在原字符串上操作以减少难度，以下都是基于这个限度条件的思路。
思路一：程序替换
程序遍历字符串，将空格替换为 20%，这是最直观的解法。然而这外面波及到一个问题：一个字符替换为三个字符，每次遇到空格都须要将残余的字符向后挪动 2 个地位，工夫复杂度为 O(n)，总的工夫复杂度为 O(n2）。代码如下（Java 字符串自身也是不可变的，须要转换成字符数组操作）：
| class Solution {public String replaceSpace(String s) {if(s == null || s.length() == 0) {return s;} | |
| // 统计空格个数以确定新字符串的长度 | |
| int count = 0; | |
| for (char c : s.toCharArray()) {if(c == ' ') count++; | |
| } | |
| // 创立新的字符数组 | |
| char[] chars = new char[s.length() + count * 2]; | |
| // 初始化字符数组 | |
| for (int i = 0; i < s.length(); i++) {chars[i] = s.charAt(i); | |
| } | |
| // 程序遍历替换 | |
| for (int i = 0; i < chars.length; i++) {if(chars[i] == ' ') {for (int j = chars.length - 1; j > i + 2 ; j--) { | |
| // 往后挪动两个地位 | |
| chars[j] = chars[j - 2]; | |
| } | |
| // 替换空格 | |
| chars[i] = '%'; | |
| chars[i+1] = '2'; | |
| chars[i+2] = '0'; | |
| } | |
| } | |
| // 返回字符串类型 | |
| return new String(chars); | |
| } | |
| } |
思路二：逆序替换
程序遍历的问题就是每次替换以后字符之后的那些字符都要向后挪动，如果换个思路，从后往前遍历，同时保护两个指针：left 和 right，left 指向原始字符串完结地位，right 指向替换后字符串的完结地位。从后往前遍历，如果没有遇到空格就顺次将 chars[left]的值赋给 chars[right]；遇到空格就填充 right、right- 1 和 right- 2 的地位。从而防止了反复挪动，工夫复杂度为 O(n)，代码如下：
| class Solution {public String replaceSpace(String s) {if(s == null || s.length() == 0) {return s;} | |
| // 统计数组长度和空格的个数 | |
| int n = s.length(); | |
| int count = 0; | |
| for(int i=0;i<n;i++) {if(s.charAt(i) == ' ') {count++;} | |
| } | |
| // 新增 char 数组 | |
| char[] arr = new char[n+count*2]; | |
| // 初始化 char 数组 | |
| for(int i=0;i<n;i++) {arr[i] = s.charAt(i); | |
| } | |
| // 从后往前遍历 | |
| int left = n - 1; | |
| int right = n + count*2 - 1; | |
| while(left >= 0) {if(arr[left] != ' ') {arr[right] = arr[left]; | |
| left--; | |
| right--; | |
| }else{arr[right-2] = '%'; | |
| arr[right-1] = '2'; | |
| arr[right] = '0'; | |
| left--; | |
| right -= 3; | |
| } | |
| } | |
| // 转换为 string 输入 | |
| return new String(arr); | |
| } | |
| } |
06. 从尾到头打印链表
输出一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
实现一：栈
单向链表自身是只能从头到尾遍历，这里要求从尾到头，刚好合乎 栈这个数据结构的特色：顺次遍历链表节点压栈，顺次弹出返回后果数组。代码如下：
| /** | |
| * Definition for singly-linked list. | |
| * public class ListNode { | |
| * int val; | |
| * ListNode next; | |
| * ListNode(int x) {val = x;} | |
| * } | |
| */ | |
| class Solution {public int[] reversePrint(ListNode head) {if(head == null) return new int[]{}; | |
| // 入栈并判断栈长度 | |
| int size = 0; | |
| Stack<ListNode> stack = new Stack<ListNode>(); | |
| while(head != null) {stack.push(head); | |
| head = head.next; | |
| size++; | |
| } | |
| // 弹出并返回数据 | |
| int[] res = new int[size]; | |
| for(int i=0;i<size;i++) {res[i] = stack.pop().val;} | |
| return res; | |
| } | |
| } |
实现二：递归
链表或者树这种数据结构人造就有递归的特点，且递归实质上也是通过虚拟机函数栈调用实现的。然而递归这种形式比拟反人类，须要思考透彻调用逻辑能力写进去正确的代码，外围：1. 递归终止条件 2. 递归返回形式。具体到这个题目，外围逻辑为：增加以后节点之前，先递归下个节点，增加以后节点。另外，须要定义成员变量 arraylist，每次遍历到以后节点就追加数据。代码如下：
| /** | |
| * Definition for singly-linked list. | |
| * public class ListNode { | |
| * int val; | |
| * ListNode next; | |
| * ListNode(int x) {val = x;} | |
| * } | |
| */ | |
| class Solution {List<Integer> resList = new ArrayList<Integer>(); | |
| public int[] reversePrint(ListNode head) {if(head == null) {return new int[0]; | |
| } | |
| reverse(head); | |
| //list2array | |
| int[] resArr = new int[resList.size()]; | |
| for(int i=0;i<resArr.length;i++) {resArr[i] = resList.get(i); | |
| } | |
| return resArr; | |
| } | |
| // 递归办法，每次增加元素前先递归下个节点 | |
| public void reverse(ListNode head) {if(head.next != null) {reverse(head.next); | |
| } | |
| resList.add(Integer.valueOf(head.val)); | |
| } | |
| } |
07. 重建二叉树
输出某二叉树的前序遍历和中序遍历的后果，请构建该二叉树并返回其根节点。
假如输出的前序遍历和中序遍历的后果中都不含反复的数字。
示例：前序{1,2,4,7,3,5,6,8} 中序{4,7,2,1,5,3,8,6}
思路：二叉树的前序和中序遍历可能惟一确定一棵二叉树。这道题目了解起来并不艰难，留神两点：1. 前序和中序遍历中根节点和左右子树的地位：前序根左右，中序左根右。2. 有急躁，一步一步画图了解算法迭代的过程，最终转换成代码实现。核心思想：先在前序里找到根节点，再在中序里找到根节点的地位将中序分成左右两局部，顺次迭代。示意图如下：
代码实现上须要留神的点：递归。一般来讲树的算法都能用递归实现且代码绝对简洁，应用整体思维，考查以后根节点的左右子树的时候将其视为一个整体，不关怀其子节点，可能升高了解的复杂度。具体代码如下：
| /** | |
| * Definition for a binary tree node. | |
| * public class TreeNode { | |
| * int val; | |
| * TreeNode left; | |
| * TreeNode right; | |
| * TreeNode(int x) {val = x;} | |
| * } | |
| */ | |
| class Solution { | |
| //HashMap 记录中序数组中值和索引的对应关系 | |
| public HashMap<Integer, Integer> inMap = new HashMap<Integer, Integer>(); | |
| public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder == null || preorder.length == 0) {return null;} | |
| int n = preorder.length; | |
| // 遍历中序结构 hashmap | |
| for (int i = 0; i < inorder.length; i++) {inMap.put(inorder[i], i); | |
| } | |
| return recurTree(preorder, inorder, 0, n-1, 0, n-1); | |
| } | |
| // 递归函数，以前后索引确定子数组的地位 | |
| public TreeNode recurTree(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight) {if(preLeft > preRight) {return null;} | |
| // 前序第一个节点为以后子树的根节点 | |
| int rootValue = preorder[preLeft]; | |
| TreeNode root = new TreeNode(rootValue); | |
| // 获取根节点在中序序列中的地位 | |
| int rootIndex = inMap.get(rootValue); | |
| // 确定左子树的节点数 | |
| int leftSize = rootIndex - inLeft; | |
| // 确定左右子树 | |
| root.left = recurTree(preorder, inorder, preLeft+1, preLeft+leftSize, inLeft, rootIndex-1); | |
| root.right =recurTree(preorder, inorder, preLeft+leftSize+1, preRight, rootIndex+1, inRight); | |
| return root; | |
| } | |
| } |
