数据结构系统刷题
本文为系统刷leetcode的记录，会记录自己根据代码随想录刷过的leetcode，方便直接点开刷题，时常更新
时间复杂度简记为s
空间复杂度简记为k
数组
704 二分查找
一维二分查找
（1）[left, right]
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;while (left <= right) {int mid = (left + right) / 2;if (nums[mid] > target) {right = mid - 1;} else if (nums[mid] < target) {left = mid + 1;} else {return mid;}}return -1;}
};
s: O ( l o g n ) O(logn) O(logn)
k: O ( 1 ) O(1) O(1)
（2）[left, right)
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size();while (left < right) {int mid = (left + right) / 2;if (nums[mid] > target) {right = mid;} else if (nums[mid] < target) {left = mid + 1;} else return mid;}return -1;}
};
s: O ( l o g n ) O(logn) O(logn)
k: O ( 1 ) O(1) O(1)
二维二分查找：74. 搜索二维矩阵
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size();int n = matrix[0].size();int low = 0;int high = m * n - 1;while (low <= high) {int mid = (low + high) / 2;int num = matrix[mid / n][mid % n]; // 第一个是确定第几行，第二个是确定第几列，相当于把matrix降维成一维，比如要找一个4*4数组的第13个元素，13/4 = 3，为第四行（行索引是0开始），13%4=1，即第四行第一个if (num < target) {low = mid + 1;} else if (num > target) {high = mid - 1;} else return true;}return false;}
};
27. 移除元素
class Solution {
public:int removeElement(vector<int>& nums, int val) {int slow = 0;for (int fast = 0; fast < nums.size(); fast++) {if (nums[fast] != val) {nums[slow++] = nums[fast];}}return slow;}
};
s： O ( n ) O(n) O(n)
k： O ( 1 ) O(1) O(1)
977. 有序数组的平方
class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int k = nums.size() - 1;vector<int> result(nums.size(), 0);for (int i = 0, j = nums.size() - 1; i <= j;) {if (nums[i] * nums[i] > nums[j] * nums[j]) {result[k--] = nums[i] * nums[i];i++;} else {result[k--] = nums[j] * nums[j];j--;}}return result;}
};
s： O ( n ) O(n) O(n)
k： O ( n ) O(n) O(n)
209. 长度最小的子数组
59. 螺旋矩阵 II