Eric's Blogs

Better Code, Better Life

0%

发表于 分类于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

题目描述

请实现一个函数用来匹配包括’.’和’*‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab\ac*a”匹配，但是与”aa.a”和”ab*a”均不匹配

解答

待补充

网上题解

链接：https://www.nowcoder.com/questionTerminal/45327ae22b7b413ea21df13ee7d6429c?answerType=1&f=discussion
来源：牛客网

方法一：递归

假设主串为s，长度为sn， 模式串为p，长度为pn，对于模式串p当前的第i位来说，有'正常字符'、'*'、'.'三种情况。我们针对这三种情况进行讨论：

  1. 如果p[i]为正常字符， 那么我们看s[i]是否等于p[i], 如果相等，说明第i位匹配成功,接下来看s[i+1...sn-1] 和 p[i+1...pn-1]
  2. 如果p[i] 为'.', 它能匹配任意字符，直接看s[i+1...sn-1] 和 p[i+1...pn-1]
  3. 如果p[i] 为'*'， 表明p[i-1]可以重复0次或者多次，需要把p[i-1] 和 p[i]看成一个整体.
    • 如果p[i-1]重复0次，则直接看s[i...sn-1] 和 p[i+2...pn-1]
    • 如果p[i-1]重复一次或者多次,则直接看s[i+1...sn-1] 和p[i...pn-1]，但是有个前提：s[i]==p[i] 或者 p[i] == '.'

三种情况如下图：
图片说明
图片说明


显然上述的过程可以递归进行计算。
则递归三部曲为：

  1. 递归函数功能：match(s, p) -> bool, 表示p是否可以匹配s
  2. 递归终止条件：
    • 如果s 和 p 同时为空，表明正确匹配
    • 如果s不为空，p为空，表明，不能正确匹配
    • 如果s为空，p不为空，需要计算，不能直接给出结果
  3. 下一步递归：
    • 对于前面讨论的情况1，2进行合并，如果*s == *p || *p == '.',则match(s+1, p+1)
    • 对于情况3，如果重复一次或者多次，则match(s+1,p),如果重复0次，则match(s, p+2)

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool match(char* s, char* p)
    {    // 如果 s 和 p 同时为空
        if (*s == '\0' && *p == '\0') return true;
        // 如果 s不为空， 但是 p 为空
        if (*p == '\0') return false;
        // 如果没有 '*'
        if (*(p+1) != '*') {
            if (*s != '\0' && (*s == *p || *p == '.'))
                return match(s+1, p+1);
            else
                return false;
        }
        // 如果有 '*'
        else {
            bool ret = false;
            // 重复 1 次或多次
            if (*s != '\0' && (*s == *p || *p == '.'))
                ret = match(s+1, p);
            // 重复 0 次
            return ret || match(s, p+2);
        }
    }
};

方法二：动态规划

方法一的递归代码属于自顶向下，而动态规划的代码属于自底向上。

  1. 动态规划转移方程：
    f[i][j]表示s的前i个和p的前j个能否匹配

  • 对于方法一种的1,2两种情况可知：f[i][j] = f[i-1][j-1]

  • 对于第

    1
    3

    种情况可知：

    • 如果重复0次，f[i][j] = f[i][j-2]
    • 如果重复1次或者多次，f[i][j] = f[i-1][j]
  1. 动态规划初始条件：
  • s为空且p为空，为真: f[0][0] = 1
  • s不为空且p为空,为假: f[1..sn][0] = 0

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    bool match(char* s, char* p)
    {
        int sn = strlen(s), pn = strlen(p);
        vector<vector<char>> f(sn+1, vector<char>(pn+1, 0));
        for (int i=0; i<=sn; ++i) {
            for (int j=0; j<=pn; ++j) {
                // 初始条件
                if (j == 0) f[i][j] = (i == 0);
                else {
                    // 如果没有 '*'
                    if (p[j-1] != '*') {
                        if (i >= 1 && (s[i-1] == p[j-1] || p[j-1] == '.')) {
                            f[i][j] = f[i-1][j-1];
                        }
                    }
                    // 如果有 '*'
                    else {
                        // 重复 0 次
                        if (j >= 2) {
                            f[i][j] |= f[i][j-2];
                        }
                        // 重复 1 次或者多次
                        // 这里要用 | 连接， 不然重复 0 次的会直接覆盖
                        if (i >= 1 && j>=2 && (s[i-1] == p[j-2] || p[j-2] == '.')) {
                            f[i][j] |= f[i-1][j];
                        }
                    }
                }

            }
        }
        return f[sn][pn];
    }
};

