Tag Archives:

剑指 Offer 09. 用两个栈实现队列

剑指 Offer 09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

示例 1:

输入:
[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[3],[],[]]
输出:[null,null,3,-1]
示例 2:

输入:
[“CQueue”,”deleteHead”,”appendTail”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[],[5],[2],[],[]]
输出:[null,-1,null,null,5,2]
提示:

1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


用两个栈实现一个队列。栈是后进先出,队列是先进先出。设置两个栈stack_in_和stack_out_,分别负责数据的push和pop,如果stack_out_没数据,则需要从stack_in_中把数据捣腾到stack_out_中。完整代码如下:

class CQueue {
private:
    stack<int> stk_in_, stk_out_;
public:
    CQueue() {

    }
    
    void appendTail(int value) {
        stk_in_.push(value);
    }
    
    int deleteHead() {
        if(!stk_out_.empty()) {
            int ans = stk_out_.top();
            stk_out_.pop();
            return ans;
        } else if(!stk_in_.empty()) {
            while(stk_in_.size() != 1) {
                int tmp = stk_in_.top();
                stk_in_.pop();
                stk_out_.push(tmp);
            }
            int tmp = stk_in_.top();
            stk_in_.pop();
            return tmp;
        } else {
            return -1;
        }
    }
};

本代码提交AC,用时696MS。

LeetCode Design a Stack With Increment Operation

1381. Design a Stack With Increment Operation

Design a stack which supports the following operations.

Implement the CustomStack class:

  • CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.
  • void push(int x) Adds x to the top of the stack if the stack hasn’t reached the maxSize.
  • int pop() Pops and returns the top of stack or -1 if the stack is empty.
  • void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.

Example 1:

Input
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
Output
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
Explanation
CustomStack customStack = new CustomStack(3); // Stack is Empty []
customStack.push(1);                          // stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.pop();                            // return 2 --> Return top of the stack 2, stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.push(3);                          // stack becomes [1, 2, 3]
customStack.push(4);                          // stack still [1, 2, 3], Don't add another elements as size is 4
customStack.increment(5, 100);                // stack becomes [101, 102, 103]
customStack.increment(2, 100);                // stack becomes [201, 202, 103]
customStack.pop();                            // return 103 --> Return top of the stack 103, stack becomes [201, 202]
customStack.pop();                            // return 202 --> Return top of the stack 102, stack becomes [201]
customStack.pop();                            // return 201 --> Return top of the stack 101, stack becomes []
customStack.pop();                            // return -1 --> Stack is empty return -1.

Constraints:

  • 1 <= maxSize <= 1000
  • 1 <= x <= 1000
  • 1 <= k <= 1000
  • 0 <= val <= 100
  • At most 1000 calls will be made to each method of incrementpush and pop each separately.

设计一个栈Stack的数据结构,简单题,使用vector模拟。完整代码如下:

class CustomStack {
private:
	vector<int> container;
	int msz;
public:
	CustomStack(int maxSize) {
		msz = maxSize;
	}

	void push(int x) {
		if (container.size() < msz) {
			container.push_back(x);
		}
	}

	int pop() {
		if (container.size() > 0) {
			int val = container[container.size() - 1];
			container.pop_back();
			return val;
		}
		else {
			return -1;
		}
	}

	void increment(int k, int val) {
		for (int i = 0; i < k&&i < container.size(); ++i) {
			container[i] += val;
		}
	}
};

本代码提交AC,用时40MS。

LeetCode Merge Intervals

56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.


给定一个区间数组,也就是数组中保存的是一个个的区间[s,t],要求把数组中所有有overlap的区间合并起来。
简单题,先给数组排个序,然后只要看相邻的两个区间是否有重复就好了。排序的规则是先比较start,如果start相等,再比较end。
其实这个区间完全可以用pair来存,但是题目用一个自定义的Interval结构体存储。有两种方法可以对自定义结构体(或类)排序,一是重载Interval的小于<比较运算符,这样就可以直接sort(vector.begin(),vector.end())了,但是这样改变了Interval;还有一种方法是不改变Interval,自定义一个comp比较函数,传递给sort算法的第三个参数。
代码如下:

bool comp(const Interval& i, const Interval& j)
{
    return (i.start < j.start) || ((i.start == j.start) && (i.end < j.end));
}
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals)
    {
        if (intervals.size() == 0)
            return vector<Interval>();
        sort(intervals.begin(), intervals.end(), comp);
        vector<Interval> ans = { intervals[0] };
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i].start <= ans.back().end) {
                ans.back().end = max(ans.back().end, intervals[i].end);
            }
            else {
                ans.push_back(intervals[i]);
            }
        }
        return ans;
    }
};

本代码提交AC,用时12MS。

二刷。想到用栈来合并区间,代码如下:

class Solution {
public:
	bool IsOverlap(const pair<int, int>& interval1, const pair<int, int>& interval2) {
		return interval1.second >= interval2.first;
	}
	vector<vector<int>> merge(vector<vector<int>>& intervals) {
		vector<pair<int, int>> intervals2;
		for (int i = 0; i < intervals.size(); ++i) {
			intervals2.push_back(make_pair(intervals[i][0], intervals[i][1]));
		}
		sort(intervals2.begin(), intervals2.end());
		vector<vector<int>> ans;
		stack<pair<int, int>> stk;
		for (int i = 0; i < intervals2.size(); ++i) {
			if (stk.empty()) {
				stk.push(intervals2[i]);
			}
			else {
				pair<int, int> top = stk.top();
				stk.pop();
				if (IsOverlap(top, intervals2[i])) {
					stk.push(make_pair(top.first, max(top.second, intervals2[i].second)));
				}
				else {
					ans.push_back({ top.first,top.second });
					stk.push({ intervals2[i].first,intervals2[i].second });
				}
			}
		}
		if (!stk.empty())ans.push_back({ stk.top().first,stk.top().second });
		return ans;
	}
};

本代码提交AC,用时24MS,效率不如第一种方法高。

LeetCode Binary Tree Level Order Traversal II

107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

不知道这一题存在的必要性在哪里,解题方法和上一题LeetCode Binary Tree Level Order Traversal一模一样,不管是递归还是迭代,都只要在最后把结果reverse一下就好了。
完整代码如下:

class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode* root)
    {
        vector<vector<int> > ans;
        if (root == NULL)
            return ans;
        queue<TreeNode*> tree;
        tree.push(root);
        TreeNode* f;
        while (!tree.empty()) {
            int n = tree.size();
            vector<int> one_level;
            for (int i = 0; i < n; i++) {
                f = tree.front();
                tree.pop();
                one_level.push_back(f->val);
                if (f->left != NULL)
                    tree.push(f->left);
                if (f->right != NULL)
                    tree.push(f->right);
            }
            ans.push_back(one_level);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

本代码提交AC,用时6MS。

二刷。还可以借助栈:

class Solution {
public:
	vector<vector<int>> levelOrderBottom(TreeNode* root) {
		if (root == NULL)return {};

		stack<vector<int>> stk;
		queue<TreeNode*> q;
		q.push(root);
		while (!q.empty()) {
			int n = q.size();
			vector<int> cur_level;
			while (n--) {
				TreeNode* front_tn = q.front();
				q.pop();
				cur_level.push_back(front_tn->val);
				if (front_tn->left != NULL)q.push(front_tn->left);
				if (front_tn->right != NULL)q.push(front_tn->right);
			}
			stk.push(cur_level);
		}
		vector<vector<int>> ans;
		while (!stk.empty()) {
			ans.push_back(stk.top());
			stk.pop();
		}
		return ans;
	}
};

本代码提交AC,用时4MS。