力扣【leetcode】 算法基础21天刷题 记录篇一
菜鸡算法刷题打卡！！
⭐二分查找
34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
二分查找
两次二分查找应用
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n = nums.size();
int l = 0, r = n - 1;
int index1 = n, index2 = n;
// 获取第一个跟目标数相等的数的下标
while(l <= r){
int mid = l + (r - l) / 2;
if(nums[mid] >= target) {
r = mid - 1;
index1 = mid;
}
else{
l = mid + 1;
}
}
// 获取最后一个跟目标数相等的数的下标
l = 0, r = n - 1;
while(l <= r){
int mid = l + (r - l) / 2;
if(nums[mid] > target) {
r = mid - 1;
index2 = mid;
}
else{
l = mid + 1;
}
}
index2--;
if(index1 <= index2 && index2 < n && nums[index1] == target && nums[index2] == target){
return vector<int>{index1, index2};
}
else {
return vector<int>{-1, -1};
}
}
};
33. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., 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 。
// 旋转排序数组本质上就是两段升序数组,实际上,抽象讲就是经历一次的二分查找
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int l = 0, r = n - 1;
while(l < r) {
// r获取两段升序的衔接
if (nums[r] - nums[l] < 0){
r--;
}
else {
break;
}
}
// 分情况二分查找
int i, j;
if (target == nums[r]){
return r;
}
// 注意等号!若无,则会忽略第一个元素是寻找数的情况
else if(target >= nums[0] && target < nums[r]){
// target落在 0~r 间的升序数组
i = 0;
j = r - 1;
}
// target落在 r~n-1 间的升序数组
else if (target < nums[0]){
i = r + 1;
j = n - 1;
}
else {
return -1;
}
// 二分查找
while(i <= j) {
int mid = i + (j - i) / 2;
if (nums[mid] == target) {
return mid;
}
else if ( nums[mid] < target) {
i = mid + 1;
}
else{
j = mid - 1;
}
}
return -1;
}
};
74. 搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int n = matrix[0].size(), m = matrix.size();
int l = 0, r = m * n -1;
while(l <= r){
int mid = l + (r - l) / 2;
if (matrix[mid / n][mid % n] == target) {
return true;
}
else if (matrix[mid / n][mid % n] < target) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
return false;
}
};
153. 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
// 利用旋转，产生两段升序的数组，则找到分界点，利用升序特点进行求解最小值
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
int l = 0, r = n - 1;
while(l <= r) {
if (nums[r] - nums[l] < 0) {
r--;
}
else{
break;
}
}
// 若直接是升序数组，则两段升序数组并不存在，可直接返回
if (r != n-1) {
return min(nums[0],nums[r + 1]);
}
else {
return nums[0];
}
}
};
162. 寻找峰值
峰值元素是指其值大于左右相邻值的元素。
给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
// 需要再考虑一种情况，即升序，无降，此时返回数组最后一个位置
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int n = nums.size();
int i = 0;
int index = -1;
while(i < n-1){
if (nums[i] < nums[i+1]) {
i++;
}
else {
index = i;
break;
}
}
if (i == n-1){
index = n-1;
}
return index;
}
};
⭐双指针
82. 删除排序链表中的重复元素 II
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head){
return head;
}
ListNode* dumpy = new ListNode(0, head);
ListNode* cur = dumpy;
// 遍历整个链表
while(cur->next && cur->next->next) {
// 找到重复的链表，进行循环替代
if(cur->next->val == cur->next->next->val) {
int x = cur->next->val;
while(cur->next && cur->next->val == x){
cur->next = cur->next->next;
}
}
else{
cur = cur->next;
}
}
return dumpy->next;
}
};
15. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
// 对数组进行升序排序,k指针从头遍历.利用i j双指针进行移动
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> sum;
// 进行排序
sort(nums.begin(), nums.end());
for(int k = 0; k < nums.size(); ++k){
// 正数,相加也不会等于0
if(nums[k] > 0) {
break;
}
// 相等
if(k > 0 && nums[k] == nums[k - 1]) {
continue;
}
int i = k + 1, j = n - 1;
while(i < j) {
int ans = nums[k] + nums[i] + nums[j];
// <0 说明负数这边更大,因此移动左指针,使得和接近0
if( ans < 0) {
while(i < j && nums[i] == nums[++i]);
}
else if (ans > 0) {
while(i < j && nums[j] == nums[--j]);
}
else{
sum.push_back(vector<int> {nums[k], nums[i], nums[j]});
while(i < j && nums[i] == nums[++i]);
while(i < j && nums[j] == nums[--j]);
}
}
}
return sum;
}
};
844. 比较含退格的字符串
给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
class Solution {
public:
bool backspaceCompare(string s, string t) {
return backTo(s) == backTo(t);
}
string backTo(string str) {
string s;
for (char ch : str) {
if(ch != '#') {
// 把非#的字符插入字符串
s.push_back(ch);
}
else if (! s.empty()) {
// 遇到#,将此时字符串中的最后一个字符切除
s.pop_back();
}
}
return s;
}
};
986. 区间列表的交集
给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。
返回这 两个区间列表的交集 。
形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。
两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。
class Solution {
public:
vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
vector<vector<int>> ans;
int i = 0, j = 0;
while (i < firstList.size() && j < secondList.size()) {
int low = max(firstList[i][0], secondList[j][0]);
int high = min(firstList[i][1], secondList[j][1]);
if (low <= high) {
ans.push_back(vector<int> {low, high});
}
if (firstList[i][1] < secondList[j][1]) {
i++;
}
else{
j++;
}
}
return ans;
}
};
11. 盛最多水的容器
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。
class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0, r = height.size() - 1;
int ans = 0;
while (l < r) {
int area = min(height[l], height[r]) * (r - l);
ans = max(ans, area);
if (height[l] <= height[r]) {
++l;
}
else {
--r;
}
}
return ans;
}
};
⭐滑动窗口
438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指字母相同，但排列不同的字符串。
// 类似567. 字符串的排列。也就是说只需考虑字母出现的次数以及总长度即可
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int n = p.length();
vector<int> a(26,0);
for(auto c : p){
a[c-'a']++;
}
int l = 0, r = 0;
vector<int> a1(a);
vector<int> index;
while(r < s.size()){
a1[s[r] - 'a']--;
while(a1[s[r] - 'a'] < 0){
a1[s[l] - 'a']++;
l++;
}
if(n == r - l + 1) {
index.push_back(l);
}
r++;
}
return index;
}
};
713. 乘积小于K的子数组
给定一个正整数数组
nums和整数k。请找出该数组内乘积小于
k的连续的子数组的个数。
简单思路，就是从第一个数开始往后迭乘，超过k则跳出循环、
class Solution { public: int numSubarrayProductLessThanK(vector<int>& nums, int k) { int n = nums.size(); int l = 0, r = 0, cnt; int sum = 0; while(l < n) { r = l; cnt = 1; while(r < n) { cnt *= nums[r++]; if(cnt >= k){ break; } sum++; } l++; } return sum; } }; // 但是很遗憾，超出时间限制。于是我们换个思路来解决该难题。 // 之前我们一直是遍历数组进行迭乘，那么我们是否可以只迭乘一次？ // 将右指针固定移动遍历。利用左指针缩短左右指针间隔？ 如下：
√ 通过
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
// 正整数乘积小于1，不存在直接返回。
if(k <= 1)
return 0;
int l = 0, r = 0, n = nums.size();
int sum = 0, cnt = 1;
while(r < n) {
// 右指针进行移动，一直迭乘
cnt *= nums[r];
while(cnt >= k) {
// 左指针进行移动条件为 迭乘超过k
cnt /= nums[l++];
}
// 左右指针间隔差即为小于k的连续子数组的个数
sum += r - l + 1;
r++;
}
return sum;
}
};
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
跟上一题差不多
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
if(n == 0){
return 0;
}
int mins = n;
int l = 0, r = 0, len = 0;
int sum = 0;
bool flag = false;
while(r < n){
sum += nums[r];
while(sum >= target) {
len = r - l + 1;
mins = min(mins, len);
sum -= nums[l];
l++;
// 标记存在符合条件的连续子数组
flag = true;
}
r++;
}
if(!flag)
mins = 0;
return mins;
}
};