C++刷题(一):顺序表 + 单链表
📝前言说明:
本专栏主要记录本人的基础算法学习以及刷题记录,使用语言为C++。
每道题我会给出LeetCode上的题号(如果有题号),题目,以及最后通过的代码。没有题号的题目大多来自牛客网。对于题目的讲解,主要是个人见解,如有不正确,欢迎指正,一起进步!
🎬个人简介:努力学习ing
📋本专栏:C++刷题专栏
📋其他专栏:C++学习笔记,C语言入门基础,python入门基础,python刷题专栏
🎀CSDN主页 愚润泽
题目
- 88.合并两个有序数组
- 27.移除元素
- 环形链表的约瑟夫问题
- 189. 轮转数组
- 面试题17.04. 消失的数字
- 链表的回文结构
- 138. 随机链表的复制
- 142. 环形链表 II
88.合并两个有序数组
这道题的关键在于,如何讲nums2
的数组元素插入nums1
,因为nums1
的长度为m+n
,也就代表后面有空位,所以可以选择从后往前插入。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
// 从后往前放,一定有空位
int p = m + n - 1, p1 = m - 1, p2 = n - 1;
while(p2 >= 0)
{
if (p1 >= 0 && nums1[p1] > nums2[p2]){ // p1 等于0代表p1都排好了,剩下的填p2
nums1[p--] = nums1[p1--]; // 先使用后--,填入nums1[p1]
}
else{
nums1[p--] = nums2[p2--];
}
}
}
};
27.移除元素
转换思想:删掉值==val
的 → 保留(提取)值!=val
的
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int i = 0;
for(int x : nums){
if (x != val){
nums[i++] = x;
}
}
return i;
}
};
环形链表的约瑟夫问题
暴力做法(这题还可以动态规划,但是这里不提供):
class Solution {
public:
int ysf(int n, int m)
{
vector<int> nums(n);
for (int i = 0; i < n; i++){
nums[i] = i;
}
int start = 0;
while(nums.size()!=1){
int out = (start + m - 1) % nums.size(); // 往后移动m-1个位置是报到m的
nums.erase(nums.begin() + out);
start = out;
}
return nums[0] + 1;
}
};
189. 轮转数组
简单做法:先复制后半部分的,再复制前半部分的,最后再把数组重新赋值回给nums
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n;
vector<int> nums2(n); //
int j = 0;
for (int i = n - k ;i < n;i++){
nums2[j] = nums[i];
j++;
}
for(int i = 0; i < n-k; i++){
nums2[j] = nums[i];
j++;
}
// 将新数组的元素复制回原数组
for (int i = 0; i < n; i++)
{
nums[i] = nums2[i];
}
}
};
时间复杂度:因为要遍历两次数组:O(n),空间复杂度:要开一个跟随问题规模n
的同样长的数组+三个整型(常数级):O(n)
改进:时间复杂度:O(n),空间复杂度O(1)的做法:
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k %= nums.size(); // 轮转 k 次等于轮转 k % n 次
ranges::reverse(nums);
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
};
面试题17.04. 消失的数字
两次遍历,第一次遍历记录是否出现,第二次遍历找出没出现的
class Solution {
public:
int missingNumber(vector<int>& nums)
{
int n = nums.size();
vector<int>nums2 (n + 1, -1);
for(auto num : nums)
{
nums2[num] = 1;
}
int i = 0;
for(i = 0; i < n; i++)
{
if(nums2[i] == -1)
{
break;
}
}
return i;
}
};
链表的回文结构
不是第一次写回文这道题了,但是再写还是容易出现问题。方法:中间节点+反转链表+依次比较
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
ListNode* slow = A;
ListNode* fast = A;
while(fast!= nullptr && fast->next != nullptr) // 这判断条件的时候一定要注意
// 原则:下面能使用到的指针要避免为空,如:fast->next != nullptr
// 如果要判断 fast->next ,则前提是fast != nullptr (所以要写两个)
{
slow = slow->next;
fast = fast->next->next;
}
ListNode* mid = slow;
// 找到中间节点,然后反转后半部分的链表,反转后按顺序比较
// 注意:前半部分的长度>=比后半部分长(偶数时>,因为偶数时前半部分的最后一个节点依然指向mid,画图好理解),因此比完短的即可
ListNode* pre = nullptr;
ListNode* cur = mid;
while(cur){
ListNode* nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
// 反转完以后,pre指向原反转链表的最后一个节点,cur指向原最后一个节点的后一个位置
ListNode* p1 = A; // 第一段链表的开始
ListNode* p2 = pre; // 第二段反转后链表的开始
while(p2 != nullptr)
{
if(p1->val != p2->val){
return false;
}
p1 = p1->next;
p2 = p2->next;
}
return true;
}
};
138. 随机链表的复制
题解(来源于灵茶山艾府):
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) { // 这里应该是官方给漏了,实际上可以传3个参数
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if (head == nullptr){
return nullptr;
}
for (Node*cur = head; cur; cur = cur->next->next) // 走两步才到原链表的下一个节点
{
cur->next = new Node(cur->val, cur->next, nullptr); // 这里就是能传三个参数,我也不晓得为什么
}
for (Node* cur = head; cur; cur = cur->next->next){
if(cur->random){
cur->next->random = cur->random->next; // 原链表random指向的节点的下一个节点,就是新random要指向的。
}
}
Node* new_head = head->next;
Node* cur = head;
for(; cur->next->next; cur = cur->next)
{
Node* copy = cur->next; // 记录下新链表的节点
cur -> next = cur->next->next; // 恢复原来的
copy -> next = copy -> next->next; // 连接新的
}
cur->next = nullptr;
return new_head;
}
};
最后的拆分需要注意:混合链表的顺序为:旧1,新1,旧2,新2,旧3,......,旧n,新n,nullptr
,两个新节点相连时会丢失一个旧节点(旧节点同理),所以:当一开始记录了旧1
和新1
的位置时,应该先让旧1
和旧2
相连,此时不会丢失新1
要连接的下一个节点的信息。
142. 环形链表 II
这道题也是第二次写了。快慢指针(这里是快的速度是慢的的两倍),快的一定会追上慢的,然后我们探索位置关系:
这次关系都推出来了,但是还是没想到最后一步,重新让头指针和慢指针一起走,必会在入环口相遇。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast && fast->next){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){
while(head != slow){
head = head->next;
slow = slow->next;
}
return slow;
}
}
return nullptr;
}
};
🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助,那简直是太酷啦!
若有不足,还请大家多多指正,我们一起学习交流!
📢公主,王子:点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持!祝大家都能得偿所愿,天天开心!!!