题目：在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或3.思路一：遍历数组，统计每个数字出现的次数，如果当前数字出现过，则返回结果。时间复杂度O(n),空间复杂度O(n)思路二：记数组为nums，遍历数组时看当前数字nums[i]和下标i是否相等，如果相等，则略过。如果不等，则查看nums[i]和nums[nums[i]]是否相等，如果相等，则找到重复数字，如果不等则交换nums[i]和nums[nums[i]]，直到num[i]和i相等或者找到重复数字。需要修改输入数组，时间复杂度O(n),空间复杂度O(1)代码class Solution { public: int findRepeatNumber(vector<int>& nums) { int size = nums.size(); for(int i = 0;i

定义在一个二叉搜索树中，每个结点的左右子树的高度差绝对值小于等于1的二叉搜索树，被称为平衡二叉树。avl树是最早出现的平衡二叉树。优势avl树的查找、插入、删除的时间复杂度都是O(logN)平衡因子平衡因子是左子树的高度减去右子树的高度所得结果，记为bf,bf的合法范围为-1,0,1。某个结点的平衡因子超出这个范围，那么这个结点就是不平衡的。需要做旋转处理。当bf的值为-2或2时，即左子树的高度比右子树的高度小2或左子树的高度比右子树的高度大2，做树旋转。树旋转左左旋转如果插入的新结点是当前结点的左子树的左孩子,做一次右旋转即可平衡，称为左左旋转右右旋转如果插入的新结点是当前结点右子树的右孩子，做一次左旋转即可平衡，称为右右旋转左右旋转如果插入的新结点是当前结点左子树的右孩子，需要做两次旋转，先做一次左旋转，再做一次右旋转，称为左右旋转右左旋转如果插入的新结点是当前结点右子树的左孩子，也需要做两次旋转，先做一次右旋转，再做一次左旋转，称为右左旋转插入按照普通的搜索二叉树来插入，然后判断树是否平衡，如果不平衡，则做树旋转，使之重新平衡。第一步，按照普通二叉搜索树的插入算法来插入新结点，上

定义二叉搜索树是这样的一颗二叉树，如果左子树不空，则左子树上的所有结点都比根结点小。如果右子树不空，则右子树上的所有结点都比根结点大。左子树和右子树也是一颗二叉搜索树。构建插入结点x,比较x和根结点的值，如果x大，则把x插入右子树，x小，则把x插入左子树。struct TreeNode { int value; TreeNode* left; TreeNode* right; }; TreeNode* BSTInsert(TreeNode* root, int value) { if (root == nullptr) { root = (TreeNode*)malloc(sizeof(TreeNode)); return root; } if (root->value > value) { root->left = BSTInsert(root->left,value); } else if (root->value < value)

题目给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。示例 1：输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"示例 2：输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"示例 3：输入：s = "" 输出：0提示：0 <= s.length <= 3 * 104 s[i] 为 '(' 或 ')'思路定义dp[i]表示以字符s[i]结尾的有效子串的长度，这个长度包含字符s[i]。如果s[i] == '('，那么dp[i] = 0。如果s[i] == ')',s[i-1]=='(',dp[i] = dp[i-2] + 2。如果s[i] == ')',s[i-1] == ')',假如i - dp[i-1] - 1位置为'(',则dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2比如字符串)()(())),对于位置6,s[6] == ')',s[5] ==

题目给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。'.' 匹配任意单个字符'*' 匹配零个或多个前面的那一个元素所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。 示例 1：输入：s = "aa", p = "a" 输出：false 解释："a" 无法匹配 "aa" 整个字符串。示例 2:输入：s = "aa", p = "a*" 输出：true 解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。示例 3：输入：s = "ab", p = ".*" 输出：true 解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。提示：1 <= s.length <= 20 1 <= p.length <= 20