code-016

题目描述 解题思路快慢指针； 题解123456789101112131415161718192021222324/*time: O(n)space:O(1)*/class Solution {public: int removeDuplicates(vector<int>& nums) { int len = nums.size(); if(len < 1) return len; int fast = 1, slow = 1; while(fast < len) { if(nums[fast] != nums[fast - 1]) { nums[slow] = nums[fast]; ++slow; } ++fast; } return ...

题目描述 题解思路：两个边界哪个小，收缩哪个 123456789101112131415class Solution {public: int maxArea(vector<int>& height) { int left = 0; int right = height.size() - 1; int maxarea = 0; while(left < right) { int cur_area = min(height[left], height[right]) * (right - left); maxarea = max(maxarea, cur_area); height[left] < height[right] ? ++left : --right; } return maxarea; }};

题目描述 题解1234567891011121314151617181920212223242526class Solution {public: int lengthOfLongestSubstring(string s) { int len = s.size(); if (len == 0) return 0; //保存字符 unordered_set<char> usc; int maxlen = 0; int mark = -1; for (int i = 0; i < len; ++i) { if (i != 0) { usc.erase(s[i - 1]); } //该字符未插入unordered_set while (mark + 1 < le ...

题目描述 题解123456789101112131415161718192021222324class Solution {public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int totalsize = nums1.size() + nums2.size(); if (totalsize == 0) return 0; int midpos = totalsize / 2; vector<int> newnums; newnums.reserve(totalsize); for (const auto& x : nums1) { newnums.push_back(x); } for (const auto& x : ...

题目描述 题解一：贪心1234567891011121314151617class Solution {public: int maxSubArray(vector<int>& nums) { int len = nums.size(); if(len == 0) return -2147483648; //当前和 int cur_sum = nums[0]; //最大和 int max_sum = nums[0]; for(int i = 1; i < len; ++i) { cur_sum = max(nums[i], cur_sum + nums[i]); max_sum = max(max_sum, cur_sum); } return max_sum; }}; 题解二：动态规划123456789 ...

题目描述 题解一：暴力for1234567891011121314151617181920class Solution {public: bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) { int ln = matrix.size(); if(ln == 0 ) return false; int lm = matrix.front().size(); for(int i = 0; i < ln; ++i) { for(int j = 0; j < lm; ++j) { if(matrix[i][j] == target) { return true; ...

题目描述 题解：修改了数组原数据123456789101112131415161718class Solution {public: int findRepeatNumber(vector<int>& nums) { for(int i = 0; i < nums.size(); ++i) { while(nums[i] != i) { if(nums[i] == nums[nums[i]]) { return nums[i]; } //交换 std::swap(nums[i], nums[nums[i]]); } } return -1; }} ...

一、实例我们通过一个实例来说明整个结点的插入导致失衡的过程 （1）AVL初始状态 （2）不失平衡的插入 （3）失去平衡的插入我们在(2)的基础上增加了以下两种情况 注意： 上图的结点的平衡因素只设置了一部分 二、构建过程分析（1）大体流程 （2）具体函数功能1. insert该函数的主要功能就是根据二叉搜索树的insert函数增加了个PassBalance函数进行结点的平衡1234567891011121314151617181920212223242526272829303132333435//插入函数bool insert(AVLTree& tree, ElemType val){ if (tree == nullptr) { tree = BuyNode(val); return true; } AVLNode* pa = nullptr; AVLNode* ptr = tree; while (ptr != nullptr && ptr->key != val) { pa = ptr; ptr = ...

一、引入AVL树 AVL树是二叉搜索树的升级版，是为了优化整个二叉树的结构并且提高查找速率的一棵特殊的二叉搜索树。平衡二字体现了该树会对插入/删除的结点后进行自动“平衡”（通过旋转进行实现）。 二、AVL树的要求 平衡状态： 当前结点的右子树深度 - 左子树深度 == -1 or 0 or 1 三、AVL树结构设计AVL.h123456789101112#ifndef AVL_H#define AVL_Husing ElemType = int;typedef struct AVLNode{ ElemType key; AVLNode* leftchild; AVLNode* rightchild; AVLNode* parent; int balance;}AVLNode, *AVLTree; 四、旋转 当插入结点时，会出现以下情况：使树失衡，对此有两种应对策略（实质上都是旋转），通过旋转能够对失衡的树进行再次平衡 五、单左旋（1）单左旋三大关键步骤 （2）单左旋完整过程 （3）单左旋代码1234567891011121314151617181920 ...

题目描述： 题解一：计数填充法123456789101112131415161718192021222324252627282930class Solution {public: void sortColors(vector<int>& nums) { //分别计算出0 1 2的个数，在使用其个数进行填充即可 int zero = 0; int one = 0; int two = 0; for(int i = 0; i < nums.size(); ++i){ if(nums[i] == 0){ ++zero; } else if(nums[i] == 1){ ++one; } else{ ++two; ...