发表于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。

输出描述:

1
如果当前字符流没有存在出现一次的字符，返回#字符。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Map<Character, Integer> map = new LinkedHashMap<>();

//Insert one char from stringstream
public void Insert(char ch) {
    if (map.containsKey(ch)) {
        map.put(ch, map.get(ch) + 1);
    } else {
        map.put(ch, 1);
    }
}

//return the first appearence once char in current stringstream
public char FirstAppearingOnce() {
    Iterator iter = map.entrySet().iterator();
    while (iter.hasNext()) {
        Map.Entry entry = (Map.Entry) iter.next();
        if ((int) entry.getValue() == 1) {
            return (char) entry.getKey();
        }
    }
    return '#';
}

官方题解

链接：https://www.nowcoder.com/questionTerminal/00de97733b8e4f97a3fb5c680ee10720?answerType=1&f=discussion
来源：牛客网

题目描述：对于动态字符流，返回第一个不重复的字符。如果不存在，返回’#’。

方法：哈希+队列

针对题目的描述，我们先提出两个问题？

Q1. 给定一个字符串（只不过这里的字符串是可变的），如果快速判断一个字符是否存在于字符串中，如果存在，也就是重复？
Q2. 这里先不考虑重复，如果快速返回第一个字符？有没有感觉有点像先来先服务？

对于一道题，如果没有思路，就要针对题目给自己问问题。然后针对问题，来考虑需要什么样的算法或者数据结构。

A1：对于“重复问题”，惯性思维应该想到哈希或者set。对于“字符串问题”，大多会用到哈希。因此一结合，应该可以想到，判断一个字符是否重复，可以选择用哈希，在c++中，可以选择用unordered_map

A2：对于字符流，源源不断的往池子中添加字符，然后还要返回第一个满足什么条件的字符，显然设计到了“顺序”，也就是先来的先服务，这种先进先出的数据结构不就是队列嘛。因此，这里可以用队列。

假如你已经知道了要用hash 和 queue 这两个数据结构，你可以试着自己想一想，接下来的算法过程是怎么样的？
这里我提供一个算法过程，如下：

  1. 初始化一个unordered_map mp, queue q
  2. 对于Insert(char ch)操作， 如果ch是第一次出现，则添加到q中，然后在mp中记录一下次数，如果不是第一次出现，也就是重复了，那么我们就没必要添加到q中，但是还是需要在mp中更新一下次数，因为之后要根据次数来判断是否重复。
  3. 对于FirstAppearingOnce()操作，我们直接判断q的头部，然后在mp中检查一下，是否重复，如果没有重复，那就是我们想要的数据。否则，如果重复了，那就应该弹出头部，然后判断下一个头部是否满足要求。

根据算法的过程，你可以试着自己写一下代码。

我的示例代码如下，仅供参考：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution
{
public:
  //Insert one char from stringstream
    queue<char> q;
    unordered_map<char, int> mp;
    void Insert(char ch)
    {
         // 如果是第一次出现， 则添加到队列中
         if (mp.find(ch) == mp.end()) {
             q.push(ch);
         }
         // 不管是不是第一次出现，都进行计数
         ++mp[ch];
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        while (!q.empty()) {
            char ch = q.front();
            // 拿出头部，如果是第一次出现，则返回
            if (mp[ch] == 1) {
                return ch;
            }
            // 不是第一次出现，则弹出，然后继续判断下一个头部
            else {
                q.pop();
            }
        }
        return '#';
    }
};

时间复杂度：对于Insert(char ch)操作，为O(1), 对于FirstAppearingOnce()操作，为O(N)，因为最坏情况下，队列中存入一半的重复数据， 比如“abcdabcd”，队列会存入“abcd”，并且弹出的时候都是重复的。

空间复杂度：O(N)

发表于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

解答

递归判断,还可以更简洁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
boolean isSymmetrical(TreeNode pRoot) {
    if (pRoot == null) {
        return true;
    }
    if (isSame(pRoot.left, pRoot.right)) {
        return judgeSymmetrical(pRoot.left, pRoot.right);
    } else {
        return false;
    }
}

private boolean judgeSymmetrical(TreeNode leftNode, TreeNode rightNode) {
    if (leftNode == null && rightNode == null) {
        return true;
    } else {
        if (isSame(leftNode.left, rightNode.right) && isSame(leftNode.right, rightNode.left)) {
            return judgeSymmetrical(leftNode.left, rightNode.right) && judgeSymmetrical(leftNode.right, rightNode.left);
        } else {
            return false;
        }
    }
}

