题目描述

给出一个字符序列，问该序列是否是一棵合法的二叉树的先序遍历？
找到一种不需要构造二叉树的方法。
For example：
“9,3,4,#,#,1,#,#,2,#,6,#,#”
是下面这颗二叉树的先序遍历。其中＃代表空节点。

解题思路

一棵合法的二叉树去掉某个叶子节点后仍是合法的二叉树。在给出的字符序列中，叶子节点有很明显的特征，即叶子节点之后一定紧跟两个空节点＃。通过不断的把number,#,#的子串缩成空节点#(把number,#,#子串替换为#)，如果最后字符序列可以缩短到只有一个字符＃，那它就是我们要找的合法的先序遍历了。

参考代码

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

public class Solution {
  public boolean isValidSerialization(String preorder) {
    String s = preorder;
    boolean flag = true;
    while (s.length() > 1) {
      int index = s.indexOf(",#,#");
      if (index < 0){
        flag = false;
        break;
      }
      int start = index;
      while (start > 0 && s.charAt(start - 1) != ',') {
        start --;
      }
      if (s.charAt(start) == '#') {
        flag = false;
        break;
      }
      s = s.substring(0, start) + s.substring(index + 3);
    }
    if (s.equals("#") && flag)
      return true;
    else
      return false;
  }
}

算法分析

此题可以用暴力搜索解决，但线性复杂度算法也不难想到。写出以上解法，可以达到hire, 而如果用stack解法，则可以 storng hire.

相关练习

树的操作时面试中的高频题目，基础操作（遍历，求深度，求path value等）需熟练掌握。

Verify Preorder Serialization of a Binary Tree

Binary Tree Preorder Traversal

Binary Tree Level Order Traversal

Binary Tree Level Order Traversal II

Binary Tree Postorder Traversal (思考非递归算法)

Construct Binary Tree from Inorder and Postorder Traversal

From jiuzhang

题目描述

给定一个字符串，找到最长的包含最多k个不同字符的子串，输出最长子串的长度即可。

Example：
给出字符串”eceba”，k = 2
输出答案3，最长包含最多2个不同字符的子串为”ece”

解题思路

最暴力的做法是穷举所有可能的子串，一共有n^2级别个不同的子串，然后对于每一个子串统计有多少不同的字符，如果少于k个就更新答案。这是一个三重循环的穷举，复杂度是O(n^3)。聪明的读者肯定想到了第二重和第三重循环可以合并，因为之前的统计信息可以继续使用而不需要每一次重新统计。这样的话穷举子串的开始位置和结束位置，复杂度是O(n^2)。如果在面试时提出了这个算法，面试官首先会表示认同，然后希望你进行优化。我们来看看如何进行优化。

在统计的过程中我们可以发现，当穷举的开始位置改变时我们会选择重新统计，但其实当开始位置改变时，我们之前记录的大部分信息都是有用的，我们只需在原有的统计结果上稍作修改。我们在两层for循环的时候其实会发现我们内层的fo循环其实并不需要每次都再重复遍历。比如外层for循环指针i每次向前移动变成i+1的时候，内层for循环的j没必要每次都退回到i的位置，其实是可以保留在j的位置不变的。因为可以证明对于从i+1到j-1这些情况都不会出现重复的元素，所以我们只用考虑从i+1到j就可以了。

分析一下这个算法的时间复杂度，虽然我们会用到两重循环（请看参考程序），但是因为这两个指针只增不减，每次循环指针增加1，因此while循环总共只会进入n次（n = s.length( ))，所以时间复杂度是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
36
37
38
39

