面试笔试杂项积累-leetcode 221-225_simluatechainnode

221.221-Combination Sum III-Difficulty: Medium

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

思路

最大全1正方形面积

用动态规划求出最大边长，再平方

以当前点(x,y) = '1' 为右下角的最大正方形的边长f(x,y) = min( f(x-1,y), f(x,y-1), f(x-1,y-1)) + 1.

public class Solution {
    public int MaximalSquare(char[,] matrix) {
                if (matrix == null || matrix.Length == 0) return 0;
        int row = matrix.GetLength(0);
        int col = matrix.GetLength(1);
            int max = 0;
        int[,] temp = new int[row, col];
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++)
                if (matrix[i, j] == '1')
                   { temp[i, j] = 1;max = 1;}
 
    
        for (int i = 1; i < row; i++)
            for (int j = 1; j < col; j++)
            {
                if (matrix[i, j] == '1')
                {
                    temp[i, j] = Math.Min(Math.Min(temp[i - 1, j], temp[i, j - 1]), temp[i - 1, j - 1]) + 1;//求出最长边长
                    max = Math.Max(max, temp[i, j]);
                }
            }
        return max*max;
    }
}

222.222-Count Complete Tree Nodes-Difficulty: Medium

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

方法一

思路

给予一个完全二叉树，返回所有节点个数

用先序中序后序都是超时的

要利用完全二叉树这个所给条件

参考：

https://leetcode.com/discuss/73892/a-very-clear-recursive-solution-isnt-it

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int count = 0;
    public int CountNodes(TreeNode root) {
        if (root == null) return 0;
        int lh = fTreeHt(root.left);
        int rh = fTreeHt(root.right);
        if (lh == rh)
            return (1 << lh) + CountNodes(root.right);  /*1(根节点) + (1<<lh)-1(完全左子树) + # of rightNode */
        else
            return (1 << rh) + CountNodes(root.left);  /*1(根节点) + (1<<rh)-1(完全右子树) + # of leftNode*/
    }
 
    int fTreeHt(TreeNode root)
    { //get the height of a complete binary tree.
        if (root == null) return 0;
        return 1 + fTreeHt(root.left);  
    }
}

方法二

思路

public class Solution {
    public int countNodes(TreeNode root) {
        return root == null ? 0 : findLastIndex(root, 1);
    }
    private int lHeight(TreeNode node, int count) {
        return node == null ? count - 1 : lHeight(node.left, count + 1);
    }
    private int findLastIndex(TreeNode node, int currIndex) {
        if (node.left == null && node.right == null) return currIndex;
        if (lHeight(node.left, 1) == lHeight(node.right, 1))
            return findLastIndex(node.right, currIndex * 2 + 1);
        else return findLastIndex(node.left, currIndex * 2);
    }
}

223.223-Rectangle Area-Difficulty: Easy

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

思路

求出上图面积

注意二矩形位置和大小不定，有可能有一矩形面积为0，也有可能丝毫不相交，也有可能位置互换等

此时的关键就是求出中间小矩形的面积

public class Solution {
    public int ComputeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int overlap = 0;
        int minx = A < E ? E : A;
        int maxx = C < G ? C : G;
 
        int miny = F < B ? B : F;
        int maxy = H < D ? H : D;
 
        if (minx > maxx || miny > maxy)
            overlap = 0;
        else
            overlap = (maxy - miny) * (maxx - minx);
        return (C - A) * (D - B) + (G - E) * (H - F) -overlap;
    }
}

224.224-Basic Calculator-Difficulty: Medium

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

思路

给出string算式求出结果，包括+，-和括号

遇到 '(' 就把之前的结果和符号push进stack. 遇到')'就把 当前结果*stack中的符号 再加上stack中之前的结果.

+，-当做+1，-1与当前数值求积即可

public class Solution {
    public int Calculate(string s) {
          s = s.Trim(' ');
        Stack<int> stack = new Stack<int>();
        int res = 0;
        int sign = 1;
        for (int i = 0; i < s.Length; i++)
        {
            if (char.IsDigit(s[i]))
            {
                int temp = s[i] - '0';
                while (i < s.Length - 1 && char.IsDigit(s[i + 1]))
                {
                    temp = temp * 10 + s[i + 1] - '0';
                        ++i;
                }
                res = res + sign * temp;
            }
            else if (s[i] == '+')
            {
                sign = 1;
            }
            else if (s[i] == '-')
            {
                sign = -1;
            }
            else if (s[i] == '(')
            {
                stack.Push(res);
                stack.Push(sign);
                res = 0;
                sign = 1;
            }
            else if (s[i] == ')')
            {
                res =  res * stack.Pop()+stack.Pop();
                sign = 1;
            }
        }
        return res;
    }
}

225.225- Implement Stack using Queues-Difficulty: Easy

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.

