HOT100与剑指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;}
};

总结

祝大家都能学有所成，找到一份好工作！