基础算法解决相对应问题思路（二）

2021-04-12 本文已影响0人 zcwfeng

回顾基础算法
定义一个链表

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    ListNode(int x, ListNode node) {
        val = x;
        next = node;
    }
}
// 获取链表长度
 public int getLength(Node head) {
        if (head == null) {
            return 0;
        }

        int length = 0;
        Node current = head;
        while (current != null) {
            length++;
            current = current.next;
        }

        return length;
    }

1. 如何证明给定的链表是否包含循环?如何找到循环的头节点?

思路: 还是利用快慢指针解决

判断是否有环

设置一个快指针fast，一个慢指针slow，二者初始都指向链表头，fast一次走两步，slow一次走一步，两个指针同时向前移动，每移动一次，两个指针都要进行比较，如果快指针等于慢指针，则证明这是个有环的单链表，否则如果fast先行到达链表尾部或为NULL，则证明这是个不带环的单链表。

public boolean isLoop(ListNode head){
        boolean flag = false;
        ListNode fast = head;
        ListNode slow = head;
        while(fast !=null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if(fast == slow) {
                flag = true;
                break;
            }
        }
        if(fast == null || fast.next == null){
            flag = false;
        }
        return flag;
    }

如何找到环的入口点，需要一个推导

思路：
如果单链表有环，当slow指针和fast指针相遇时，slow指针还没有遍历完链表，而fast指针已经在环内循环n（n>=1）圈了，假设此时slow指针走了s步，fast指针走了2s步，r为fast在环内转了一圈的步数，a为从链表头到入口点的步数，b为从入口点到相遇点的步数，c为从相遇点再走c步到达入口点，L为整个链表的长度。

slow指针走的步数：
s = a + b
fast指针走的步数：
2s = s + n*r 即：s = n*r
链表的长度：
L = a + b + c = a+r
由上可得：
a + b = n*r = (n - 1)*r + r
而r = L - a，所以：
a + b = (n - 1)*r + L - a
a = (n - 1)*r + L - a - b
而L - a - b = c，所以：
a = (n -1)*r +c

这个推导过程有点繁琐，所以直接看结论和代码。