private boolean isSame(TreeNode node1, TreeNode node2) {
    if (node1 == null && node2 == null) {
        return true;
    } else if (node1 != null && node2 != null) {
        if (node1.val == node2.val) {
            return true;
        }
    }
    return false;
}

官方题解

链接：https://www.nowcoder.com/questionTerminal/ff05d44dfdb04e1d83bdbdab320efbcb?answerType=1&f=discussion
来源：牛客网

方法：递归

如图

根据上图可知：若满足对称二叉树，必须满足：

1
2
3
1. L->val == R->val
2. L->left->val == R->right->val
3. L->right->val == R->left->val

因此可以自顶向下，递归求解即可。

  1. 设置一个递归函数isSame(r1, r2),表示如果对称，返回true，否则返回false
  2. 递归终止条件：r1==nullptr && r2==nulllptr, 直接返回true，否则，如果只有一个为nullptr，返回false
  3. 下一步递归：如果r1->val == r2->val, 则isSame(root1->left, root2->right) && isSame(root1->right, root2->left);

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isSame(TreeNode *root1, TreeNode *root2) {
        if (!root1 && !root2) return true;
        if (!root1 || !root2) return false;
        return root1->val == root2->val && 
        isSame(root1->left, root2->right) &&
        isSame(root1->right, root2->left);
    }
    bool isSymmetrical(TreeNode* pRoot)
    {
        return isSame(pRoot, pRoot);
    }

};

时间复杂度：O(N)
空间复杂度：O(N),最坏情况下，二叉树退化为链表

发表于 分类于
本文字数： 2.9k 阅读时长 ≈ 3 分钟

题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

解答

分情况判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public TreeLinkNode GetNext(TreeLinkNode pNode) {
    if (pNode == null) {
        return null;
    }
    if (pNode.right != null) {
        TreeLinkNode tmp = pNode.right;
        while (tmp.left != null) {
            tmp = tmp.left;
        }
        return tmp;
    } else {//pNode.right == null
        if (pNode.next == null) {
            return null;
        } else if (pNode.next.left == pNode) {//pNode is left child
            return pNode.next;
        } else {//pNode is right child
            TreeLinkNode tmp = pNode.next;
            while (tmp.next.left != tmp) {//find first left child
                tmp = tmp.next;
                if (tmp.next == null) {
                    return null;
                }
            }
            return tmp.next;
        }
    }
}

官方题解

链接：https://www.nowcoder.com/questionTerminal/9023a0c988684a53960365b889ceaf5e?answerType=1&f=discussion
来源：牛客网

题目描述：给你一颗二叉树的一个结点，返回中序遍历顺序中这个结点的下一结点。二叉树不仅有左右孩子指针，还有指向父亲结点的指针。

Q1：首先问你一个问题，如果这道题出现在笔试题中，你会用什么方法做？如果出现在面试题中呢？
A1：我想你肯定有点疑惑，同一道题为什么还分出现在笔试题中还是面试题中呢？很显然，笔试题中只要能过就好，设计的算法丑点，慢点也无所畏，不一定需要最优解法，当然前提是能够通过。而面试中就不一样了，显然面试官希望听到最优解法。

方法一：暴力解法

如果在笔试题中看到这道题，直接模拟题意就好了。题意需要找到某个结点中序遍历的下一个结点，那我们的做法很显然可以这样：

  1. 根据给出的结点求出整棵树的根节点
  2. 根据根节点递归求出树的中序遍历，存入vector
  3. 在vector中查找当前结点，则当前结点的下一结点即为所求。

虽然有点暴力，但是时间复杂度也是线性的，第一步：最坏为O(N), N为整棵树结点的个数。第二步：O(N), 第三步：最坏为O(N),
所以整的时间复杂度：3*O(N)

时间复杂度还可以接受，关键是思路好想并且每一步的代码都很简单。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    void pre_order(TreeLinkNode *root, vector<TreeLinkNode*> &v) {
        if (!root) {
            return;
        }

        pre_order(root->left, v);
        v.push_back(root);
        pre_order(root->right, v);
    }
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
          TreeLinkNode *root = nullptr;
          TreeLinkNode *tmp = pNode;
          // 第一步
          while (tmp) {
              root = tmp;
              tmp = tmp->next;
          }   

          vector<TreeLinkNode*> v;
          // 第二步
          pre_order(root, v);

          // 第三步
          int n = v.size();
          for (int i = 0; i < n; ++i) {
              if (v[i] == pNode && i + 1 != n) {
                  return v[i+1];
              } 
          }
          return nullptr;
    }
};

时间复杂度：O(N)
空间复杂度：O(N)

方法二：最优解法

