每日算法刷题Day15-0到n-1中缺失的数字、调整数组顺序、从尾到头打印链表、用两个栈实现队列

简介: ⭐每日算法题解系列文章旨在精选重点与易错的算法题,总结常见的算法思路与可能出现的错误,与笔者另一系列文章有所区别,并不是以知识点的形式提升算法能力,而是以实战习题的形式理解算法,使用算法。

6d4ffada7fe0312172f742dc9409ec40

45.0到n-1中缺失的数字

一个长度为 n−1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围 0 到 n−1之内。

在范围 0 到 n−1的 n 个数字中有且只有一个数字不在该数组中,请找出这个数字。

数据范围

1≤n≤1000

样例

输入:[0,1,2,4]

输出:3

思路

此题思路比较简单,主要考察的是对于STL的应用

本次采用的思路是:采用哈希表,先插入0~n-1这n个数字,然后再删除其中nums含有的数字,最后剩下的一个数字即是所需的。

代码

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
    unordered_set<int> S;
    for(int i = 0; i <= nums.size();i++)S.insert(i);
    
    for(auto x : nums)S.erase(x);
    
    return *S.begin();
    
    }
};

46.调整数组顺序使奇数位于偶数前面

输入一个整数数组,实现一个函数来调整该数组中数字的顺序。

使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分。

数据范围

数组长度 [0,100]。

样例

输入:[1,2,3,4,5]

输出: [1,3,5,2,4]

思路

这道题可以采用双指针的方法实现。

首先第一个指针指向第一个地方。

  • 判断第一个指针,如果是奇数就跳过,直到停到偶数为止
  • 判断第二个指针,如果是偶数就跳过,直到奇数为止。
  • 最后交换两个数即可。

当i > j时退出循环。

class Solution {
public:
    void reOrderArray(vector<int> &array) {
         int i = 0, j = array.size() - 1;
         while( i < j)
         {
             while(array[i]%2)i++;
             while(array[j]%2 == 0)j--;
             if( i < j)swap(array[i] , array[j]);
         }
    }
};

47.从尾到头打印链表

输入一个链表的头结点,按照 从尾到头 的顺序返回节点的值。

返回的结果用数组存储。

数据范围

0≤ 链表长度 ≤1000。

样例

输入:[2, 3, 5]
返回:[5, 3, 2]

思路

注意这里函数是vector\<int> 型的,因此return的变量也应该是vector\<int> 型。首先定义vector,然后用push_back压入,再经过reverse,输出即可。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
        vector<int> res;
        for(auto p = head; p ; p = p -> next)res.push_back(p -> val);
        reverse(res.begin() , res.end());
        return res;
    }
};

48.用两个栈实现队列

请用栈实现一个队列,支持如下四种操作:

  • push(x) – 将元素x插到队尾;
  • pop() – 将队首的元素弹出,并返回该元素;
  • peek() – 返回队首元素;
  • empty() – 返回队列是否为空;

注意:

  • 你只能使用栈的标准操作:push to toppeek/pop from top, sizeis empty
  • 如果你选择的编程语言没有栈的标准库,你可以使用list或者deque等模拟栈的操作;
  • 输入数据保证合法,例如,在队列为空时,不会进行pop或者peek等操作;

数据范围

每组数据操作命令数量 [0,100]。

样例

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

思路

此题的思路类似于汉诺塔,如果想要通过两个栈实现队列的操作,即先进后出。pop的是队首的元素,这里采用类似的方式如下图所示:

image-20220827224152227

image-20220827224321862

image-20220827224429737

class MyQueue {
public:
    /** Initialize your data structure here. */
    stack<int> s1,s2;
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        while(s1.size() > 1)s2.push(s1.top()),s1.pop();
        int t = s1.top();
        s1.pop();
        while(s2.size()) s1.push(s2.top()),s2.pop();
        return t;
    }
    
    /** Get the front element. */
    int peek() {
        while(s1.size() > 1)s2.push(s1.top()),s1.pop();
        int t = s1.top();
        while(s2.size()) s1.push(s2.top()),s2.pop();
        return t;
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        s1.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * bool param_4 = obj.empty();
 */
目录
相关文章
|
22天前
|
缓存 监控 算法
内网监控管理软件:PHP 语言队列算法揭秘
在数字化办公环境中,内网监控管理软件对企业的稳定运行和信息安全至关重要。本文深入介绍PHP中的队列算法及其在内网监控软件中的应用,包括监控数据收集、任务调度和日志记录等场景,通过代码示例展示其实现方法。队列算法可提高性能、保证数据顺序并实现异步处理,为企业提供高效的安全保障。
23 1
|
3月前
|
算法
【算法】栈
栈相关算法题,供参考,附有链接地址及板书
|
5月前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
167 64
|
4月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
110 5
|
5月前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
215 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
5月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
89 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
4月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
4月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
78 0
|
5月前
|
算法
数据结构与算法二:栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用,并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
106 3
|
5月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
60 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列