综上可得：从链表头到环入口点等于(n - 1)循环内环 + 相遇点到环入口点，于是在链表头和环入口点分别设置一个指针，同时出发，每次各走一步，它们必定会相遇，且第一次相遇的点就是环入口点。

  public static ListNode findLoopPort(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // 先判断是否有环
//        boolean flag = false;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
//                flag = true;
                break;
            }
        }
        if (fast == null || fast.next == null) {
//            flag = false;
            return null;
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

2. 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
 

提示：

1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

思路：
栈是一种后进先出的数据结构，元素从顶端入栈，然后从顶端出栈。

队列是一种先进先出的数据结构，元素从后端入队，然后从前端出队。

方法一：两个队列
为了满足栈的特性，即最后入栈的元素最先出栈，在使用队列实现栈时，应满足队列前端的元素是最后入栈的元素。可以使用两个队列实现栈的操作，其中 queue1用于存储栈内的元素queue2作为入栈操作的辅助队列
入栈操作时，首先将元素入队到 queue2，然后将 queue1的全部元素依次出队并入队到 queue2，此时 queue2的前端的元素即为新入栈的元素，再将queue1和 queue2互换，则queue1的元素即为栈内的元素，queue1的前端和后端分别对应栈顶和栈底。
由于每次入栈操作都确保queue 1的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。
出栈操作只需要移除 queue 1的前端元素并返回即可，获得栈顶元素操作只需要获得queue 1的前端元素并返回即可（不移除元素）。
由于queue 1用于存储栈内的元素，判断栈是否为空时，只需要判断queue1是否为空即可。

方法二：一个队列
和方法一思想一样，只不过，需要将元素每次，全部出队在入队。

两个队列解决方案：

class MyStack {

    private Queue<Integer> queue;

    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue.offer(x);
        for (int i = 1; i < queue.size(); i++) {
            queue.offer(queue.poll());
        }
       
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return  queue.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

单个队列解决方案：

class MyStack {

    private Queue<Integer> queue;

    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue.offer(x);
        for (int i = 1; i < queue.size(); i++) {
            queue.offer(queue.poll());
        }
       
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return  queue.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

C++ 的实现

lass MyStack {
private:
    queue<int> q;
public:
    /** Initialize your data structure here. */
    MyStack() {
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        q.push(x);
        int n = q.size();
        while(n > 1){
            q.push(q.front());
            q.pop();
            n--;
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int ret = q.front();
        q.pop();

        return  ret;
    }
    
    /** Get the top element. */
    int top() {
        return q.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return q.empty();
    }
};

3. 两个栈实现一个队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

思路：A一个入栈，模拟尾插。B模拟head删除。
先吧B全部压栈到A，在将value压栈，模拟尾插。
同理吧A全部压栈到B，在从B中出栈栈顶元素返回，模拟head删除
注意peek方法

Java实现

class MyQueue {

    Stack<Integer> tail;
    Stack<Integer> head;
    /** Initialize your data structure here. */
    public MyQueue() {
        tail = new Stack<>();
        head = new Stack<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        while(!head.isEmpty()){
            tail.push(head.pop());
        }
        tail.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        while(!tail.isEmpty()){
            head.push(tail.pop());
        }
        if(head.isEmpty()){
            return -1;
        }
        return head.pop();
    }

   /** Get the front element. */
    public int peek() {
        if(head.isEmpty()){
            if(tail.isEmpty()){
                return -1;
            }else {
                while(!tail.isEmpty()){
                    head.push(tail.pop());
                }
                return head.peek();
            }
        }else {
            return head.peek();
        }
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return tail.isEmpty() && head.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

C++实现

class MyQueue {
private:
    stack<int> tail;
    stack<int> head;
public:
    /** Initialize your data structure here. */
    MyQueue() {

    }

    /** Push element x to the back of queue. */
    void push(int x) {
        while(!head.empty()){
            tail.push(head.top());
            head.pop();
        }
        tail.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        while(!tail.empty()){
            head.push(tail.top());
            tail.pop();
        }
        if(head.empty()){
            return -1;
        }
        int ret = head.top();
        head.pop();
        return ret;
    }

    /** Get the front element. */
    int peek() {
        if(head.empty()){
            if(tail.empty())
                return -1;
            else{
                while(!tail.empty()){
                    head.push(tail.top());
                    tail.pop();
                }
                return head.top();
            }

        }else{
            
            return head.top();
        }
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return tail.empty() && head.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

4. . 两个栈实现一个队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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 次调用

思路：A一个入栈，模拟尾插。B模拟head删除。
先吧B全部压栈到A，在将value压栈，模拟尾插。
同理吧A全部压栈到B，在从B中出栈栈顶元素返回，模拟head删除

Java写法

class CQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void appendTail(int value) {
        while(!stack2.isEmpty()){
            stack1.push(stack2.pop());
        }
        stack1.push(value);
    }
    
    public int deleteHead() {
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        if(stack2.isEmpty()){
            return -1;
        }
        return stack2.pop();
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

C++写法

class CQueue {
private:
   stack<int> tail;
   stack<int> head;
public:
   CQueue() {

   }

   void appendTail(int value) {
       while(!head.empty()){
           tail.push(head.top());
           head.pop();
       }
       tail.push(value);
   }

   int deleteHead() {
       while(!tail.empty()){
           head.push(tail.top());
           tail.pop();
       }
       if(head.empty()){
           return -1;
       }
       int ret = head.top();
       head.pop();
       return ret;
   }
};

/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/

5. 给你二叉树的根节点 root ，返回它节点值的前序遍历。

示例1：

image.png

输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]

示例 4：

image.png

输入：root = [1,null,2]
输出：[1,2]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

思路： 1. 递归。超级简单 2. while 消除递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> list = new ArrayList<Integer>();
    public List<Integer> preorderTraversal(TreeNode root) {
         if(root == null) {
            return list;
        }else {
            list.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
        
        return list;
    }
}

非递归做法

// 除去递归
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();

        while(root !=null || !stack.isEmpty()){
            while(root != null){
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }
            TreeNode cur = stack.pop();
            root = cur.right;
        }
        
        return list;
    }
}

6. 二叉树的后序遍历

给定一个二叉树，返回它的后序遍历。

示例:

输入: [1,null,2,3]

输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路：1. 递归 2. while消除递归

class Solution {
    public List<Integer> list = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null) {
            return list;
        } else {
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            list.add(root.val);

        }
        return list;

    }
}

非递归做法

//消除递归
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            Deque<TreeNode> stack = new ArrayDeque<>();
            while(root != null || !stack.isEmpty()){
                while(root != null) {
                    list.add(root.val);
                    stack.push(root);
                    root = root.right;
                }
                TreeNode cur = stack.pop();
                root = cur.left;
            }

            Collections.reverse(list);
            return list;

    }
}

统一说下5，6的思路
其实就是一个框架型思考，前，中，后续遍历二叉树的思路
前序遍历：根 -> 左 -> 右。思想就是尽量像左下方左子树走到五路可走位置在回来
后中遍历：左 -> 右 -> 根。巧妙的变换，我们看倒过来是不是根->右 ->左
这样，我们用前序的方法，只需要，左右互换，结果在。反过来，就是我们的后续遍历。
逆向思维。
中序遍历: 左 -> 根 -> 右。核心思想一致，只是顺序不同，完整代码，我们看过了。写下中序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            Deque<TreeNode> stack = new ArrayDeque<>();
            while(root != null || !stack.isEmpty()){
                while(root != null) {
                    stack.push(root);
                    root = root.left;
                }
                TreeNode cur = stack.pop();
                list.add(cur.val);
                root = cur.right;
            }

            return list;

    }
}

