题目： 在一个长度为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
定义 在一个二叉搜索树中，每个结点的左右子树的高度差绝对值小于等于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 < val
题目 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 示例 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[i - dp[i-1] - 1] ==
题目 给你一个字符串 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 s 只包含从 a-z 的小写字母。 p 只包含从 a-z 的小写字母，以及字符 . 和 。 保证每次出现字符 时，前面都匹配到有效的字符 ###思路 状态定义