但是，如果在面试中，方法一肯定上不了台面。但是最优解法该怎么去想呢？想不出来就画图分析，举个中序遍历的图：如下：

图片说明
红色数字是中序遍历的顺序。接下来，我们就假设，如果当前结点分别是1,2 … 7，下一结点看有什么规律没？

1
2
3
4
5
6
7
1 => 2 // 显然下一结点是 1 的父亲结点
2 => 3 // 下一节点是当前结点右孩子的左孩子结点，其实你也应该想到了，应该是一直到左孩子为空的那个结点
3 => 4 // 跟 2 的情况相似，当前结点右孩子结点的左孩子为空的那个结点
4 => 5 // 5 是父亲结点 3 的父亲结点，发现和1有点像，因为 1，3,同样是父亲结点的左孩子
5 => 6 // 跟 4=>5 一样的道理
6 => 7 // 跟 3=>4 一样的道理
7 => null // 因为属于最尾结点

此时，可以总结一下：
[1] 是一类：特点：当前结点是父亲结点的左孩子
[2 3 6] 是一类，特点：当前结点右孩子结点，那么下一节点就是：右孩子结点的最左孩子结点,如果右孩子结点没有左孩子就是自己
[4 5]是一类，特点：当前结点为父亲结点的右孩子结点，本质还是[1]那一类
[7]是一类，特点：最尾结点

我写的可能不够清晰，但是，思想你要明白，当遇到不会的题，可以根据题意画图，分析，分析方法是关键。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if (!pNode) {
            return pNode;
        }

        // 属于[2 3 6]类
        if (pNode->right) {
            pNode = pNode->right;
            while (pNode->left) {
                pNode = pNode->left;
            }
            return pNode;
        }

        // 属于 [1] 和 [4 5]
        while (pNode->next) {
            TreeLinkNode *root = pNode->next;
            if (root->left == pNode) {
                return root;
            }
            pNode = pNode->next;
        }

        // 属于[7]
        return nullptr;
    }
};

时间复杂度：最坏情况下为O(N)
空间复杂度：O(1)

发表于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

题目描述

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。

解答

结合正则表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public boolean isNumeric(char[] str) {
    String s = new String(str);
    if (s.startsWith("+") || s.startsWith("-")) {
        s = s.substring(1);
    }
    if (s.matches("[0-9]+.*")) {
        s = s.replaceFirst("[0-9]+", "");
        if ("".equals(s)) {
            return true;
        }
    }

    if (s.startsWith(".")) {
        s = s.substring(1);
        if (!s.matches("[0-9]+.*")) {
            return false;
        }
        s = s.replaceFirst("[0-9]+", "");
    }
    if ("".equals(s)) {
        return true;
    }

    if (s.startsWith("e") || s.startsWith("E")) {
        s = s.substring(1);
        if (s.startsWith("+") || s.startsWith("-")) {
            s = s.substring(1);
        }
        if (!s.matches("[0-9]+")) {
            return false;
        } else {
            return true;
        }
    } else {
        return false;
    }
}

我不服,也写了个正则表达式,好像也能通过

1
2
3
4
public boolean isNumeric(char[] str) {
    String pattern = "[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?";
    return new String(str).matches(pattern);
}

网上题解

链接：https://www.nowcoder.com/questionTerminal/6f8c901d091949a5837e24bb82a731f2?answerType=1&f=discussion
来源：牛客网

来玩正则表达式吧！~

1
2
3
4
5
6
7
8
9
import java.util.regex.Pattern;

public class Solution {
    public static boolean isNumeric(char[] str) {
        String pattern = "^[-+]?\\d*(?:\\.\\d*)?(?:[eE][+\\-]?\\d+)?$";
        String s = new String(str);
        return Pattern.matches(pattern,s);
    }
}

^ 和 美元符号框定正则表达式，它指引这个正则表达式对文本中的所有字符都进行匹配。如果省略这些标识，那么只要一个字符串中包含一个数字这个正则表达式就会进行匹配。如果仅包含 ^ ，它将匹配以一个数字开头的字符串。如果仅包含$ ，则匹配以一个数字结尾的字符串。

1
[-+]?

正负号后面的 ? 后缀表示这个负号是可选的,表示有0到1个负号或者正号

1
\\d*

\d的含义和[0-9]一样。它匹配一个数字。后缀 * 指引它可匹配零个或者多个数字。

1
(?:\\.\\d*)?

(?: …)?表示一个可选的非捕获型分组。* 指引这个分组会匹配后面跟随的0个或者多个数字的小数点。

1
(?:[eE][+\\-]?\d+)?

