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);}
};