7. 检查子树

检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。

如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。

注意：此题相对书上原题略有改动。

示例1:

输入：t1 = [1, 2, 3], t2 = [2]
输出：true
示例2:

输入：t1 = [1, null, 2, 4], t2 = [3, 2]
输出：false
提示：

树的节点数目范围为[0, 20000]。

思路：检查，两个树完全相同，检查是否是左子树，检查是否是右子数。用递归检测

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean checkSubTree(TreeNode t1, TreeNode t2) {
        if(t1 == null) {
            return t2 == null;
        }
        return isSame(t1,t2) || checkSubTree(t1.left,t2) || checkSubTree(t1.right,t2);
    }
    
    public boolean isSame(TreeNode t1, TreeNode t2){
        if(t1 == t2) return true;
        return t1.val==t2.val && isSame(t1.left,t2.left) && isSame(t1.right,t1.right);
    }
}

8. 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。

示例:

你可以将以下二叉树：

序列化为 "[1,2,3,null,null,4,5]"

思路: 层次遍历思想

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null){
            return "";
        }
        StringBuilder res = new StringBuilder();
        res.append("[");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node != null){
                res.append("" + node.val);
                queue.offer(node.left);
                queue.offer(node.right);
            }else{
                res.append("null");
            }
            res.append(",");
        }
        res.append("]");
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == ""){
            return null;
        }
        String[] dataList = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(dataList[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 1;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(!"null".equals(dataList[i])){
                node.left = new TreeNode(Integer.parseInt(dataList[i]));
                queue.offer(node.left);
            }
            i++;
            if(!"null".equals(dataList[i])){
                node.right = new TreeNode(Integer.parseInt(dataList[i]));
                queue.offer(node.right);
            }
            i++;
        }
        return root;
    }
}

9. 任意一颗二叉树，求最大节点距离