public class Solution{
  /**
   * @param s: A string
   * @return : The length of the longest substring
   *           that contains at most k distinct characters.
   */
   public int lengthOfLongestKDistinct(String s, int k){
     int maxLen = 0;
     // Key: letter; value: the number of occurrences.
     Map<Character, Integer> map = new HashMap<Character, Integer>();
     int i, j = 0;
     char c;
     for (i = 0; i < s.length(); i++){
       while (j < s.length()){
         c = s.charAt(j);
         if(map.containsKey(c)){
           map.put(c, map.get(c) + 1);
         } else {
           if (map.size() == k)
             break;
           map.put(c, 1);
         }
         j++;
       }

       maxLen = Math.max(maxLen, j - i);
       c = s.charAt(i);
       if(map.containsKey(c)){
         int count = map.get(c);
         if (count > 1) {
           map.put(c, count - 1);
         } else {
           map.remove(c);
         }
       }
     }
     return maxLen;
   }
}

算法分析

这是一道很有区分度的题目，有O(n^3),O(n^2),O(nlogn)（follow up）,O(n)时间复杂度的做法。先提出一种可行算法，通过一步步分析、优化，最后提出O(n)的最优算法并完成代码就可以达到hire的程度。

相关练习

minimum-size-subarray-sum
longest-without-repeating-characters

I. What is Markdown

Targets of Markdown

Markdown is a text-to-HTML conversion tool for web writers by John Gruber @Daringfireball. Thus other details can be seen in author’s website above.

Tools for Markdown

Most people recommend Mou on Mac OS. While on Windows, here are MarkdownPad (much better than the followings …) and MarkPad (er… it’s too slow at least for me). For convenience, I just use Atom by Google with MD plugin, it’s enough for me.

II. Markdown Syntax

Headers

1
2
3

# This is an H1
## This is an H2
###### This is an H6

There are 6 levels of header, adding # , from H1 to H6.

Lists

Markdown supports ordered (numbered) and unordered (bulleted) lists.

unordered

1
2
3

*   Red
*   Green
*   Blue

is equivalent to:

1
2
3

-   Red
-   Green
-   Blue

numbered

1
2
3

1.  Bird
2.  McHale
3.  Parish

Quotes

Markdown allows you to be lazy and only put the > before the first line of a hard-wrapped paragraph:

1
2
3

> This is a blockquote with two paragraphs. Lorem ipsum dolor sit amet,
consectetuer adipiscing elit. Aliquam hendrerit mi posuere lectus.
Vestibulum enim wisi, viverra nec, fringilla in, laoreet vitae, risus.

shown as,

This is a blockquote with two paragraphs. Lorem ipsum dolor sit amet,
consectetuer adipiscing elit. Aliquam hendrerit mi posuere lectus.
Vestibulum enim wisi, viverra nec, fringilla in, laoreet vitae, risus.

This style is based on the template used in Hexo.

Links and images

Markdown supports two style of links and images: inline and reference.

inline

1
2
3
4
5
6
7

links : This is [an example](http://example.com/ "Title") inline link.
        or
        [This link](http://example.net/) has no title attribute.

images : ![Alt text](/path/to/img.jpg)
         or
         ![Alt text](/path/to/img.jpg "Optional title")

If you’re referring to a local resource on the same server, you can use relative paths:

1

See my [About](/about/) page for details.

reference

1
2
3
4
5
6
7

links: This is [an example] [id] reference-style link.
       where id is defined by
       [id]: http://example.com/  "Optional Title Here"

images: ![Alt text][id]
        where id is defined by
        [id]: url/to/image  "Optional title attribute"

Code

To indicate a span of code, wrap it with backtick quotes `.

1

Use the `printf()` function.

Emphasis

Markdown treats asterisks () and underscores (_) as indicators of emphasis. Text wrapped with one or will be wrapped with an HTML tag; double *’s or ’s will be wrapped with an HTML tag. E.g., this input:

single asterisks

single underscores

double asterisks

double underscores

Tables

An example of table：

1
2
3
4
5

| Tables        | Are           | Cool  |
| ------------- |:-------------:| -----:|
| col 3 is      | right-aligned | $1600 |
| col 2 is      | centered      |   $12 |
| zebra stripes | are neat      |    $1 |

produce

First Post

Use my pics to test Hexo~~

Ducks in Houhai Park @Beijing ~

by html

Hope it can be seen~