百度账号中心官网,湘乡网站seo,域名网站备案,人工智能ai写作网站免费目录 1.leetcode-59. 螺旋矩阵 II#xff08;题2.题3相当于二分变形#xff09;2.leetcode-33. 搜索旋转排序数组3.leetcode-81. 搜索旋转排序数组 II(与题目2对比理解)#xff08;题4和题5都是排序双指针#xff09;4.leetcode-15. 三数之和5.leetcode-18. 四数之和6.leet… 目录 1.leetcode-59. 螺旋矩阵 II题2.题3相当于二分变形2.leetcode-33. 搜索旋转排序数组3.leetcode-81. 搜索旋转排序数组 II(与题目2对比理解)题4和题5都是排序双指针4.leetcode-15. 三数之和5.leetcode-18. 四数之和6.leetcode-80. 删除有序数组中的重复项 II通解方法 1.leetcode-59. 螺旋矩阵 II
1题目描述 给你一个正整数 n 生成一个包含 1 到 n2 所有元素且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 2方法与思路模拟 1.首先明白螺旋矩阵的拐点是在哪里并且在旋转一周后边界值会有哪些变化。 2.先定义四个变量分别来表示这个正方形的上左下右的边界值。 3.走完一条边就要将这条边减去一。 4.终止条件就是数组元素所给值达到n*n。 3代码实现
class Solution {
public:vectorvectorint generateMatrix(int n) {int t 0; // topint b n-1; // bottomint l 0; // leftint r n-1; // rightvectorvectorint ans(n,vectorint(n));int k1;while(kn*n){for(int il;ir;i,k) ans[t][i] k;t;for(int it;ib;i,k) ans[i][r] k;--r;for(int ir;il;--i,k) ans[b][i] k;--b;for(int ib;it;--i,k) ans[i][l] k;l;}return ans;}
};题2.题3相当于二分变形
2.leetcode-33. 搜索旋转排序数组
1题目描述 整数数组 nums 按升序排列数组中的值 互不相同 。 在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了 旋转使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]下标 从 0 开始 计数。例如 [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。 给你 旋转后 的数组 nums 和一个整数 target 如果 nums 中存在这个目标值 target 则返回它的下标否则返回 -1 。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 2方法及思路二分查找虽然可以直接查找但是还是多练练吧嘻嘻 先上图 由此图可以看出分两种不同情况在由mid第一次分开后 1.target落在左右半部分有序部分中。 2.target还是落在错位的区间即不有序那就在while循环中进行再分。但是要更新左右的值 如果左半部分不是有序那右半部分必有序反之也一样 3代码实现
class Solution {
public:int search(vectorint nums, int target) {int n (int)nums.size();if (!n) {return -1;}if (n 1) {return nums[0] target ? 0 : -1;}int l 0, r n - 1;while (l r) {int mid (l r) / 2;if (nums[mid] target) return mid;if (nums[0] nums[mid]) {if (nums[0] target target nums[mid]) {r mid - 1;} else {l mid 1;}} else {if (nums[mid] target target nums[n - 1]) {l mid 1;} else {r mid - 1;}}}return -1;}
};3.leetcode-81. 搜索旋转排序数组 II(与题目2对比理解)
1其他条件与上题相同唯有此题中数组是非降序。 2方法与思路二分查找 思路 1.对于数组中有重复元素的情况二分查找时可能会有 a[l]a[mid]a[r]此时无法判断区间 [l,mid] 和区间 [mid1,r] 哪个是有序的。
2.例如 nums[3,1,2,3,3,3,3]target2首次二分时无法判断区间 [0,3][0,3][0,3] 和区间 [4,6][4,6][4,6] 哪个是有序的。
3.对于这种情况我们只能将当前二分区间的左边界加一右边界减一然后在新区间上继续二分查找。 3代码实现
class Solution {
public:bool search(vectorint nums, int target) {int n nums.size();if (n 0) {return false;}if (n 1) {return nums[0] target;}int l 0, r n - 1;while (l r) {int mid (l r) / 2;if (nums[mid] target) {return true;}if (nums[l] nums[mid] nums[mid] nums[r]) {l;--r;} else if (nums[l] nums[mid]) {if (nums[l] target target nums[mid]) {r mid - 1;} else {l mid 1;}} else {if (nums[mid] target target nums[n - 1]) {l mid 1;} else {r mid - 1;}}}return false;}
};题4和题5都是排序双指针
4.leetcode-15. 三数之和
1)题目描述 给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意答案中不可以包含重复的三元组。 (2)方法与思路排序双指针 1.对数组进行排序。 2.遍历排序后数组 若 nums[i]0因为已经排序好所以后面不可能有三个数加和等于 0直接返回结果。 对于重复元素跳过避免出现重复解
3.令左指针 Li1右指针 Rn−1当 LR时执行循环
4.当 nums[i]nums[L]nums[R]0执行循环判断左界和右界是否和下一位置重复去除重复解。并同时将 L,RL,RL,R 移到下一位置寻找新的解 若和大于 0说明 nums[R]太大R 左移 若和小于 0说明 nums[L] 太小L 右移
class Solution {
public:vectorvectorint threeSum(vectorint nums) {int nnums.size();sort(nums.begin(),nums.end());vectorvectorint ans;for(int first0;firstn;first){if(first0nums[first-1]nums[first]){continue;}int thirdn-1;for(int secondfirst1;secondn;second){if(secondfirst1nums[second-1]nums[second]){continue;}while(second third nums[first]nums[second]nums[third]0){third--;}if(secondthird){break;}if (nums[first]nums[second] nums[third] 0) {ans.push_back({nums[first], nums[second], nums[third]});}}}return ans;}
};5.leetcode-18. 四数之和
1题目简述 给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复 2方法及思路排序双指针 1.首先要定义四个指针first0, secondfirst1, thirdsecond1, forthn-1(这是四个指针的初始位置)后续过程还要进行循环。 2.其次是对于重复元素的处理切记要放在循环当中否则只能除掉一个重复尤其是third 3.接着是对于结果的排查如果结果小于0third右移如果结果大于0forth左移。 4.最后将找到的值插入新的数组中。
3代码实现
class Solution
{
public:vectorvectorint fourSum(vectorint num, int target){vectorvectorint newnum;sort(num.begin(), num.end());int n num.size();for (int first 0; first n; first){if (first 0 num[first] num[first - 1])continue;for (int second first 1; second n; second){if (second first 1 num[second] num[second - 1])continue;int third second 1;int forth n - 1;long long target_c (long long)target - num[first] - num[second];while (third forth){if (target_c num[third] num[forth]) {newnum.push_back({ num[first], num[second], num[third], num[forth] });do {third;} while (third n num[third] num[third - 1]);}else if (target_c num[third] num[forth]){third;}elseforth--;}}}return newnum;}
};6.leetcode-80. 删除有序数组中的重复项 II
(1)题目描述 给你一个有序数组 nums 请你 原地 删除重复出现的元素使得出现次数超过两次的元素只出现两次 返回删除后数组的新长度。 不要使用额外的数组空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 2方法及思路双指针 1.首先定义slow和fast位于第三个位置 2.如果slow-2和fast的元素相同fast 3.如果slow-2和fast不同将slow处的元素替换为fast处的元素并且和fast一起往前移。 3代码实现
class Solution {
public:int removeDuplicates(vectorint nums) {int n nums.size();if (n 2) {return n;}int slow 2, fast 2;while (fast n) {if (nums[slow - 2] ! nums[fast]) {nums[slow] nums[fast];slow;}fast;}return slow;}
};通解方法
为了让解法更具有一般性我们将原问题的「保留 2 位」修改为「保留 k 位」。 由于是保留 k 个相同数字对于前 k 个数字我们可以直接保留 对于后面的任意数字能够保留的前提是与当前写入的位置前面的第 k 个元素进行比较不相同则保留 举个例子[1,1,1,1,1,1,2,2,2,2,2,2,3] 1.首先我们先让前 2 位直接保留得到 1,1 2.对后面的每一位进行继续遍历能够保留的前提是与当前位置的前面 k 个元素不同答案中的第一个 1因此我们会跳过剩余的 1将第一个 2 追加得到 1,1,2 3.继续这个过程这时候是和答案中的第 2 个 1 进行对比因此可以得到 1,1,2,2 4.这时候和答案中的第 1 个 2 比较只有与其不同的元素能追加到答案因此剩余的 2 被跳过3 被追加到答案1,1,2,2,3 代码实现
class Solution {
public:int work(vectorint nums, int k) {int len 0;for(auto num : nums)if(len k || nums[len-k] ! num)nums[len] num;return len;}int removeDuplicates(vectorint nums) {return work(nums, 2);}
};
