题目：输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。思路：思路比较直白，由前序遍历可得根节点，然后由中序遍历得左右子树。左右子树重复这个过程。即递归。代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: //找到目标数的下标 int helpIndex(vector<int>& nums,int start,int end,int target) { int n = nums.size(); for(int i = start;i <= end;i+
题目：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。示例 1：输入：head = [1,3,2]输出：[2,3,1]思路一：从尾到头，刚好是先进后出，栈结构，把链表从头到尾依次入栈，然后从栈顶到栈底，依次出栈，即是答案。代码:/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: vector<int> reversePrint(ListNode* head) { if (head == nullptr) { return {}; } stack<int> stk; ListNode* tmp = head; while(t
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。思路：二分法。旋转之后，旋转部分比未旋转部分小，两个指针left、right，第一个指针left指向查找范围的第一个数，第二个指针right指向查找范围的最后一个数，然后取中间值mid，如果中间值比right指向的数大，说明mid位于未旋转部分，令left = mid+1,如果mid指向的数比right指向的数小，则right = mid。如果right==left则说明left指向的数就是要找的答案。特殊情况，旋转部分的长度为0，此时最小数为数组的第一个数,此时mid指向的数一直小于right指向的
题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。思路：这种递增的特征很容易联想到二分法。每一行从左到右递增，每一列从上到下递增，那么右上角的那个数字就是中间数字，大于左边的数字，小于下面的数字。可以用二分法。代码：class Solution { public: bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) { int m = matrix.size(); if(m == 0) { return false; } int n = matrix[0].size(); int row = 0,col = n-1; while(row < m && col >=0) { if(
题目：在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出时重复的数字2或者3思路：把从1～n的数字从中间的数字m分为两部分，前面一半为1～m，后面一半为m+1~n。如果1～m的数字的数目超过m，那么这一半的区间里一定包含重复的数字；否则，另一半m+1~n的区间里一定包含重复的数字。继续把包含重复数字的区间一分为二，直到找到一个重复的数字。时间复杂度O(nlogN),空间复杂度O(1)。代码int getDuplication(const int* numbers, int length) { if(numbers == nullptr || length <= 0) return -1; int start = 1; int end = length - 1; while(end >= start) { int middle = (