这是另外一个可选的非捕获型分组。它会匹配一个e(或E)、一个可选的正负号以及一个或多个数字。

发表于 分类于
本文字数： 2.6k 阅读时长 ≈ 2 分钟

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

解答

层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {

    ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
    if (pRoot == null) {
        return lists;
    }
    int curLevelNum = 1, nextLevelNum = 0, num = 0, level = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(pRoot);
    ArrayList<Integer> tmpList = new ArrayList<>();
    while (!queue.isEmpty()) {
        TreeNode t = queue.poll();

        if (t.left != null) {
            queue.add(t.left);
            nextLevelNum++;
        }
        if (t.right != null) {
            queue.add(t.right);
            nextLevelNum++;
        }
        num++;
        tmpList.add(t.val);
        if (num == curLevelNum) {
            level++;
            curLevelNum = nextLevelNum;
            nextLevelNum = 0;
            num = 0;
            if (level % 2 == 0) {//反转
                Collections.reverse(tmpList);
            }
            lists.add(tmpList);
            tmpList = new ArrayList<>();
        }
    }
    return lists;
}

官方题解

链接：https://www.nowcoder.com/questionTerminal/91b69814117f4e8097390d107d2efbe0?answerType=1&f=discussion
来源：牛客网

方法：队列

层次遍历打印二叉树，用队列实现。
有一句话，我觉得说的特别好：做题=解法+模板，意思就是说，对于一道题目，首先明白正确的解法已经解决该问题70%，剩下的就直接套模板。

所以BFS的模板为：

  1. 如果不需要确定当前遍历到了哪一层，模板如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void bfs() {
     vis[] = {0}; // or set
     queue<int> pq(start_val);

     while (!pq.empty()) {
         int cur = pq.front(); pq.pop();
         for (遍历cur所有的相邻节点nex) {
             if (nex节点有效 && vis[nex]==0){
                 vis[nex] = 1;
                 pq.push(nex)
             }
         } // end for
     } // end while
    }

上述是伪代码，不仅可用于二叉树，可针对所有用BFS解题。

  1. 如果需要确定遍历到哪一层，模板如下；

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    void bfs() {
     int level = 0;
     vis[] = {0}; // or set
     queue<int> pq(original_val);
     while (!pq.empty()) {
         int sz = pq.size();

         while (sz--) {
                 int cur = pq.front(); pq.pop();
             for (遍历cur所有的相邻节点nex) {
                 if (nex节点有效 && vis[nex] == 0) {
                     vis[nex] = 1;
                     pq.push(nex)
                 }
             } // end for
         } // end inner while
         level++;

     } // end outer while
    }

此题跟“按层打印二叉树”，仅有一点区别，“按层打印二叉树”是每层都按照从左到右打印二叉树。
而此题是，按照奇数层，从左到右打印，偶数层，从右到左打印。
所以此题可直接套用模板，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> ret;
        if (!pRoot) return ret;
        queue<TreeNode*> q;
        q.push(pRoot);
        int level = 0;

        while (!q.empty()) {
            int sz = q.size();
            vector<int> ans;
            while (sz--) {
                TreeNode *node = q.front();
                q.pop();
                ans.push_back(node->val);

                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            ++level;
            if (!(level&1)) // 偶数层 反转一下
                reverse(ans.begin(), ans.end());
            ret.push_back(ans);
        }
        return ret;
    }

};

时间复杂度：O(N^2)
空间复杂度：O(1), vecotr<vecotr<int>>是必须要开的，不算在额外空间里

发表于 分类于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

解答

层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
    if (pRoot == null) {
        return lists;
    }

    int curLevelNum = 1, nextLevelNum = 0, num = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(pRoot);
    ArrayList<Integer> tmpList = new ArrayList<>();
    while (!queue.isEmpty()) {
        TreeNode t = queue.poll();

        if (t.left != null) {
            queue.add(t.left);
            nextLevelNum++;
        }
        if (t.right != null) {
            queue.add(t.right);
            nextLevelNum++;
        }

        num++;
        tmpList.add(t.val);
        if (num == curLevelNum) {
            curLevelNum = nextLevelNum;
            nextLevelNum = 0;
            num = 0;
            lists.add(tmpList);
            tmpList = new ArrayList<>();
        }

    }
    return lists;
}

官方题解

链接：https://www.nowcoder.com/questionTerminal/445c44d982d04483b04a54f298796288?answerType=1&f=discussion
来源：牛客网

方法：队列

层次遍历打印二叉树，用队列实现。
有一句话，我觉得说的特别好：做题=解法+模板，意思就是说，对于一道题目，首先明白正确的解法已经解决该问题70%，剩下的就直接套模板。