• 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).

方法一

思路

使用队列实现栈的操作，

博主开始没注意是使用队列，就用链表实现了= =。。。这个方法先放这

public class Stack {
   class ChainNode
    {
        public int val;
        public ChainNode next;
        public ChainNode(int _val)
        {
            this.val = _val;
        }
    }
 
    ChainNode head;
    int size = 0;
    // Push element x onto stack.
    public void Push(int x)
    {
        ChainNode temp = head;
        head = new ChainNode(x);
        head.next = temp;
        ++size;
    }
 
    // Removes the element on top of the stack.
    public void Pop()
    {
        head = head.next;
                --size;
    }
 
    // Get the top element.
    public int Top()
    {
        return head.val;
    }
 
    // Return whether the stack is empty.
    public bool Empty()
    {
        return size <= 0;
    }
}

方法二

思路

众所周知，栈和队列的不同一个是先入后出，一个是先入先出，

我们完全可以在push的时候调一下位置使队列的位置满足栈的位置即可，剩下的操作就都用队列的就可以了

class MyStack {
 
//one Queue solution
private Queue<Integer> q = new LinkedList<Integer>();
 
// Push element x onto stack.
public void push(int x) {
    q.add(x);
    for(int i = 1; i < q.size(); i ++) { //rotate the queue to make the tail be the head
        q.add(q.poll());
    }
}
 
// Removes the element on top of the stack.
public void pop() {
    q.poll();
}
 
// Get the top element.
public int top() {
    return q.peek();        
}
 
// Return whether the stack is empty.
public boolean empty() {
    return q.isEmpty();
}

方法三

思路

也是在push中进行操作，两个队列来回颠倒，使其中一个有栈的顺序，其中一个为空

参考：

https://leetcode.com/discuss/84233/solutions-about-which-utilizes-queue-others-utilize-queues

1 Push method is inefficient.

when you push an element, choose one empty queue(whichever when both are empty) to add this element, and then push all elements of the other queue into the chosen queue. After that, the newest element is at the head of the chosen queue so that whenever you want to do pop() or top(), you always get the newest element.

For example,

push(1):

[ , ,1] [ , , ]

push(2):

[ , , ] [ ,1,2]

push(3):

[ 1, 2,3 ] [ , , ]

class MyStack {
//using two queue. The push is inefficient.
private Queue<Integer> q1 = new LinkedList<Integer>();
private Queue<Integer> q2 = new LinkedList<Integer>();
public void push(int x) {
    if(q1.isEmpty()) {
        q1.add(x);
        for(int i = 0; i < q2.size(); i ++)
            q1.add(q2.poll());
    }else {
        q2.add(x);
        for(int i = 0; i < q1.size(); i++)
            q2.add(q1.poll());
    }
}
 
public void pop() {
    if(!q1.isEmpty()) 
        q1.poll();
    else
        q2.poll();
}
public int top() {
    return q1.isEmpty() ? q2.peek() : q1.peek();
}
public boolean empty() {
    return q1.isEmpty() && q2.isEmpty();
}
}

方法四

思路

参考：

2 pop() and top() are inefficient

When you push elements, choose a queue which is not empty(whichever when both are empty).When you do pop() or top(), first pop all elements of the queue except the tail into another empty queue, and then pop the tail which is your want.

For example:

push(1):

[ , , 1] [ , , ]

push(2):

[ ,2,1] [ , , ]

top();

[ , , 2] [ , ,1] -> [ , , ] [ ,2,1]

pop():

[ , , 1] [ , ,2] -> [ , ,1] [ , , ]

push(3) :

[ ,3,1] [ , , ]

class MyStack{
//using two queue. The pop and top are inefficient.
private Queue<Integer> q1 = new LinkedList<Integer>();
private Queue<Integer> q2 = new LinkedList<Integer>();
public void push(int x) {
    if(!q1.isEmpty()) 
        q1.add(x);
    else
        q2.add(x);
}
public void pop() {
    if(q1.isEmpty()) {
        int size = q2.size();
        for(int i = 1; i < size; i ++) {
            q1.add(q2.poll());
        }
        q2.poll();
    }else {
        int size = q1.size();
        for(int i = 1; i < size; i ++) {
            q2.add(q1.poll());
        }
        q1.poll();
    }
}
public int top() {
    int res;
    if(q1.isEmpty()) {
        int size = q2.size();
        for(int i = 1; i < size; i ++) {
            q1.add(q2.poll());
        }
        res = q2.poll();
        q1.add(res);
    }else {
        int size = q1.size();
        for(int i = 1; i < size; i ++) {
            q2.add(q1.poll());
        }
        res = q1.poll();
        q2.add(res);
    }
    return res;
}
public boolean empty() {
    return q1.isEmpty() && q2.isEmpty();
}
}