数据结构系统刷题

本文为系统刷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(logn)$
k:$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(logn)$
k:$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)$
k：$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)$
k：$O(n)$
209. 长度最小的子数组

59. 螺旋矩阵 II