如果我们把二叉树看做图，父子节点之间的连线看成是双向的，我们姑且定义“距离”为两个节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。

这个还是难度不小的。关键是比较抽象，大多数人到这里都是前进困难

搜集资料的一些方法参考。

如下图所示，树中相距最远的两个节点为A,B，最大距离为6。

image.png

思路：
计算一个二叉树的最大距离有两个情况：
① 情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
② 情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。

imageA_B.png

对于情况A来说，只需要知道左右子树的深度，然后加起来即可。

对于情况B来说，需要知道左子树的最远距离，右子树的最远距离。

对于B情况有点不好理解

// 数据结构定义
struct NODE {
    NODE *pLeft;        // 左子树
    NODE *pRight;       // 右子树
    int nMaxLeft;       // 左子树中的最长距离
    int nMaxRight;      // 右子树中的最长距离
    char chValue;       // 该节点的值
};

int nMaxLen = 0;

// 寻找树中最长的两段距离
void FindMaxLen(NODE *pRoot) {
    // 遍历到叶子节点，返回
    if (pRoot == NULL) {
        return;
    }

    // 如果左子树为空，那么该节点的左边最长距离为0
    if (pRoot->pLeft == NULL) {
        pRoot->nMaxLeft = 0;
    }

    // 如果右子树为空，那么该节点的右边最长距离为0
    if (pRoot->pRight == NULL) {
        pRoot->nMaxRight = 0;
    }

    // 如果左子树不为空，递归寻找左子树最长距离
    if (pRoot->pLeft != NULL) {
        FindMaxLen(pRoot->pLeft);
    }

    // 如果右子树不为空，递归寻找右子树最长距离
    if (pRoot->pRight != NULL) {
        FindMaxLen(pRoot->pRight);
    }

    // 计算左子树最长节点距离
    if (pRoot->pLeft != NULL) {
        int nTempMax = 0;
        if (pRoot->pLeft->nMaxLeft > pRoot->pLeft->nMaxRight) {
            nTempMax = pRoot->pLeft->nMaxLeft;
        } else {
            nTempMax = pRoot->pLeft->nMaxRight;
        }
        pRoot->nMaxLeft = nTempMax + 1;
    }

    // 计算右子树最长节点距离
    if (pRoot->pRight != NULL) {
        int nTempMax = 0;
        if (pRoot->pRight->nMaxLeft > pRoot->pRight->nMaxRight) {
            nTempMax = pRoot->pRight->nMaxLeft;
        } else {
            nTempMax = pRoot->pRight->nMaxRight;
        }
        pRoot->nMaxRight = nTempMax + 1;
    }

    // 更新最长距离
    if (pRoot->nMaxLeft + pRoot->nMaxRight > nMaxLen) {
        nMaxLen = pRoot->nMaxLeft + pRoot->nMaxRight;
    }
}

解决缺陷：

算法加入了侵入式(intrusive)的资料nMaxLeft, nMaxRight
使用了全局变量 nMaxLen。每次使用要额外初始化。
而且就算是不同的独立资料，也不能在多个线程使用这个函数
逻辑比较复杂，也有许多 NULL 相关的条件测试。

-》优化

#include <iostream>

using namespace std;

struct NODE {
    NODE *pLeft;
    NODE *pRight;
};

struct RESULT {
    int nMaxDistance;
    int nMaxDepth;
};

RESULT GetMaximumDistance(NODE *root) {
    if (!root) {
        RESULT empty = {0, -1};   // trick: nMaxDepth is -1 and then caller will plus 1 to balance it as zero.
        return empty;
    }

    RESULT lhs = GetMaximumDistance(root->pLeft);
    RESULT rhs = GetMaximumDistance(root->pRight);

    RESULT result;
    result.nMaxDepth = max(lhs.nMaxDepth + 1, rhs.nMaxDepth + 1);
    result.nMaxDistance = max(max(lhs.nMaxDistance, rhs.nMaxDistance), lhs.nMaxDepth + rhs.nMaxDepth + 2);
    return result;
}