所以BFS的模板为：

  1. 如果不需要确定当前遍历到了哪一层，模板如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void bfs() {
     vis[] = {0}; // or set
     queue<int> pq(start_val);

     while (!pq.empty()) {
         int cur = pq.front(); pq.pop();
         for (遍历cur所有的相邻节点nex) {
             if (nex节点有效 && vis[nex]==0){
                 vis[nex] = 1;
                 pq.push(nex)
             }
         } // end for
     } // end while
    }

上述是伪代码，不仅可用于二叉树，可针对所有用BFS解题。

  1. 如果需要确定遍历到哪一层，模板如下；

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    void bfs() {
     int level = 0;
     vis[] = {0}; // or set
     queue<int> pq(original_val);
     while (!pq.empty()) {
         int sz = pq.size();

         while (sz--) {
                 int cur = pq.front(); pq.pop();
             for (遍历cur所有的相邻节点nex) {
                 if (nex节点有效 && vis[nex] == 0) {
                     vis[nex] = 1;
                     pq.push(nex)
                 }
             } // end for
         } // end inner while
         level++;

     } // end outer while
    }

所以此题可直接套用模板，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> ret;
        queue<TreeNode*> q;
        q.push(pRoot);

        while (!q.empty()) {
            int sz = q.size();
            vector<int> ans;
            while (sz--) {
                TreeNode *node = q.front();
                q.pop();
                ans.push_back(node->val);

                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            ret.push_back(ans):
        }
        return ret;
    }

};

时间复杂度：O(N)
空间复杂度：O(1), vecotr<vecotr<int>> 是必须要开的，不算在额外空间里

发表于 分类于
本文字数： 4.8k 阅读时长 ≈ 4 分钟

题目描述

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

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，我们可以把一个只有根节点为1的二叉树序列化为”1,”，然后通过自己的函数来解析回这个二叉树

解答

树中节点值不重复的情况下可使用如下方法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * 保存前序和中序序列
 */
String Serialize(TreeNode root) {
    StringBuilder pre = new StringBuilder();
    getPreOrder(root, pre);
    StringBuilder in = new StringBuilder();
    getInOrder(root, in);
    return pre + ";" + in;
}

private void getInOrder(TreeNode root, StringBuilder builder) {
    if (root == null) {
        return;
    }
    getInOrder(root.left, builder);
    builder.append(root.val + ",");
    getInOrder(root.right, builder);
}

private void getPreOrder(TreeNode root, StringBuilder builder) {
    if (root == null) {
        return;
    }
    builder.append(root.val + ",");
    getPreOrder(root.left, builder);
    getPreOrder(root.right, builder);
}

/**
 * 递归建树
 */
TreeNode Deserialize(String str) {
    String[] strs = str.split(";");
    if (strs.length == 0) {
        return null;
    }
    String[] pre = strs[0].split(",");
    String[] in = strs[1].split(",");

    TreeNode root = buildTree(pre, in);
    return root;
}

private TreeNode buildTree(String[] pre, String[] in) {
    if (pre == null || pre.length == 0) {
        return null;
    }
    TreeNode root = new TreeNode(Integer.valueOf(pre[0]));
    int leftNum = 0;
    for (int i = 0; i < in.length; i++) {
        if (in[i].equals(pre[0])) {
            leftNum = i;
            break;
        }
    }

    root.left = buildTree(Arrays.copyOfRange(pre, 1, leftNum + 1), Arrays.copyOfRange(in, 0, leftNum));
    root.right = buildTree(Arrays.copyOfRange(pre, leftNum + 1, pre.length), Arrays.copyOfRange(in, leftNum + 1, in.length));

    return root;
}

官方题解

链接：https://www.nowcoder.com/questionTerminal/cf7e25aa97c04cc1a68c8f040e71fb84?answerType=1&f=discussion
来源：牛客网

方法一：先序遍历实现

预备知识：先序遍历的递归实现：

1
2
3
4
5
6
7
8
9
10
void pre_order(TreeNode *root) {
    if (!root) {
        return;
    }

    // process root
    // ...
    pre_order(root->left);
    pre_order(root->right);
}

对于本题来说，可以套用上述模板。
假设序列化的结果为字符串 str, 初始str = “”.根据要求，遇到nullptr节点，str += “#”
遇到非空节点，str += “val” + “!”; 假设val为3， 就是 str += “3!”

