LeetCode Path Sum III You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes). The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000. Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1
Return 3. The paths that sum to 8 are:
1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

73. Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

Follow up:

• A straight forward solution using O(mn) space is probably a bad idea.
• A simple improvement uses O(m + n) space, but still not the best solution.
• Could you devise a constant space solution?

给定一个矩阵，如果元素(i,j)是0，则把第i行和第j列都赋值为0。要求用常数空间。 因为前面的元素如果赋值为0，会影响后面的行列，所以是否赋值为0需要预先存起来，最后再一次性处理矩阵。 可以用一个行向量row[]和一个列向量col[]分别存储第i行和第j列是否应该赋值为0，具体方法就是扫描矩阵，如果matrix[i][j]==0，则赋值row[i]=0和col[j]=0表明第i行和第j列应该被赋值为0。但是这种方法需要O(m+n)的空间。

为了不使用额外的空间，我们可以借用原矩阵的第一行和第一列当作上面的row[]和col[]，但是需要提前判断第一行和第一列是否应该被置为0。具体代码如下：

class Solution {
public:
    void setZeroes(vector<vector<int> >& matrix)
    {
        int m = matrix.size();
        if (m == 0)
            return;
        int n = matrix[0].size();
        if (n == 0)
            return;
        bool clearFirstRow = false, clearFirstColumn = false;
        for (int i = 0; i < m; ++i) { // first column
            if (matrix[i][0] == 0) {
                clearFirstColumn = true;
                break;
            }
        }
        for (int j = 0; j < n; ++j) { // first row
            if (matrix[0][j] == 0) {
                clearFirstRow = true;
                break;
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0)
                    matrix[i][j] = 0;
            }
        }
        if (clearFirstRow) {
            for (int j = 0; j < n; ++j)
                matrix[0][j] = 0;
        }
        if (clearFirstColumn) {
            for (int i = 0; i < m; ++i)
                matrix[i][0] = 0;
        }
    }
};

本代码提交AC，用时59MS。

225. Implement Stack using Queues

Implement the following operations of a stack using queues.

• push(x) — Push element x onto stack.
• pop() — Removes the element on top of the stack.
• top() — Get the top element.
• empty() — Return whether the stack is empty.

Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Notes:

• You must use only standard operations of a queue — which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack). 225. Implement Stack using Queues

和LeetCode Implement Queue using Stacks正好相反，本题要用队列实现堆栈的效果。 队列是先进先出的，而堆栈是后进先出。如果用队列q保存数据，则要实现堆栈的pop效果时，需要获取到q的队尾元素，可以不断把q的数据从队首弹出，同时压回队尾，重复n-1次，此时队首元素就是原来的队尾元素了。堆栈的top效果和push的实现方法是类似的。 这种题目就是数据不断的倒腾。。。 完整代码如下：

class MyStack {
private:
    queue<int> m_q;
public: /** Initialize your data structure here. */
    MyStack() {} /** Push element x onto stack. */
    void push(int x) { m_q.push(x); } /** Removes the element on top of the stack and returns that element. */
    int pop()
    {
        int sz = m_q.size();
        for (int i = 0; i < sz – 1; ++i) {
            m_q.push(m_q.front());
            m_q.pop();
        }
        int front = m_q.front();
        m_q.pop();
        return front;
    } /** Get the top element. */
    int top()
    {
        int sz = m_q.size(), front = m_q.front();
        for (int i = 0; i < sz; ++i) {
            front = m_q.front();
            m_q.push(front);
            m_q.pop();
        }
        return front;
    } /** Returns whether the stack is empty. */
    bool empty() { return m_q.empty(); }
};

本代码提交AC，用时3MS。

二刷。用两个queue来模拟stack，不如上面的解法好看：

class MyStack {
private:
	vector<queue<int>> vq_;
	int data_queue_id_;
public:
	/** Initialize your data structure here. */
	MyStack() {
		vq_.push_back(queue<int>());
		vq_.push_back(queue<int>());
		data_queue_id_ = 0;
	}