void Link(NODE* nodes, int parent, int left, int right)
{
    if (left != -1)
        nodes[parent].pLeft = &nodes[left];

    if (right != -1)
        nodes[parent].pRight = &nodes[right];
}

int main()
{
    // P. 241 Graph 3-12
    NODE test1[9] = { 0 };
    Link(test1, 0, 1, 2);
    Link(test1, 1, 3, 4);
    Link(test1, 2, 5, 6);
    Link(test1, 3, 7, -1);
    Link(test1, 5, -1, 8);
    cout << "test1: " << GetMaximumDistance(&test1[0]).nMaxDistance << endl;

    // P. 242 Graph 3-13 left
    NODE test2[4] = { 0 };
    Link(test2, 0, 1, 2);
    Link(test2, 1, 3, -1);
    cout << "test2: " << GetMaximumDistance(&test2[0]).nMaxDistance << endl;

    // P. 242 Graph 3-13 right
    NODE test3[9] = { 0 };
    Link(test3, 0, -1, 1);
    Link(test3, 1, 2, 3);
    Link(test3, 2, 4, -1);
    Link(test3, 3, 5, 6);
    Link(test3, 4, 7, -1);
    Link(test3, 5, -1, 8);
    cout << "test3: " << GetMaximumDistance(&test3[0]).nMaxDistance << endl;

    // P. 242 Graph 3-14
    // Same as Graph 3-2, not test

    // P. 243 Graph 3-15
    NODE test4[9] = { 0 };
    Link(test4, 0, 1, 2);
    Link(test4, 1, 3, 4);
    Link(test4, 3, 5, 6);
    Link(test4, 5, 7, -1);
    Link(test4, 6, -1, 8);
    cout << "test4: " << GetMaximumDistance(&test4[0]).nMaxDistance << endl;
    return 0;
}

计算 result 的代码很清楚；nMaxDepth 就是左子树和右子树的深度加1；nMaxDistance 则取 A 和 B 情况的最大值。

为了减少 NULL 的条件测试，进入函数时，如果节点为 NULL，会传回一个 empty 变量。比较奇怪的是 empty.nMaxDepth = -1，目的是让调用方 +1 后，把当前的不存在的 (NULL) 子树当成最大深度为 0。

除了提高了可读性，这个解法的另一个优点是减少了 O(节点数目) 大小的侵入式资料，而改为使用 O(树的最大深度) 大小的栈空间。这个设计使函数完全没有副作用(side effect)。

引申：

求二叉树的深度的代码

int DepthOfBinaryTree(BinaryTreeNode *pNode) {
    if (pNode == NULL) {
        return 0;
    } else {  //递归
        return DepthOfBinaryTree(pNode->m_pLeft) > DepthOfBinaryTree(pNode->m_pRight) ?
        DepthOfBinaryTree(pNode->m_pLeft) + 1 : DepthOfBinaryTree(pNode->m_pRight) + 1;
    }
}


//改进的版本
int HeightOfBinaryTree(BinaryTreeNode*pNode, int&nMaxDistance){
    if (pNode == NULL)
        return -1;   //空节点的高度为-1
    //递归
    int nHeightOfLeftTree = HeightOfBinaryTree(pNode->m_pLeft, nMaxDistance) + 1;   //左子树的的高度加1
    int nHeightOfRightTree = HeightOfBinaryTree(pNode->m_pRight, nMaxDistance) + 1;   //右子树的高度加1
    int nDistance = nHeightOfLeftTree + nHeightOfRightTree;    //距离等于左子树的高度加上右子树的高度+2
    nMaxDistance = nMaxDistance > nDistance ? nMaxDistance : nDistance;            //得到距离的最大值
    return nHeightOfLeftTree > nHeightOfRightTree ? nHeightOfLeftTree : nHeightOfRightTree;
}

10.旋转矩阵

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
不占用额外内存空间能否做到？

