网站建设做的快百度提升排名
文章目录
- 前言
- 一、41. 缺失的第一个正数(HOT100)
- 二、6. 从尾到头打印链表(剑指Offer)
- 总结
前言
一个本硕双非的小菜鸡,备战24年秋招,计划刷完hot100和剑指Offer的刷题计划,加油!
根据要求,每一道题都要写出两种以上的解题技巧。
一、41. 缺失的第一个正数(HOT100)
41. 缺失的第一个正数
Note:原地哈希
首先将数组中所有小于等于 0 或大于size 的数修改为 size+1;
遍历数组,开始做标记。如果 ∣x∣∈[1,size],那么给数组中的第 ∣x∣−1 个位置的数添加一个负号。
在遍历完成之后,如果数组中的每一个数都是负数,那么答案是 size +1,否则答案是第一个正数的位置加 1
class Solution {
public:int firstMissingPositive(vector<int>& nums) {int size = nums.size();if (find(nums.begin(), nums.end(), 1) == nums.end())return 1;for (int i = 0; i < size; i++) {if (nums[i] <= 0 || nums[i] > size)nums[i] = 1;}for (int i = 0; i < size; i++) {int num = abs(nums[i]) - 1;nums[num] = -abs(nums[num]);}for (int i = 0; i < size; i++) {if (nums[i] > 0)return i + 1;}return size + 1;}
};
Note:置换解题
我们可以对数组进行一次遍历,对于遍历到的数 x=nums[i],如果 x∈[1,size],我们就知道 x 应当出现在数组中的 x−1 的位置,因此交换 nums[i] 和 nums[x−1],这样 x 就出现在了正确的位置。在完成交换后,新的 nums[i] 可能还在 [1,size]的范围内,我们需要继续进行交换操作,直到 x∉[1,size]。
注意到上面的方法可能会陷入死循环。如果 nums[i]恰好与 nums[x−1] 相等,那么就会无限交换下去。此时nums[i] = x = nums[x−1],说明 x 已经出现在了正确的位置。因此可以跳出循环,开始遍历下一个数。
class Solution {
public:int firstMissingPositive(vector<int>& nums) {int size = nums.size();for (int i = 0; i < size; ++i) {while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {swap(nums[nums[i] - 1], nums[i]);}}for (int i = 0; i < size; ++i) {if (nums[i] != i + 1) {return i + 1;}}return size + 1;}
};
二、6. 从尾到头打印链表(剑指Offer)
从尾到头打印链表
Note:使用栈作为辅助
class Solution {
public:vector<int> printListReversingly(ListNode* head) {stack<int> stk;ListNode* pNode = head;while (pNode != nullptr) {stk.push(pNode->val);pNode = pNode->next;}int sizes = stk.size();vector<int> res(sizes);for (int i = 0; i < sizes; i++) {res[i] = stk.top();stk.pop();}return res;}
};
Note:翻转数组
class Solution {
public:vector<int> printListReversingly(ListNode* head) {vector<int> res;while (head != nullptr) {res.push_back(head->val);head = head->next;}reverse(res.begin(), res.end());return res;}
};
总结
祝大家都能学有所成,找到一份好工作!