Leetode刷题记录
编辑
114
2024-06-09
Leetcode刷题记录
最近在跟着代码随想录刷Leetcode, 在此进行记录
我的所有代码都存在了我的gitee仓库中
1. 数组
704. 二分查找
二分查找的重点在于区间的定义:左开右闭,还是左闭右开
定义影响的是:
r = nums.size()还是r = nums.size() - 1while(l < r)还是while(l <= r)- 在
nums[mid] > target的情况下,r = mid还是r = mid - 1
我的初始代码:
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
int mid = (l + r) >> 1;
int flag = 1;
while (l <= r) {
mid = (l + r) >> 1;
if (nums[mid] > target) {
// 注意, 如果为mid,可能导致边界无法取到
r = mid - 1;
} else if (nums[mid] < target) {
// 注意, 如果为mid,可能导致边界无法取到
l = mid + 1;
} else {
flag = 0;
break;
}
}
if (flag) {
return -1;
} else {
return mid;
}
}
};
边界条件根据直觉来写的, l,r是两个能够取到的两个边界,因为想着可能出现l和r指向同一个位置,然后因为想着l = r - 1时,可以取到r,所以写成l = mid + 1
按照卡哥的讲解,咱们需要注意不变量,即咱们区间的取值范围,按照行业内的规则,一般取为左闭右闭或左闭右开,根据这两个条件,有以下两个解法
左闭右开
class Solution {
public:
// 左闭右开
int search(vector<int>& nums, int target) {
// 左闭右开,所以l=0, 而r为最右边第一个取不到的正整数
int l = 0, r = nums.size();
int mid;
// 因为是左闭右开,所以l可以取到,而r不能取到,所以循环条件为l < r
while (l < r) {
mid = (l + r) >> 1;
if (nums[mid] > target) {
// 已经判断nums[mid]为当前最大不能取到的值,所以可以作为有边界
r = mid;
} else if (nums[mid] < target) {
// 因为是左闭,所以将左边界设为当前最小的可能取值
l = mid + 1;
} else {
// 剩下相等的情况直接返回mid的值
return mid;
}
}
// 范围不断收缩,知道循环完毕,若循环完毕而没有结束,则返回-1
return -1;
}
};
左开右闭
class Solution {
public:
// 左闭右闭
int search(vector<int>& nums, int target) {
// 左闭右闭,所以l=0, 而r为最右边最大可以取到到的正整数
int l = 0, r = nums.size() - 1;
int mid;
// 因为是左闭右闭,所以l可以取到,r也可以取到,存在l = r的情况,所以循环条件为l
// <= r
while (l <= r) {
mid = (l + r) >> 1;
if (nums[mid] > target) {
// 已经判断nums[mid]为当前最大不能取到的值,所以右边界为mid - 1
r = mid - 1;
} else if (nums[mid] < target) {
// 因为是左闭,所以将左边界设为当前最小的可能取值
l = mid + 1;
} else {
// 剩下相等的情况直接返回mid的值
return mid;
}
}
// 范围不断收缩,知道循环完毕,若循环完毕而没有结束,则返回-1
return -1;
}
};
27. 移除元素
^52cd32
题目链接: 27. 移除元素 - 力扣（LeetCode）
本题使用了双指针的方法,一个fast指针和一个slow指针,slow指针指向要放入元素的位置,而fast指针指向要判断是否可以放入的元素,两个指针一快一慢,可以在时间复杂度为O(n)的情况下对所有元素进行判断处理
代码实现:
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int fast = 0, slow = 0;
int lens = nums.size();
while (fast < lens) {
if (nums[fast] != val) {
nums[slow++] = nums[fast++];
} else {
fast++;
}
}
return slow;
}
};
977. 有序数组的平方
^bcb23c
此题也使用了双指针的方法,一个left指针和一个right指针,因为给定的数组是有序的,所以比较左右两个指针所指向的数的平方的大小,将大的那个值放入数组的最后位置,并且指针向中间移动,重复此流程,直到右指针小于左指针(遍历完成),返回结果数组
个人误区: 我尝试寻找符号变换的中间值,然后向左右遍历,做了一些无用功
代码实现:
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> result(nums.size(), 0);
int l = 0, r = nums.size() - 1;
int k = nums.size() - 1;
while (l <= r) {
if (nums[l] * nums[l] > nums[r] * nums[r]) {
result[k] = nums[l] * nums[l];
l++, k--;
} else {
result[k] = nums[r] * nums[r];
r--, k--;
}
}
return result;
}
};
59. 螺旋矩阵II
这道题目我是直接看题解写的,主要的问题就是要注意循环不变量
代码实现:
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> result(n, vector<int>(n, 0));
int startx = 0, starty = 0;
int loop = n >> 1;
int mid = n >> 1;
int count = 1;
int offset = 1;
int i, j;
while (loop--) {
i = startx;
j = starty;
for (; j < n - offset; j++) {
result[i][j] = count++;
}
for (; i < n - offset; i++) {
result[i][j] = count++;
}
for (; j > starty; j--) {
result[i][j] = count++;
}
for (; i > startx; i--) {
result[i][j] = count++;
}
startx++;
starty++;
offset += 1;
}
if (n % 2) {
result[mid][mid] = count;
}
return result;
}
};
209. 长度最小的字数组
这道题目也使用了双指针的方法,左指针指向你当前数组的开始,右指针指向你下一个要包括的元素,使用右指针遍历直到左右指针包括的值大于目标,然后记录当前长度,随后移动左指针,判断是否符合条件来更新最短长度,直到包括的值小于target,如此循环,直到遍历完数组,返回最小值
代码实现:
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int l = 0, r = 0;
int size = nums.size();
int result = INT32_MAX;
int sum = 0;
int tmp = 0;
for (; r < size; r++) {
sum += nums[r];
while (sum >= target) {
tmp = r - l + 1;
result = tmp < result ? tmp : result;
sum -= nums[l++];
}
}
return result == INT32_MAX ? 0 : result;
}
};
203. 移除链表元素
这道题目其实没有什么难度,只是考察了一下链表的遍历以及元素的删除,需要注意的就是在删除元素的时候可以用一个指针指向它,然后在删除完成后将这个节点的delete,还有一点就是在做链表相关题目的时候,可以声明一个虚拟头节点来指向头节点,方便对于头节点进行操作,然后在问题解决完之后将虚拟头节点删除
代码实现:
class Solution {
public:
ListNode *removeElements(ListNode *head, int val) {
ListNode *Head = new ListNode;
Head->next = head;
ListNode *cur = Head;
while (cur->next != nullptr) {
if (cur->next->val == val) {
ListNode *tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
} else {
cur = cur->next;
}
}
ListNode *result = Head->next;
delete Head;
return result;
}
};
707. 设计链表
题目链接: 707. 设计链表 - 力扣（LeetCode）
这道题目没什么技术含量,就按照要求实现所需要的功能就行了
代码实现:
class MyLinkedList {
public:
struct LinkedNode {
int val;
LinkedNode *next;
LinkedNode(int val) : val(val), next(nullptr) {
}
};
MyLinkedList() {
Head = new LinkedNode(0);
lens = 0;
}
int get(int index) {
if (index >= lens) {
return -1;
}
LinkedNode *cur = Head->next;
while (index--) {
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
LinkedNode *tmp = new LinkedNode(val);
tmp->next = Head->next;
Head->next = tmp;
lens++;
}
void addAtTail(int val) {
int tmp_lens = lens;
LinkedNode *cur = Head;
while (tmp_lens--) {
cur = cur->next;
}
LinkedNode *tmp = new LinkedNode(val);
cur->next = tmp;
lens++;
}
void addAtIndex(int index, int val) {
if (index == lens) {
addAtTail(val);
} else if (index == 0) {
addAtHead(val);
} else if (index < lens) {
LinkedNode *cur = Head;
while (index--) {
cur = cur->next;
}
LinkedNode *tmp = new LinkedNode(val);
tmp->next = cur->next;
cur->next = tmp;
lens++;
}
}
void deleteAtIndex(int index) {
if (index < lens) {
LinkedNode *cur = Head;
while (index--) {
cur = cur->next;
}
LinkedNode *tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
lens--;
}
}
private:
LinkedNode *Head;
int lens;
};
206. 反转链表
题目链接: 206. 反转链表 - 力扣（LeetCode）
这道题目其实可以看作从头部插入节点,被处理的链表可以用一个临时的指针指向要处理的位置,循环的变量是下一个要处理的位置,不断循环
代码实现:
class Solution {
public:
ListNode *reverseList(ListNode *head) {
ListNode *Head = new ListNode(0);
ListNode *cur = head;
ListNode *tmp;
while (cur) {
tmp = cur;
cur = cur->next;
tmp->next = Head->next;
Head->next = tmp;
}
ListNode *result = Head->next;
delete Head;
return result;
}
};
24. 两两交换链表中的节点
这道题没什么好说的
代码实现:
class Solution {
public:
ListNode *swapPairs(ListNode *head) {
ListNode *Head = new ListNode(0);
Head->next = head;
ListNode *cur = Head;
while (cur->next != nullptr && cur->next->next != nullptr) {
ListNode *tmp = cur->next->next->next;
cur->next->next->next = cur->next;
cur->next = cur->next->next;
cur->next->next->next = tmp;
cur = cur->next->next;
}
ListNode *result = Head->next;
delete Head;
return result;
}
};
19.删除链表的倒数第N个节点
这道题就用到了双指针,与上面的 [[Leetode刷题记录#^52cd32|27. 移除元素]], [[#^bcb23c|977. 有序数组的平方]] 使用了相同的思想,在这里定义一个快指针一个慢指针,两个指针间的距离就是题目中的n,所以当快指针指向最后一个节点的时候,慢节点指向就是要删除节点的前一个节点,然后进行删除操作
代码实现:
class Solution {
public:
ListNode *removeNthFromEnd(ListNode *head, int n) {
ListNode *Head = new ListNode(0);
Head->next = head;
ListNode *fast = Head, *slow = Head;
while (n--) {
fast = fast->next;
}
while (fast->next != nullptr) {
fast = fast->next;
slow = slow->next;
}
ListNode *tmp = slow->next;
slow->next = slow->next->next;
delete tmp;
ListNode *result = Head->next;
delete Head;
return result;
}
};
160. 相交链表
题目链接: 160. 相交链表 - 力扣（LeetCode）
因为两链表是在后端相交,所以前端的长的链表比短的链表多出的部分肯定是不会有相交节点的(毕竟你不可能跟一个不存在的人结婚吧😂).然后统计出相差的长度后对两个链表进行对齐,让指向两个链表的指针距离结尾的距离是相等的,然后开始向后遍历,如果两个指针相同,即它们指向同一节点,则两链表相交
代码实现:
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *cur = headA;
int len_A = 0;
while (cur != nullptr) {
len_A++;
cur = cur->next;
}
cur = headB;
int len_B = 0;
while (cur != nullptr) {
len_B++;
cur = cur->next;
}
ListNode *cur_A = headA, *cur_B = headB;
if (len_A > len_B) {
int times = len_A - len_B;
while (times--) {
cur_A = cur_A->next;
}
} else if (len_A < len_B) {
int times = len_B - len_A;
while (times--) {
cur_B = cur_B->next;
}
}
ListNode *result = nullptr;
while (cur_A != nullptr) {
if (cur_A == cur_B) {
result = cur_A;
break;
}
cur_A = cur_A->next;
cur_B = cur_B->next;
}
return result;
}
};
- 0
- 0
-
分享