Java C++题解leetcode1441用栈操作构建数组示例

目录
  • 题目要求
  • 思路：模拟【双指针】
    • Java
    • C++
    • Rust

题目要求

思路：模拟【双指针】

按题意模拟即可：

一个指针cur依次指向target中的每个元素，另一个指针i依次指向1∼n的数字；

对i所指向的每个数字进行Push操作，然后判断当前数字与target[cur]是否相等；

  • 相等则判断下一个数字，同时将cur指向下一个元素；
  • 否则需进行Pop操作。

过程中需注意cur的越界，当其越界则target构造完毕。

Java

class Solution {
    public List<String> buildArray(int[] target, int n) {
        List<String> res = new ArrayList<>();
        for (int i = 1, cur = 0; i <= n && cur < target.length; i++) {
            res.add("Push");
            if (target[cur] != i)
                res.add("Pop");
            else
                cur++;
        }
        return res;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

C++

class Solution {
public:
    vector<string> buildArray(vector<int>& target, int n) {
        vector<string> res;
        for (int i = 1, cur = 0; i <= n && cur < target.size(); i++) {
            res.emplace_back("Push");
            if (target[cur] != i)
                res.emplace_back("Pop");
            else
                cur++;
        }
        return res;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

Rust

impl Solution {
    pub fn build_array(target: Vec<i32>, n: i32) -> Vec<String> {
        let mut res = Vec::new();
        let mut cur = 0;
        for i in 1..(n + 1) {
            if (cur < target.len()) {
                res.push(String::from("Push"));
                if (target[cur] != i) {
                    res.push(String::from("Pop"));
                }
                else {
                    cur += 1;
                }
            }
        }
        res
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

以上就是Java C++题解leetcode1441用栈操作构建数组示例的详细内容，更多关于Java C++ 栈操作构建数组的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C C++ 题解LeetCode2360图中的最长环示例

    C C++ 题解LeetCode2360图中的最长环示例

    目录 题目描述 整理题意 解题思路分析 具体实现 复杂度分析 代码实现 总结 题目描述 题目链接:2360. 图中的最长环 给你一个 n 个节点的 有向图 ,节点编号为 0 到 n - 1 ,其中每个节点 至多 有一条出边. 图用一个大小为 n 下标从 0 开始的数组 edges 表示,节点 i 到节点 edges[i] 之间有一条有向边.如果节点 i 没有出边,那么 edges[i] == -1 . 请你返回图中的 最长 环,如果没有任何环,请返回 -1 . 一个环指的是起点和终点是 同一个 

  • Java C++ leetcode面试零矩阵

    目录 题目要求 思路:模拟 Java C++ Rust 总结 题目要求 思路:模拟 定义两个数组分别记录每行or每列中为0的元素: 0所在的行列清零也就意味着元素所在行or列有0则置零[废话连篇]: 所以一次遍历找出有0的行列,一次遍历根据其将相应元素置零. Java class Solution { public void setZeroes(int[][] matrix) { int n = matrix.length, m = matrix[0].length; boolean[] row

  • C++ LeetCode1945题解字符串转化后的各位数字之和

    目录 1945.字符串转化后的各位数字之和 方法一:计算 AC代码 C++ 1945.字符串转化后的各位数字之和 力扣题目链接:leetcode.cn/problems/su… 给你一个由小写字母组成的字符串 s ,以及一个整数 k . 首先,用字母在字母表中的位置替换该字母,将 s 转化 为一个整数(也就是,'a' 用 1 替换,'b' 用 2 替换,... 'z' 用 26 替换).接着,将整数 转换 为其 各位数字之和 .共重复 转换 操作 k 次 . 例如,如果 s = "zbax&qu

  • C C++ 题解LeetCode1417重新格式化字符串

    目录 题目描述 整理题意 解题思路分析 具体实现 复杂度分析 代码实现 总结 题目描述 题目链接:1417. 重新格式化字符串 给你一个混合了数字和字母的字符串 s,其中的字母均为小写英文字母. 请你将该字符串重新格式化,使得任意两个相邻字符的类型都不同.也就是说,字母后面应该跟着数字,而数字后面应该跟着字母. 请你返回 重新格式化后 的字符串:如果无法按要求重新格式化,则返回一个 空字符串 . 提示: 1⩽s.length⩽5001 s 仅由小写英文字母和/或数字组成. 示例 1: 输入:s

  • Java C++题解leetcode915分割数组示例

    目录 题目要求 思路一:两次遍历 Java C++ Rust 思路二:一次遍历 Java C++ Rust 题目要求 题目链接 思路一:两次遍历 题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值,那么就找这个分界点就好: 首先从后向前遍历,找[i,n−1]里最小的值: 然后从前向后遍历,找[0,i]里最大的值: 然后找满足max[i]<=min[i+1]的分割点i: 可以将2.3两步结合为一步完成,由于iii从前向后不断增大,所以用后面(较大)的值覆盖更新之前的值. 找到分界点的索引

  • Java C++题解leetcode1441用栈操作构建数组示例

    目录 题目要求 思路:模拟[双指针] Java C++ Rust 题目要求 思路:模拟[双指针] 按题意模拟即可: 一个指针cur依次指向target中的每个元素,另一个指针i依次指向1∼n的数字: 对i所指向的每个数字进行Push操作,然后判断当前数字与target[cur]是否相等: 相等则判断下一个数字,同时将cur指向下一个元素: 否则需进行Pop操作. 过程中需注意cur的越界,当其越界则target构造完毕. Java class Solution { public List<Str

  • Java C++题解leetcode1598文件夹操作日志搜集器

    Java C++题解leetcode1598文件夹操作日志搜集器

    目录 题目要求 思路:模拟 Java C++ Rust 总结 题目要求 思路:模拟 根据日志判断目前在哪一级子文件夹即可,级数就等于返回时的步数,主文件夹级数初始为000: xl:级数+1+1+1: ./:级数不变: ../:级数−1-1−1. Java class Solution { public int minOperations(String[] logs) { int res = 0; for (String l : logs) { if (l.equals("../"))

  • 剑指Offer之Java算法习题精讲字符串操作与数组及二叉搜索树

    剑指Offer之Java算法习题精讲字符串操作与数组及二叉搜索树

    题目一  解法 class Solution { public String reverseOnlyLetters(String s) { char[] chars = s.toCharArray(); int left = 0; int right = chars.length-1; while(left<=right){ char tmp = 0; if(chars[left]>='a'&&chars[left]<='z'||(chars[left]>='A'&

  • Java C++ 题解leetcode1619删除某些元素后数组均值

    Java C++ 题解leetcode1619删除某些元素后数组均值

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 根据题意模拟即可: 排序然后只取中间符合条件的数加和然后计算均值: 根据给出的数组长度n为20的倍数,5%可直接取n/20: 两边各去除5%,则剩余长度为0.9n. Java class Solution { public double trimMean(int[] arr) { Arrays.sort(arr); int n = arr.length, tot = 0; for (int i = n / 20; i

  • go语言题解LeetCode88合并两个有序数组示例

    目录 题目描述 思路分析 AC 代码 题目描述 原题链接 : 88. 合并两个有序数组 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目. 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列. 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中.为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素

  • JAVA实现账户取款和存款操作

    这篇文章主要介绍了JAVA实现账户取款和存款操作,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 JAVA 编写一个程序完成从某账户取款和存款的操作 (1)输入存款金额是,如果非数值型,捕获一场并进行处理 (2)操作账户类是,如果取款金额大于余额时则做异常处理 import java.util.Scanner; public class Blank { public static void main(String[] args) { float

  • java使用链表来模拟栈的入栈出栈操作实例代码

    java使用链表来模拟栈的入栈出栈操作实例代码

    栈:后进先出:最后一个放入堆栈中的物体总是被最先拿出来. 使用链表来模拟栈的入栈出栈操作. 1.节点类代码 public class Entry<T> { private T value; private Entry<T> next; public Entry() { this(null); } public Entry(T value) { this.value=value; this.next=null; } public void setValue(T value) { th

  • Java定义栈结构，并实现入栈、出栈操作完整示例

    本文实例讲述了Java定义栈结构,并实现入栈.出栈操作.分享给大家供大家参考,具体如下: package com.example.demo; import java.util.ArrayList; public class Stack { ArrayList<Object> list = new ArrayList<>(); //入栈 public void push(Object o){ list.add(o); } //出栈 public Object pop(){ Objec

  • Java数据结构之链表、栈、队列、树的实现方法示例

    本文实例讲述了Java数据结构之链表.栈.队列.树的实现方法.分享给大家供大家参考,具体如下: 最近无意中翻到一本书,闲来无事写几行代码,实现几种常用的数据结构,以备后查. 一.线性表(链表) 1.节点定义 /**链表节点定义 * @author colonel * */ class Node { public int data; Node next=null; public Node(int data){ this.data=data; } } 2.链表操作类 /**链表操作类 * @auth

  • Java数据结构专题解析之栈和队列的实现

    Java数据结构专题解析之栈和队列的实现

    目录 1. 栈 1.1 概念 1.2 助解图题 1.3 栈的数组实现 1.4 问题 1.5 栈的单链表实现 2. 队列 2.1 概念 2.2 问题 2.3 队列的单链表实现 2.4 数组实现队列 2.5 循环队列 2.6 双端队列 3. 栈和队列练习题 3.1 有效的括号 3.2 用队列实现栈 3.3 用栈实现队列 3.4 实现一个最小栈 3.5 设计循环队列 1. 栈 1.1 概念 栈:是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作. 特点:栈中的数据元素遵循先进后出的原则,但

随机推荐