示例 1:

image.png

给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例 2:

image.png

给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],

原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

思路：
① 暴力解法，借助辅助数组
使用一个与 matrix 大小相同的辅助数组 matrix_new，临时存储旋转后的结果。我们遍历 matrix 中的每一个元素，根据上述规则将该元素存放到 matrix_new中对应的位置。在遍历完成之后，再将 matrix_new中的结果复制到原数组中即可。
核心的等式，matrix_new[col][n−row−1]=matrix[row][col]

截屏2021-04-11 16.57.52.png

复杂度分析

时间复杂度：O(N^2)O(N 2)，其中 NN 是 matrix 的边长。

空间复杂度：O(N^2)O(N 2)。我们需要使用一个和 matrix 大小相同的辅助数组。

② 找到规律，a[i][j] 的规律,原地旋转

分析	变换	变换
1.png	2.png	3.png
4.png	......	5.png
6.png	......	7.png

复杂度分析

时间复杂度：时间复杂度：O(N²)，其中 N 是matrix 的边长。我们需要枚举的子矩阵大小为O(「n/2」 x 「(n+1)/2」 ) = O(N²)
空间复杂度：O(1)。为原地旋转。

核心的等式，matrix_new[col][n−row−1]=matrix[row][col]
然后将每一周的四个数交换

③ 利用翻转代替旋转，两次翻转
沿着中轴线翻转，然后对角线翻转。

时间复杂度：时间复杂度：O(N²)，其中 N 是matrix 的边长。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。
空间复杂度：O(1)。为原地翻转得到的原地旋转。

方法①实现（暴力解）

    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int matrix_new[][] = new int[n][n];
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                matrix_new[j][n-i-1] = matrix[i][j]; 
            }
        }

        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                matrix[i][j] = matrix_new[i][j];
            }
        }

    }

方法②实现

public void rotate(int[][] matrix) {
        int n = matrix.length;
        for(int i=0;i<n/2;++i){
            for(int j=0;j<(n+1)/2;++j){
                int temp = matrix[i][j]; 
                matrix[i][j] = matrix[n-j-1][i];
                matrix[n-j-1][i] = matrix[n-i-1][n-j-1];
                matrix[n-i-1][n-j-1] =  matrix[j][n-i-1];
                matrix[j][n-i-1] = temp;
            }
        }

    }

方法③实现

public void rotate(int[][] matrix) {
        int n = matrix.length;
        for(int i=0;i<n/2;++i){
            for(int j=0;j<n;++j){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n-i-1][j];
                matrix[n-i-1][j] = temp;
            }
        }

        for(int i=0;i<n;++i){
            for(int j=0;j<i;++j){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        
    }

基础算法解决相对应问题思路（二）

1. 如何证明给定的链表是否包含循环?如何找到循环的头节点?

2. 用队列实现栈

3. 两个栈实现一个队列

Java实现

C++实现

4. . 两个栈实现一个队列

Java写法

C++写法

5. 给你二叉树的根节点 root ，返回它节点值的前序遍历。

非递归做法

6. 二叉树的后序遍历

非递归做法

7. 检查子树

8. 序列化二叉树

9. 任意一颗二叉树，求最大节点距离

求二叉树的深度的代码

10.旋转矩阵

猜你喜欢

热点阅读

基础算法解决相对应问题思路（二）

1. 如何证明给定的链表是否包含循环?如何找到循环的头节点?

2. 用队列实现栈

3. 两个栈实现一个队列

Java实现

C++实现

4. . 两个栈实现一个队列

Java写法

C++写法

5. 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

非递归做法

6. 二叉树的后序遍历

非递归做法

7. 检查子树

8. 序列化二叉树

9. 任意一颗二叉树，求最大节点距离

求二叉树的深度的代码

10.旋转矩阵

猜你喜欢

热点阅读

5. 给你二叉树的根节点 root ，返回它节点值的前序遍历。