所以，最终的代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
char* Serialize(TreeNode *root) {    
    if (!root) {
        return "#";
    }

    string res = to_string(root->val);
    res.push_back(',');

    char* left = Serialize(root->left);
    char* right = Serialize(root->right);

    char* ret = new char[strlen(left)+strlen(right)+res.size()];
    // 如果是string类型，直接用operator += ,这里char* 需要用函数
    strcpy(ret,res.c_str());
    strcat(ret,left);
    strcat(ret,right);

    return ret;
}

反序列化的结果，就是根据先序遍历，再重建二叉树即可。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 参数使用引用&， 以实现全局变量的目的
TreeNode* deseri(char *&s) {
    if (*s == '#') {
        ++s;
        return nullptr;
    }

    // 构造根节点值
    int num = 0;
    while (*s != ',') {
        num = num * 10 + (*s - '0');
        ++s;
    }
    ++s; 
    // 递归构造树
    TreeNode *root = new TreeNode(num);
    root->left = deseri(s);
    root->right = deseri(s);

    return root;
}

TreeNode* Deserialize(char *str) {
    return deseri(str);
}

中序遍历，后序遍历大致都差不多。

方法二：层次遍历实现

层次遍历采用队列实现。跟先序遍历的思想差不多，无非都是把树的所有数据遍历一遍，然后记录下来。
层次遍历模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void bfs(TreeNode *root){
    queue<TreeNode*> qt;
    qt.push(root);
     string s;
    while (!qt.empty())
    {
        // pop operator
        TreeNode *node = qt.front();
        qt.pop();

        // process node
        if (node == NULL)
        {
            s.push_back('#');
            s.push_back(',');
            continue;
        }
        s += to_string(node->val);
        s.push_back(',');

        // push operator
        qt.push(node->left);
        qt.push(node->right);

    }
}

序列化的操作直接根据模板套即可。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
char* Serialize(TreeNode *root)
{
    string s;
    queue<TreeNode*> qt;
    qt.push(root);

    while (!qt.empty())
    {
        // pop operator
        TreeNode *node = qt.front();
        qt.pop();
        // process null node
        if (node == nullptr)
        {
            s.push_back('N');
            s.push_back(',');
            continue;
        }
        // process not null node
        s += to_string(node->val);
        s.push_back(',');
        // push operator
        qt.push(node->left);
        qt.push(node->right);

    }

    char *ret = new char[s.length() + 1];
    strcpy(ret, s.c_str());

    return ret;
}

反序列化就是根据层次遍历在走一遍即可。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
TreeNode* Deserialize(char *str)
{
    if (str == nullptr) {
        return nullptr;
    }
    // 可用string成员函数
    string s(str);
    if (str[0] == '#') {
        return nullptr;
    }

    // 构造头结点
    queue<TreeNode*> nodes;
    TreeNode *ret = new TreeNode(atoi(s.c_str()));
    s = s.substr(s.find_first_of(',') + 1);
    nodes.push(ret);
    // 根据序列化字符串再层次遍历一遍，来构造树
    while (!nodes.empty() && !s.empty())
    {
        TreeNode *node = nodes.front();
        nodes.pop();
        if (s[0] == '#')
        {
            node->left = nullptr;
            s = s.substr(2);
        }
        else
        {
            node->left = new TreeNode(atoi(s.c_str()));
            nodes.push(node->left);
            s = s.substr(s.find_first_of(',') + 1);
        }

        if (s[0] == '#')
        {
            node->right = nullptr;
            s = s.substr(2);
        }
        else
        {
            node->right = new TreeNode(atoi(s.c_str()));
            nodes.push(node->right);
            s = s.substr(s.find_first_of(',') + 1);
        }
    }
    return ret;
}

此题主要考察对树的遍历和构造树。

发表于 分类于
本文字数： 459 阅读时长 ≈ 1 分钟

题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

解答

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int K,i=0;
TreeNode node = null;

TreeNode KthNode(TreeNode pRoot, int k) {
    if (k==0){
        return null;
    }
    K = k;
    dfs(pRoot);

    return node;
}

private void dfs(TreeNode pRoot) {
    if (pRoot == null) {
        return;
    }
    dfs(pRoot.left);
    if (node != null) {
        return;
    }
    if (i < K) {
        i++;
    }
    if (i == K) {
        node = pRoot;
        return;
    }
    dfs(pRoot.right);
}

发表于 分类于
本文字数： 3.1k 阅读时长 ≈ 3 分钟

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ArrayList<Integer> list = new ArrayList<>();

public void Insert(Integer num) {
    int i = 0;
    for (; i < list.size(); i++) {
        if (list.get(i) >= num) {
            break;
        }
    }
    list.add(i, num);
}

