704.二分查找
- 题目链接:704.二分查找
- 思路:二分法查找,有不同的方式,闭区间,左闭右开,开区间
- 代码如下:
class Solution {
public:// 闭区间int Dichotomy1(int n, int l, int r) {r = n - 1;while(l <= r) {int mid = l + (r - l) / 2;if(nums[mid] < target) {l = mid + 1;} else {r = mid - 1;}}return left;}// 左闭右开int Dichotomy2(int n, int l, int r) {while(l < r) {int mid = l + (r - l) / 2;if(nums[mid] < target) {l = mid + 1;} else {r = mid;}}return left;}// 开区间int Dichotomy3(int n, int l, int r) {while(l < r) {int mid = l + (r - l) / 2;if(nums[mid] < target) {l = mid;} else {r = mid;}}return right;}int search(vector<int>& nums, int target) {int n = nums.size();int l = 0, r = n;Dichotomy2(n, r, l)}
};
27. 移除元素
- 题目链接:27. 移除元素
- 思路:题目一开始做的时候直接想的是暴力法,直接新建一个数组,记录不等val的数,然后赋值到原数组中,后来思考参考灵神的解法,遍历原数组,直接赋值即可
- 代码:
class Solution {
public:// 暴力法int f1(vector<int>& nums, int val) {int n = nums.size();vector<int> t(n, 0);int k = 0;for(int i = 0; i < n; i++) {if(nums[i] != val) {t[k++] = nums[i];}}for(int i = 0; i < k; i++) {nums[i] = t[i];}return k;}// 原地法int f2(vector<int>& nums, int val) {int k = 0;for(int x : nums) {if(x != val) {nums[k++] = x;} }}int removeElement(vector<int>& nums, int val) {return f2(nums, val);}
977.有序数组的平方
- 题目链接:977.有序数组的平方
- 思路:
- 暴力法:直接新建一个数组,存储当前数的平方,然后排序
- 双指针:参考灵神的思路,本题的数组的数有小于0的部分,和大于等于0的部分,非递减序列,数字一定是升序,所以数的平方值最大的两个一定是第一个或者是最后一个,所以使用双指针,分别比较第一个和最后一个数的平方的大小,平方数的大的放到新的数组的最后一个,然后对应指针往前或者往右移一位,以此循环,最终全部填充
- 代码:
class Solution {
public:vector<int> f1(vector<int>& nums) {int n = nums.size();vector<int> ans(n, 0);for(int i = 0; i < n; i++) {ans[i] = nums[i] * nums[i];}sort(ans.begin(), ans.end());return ans;}vector<int> f2(vector<int>& nums) {int n = nums.size();vector<int> ans(n);int i = 0, j = n - 1, t = n - 1;while(t >= 0) {if(-nums[i] < nums[j]) {ans[t--] = nums[j] * nums[j];j--;} else {ans[t--] = nums[i] * nums[i];i++;}}return ans;}vector<int> sortedSquares(vector<int>& nums) {return f2(nums);}
};