	/** Push element x onto stack. */
	void push(int x) {
		vq_[data_queue_id_].push(x);
	}

	/** Removes the element on top of the stack and returns that element. */
	int pop() {
		int another_id = 1 - data_queue_id_;
		int last_data = 0;
		while (!vq_[data_queue_id_].empty()) {
			last_data = vq_[data_queue_id_].front();
			vq_[data_queue_id_].pop();
			if (!vq_[data_queue_id_].empty()) {
				vq_[another_id].push(last_data);
			}
		}
		swap(another_id, data_queue_id_);
		return last_data;
	}

	/** Get the top element. */
	int top() {
		int another_id = 1 - data_queue_id_;
		int last_data = 0;
		while (!vq_[data_queue_id_].empty()) {
			last_data = vq_[data_queue_id_].front();
			vq_[data_queue_id_].pop();
			vq_[another_id].push(last_data);
		}
		swap(another_id, data_queue_id_);
		return last_data;
	}

	/** Returns whether the stack is empty. */
	bool empty() {
		return vq_[data_queue_id_].empty();
	}
};

本代码提交AC，用时0MS。

232. Implement Queue using Stacks 232. Implement Queue using Stacks

Implement the following operations of a queue using stacks.

• push(x) — Push element x to the back of queue.
• pop() — Removes the element from in front of queue.
• peek() — Get the front element.
• empty() — Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

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

Notes:

• You must use only standard operations of a stack — which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue). 232. Implement Queue using Stacks

本题要求用堆栈来实现队列的功能。因为堆栈是后进先出，而队列是先进先出，顺序正好相反。比如进入队列的顺序是1,2,3，但是进到堆栈stk1之后，从栈顶到栈底的顺序就变成了3,2,1，此时如果要实现队列出队的效果，就必须借助另一个堆栈stk2，把stk1的内容压入到stk2，这样从栈顶到栈底的顺序就和队列一样了，是1,2,3。 所以本题借助两个堆栈stk1和stk2，stk1就是常规的数据来了就压栈，当需要实现队列的pop效果时，就借助stk2倒腾一下，如果又要实现队列的push效果时，又要把stk2的数据捣腾回stk1。 总的来说，我们使用懒人规则，每次直到调用某个操作，且当前stk*不能满足要求时，才捣腾stk1和stk2。 完整代码如下：

class MyQueue {
private:
    stack<int> stk1, stk2; // 输入来源1,2,3，stk1从栈底到栈顶的顺序是1,2,3，stk2从栈底到栈顶的顺序是3,2,1
public: /** Initialize your data structure here. */
    MyQueue() {} /** Push element x to the back of queue. */
    void push(int x)
    {
        while (!stk2.empty()) {
            stk1.push(stk2.top());
            stk2.pop();
        }
        stk1.push(x);
    } /** Removes the element from in front of queue and returns that element. */
    int pop()
    {
        while (!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }
        int top = stk2.top();
        stk2.pop();
        return top;
    } /** Get the front element. */
    int peek()
    {
        while (!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }
        return stk2.top();
    } /** Returns whether the queue is empty. */
    bool empty() { return stk1.empty() && stk2.empty(); }
};

本代码提交AC，用时3MS。
二刷。其实push的时候可以不需要把stk2的数据倒腾回stk1，stk2的数据始终是队列头的，stk1的数据始终是队列尾的，代码如下：

class MyQueue {
private:
    stack<int> stk1, stk2;
    void adjust()
    {
        while (!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }
    }
public: /** Initialize your data structure here. */
    MyQueue() {} /** Push element x to the back of queue. */
    void push(int x) { stk1.push(x); } /** Removes the element from in front of queue and returns that element. */
    int pop()
    {
        if (stk2.empty())
            adjust();
        int ans = stk2.top();
        stk2.pop();
        return ans;
    } /** Get the front element. */
    int peek()
    {
        if (stk2.empty())
            adjust();
        int ans = stk2.top();
        return ans;
    } /** Returns whether the queue is empty. */
    bool empty() { return stk1.empty() && stk2.empty(); }
};

本代码提交AC，用时3MS。