国家建设部网站官网证件查询,网站如何做su,建一个商城网站需要多少钱,廊坊百度提升优化文章目录 前言一、41. 缺失的第一个正数#xff08;HOT100#xff09;二、6. 从尾到头打印链表#xff08;剑指Offer#xff09;总结 前言
一个本硕双非的小菜鸡#xff0c;备战24年秋招#xff0c;计划刷完hot100和剑指Offer的刷题计划#xff0c;加油#xff01; 根… 文章目录 前言一、41. 缺失的第一个正数HOT100二、6. 从尾到头打印链表剑指Offer总结 前言
一个本硕双非的小菜鸡备战24年秋招计划刷完hot100和剑指Offer的刷题计划加油 根据要求每一道题都要写出两种以上的解题技巧。
一、41. 缺失的第一个正数HOT100
41. 缺失的第一个正数 Note原地哈希 首先将数组中所有小于等于 0 或大于size 的数修改为 size1 遍历数组开始做标记。如果 ∣x∣∈[1,size]那么给数组中的第 ∣x∣−1 个位置的数添加一个负号。 在遍历完成之后如果数组中的每一个数都是负数那么答案是 size 1否则答案是第一个正数的位置加 1
class Solution {
public:int firstMissingPositive(vectorint 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置换解题 我们可以对数组进行一次遍历对于遍历到的数 xnums[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(vectorint 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:vectorint printListReversingly(ListNode* head) {stackint stk;ListNode* pNode head;while (pNode ! nullptr) {stk.push(pNode-val);pNode pNode-next;}int sizes stk.size();vectorint res(sizes);for (int i 0; i sizes; i) {res[i] stk.top();stk.pop();}return res;}
};Note翻转数组
class Solution {
public:vectorint printListReversingly(ListNode* head) {vectorint res;while (head ! nullptr) {res.push_back(head-val);head head-next;}reverse(res.begin(), res.end());return res;}
};总结
祝大家都能学有所成找到一份好工作