public Double GetMedian() {
    if (list.size() % 2 == 0) {
        return (list.get(list.size() / 2 - 1) + list.get(list.size() / 2)) / 2.0;
    } else {
        return (double) list.get(list.size() / 2);
    }
}

官方题解

链接：https://www.nowcoder.com/questionTerminal/9be0172896bd43948f8a32fb954e1be1?answerType=1&f=discussion
来源：牛客网

方法一：暴力方法

对于一组数据，我们可以用vector arr来存取。如果对vector排好序，则很容易求出中位数。如果vector的大小为sz。

  • 如果sz为奇数，假如为3，即[0 1 2]，则中位数就是中间的那个数arr[1]。
  • 如果sz为偶数，假如为4，即[0 1 2 3], 则中位数就是中间两个数的加权平均数。即 (arr[1] + arr[2]) / 2

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    #define SCD static_cast<double>
    vector<int> v;
    void Insert(int num)
    {
        v.push_back(num);

    }

    double GetMedian()
    { 
        sort(v.begin(), v.end());
        int sz = v.size();
        if (sz & 1) {
            return SCD(v[sz >> 1]);
        }
        else {
            return SCD(v[sz >> 1] + v[(sz - 1) >> 1]) / 2;
        }
    }

};

时间复杂度：Insert()为O(1),GetMedian()为O(nlogn)
空间复杂度：O(n)

方法二：插入排序

对于方法一，可以发现有个优化的地方。
方法一中GetMEdian()操作，是每次都对整个vector调用排序操作。
但是其实每次都是在一个有序数组中插入一个数据。因此可以用插入排序。
所以：

  • Insert()操作可改为插入排序
  • GetMedian()操作可直接从有序数组中获取中位数

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    #define SCD static_cast<double>
    vector<int> v;
    void Insert(int num)
    {
        if (v.empty()) {
            v.push_back(num);
        }
        else {
            auto it = lower_bound(v.begin(), v.end(), num);
            v.insert(it, num);
        }
    }

    double GetMedian()
    { 
        int sz = v.size();
        if (sz & 1) {
            return SCD(v[sz >> 1]);
        }
        else {
            return SCD(v[sz >> 1] + v[(sz - 1) >> 1]) / 2;
        }
    }

};

时间复杂度：Insert()为O(n),即二分查找的O(logn)和挪动数据的O(n), GetMedian()为O(1)
空间复杂度：O(n)

方法三：堆

中位数是指：有序数组中中间的那个数。则根据中位数可以把数组分为如下三段:
[0 ... median - 1], [median], [median ... arr.size() - 1]，即[中位数的左边，中位数，中位数的右边]

那么，如果我有个数据结构保留[0…median-1]的数据，并且可以O(1)时间取出最大值，即arr[0...median-1]中的最大值
相对应的，如果我有个数据结构可以保留[median + 1 ... arr.size() - 1] 的数据， 并且可以O(1)时间取出最小值，即
arr[median + 1 ... arr.size() - 1] 中的最小值。
然后，我们把[median]即中位数，随便放到哪个都可以。

假设[0 ... median - 1]的长度为l_len, [median + 1 ... arr.sise() - 1]的长度为 r_len.
1.如果l_len == r_len + 1, 说明，中位数是左边数据结构的最大值
2.如果l_len + 1 == r_len, 说明，中位数是右边数据结构的最小值
3.如果l_len == r_len, 说明，中位数是左边数据结构的最大值与右边数据结构的最小值的平均值。

说了这么多，一个数据结构可以O(1)返回最小值的，其实就是小根堆，O(1)返回最大值的，其实就是大根堆。并且每次插入到堆中的时间复杂度为O(logn)

所以，GetMedian()操作算法过程为：

  • 初始化一个大根堆，存中位数左边的数据，一个小根堆，存中位数右边的数据
  • 动态维护两个数据结构的大小，即最多只相差一个

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    #define SCD static_cast<double>
    priority_queue<int> min_q; // 大顶推
    priority_queue<int, vector<int>, greater<int>> max_q; // 小顶堆

    void Insert(int num)
    {

        min_q.push(num); // 试图加入到大顶推

        // 平衡一个两个堆
        max_q.push(min_q.top()); 
        min_q.pop();

        if (min_q.size() < max_q.si***_q.push(max_q.top());
            max_q.pop();
        }

    }

    double GetMedian()
    { 
        return min_q.size() > max_q.size() ? SCD(min_q.top()) : SCD(min_q.top() + max_q.top()) / 2;
    }

};

时间复杂度：Insert()为O(logn), GetMedian()为O(1)
空间复杂度：O(n)