基础算法解决相对应问题思路(二)

时间:2021-7-3 作者:qvyue

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

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 

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

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

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

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

两个队列解决方案:

class MyStack {

    private Queue 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 

单个队列解决方案:

class MyStack {

    private Queue 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 

C++ 的实现

lass MyStack {
private:
    queue 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 tail;
    Stack 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 tail;
    stack 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 

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

Java写法

class CQueue {
    Stack stack1;
    Stack 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 tail;
   stack 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

进阶:递归算法很简单,你可以通过迭代算法完成吗?

思路: 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 list = new ArrayList();
    public List 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 preorderTraversal(TreeNode root) {
        List list = new ArrayList();
        Deque stack = new ArrayDeque();

        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]

1
   
    2
   /
  3 

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

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

class Solution {
    public List list = new ArrayList();
    public List 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 postorderTraversal(TreeNode root) {
            List list = new ArrayList();
            Deque 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 postorderTraversal(TreeNode root) {
            List list = new ArrayList();
            Deque 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
     / 
    4   5

序列化为 “[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 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 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 

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 

计算 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

方法②实现

public void rotate(int[][] matrix) {
        int n = matrix.length;
        for(int i=0;i

方法③实现

public void rotate(int[][] matrix) {
        int n = matrix.length;
        for(int i=0;i
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。